Пошук функціональних залежностей у даних застосовується у різних напрямах аналізу даних: управління базами даних, очищення даних, реверс-інжиніринг баз даних та експлорація даних. Про самі залежності ми вже публікували Анастасії Бірілло та Микити Боброва. Цього разу Анастасія — цьогорічна випускниця Computer Science Center — ділиться розвитком цієї роботи в рамках НДР, яку вона захистила в центрі.
вибір завдання
Під час навчання в CS центрі я почала поглиблено вивчати бази даних, а саме пошук функціональних і різницевих залежностей. Ця тема була пов'язана з темою моєї курсової в університеті, тому під час роботи над курсовою я почала читати статті про різні залежності в базах даних. Я написала огляд цієї області - одну з перших своїх англійською мовою та подала її на конференцію SEIM-2017. Я була дуже рада, коли дізналася, що її все ж таки прийняли, і вирішила заглибитися в тему. Сама концепція не нова - її почали застосовувати ще в 90-х роках, але і зараз вона знаходить застосування в багатьох сферах.
У другому семестрі навчання в центрі я розпочала науково-дослідний проект щодо покращення алгоритмів пошуку функціональних залежностей. Працювала над ним разом із аспірантом СПбДУ Микитою Бобровим на базі JetBrains Research.
Обчислювальна трудомісткість пошуку функціональних залежностей
Основна проблема - обчислювальна трудомісткість. Число можливих мінімальних та нетривіальних залежностей обмежене зверху значенням , Де - Число атрибутів таблиці. Час роботи алгоритмів залежить від кількості атрибутів, а й кількості рядків. У 90-х роках алгоритми пошуку ФЗ на звичайному настільному ПК могли обробляти набори даних, що містять до 20 атрибутів і десятки тисяч рядків, до декількох годин. Сучасні алгоритми, що працюють на багатоядерних процесорах, виявляють залежності для наборів даних, що складаються з сотень атрибутів (до 200) і сотень тисяч рядків приблизно за той же час. Проте цього недостатньо: такий час є неприйнятним для більшості реальних додатків. Тому ми розробляли підходи щодо прискорення існуючих алгоритмів.
Схеми кешування для перетину партицій
У першій частині роботи ми розробили схеми кешування для класу алгоритмів, які використовують метод перетину партицій. Партиція для атрибута являє собою набір списків, де кожен список містить номери рядків з однаковими значеннями для цього атрибута. Кожен такий список називається кластером. Багато сучасних алгоритмів використовують партиції для визначення, чи утримується залежність, чи ні, а саме дотримуються леми: Залежність утримується, якщо . тут позначається партиція і використовують поняття розмір партиції — кількість кластерів у ній. Алгоритми, що використовують партиції, при порушенні залежності додають додаткові атрибути в ліву частину залежності, після чого перераховують її, роблячи операцію перетину партицій. Така операція у статтях називається спеціалізацією. Але ми помітили, що партиції для залежностей, які будуть утримані лише після кількох раундів спеціалізації, можуть бути активно перевикористані, що може суттєво скоротити час роботи алгоритмів, оскільки операція перетину є дорогою.
Тому ми запропонували евристику, засновану на Ентропії Шеннона та невизначеності Джіні, а також нашій метриці, яку ми назвали Зворотна Ентропія. Вона є незначною модифікацією Ентропії Шеннона і зростає в міру того, як зростає унікальність набору даних. Запропонована евристика виглядає так:
Тут - Ступінь унікальності нещодавно обчисленої партиції , а є медіаною ступенів унікальності для окремих атрибутів. Як метрика унікальності були випробувані всі три метрики, описані вище. Також можна помітити, що в евристиці присутні два модифікатори. Перший вказує наскільки близька поточна партиція до первинного ключа і дозволяє більшою мірою кешувати ті партиції, які далекі від потенційного ключа. Другий модифікатор дозволяє відстежувати зайнятість кешу і тим самим стимулює додавання більшої кількості партицій до кешу за наявності вільного місця. Успішне вирішення цього завдання дозволило прискорити алгоритм PYRO на 10-40% залежно від датасета. Варто зазначити, що алгоритм PYRO є найуспішнішим у цій галузі.
На малюнку нижче можна побачити результати застосування запропонованої евристики в порівнянні з базовим підходом кешування, заснованому на підкиданні монетки. Вісь X логарифмічна.
Альтернативний спосіб зберігання партицій
Потім ми запропонували альтернативний спосіб зберігання партій. Партиції є набором кластерів, у кожному з яких зберігаються номери кортежів з однаковими значеннями за певними атрибутами. Ці кластери можуть містити довгі послідовності номерів кортежів, наприклад, якщо дані впорядковані в таблиці. Тому ми запропонували схему стиснення для зберігання партій, а саме інтервальне зберігання значень у кластерах партій:
$$display$$pi(X) = {{underbrace{1, 2, 3, 4, 5}_{Перший~інтервал}, underbrace{7, 8}_{Другий~інтервал}, 10}}\ downarrow{ Стиснення}\ pi(X) = {{underbrace{$, 1, 5}_{Перший~інтервал}, underbrace{7, 8}_{Другий~інтервал}, 10}}$$display$$
Цей метод зміг скоротити споживання пам'яті під час алгоритму TANE від 1 до 25%. Алгоритм TANE - класичний алгоритм пошуку ФЗ, він використовує партиції в ході своєї роботи. В рамках практики було обрано саме алгоритм TANE, оскільки впровадити в нього інтервальне зберігання було значно простіше, ніж, наприклад, у PYRO, щоб оцінити, чи підхід, що пропонується. Отримані результати представлені нижче. Вісь X логарифмічна.
Конференція ADBIS-2019
За результатами дослідження у вересні 2019 року я виступила із статтею на конференції 23rd European Conference on Advances in Databases and Information Systems (ADBIS-2019). Під час виступу роботу відзначив Bernhard Thalheim, значуща людина у галузі баз даних. Результати досліджень лягли в основу моєї дисертації в магістратурі мат-хутра СПбГУ, в ході якої обидва запропоновані підходи (кешування та стиснення) були впроваджені в обидва алгоритми: TANE і PYRO. При цьому результати показали, що запропоновані підходи є універсальними, оскільки на обох алгоритмах при обох підходах спостерігалося значне скорочення пам'яті, що споживається, а також значне скорочення часу роботи алгоритмів.
Джерело: habr.com