Введення у функціональні залежності

У цій статті ми поговоримо про функціональні залежності в базах даних — що це таке, де застосовуються і які алгоритми існують для їхнього пошуку.

Розглядатимемо функціональні залежності ми будемо в контексті реляційних баз даних. Якщо говорити дуже грубо, то таких базах даних інформація зберігається як таблиць. Далі ми використовуємо наближені поняття, які в суворій реляційній теорії не взаємозамінні: саму таблицю називатимемо ставленням, стовпці — атрибутами (їх безліч — схемою відношення), а набір значень рядка на підмножині атрибутів — кортежем.

Наприклад, у таблиці вище, (Benson, M, M орган) є кортежем за атрибутами (Пацієнт, Пол, Лікар).
Більше формально це записується в наступному вигляді: [Пацієнт, Стать, Лікар] = (Benson, M, M organ).
Тепер ми можемо запровадити поняття функціональної залежності (ФЗ):

Визначення 1. Відношення R задовольняє ФЗ X → Y (де X, Y ⊆ R) тоді і лише тоді, коли для будь-яких кортежів , ∈ R виконується: якщо [X] = [X], то [Y] = [Y]. У такому випадку кажуть, що X (детермінант, або визначальна множина атрибутів) функціонально визначає Y (залежна множина).

Іншими словами, наявність ФЗ X → Y означає, що якщо ми маємо два кортежі в R і вони збігаються за атрибутами X, то вони збігатимуться і за атрибутами Y.
А тепер по порядку. Розглянемо атрибути Пацієнт и Стать для яких хочемо дізнатися, чи є між ними залежність чи ні. Для такої множини атрибутів можуть існувати наступні залежності:

1. Пацієнт → Пол
2. Стать → Пацієнт

Згідно з визначенням вище, щоб утрималася перша залежність, кожному унікальному значенню стовпця Пацієнт має відповідати лише одне значення стовпця Стать. І для таблиці-прикладу це справді так. Однак у зворотний бік це не працює, тобто друга залежність не виконується, а атрибут Стать не є детермінантом для Пацієнта. Аналогічно, якщо взяти залежність Лікар → Пацієнтможна помітити, що вона порушується, оскільки значення Робін з цього атрибуту має кілька різних значень. Ellis та Graham.

Таким чином, функціональні залежності дозволяють визначити наявні зв'язки між множинами атрибутів таблиці. Звідси й надалі ми розглядатимемо найцікавіші зв'язки, а точніше такі X → Y, що вони є:

• нетривіальними, тобто права частина залежності не є підмножиною лівої (Y ̸⊆ X);
• мінімальними, тобто немає такої залежності Z → Y, що Z ⊂ X.

Розглянуті до цього моменту залежності були строгими, тобто такими, що не передбачають жодних порушень на таблиці, але крім них є і такі, які допускають деяку неузгодженість між значеннями кортежів. Такі залежності виносять в окремий клас, називають наближеними та дозволяють їм порушуватися на певній кількості кортежів. Ця кількість регулюється показником максимальної помилки emax. Наприклад, частка помилки = 0.01 може означати, що залежність може порушуватися на 1% від наявних кортежів на розглянутій множині атрибутів. Тобто для 1000 записів максимум 10 кортежів можуть порушувати ФЗ. Ми ж розглядатимемо трохи іншу метрику, засновану на попарно-різних значеннях кортежів, що порівнюються. Для залежності X → Y щодо r вона вважається так:

Порахуємо помилку для Лікар → Пацієнт з прикладу вище. Маємо два кортежі, значення яких різняться на атрибуті Пацієнт, але збігаються на Лікарі: [Лікар, Пацієнт] = (Robin, Ellis) і [Лікар, Пацієнт] = (Robin, Graham). Наслідуючи визначення помилки, ми повинні враховувати всі конфліктуючі пари, а отже таких буде дві: (, ) та її інверсія (, ). Підставимо у формулу та отримаємо:

А тепер спробуємо відповісти на запитання: "А навіщо воно все?". Насправді ФЗ бувають різні. Перший тип — це залежність, які визначаються адміністратором на етапі проектування бази даних. Їх зазвичай небагато, вони суворі, а основне застосування – нормалізація даних та дизайн схеми відношення.

Другий тип — залежності, які представляють «приховані» дані та раніше невідомі зв'язки між атрибутами. Тобто про такі залежності не думали в момент проектування і їх знаходять вже для наявного набору даних, щоб потім на основі безлічі виявлених ФЗ зробити будь-які висновки про інформацію, що зберігається. Саме з такими залежностями ми й працюємо. Ними займається ціла область дата майнінгу з різними техніками пошуку та побудованими на їх основі алгоритмами. Давайте розбиратися, чим можуть бути корисними знайдені функціональні залежності (точні або наближені) до будь-яких даних.

