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

1. Введение 4
1.1. Постановка задачи 5
2. Обзор 7
2.1. Основные понятия 7
2.2. Классификация алгоритмов 8
2.3. Проприетарные решения 9
2.4. Исследовательские решения 11
2.5. Metanome 12
3. Архитектура Desbordante 14
4. Подготовка экспериментов 17
4.1. Вопросы экспериментального исследования 17
4.2. Среда для проведения экспериментов 17
4.3. Оцениваемые метрики 19
4.4. Обеспечение стабильности экспериментов 20
5. Сравнение с Metanome 22
5.1. Сравнение производительности 22
5.2. Настройка Metanome 24
5.3. Причины повышения производительности 27
6. Уменьшение трудоёмкости задачи 31
7. Выводы 33
8. Заключение 34
9. Благодарности 35
Список литературы 36
Купить

Зависимости в базах данных представляют собой закономерности в дан­ных. Владение подобной метаинформацией облегчает решение многих задач, таких как: нормализация схемы, очистка данных и оптимизация запросов [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. С помощью разработанной платформы исследовать возможность уменьшения трудоёмкости алгоритмов за счёт ограничения мак­симального размера левой части зависимости.
Купить