Тема: Платформа для высокопроизводительного поиска зависимостей в базах данных

Зависимости в базах данных представляют собой закономерности в дан­ных. Владение подобной метаинформацией облегчает решение многих задач, таких как: нормализация схемы, очистка данных и оптимизация запросов [3, 25, 26]. Многие подвиды зависимостей, такие как рассмат­риваемые в данной работе функциональные зависимости, соответству­ют известным в предметной области правилам, и зачастую эксперт мо­жет определить большинство зависимостей, имеющих место в данной таблице.
Если подобное исследование зависимостей недоступно, использует­ся автоматическое обнаружение зависимостей — его целью является составление списка всех зависимостей, удерживающихся на заданной таблице. К сожалению, в данной постановке задача имеет сложность O(N • 2м), где N — количество кортежей, M — количество атрибу­тов [15].
Тем не менее, в области были предложены дюжины алгоритмов по­иска функциональных зависимостей, и в каждом проблема решается уникальным способом. Таким образом, становится актуальной плат­форма:
1. позволяющая использовать эффективные реализации алгоритмов для непосредственного поиска зависимостей;
2. реализующая различные алгоритмы с использованием одинако­вых технологий для их последующего сравнения и проведения прочих экспериментов.
При анализе предметной области было найдено единственное реше­ние, подходящее на роль подобной платформы. Metanome — открытая платформа, на уровне бэкэнда реализованная на языке программиро­вания Java, основной целью которой является анализ метаданных [8]. Несмотря на множество положительных сторон, Metanome не удовле­творяет вышеупомянутым требованиям в полной мере по следующим причинам:
• Программы, реализованные на языке Java, обладают достаточной производительностью при решении бизнес-задач, однако для ре­шения задач, требующих высокопроизводительных вычислений, существуют другие языки и технологии, позволяющие добиться более высокой эффективности.
• Используемые при работе кода, написанного на Java, техноло­гии наподобие динамической компиляции и сборки мусора вносят неопределенность в скорость работы программы, что усложняет задачу оценки производительности [14].
Таким образом, было решено спроектировать и реализовать аль­тернативную платформу для высокопроизводительного поиска функ­циональных зависимостей, получившую название Desbordante1. Чтобы избежать недостатков, присущих Metanome, было принято решение ис­пользовать для реализации язык программирования C++:
• Благодаря широким возможностям по низкоуровневой оптимиза­ции и предоставлению программисту полного контроля над ис­полняемым кодом, С++ является одним из самых высокопроиз­водительных языков программирования. При этом C++ предо­ставляет обширный инструментарий для разработки масштабных, расширяемых проектов.
• Наличие полного контроля над исполняемым кодом также позво­ляет уменьшить флуктуации при проведении экспериментов.
1.1. Постановка задачи
Целью данной работы является реализация платформы для высокопро­изводительного поиска функциональных зависимостей. Для достиже­ния данной цели были поставлены следующие задачи:
1. Выполнить обзор алгоритмов поиска функциональных зависимо­стей, а также существующих решений.
2. Спроектировать и реализовать платформу для высокопроизводи­тельного поиска функциональных зависимостей.
3. Сравнить производительность реализованной платформы и суще­ствующего решения Metanome.
• выработать метрики и показать превосходство предложенной платформы;
• показать, что невозможно достичь аналогичного уровня про­изводительности с помощью настройки Metanome;
• исследовать причины повышенного уровня производительно­сти.
4. С помощью разработанной платформы исследовать возможность уменьшения трудоёмкости алгоритмов за счёт ограничения мак­симального размера левой части зависимости.
Купить

В рамках данной работы были достигнуты следующие результаты:
1. Выполнен обзор алгоритмов и инструментов для поиска функци­ональных зависимостей.
2. Спроектирована и реализована платформа Desbordante, позволя­ющая использовать алгоритмы TANE, Pyro и предоставляющая возможности для добавления новых алгоритмов.
3. Проведено сравнение производительности Desbordante и существу­ющего решения Metanome.
• сформулированы метрики для сравнения и проведены экспе­рименты, показавшие превосходство Desbordante;
• проведены эксперименты, показавшие, что невозможно до­стичь аналогичного уровня производительности с помощью настройки Metanome;
• сформулированы и экспериментально проверены гипотезы, объясняющие причины повышенного уровня производитель­ности.
4. Исследована возможность уменьшения трудоёмкости алгоритмов поиска ФЗ через ограничение максимального размера левой ча­сти.
Кроме того, по теме данной работы была написана статья “Desbordante: a Framework for Exploring Limits of Dependency Discovery Algorithms” [9], представленная на конференции FRUCT’29 и принятая к публикации в сборнике трудов.
Купить