Сьогодні серед основних областей застосування залежностей виділяють очищення даних. Вона передбачає розробку процесів виявлення «брудних даних» з подальшим їх виправленням. Яскравими представниками «брудних даних» є дублікати, помилки в даних чи друкарські помилки, пропущені значення, застарілі дані, зайві прогалини тощо.

Приклад помилки даних:

Приклад дублікатів у даних:

Наприклад, ми маємо таблицю та набір ФЗ, які мають виконуватися. Очищення даних у разі передбачає змінити дані в такий спосіб, щоб ФЗ стали правильні. При цьому число модифікацій має бути мінімальним (для даної процедури існують свої алгоритми, на яких ми не зосереджуватимемо увагу в цій статті). Нижче наведено приклад такого перетворення даних. Зліва вихідне відношення, в якому, очевидно, не виконуються необхідні ФЗ (червоним кольором виділено приклад порушення однієї з ФЗ). Справа представлено оновлене відношення, в якому зелені осередки показують змінені значення. Після проведення такої процедури необхідні залежності стали утримуватись.

Іншою популярною сферою застосування є дизайн бази даних. Тут варто нагадати про нормальні форми та нормалізацію. Нормалізація - це процес приведення відносини у відповідність деякому набору вимог, кожен з яких визначається нормальною формою по-своєму. Розписувати вимоги різних нормальних форм ми не станемо (це робиться у будь-якій книзі за курсом БД для початківців), а лише зауважимо, що кожна з них по-своєму використовує концепцію функціональних залежностей. Адже ФЗ за своєю суттю є обмеженнями цілісності, які враховуються під час проектування бази даних (у контексті цього завдання ФЗ іноді називають суперключами).

Розглянемо їх застосування для чотирьох нормальних форм на зображенні нижче. Нагадаємо, що нормальна форма Бойса-Кодда є суворішою, ніж третя форма, але при цьому менш суворою, ніж четверта. Останню поки що не розглядаємо, оскільки для її постановки потрібне розуміння багатозначних залежностей, які в цій статті нам не цікаві.

Ще однією областю, в якій залежності знайшли своє застосування, є зниження розмірності простору ознак у таких завданнях як побудова наївного байєсівського класифікатора, виділення значних ознак та репараметризація регресійної моделі. В оригінальних статтях це завдання називається визначенням надлишкових ознак (feature redundancy) та релевантних (feature relevancy) [5, 6], і вирішується вона з активним використанням концепцій баз даних. З появою таких робіт ми можемо говорити, що сьогодні спостерігається запит на рішення, що дозволяють об'єднати базу даних, аналітику та реалізацію перерахованих вище проблем оптимізації в один інструмент [7, 8, 9].

Для пошуку ФЗ в наборі даних існує безліч алгоритмів (як сучасних, так і не дуже). Такі алгоритми можна поділити на три групи:

• Алгоритми, що використовують обхід решіток алгебри (Lattice traversal algorithms)
• Алгоритми, засновані на пошуку узгоджених значень (Difference- and agree-set algorithms)
• Алгоритми, засновані на попарних порівняннях (Dependency induction algorithms)

Короткий опис кожного типу алгоритмів наведено в таблиці нижче:


Докладніше про цю класифікацію можна почитати [4]. Нижче наведено приклади алгоритмів на кожен з типів:

Нині з'являються нові алгоритми, які поєднують у собі відразу кілька підходів до пошуку функціональних залежностей. Прикладами таких алгоритмів є Pyro [2] та HyFD [3]. Розбір їх роботи передбачається у наступних статтях цього циклу. У цій статті ми лише розберемо основні поняття та лему, які необхідні для розуміння техніки виявлення залежностей.

Почнемо з простого – difference- та agree-set, що використовуються у другому типі алгоритмів. Difference-set є безліч кортежів, які не збігаються за значеннями, а agree-set навпаки - кортежі, що збігаються за значеннями. Варто зазначити, що в даному випадку ми розглядаємо лише ліву частину залежності.

Також важливим поняттям, яке зустрічалося вище, є решітка алгебри. Так як багато сучасних алгоритмів оперують даним поняттям, нам потрібно мати уявлення про те, що це таке.

Для того щоб ввести поняття ґрат, необхідно визначення частково впорядкованої множини (або partially ordered set, скорочено — poset).

Визначення 2. Кажуть, що безліч S частково впорядковано бінарним ставленням ⩽, якщо для всяких a, b, c ∈ S виконані властивості:

