Въведение във функционалните зависимости

В тази статия ще говорим за функционалните зависимости в базите данни — какво представляват, къде се прилагат и какви алгоритми съществуват за тяхното намиране.

Ние ще разглеждаме функционалните зависимости в контекста на релационните бази данни. Ако говорим съвсем простичко, информацията в такива бази данни се съхранява под формата на таблици. След това ще използваме приблизителни понятия, които в строгата релационна теория не са взаимозаменяеми: самата таблица ще наричаме отношение, колоните — атрибути (множество от тях — схема на отношението), а наборът от стойности на реда в подмножество от атрибутите — кортеж.

Например, в таблицата по-горе, (Benson, M, M organ) е кортеж по атрибутите (Пациент, Пол, Доктор).
По-формално това може да се запише по следния начин: [Пациент, Пол, Доктор] = (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 тя се счита по следния начин:

Да изчислим грешката за Доктор → Пациент от примера по-горе. Имаме два кортежа, стойностите на които се различават по атрибута Пациент, но съвпадат по Докторе: [Доктор, Пациент] = (Робин, Елис) и [Доктор, Пациент] = (Робин, Греъм). Следвайки определението за грешка, трябва да вземем предвид всички конфликтни двойки, а значи те ще бъдат две: (, ) и нейната инверсия (, ). Подставяме в формулата и получаваме:

А сега да се опитаме да отговорим на въпроса: «А защо всичко това?». Всъщност ФЗ могат да бъдат различни. Първият тип — това са такива зависимости, които се определят от администратора на етапа на проектиране на базата данни. Обикновено са малко, те са строги, а основното им приложение е нормализиране на данни и дизайн на схемата на отношенията.

Вторият тип са зависимостите, представляващи „скрити“ данни и преди неизвестни връзки между атрибутите. Тоест, за тези зависимости не са мислили в момента на проектиране и те се откриват вече за съществуващ набор от данни, за да могат след това на базата на многобройни открити функционални зависимости да се направят каквито и да е изводи за съхраняваната информация. Именно с такива зависимости работим. С тях се занимава цяла облас дата майнинг, използвайки различни техники за търсене и изградени на тяхна основа алгоритми. Нека да разгледаме как могат да бъдат полезни откритите функционални зависимости (точни или приблизителни) в някои данни.

Днес сред основните области на приложение на зависимостите се откроява почистването на данни. То предполага разработването на процеси за откриване на „мръсни данни“ и последващото им коригиране. Ярки примери за „мръсни данни“ са дубликатите, грешките в данните или печатните грешки, пропуснатите стойности, остарелите данни, излишните пространства и подобни.

Пример за грешка в данните:

Пример за дубликати в данните:

Например, имаме таблица и набор от функционални зависимости, които трябва да се изпълняват. Почистването на данни в този случай предполага изменение на данните по такъв начин, че функционалните зависимости да станат верни. При това броят на модификациите трябва да бъде минимален (за тази процедура съществуват свои алгоритми, на които няма да се фокусираме в тази статия). По-долу е представен пример за такова преобразуване на данни. Вляво е изходното отношение, в което очевидно не се изпълняват необходимите функционални зависимости (червеният цвят подчертава пример за нарушение на една от тях). Вдясно е представено обновеното отношение, в което зелените клетки показват изменените стойности. След провеждането на такава процедура необходимите зависимости започнаха да се задържат.

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

Да разгледаме тяхното приложение за четирите нормални форми на изображението по-долу. Напомняме, че нормалната форма на Бойс-Кодд е по-строга от третата форма, но по-малко строга от четвъртата. Последната в момента не я разглеждаме, тъй като за нейното прилагане е необходимо разбиране на многозначните зависимости, които за целите на тази статия не ни интересуват.

Още една област, в която зависимостите намериха своето приложение, е намаляването на размерността на пространството на признаците в задачи като изграждането на наивен байесовски класификатор, извеждането на значими признаци и репараметризация на регресионни модели. В оригиналните статии тази задача се нарича идентифициране на излишни признаци (feature redundancy) и релевантни (feature relevancy) [5, 6], и тя се решава с активно използване на концепции от бази данни. С появата на подобни изследвания можем да говорим, че dnes се наблюдава търсене на решения, които съчетават бази данни, аналитика и реализация на горепосочените проблеми на оптимизация в един инструмент [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 и 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, тъй като това са клъстери, съдържащи само номер на записа с уникална стойност, която винаги ще бъде лесно установима.

Нека разгледаме пример. Върнете се към същата таблица с пациенти и изградете партиции за колоните Пациент и Пол (отляво се появи нова колона, в която са отбелязани номерата на редовете на таблицата):

При това, според определението, партицията за колоната Пациент всъщност ще бъде празна, тъй като единичните клъстери се изключват от партицията.

Партиции могат да се получават по няколко атрибута. И за това съществуват два начина: като преминете през таблицата и изградите партиция едновременно по всички необходими атрибути или да я изградите с помощта на операцията за пресичане на партиции по подмножество от атрибути. Алгоритмите за търсене на ФЗ използват втория вариант.

Простичко казано, за да получите партиция по колоните ABC, можете да вземете партиции за AC и B (или която и да е друга група несвързани подмножества) и да ги пресечем помежду им. Операцията по пресичане на две партиции откроява клъстери с най-дълга дължина, общи и за двете партиции.

Нека да разгледаме пример:

В първия случай получихме празна партиция. Ако се вгледаме в таблицата, ще видим, че наистина няма еднакви стойности по две атрибута. Но ако малко модифицираме таблицата (случай вдясно), ще получим непразно пресичане. В същото време редовете 1 и 2 действително съдържат едни и същи стойности по атрибутите. Пол и Доктор.

Следващото, което ще ни е необходимо, е понятието за размер на партиция. Формално:

По-просто казано, размерът на партицията представлява броя на клъстерите, влизащи в партицията (помним, че единични клъстери не влизат в партицията!):

Сега можем да дефинираме една от ключовите леми, която за зададените партиции позволява да се установи дали се задържа зависимост или не:

Лема 1. Зависимостта A, B → C се задържа, ако и само ако

Според лемата, за да се определи дали зависимостта се задържа, е необходимо да се извършат четири стъпки:

1. Да се изчисли партицията за лявата част на зависимостта
2. Да се изчисли партицията за дясната част на зависимостта
3. Да се изчисли произведението на първата и втората стъпка
4. Да се сравнят размерите на партициите, получени на първата и третата стъпка

По-долу е представен пример за проверка дали зависимостта се задържа според дадената лема:

В тази статия разгледахме понятия като функционална зависимост, приблизителна функционална зависимост, къде се прилагат, както и какви алгоритми за търсене на ФЗ съществуват. Също така подробно анализирахме основни, но важни понятия, активно използвани в съвременните алгоритми за търсене на ФЗ.

Препратки към литературата:

1. Huhtala Y. et al. 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. A hybrid approach to functional dependency discovery //Proceedings of the 2016 International Conference on Management of Data. – ACM, 2016. – С. 821-833.
4. Papenbrock T. et al. Functional dependency discovery: An experimental evaluation of seven algorithms //Proceedings of the VLDB Endowment. – 2015. – Т. 8. – №. 10. – С. 1082-1093.
5. Kumar A. et al. To join or not to join?: Thinking twice about joins before feature selection //Proceedings of the 2016 International Conference on Management of Data. – ACM, 2016. – С. 19-34.
6. Abo Khamis M. и др. Обучение в базах данных с разреженными тензорами // Сборник трудов 37-го симпозиума ACM SIGMOD-SIGACT-SIGAI по принципам систем баз данных. – ACM, 2018. – С. 325-340.
7. Hellerstein J. M. и др. Аналитическая библиотека MADlib: или MAD навыки, SQL // Сборник трудов VLDB Endowment. – 2012. – Т. 5. – № 12. – С. 1700-1711.
8. Qin C., Rusu F. Спекулятивные апроксимации для оптимизации градиентного спуска на терескалярных дистрибуциях // Сборник трудов Четвертой мастерской по аналитике данных в облаке. – ACM, 2015. – С. 1.
9. Meng X. и др. Mllib: Машинное обучение в Apache Spark // Журнал исследований машинного обучения. – 2016. – Т. 17. – № 1. – С. 1235-1241.

Авторите на статията: Анастасия Бирилло, изследовател в JetBrains Research, студентка в CS центъра и Никита Бобров, изследовател в JetBrains Research

Източник: habr.com