1. Рефлексивність, тобто a ⩽ a
2. Антисиметричність, тобто, якщо a ⩽ b і b ⩽ a, то a = b
3. Транзитивність, тобто для a ⩽ b і b ⩽ c випливає, що a ⩽ c

Таке ставлення називається ставленням (не суворого) часткового порядку, а саме безліч - частково впорядкованим безліччю. Формальне позначення: ⟨S, ⩽⟩.

Як найпростіший приклад частково впорядкованої множини можна взяти безліч усіх натуральних чисел N із звичайним ставленням порядку ⩽. Неважко перевірити, що всі необхідні аксіоми виконуються.

Більш змістовний приклад. Розглянемо безліч всіх підмножин {1, 2, 3}, упорядковане ставленням включення ⊆. Справді, це ставлення задовольняє всім умовам часткового порядку, тому ⟨P ({1, 2, 3}), ⊆⟩ — частково впорядкована множина. На малюнку нижче зображено структуру цієї множини: якщо з одного елемента можна дійти по стрілочкам до іншого елемента, то вони знаходяться у порядку.

Нам будуть потрібні ще два простих визначення з галузі математики — супремум (supremum) та інфімум (infimum).

Визначення 3. Нехай ⟨S, ⩽⟩ — частково впорядкована множина, A ⊆ S. Верхня межа A — це такий елемент u ∈ S, що ∀x ∈ S: x ⩽ u. Нехай U - безліч всіх верхніх кордонів S. Якщо U існує найменший елемент, тоді він називається супремумом і позначається як sup A.

Аналогічно запроваджується поняття точного нижнього кордону.

Визначення 4. Нехай ⟨S, ⩽⟩ — частково впорядкована множина, A ⊆ S. Нижня межа A — це такий елемент l ∈ S, що ∀x ∈ S: l ⩽ x. Нехай L - безліч всіх нижніх кордонів S. Якщо L існує найбільший елемент, тоді він називається інфімумом і позначається як inf A.

Розглянемо як приклад наведене вище частково впорядковане безліч ⟨P ({1, 2, 3}), ⊆⟩ і знайдемо в ньому супремум та інфімум:

Тепер можна сформулювати визначення решітки алгебри.

Визначення 5. Нехай ⟨P, ⩽⟩ — частково впорядковане безліч, таке, що всяке двоелементне підмножина має точні верхню та нижню межі. Тоді P називається алгебраїчними гратами. У цьому sup{x, y} записують як x ∨ y, а inf {x, y} — як x ∧ y.

Перевіримо, що наш робочий приклад ⟨P ({1, 2, 3}), ⊆⟩ є ґратами. Справді, для всяких a, b ∈ P ({1, 2, 3}), a∨b = a∪b, а a∧b = a∩b. Наприклад, розглянемо безлічі {1, 2} і {1, 3} і знайдемо їхній інфімум і супремум. Якщо ми їх перетнемо, то отримаємо безліч {1}, яка і буде інфімумом. Супремум отримаємо їх об'єднанням - {1, 2, 3}.

В алгоритмах виявлення ФЗ простір пошуку найчастіше представляється у формі решітки, де множини з одного елемента (читай перший рівень решітки пошуку, де ліва частина залежностей складається з одного атрибуту) являють собою кожен атрибут вихідного відношення.
На початку розглядаються залежності виду ∅ → Поодинокий атрибут. Цей крок дозволяє визначити, які атрибути є первинними ключами (для таких атрибутів немає детермінантів, тому ліва частина порожня). Далі такі алгоритми рухаються решіткою вгору. При цьому варто зазначити, що решітку можна обходити не всю, тобто якщо на вхід передати бажаний максимальний розмір лівої частини, далі рівня з таким розміром алгоритм йти не буде.

На малюнку нижче показано, як можна використовувати решітку алгебри в задачі пошуку ФЗ. Тут кожне ребро (X, XY) є залежністю X → Y. Наприклад, ми пройшли перший рівень і знаємо, що утримується залежність А → Б (відобразимо це зеленим зв'язком між вершинами A и B). Значить далі, коли просуватимемося ґратами вгору, ми можемо не перевіряти залежність A, C → Bтому, що вона буде вже не мінімальною. Аналогічно ми не стали б її перевіряти, якби утримувалася залежність. C → B.

Крім того, як правило, всі сучасні алгоритми пошуку ФЗ використовують таку структуру даних, як партиція (у першоджерелі — stripped partition [1]). Формальне визначення партиції виглядає так:

Визначення 6. Нехай X ⊆ R — набір атрибутів для відношення r. Кластер є набором індексів кортежів з r, які мають однакове значення для X, тобто c(t) = {i|ti[X] = t[X]}. Партиція є безліч кластерів, що виключає кластери одиничної довжини:

Простими словами, партиція для атрибуту X являє собою набір списків, де кожен список містить номери рядків з однаковими значеннями для X. У сучасній літературі структура, що представляє партію, називається position list index (PLI). Кластери одиничної довжини виключаються з метою стиснення PLI, тому що це кластери, які містять лише номер запису з унікальним значенням, яке завжди буде легко встановити.

Розглянемо приклад. Повернемося до тієї ж таблиці з пацієнтами і побудуємо партиції для стовпців Пацієнт и Стать (зліва з'явився новий стовпець, у якому відмічені номери рядків таблиці):

При цьому, згідно з визначенням, партиція для стовпця Пацієнт насправді буде порожня, оскільки одиночні кластери виключаються із партиції.

Партиції можна отримувати за кількома атрибутами. І для цього існує два шляхи: пройшовшись по таблиці, побудувати партицію відразу по всіх необхідних атрибутах, або ж побудувати її за допомогою операції перетину партицій за підмножиною атрибутів. Алгоритми пошуку ФЗ використовують другий варіант.

Простими словами, щоб, наприклад, отримати партицію стовпцями азбука, можна взяти партиції для AC и B (або будь-який інший набір непересічних підмножин) і перетнути їх між собою. Операція перетину двох партій виділяє кластери найбільшої довжини, загальні для обох партій.

Давайте розглянемо приклад:

У першому випадку ми одержали порожню партицію. Якщо придивитися до таблиці, то дійсно однакових значень за двома атрибутами там немає. Якщо ми трохи модифікуємо таблицю (випадок праворуч), то отримаємо непусте перетин. При цьому рядки 1 і 2 і справді містять однакові значення за атрибутами Стать и доктор.

Далі нам знадобиться таке поняття, як розмір партиції. Формально:

Простіше кажучи, розмір партиції є кількістю кластерів, що входять до партиції (пам'ятаємо, що одиничні кластери до партиції не входять!):

Тепер ми можемо визначити одну з ключових лем, яка для заданих партій дозволяє встановити, утримується залежність чи ні:

Лемма 1. Залежність A, B → C утримується, якщо тільки якщо

Відповідно до леми, для визначення, чи утримується залежність, необхідно виконати чотири кроки:

1. Обчислити партицію для лівої частини залежності
2. Обчислити партицію для правої частини залежності
3. Обчислити твір першого та другого кроку
4. Порівняти розміри партицій, отриманих на першому та третьому кроці

Нижче наведено приклад перевірки, чи утримується залежність по даній лемі:

У цій статті ми розібрали такі поняття, як функціональна залежність, наближена функціональна залежність, розглянули де вони застосовуються, а також які алгоритми пошуку ФЗ існують. Також ми докладно розібрали базові, але важливі поняття, які активно використовуються в сучасних алгоритмах пошуку ФЗ.

Посилання на літературу:

1. Huhtala Y. та ін. TANE: An efficient algorithm for discovering functional and approximate dependencies //The computer journal. - 1999. - Т. 42. - №. 2. - С. 100-111.
2. Kruse S., Naumann F. Efficient discovery of approximate dependencies //Proceedings of the VLDB Endowment. – 2018. – Т. 11. – №. 7. - С. 759-772.
3. Papenbrock T., Naumann F. Як hybrid approach to functional dependency discovery //Proceedings of the 2016 International Conference on Management of Data. - ACM, 2016. - С. 821-833.
4. Papenbrock T. та ін. Функціональна dependency discovery: An experimental evaluation of seven algorithms //Proceedings of the VLDB Endowment. – 2015. – Т. 8. – №. 10. - С. 1082-1093.
5. Kumar A. та ін. Щоб зробити чи не робити? - ACM, 2016. - С. 2016-19.
6. Abo Khamis M. та ін. In-database вивчає з sparse tensors //Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Посилання на Principles of Database Systems. - ACM, 2018. - С. 325-340.
7. Hellerstein J. M. та ін. MADlib analytics library: або MAD skills, SQL //Proceedings of the VLDB Endowment. – 2012. – Т. 5. – №. 12. - С. 1700-1711.
8. Qin C., Rusu F. Спеціальні пристосування для територіального розповсюдження gradient descent optimization //Proceedings of Fourth Workshop on Data analytics in the Cloud. - ACM, 2015. - С. 1.
9. Meng X. та ін. Mllib: Machine learning in apache spark //The Journal of Machine Learning Research. – 2016. – Т. 17. – №. 1. - С. 1235-1241.

Автори статті: Анастасія Бірілло, дослідник у Дослідження JetBrains, студентка CS центру и Микита Бобрів, дослідник у Дослідження JetBrains

Джерело: habr.com