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

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

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

Например, в таблицата по-горе, (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. Пол → Пациент

Според определението по-горе, за да се запази първата зависимост, на всяко уникално значение на колоната Пациент трябва да съответства само една стойност на колоната Пол. И за примера с таблицата това наистина е така. Въпреки това, в обратната посока това не работи, т.е. втората зависимост не се изпълнява, а атрибутът Пол не е детерминант за Пациента. По подобен начин, ако вземем зависимостта Доктор → Пациент, можем да забележим, че тя се нарушава, тъй като стойността Robin по този атрибут има няколко различни стойности — 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), и се решава с активното използване на концепции от бази данни. С появата на такива работи можем да говорим за нарастващото търсене на решения, които да обединят базата данни, аналитиката и изпълнението на посочените проблеми на оптимизация в един инструмент.

Съществуват множество алгоритми за търсене на ФЗ в набор от данни (както съвременни, така и не толкова). Тези алгоритми могат да бъдат разделени на три групи:

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

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


Допълнителна информация за тази класификация можете да прочетете [4]. По-долу са представени примери за алгоритми за всеки от типовете:

В момента се появяват нови алгоритми, които обединяват няколко подхода за откриване на функционални зависимости. Примери за такива алгоритми са Pyro [2] и HyFD [3]. Разборът на тяхната работа ще бъде в следващите статии от този цикл. В тази статия ще разгледаме основните понятия и лемата, необходима за разбирането на техниките за откриване на зависимости.

Да започнем с просто — difference-set и 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 и Б). Следователно, когато продължим нагоре по решетката, не можем да проверим зависимостта 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 и Б (или която и да е друга комбинация от неперекриващи се подмножества) и да ги пресечем помежду им. Операцията за пресичане на две партиции освобождава клъстери с най-дълга обща дължина и за двете партиции.

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

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

Следва ни да се запознаем с понятието размер на партицията. Формално:

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

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

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

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

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

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

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

Литература:

1. Huhtala Y. и др. TANE: ефикасен алгоритъм за откриване на функционални и приблизителни зависимости //The computer journal. – 1999. – Т. 42. – №. 2. – С. 100-111.
2. Kruse S., Naumann F. Ефикасно откриване на приблизителни зависимости //Proceedings of the VLDB Endowment. – 2018. – Т. 11. – №. 7. – С. 759-772.
3. Papenbrock T., Naumann F. Хибриден подход за откриване на функционални зависимости //Proceedings of the 2016 International Conference on Management of Data. – ACM, 2016. – С. 821-833.
4. Papenbrock T. и др. Откриване на функционални зависимости: експериментална оценка на седем алгоритма //Proceedings of the VLDB Endowment. – 2015. – Т. 8. – №. 10. – С. 1082-1093.
5. Kumar A. и др. Да се присъединим или не?: Да помислим два пъти за присъединенията преди избора на характеристики //Proceedings of the 2016 International Conference on Management of Data. – ACM, 2016. – С. 19-34.
6. Або Хамис М. и др. Обучение в базе данных с использованием разреженных тензоров // Труды 37-й симпозиума ACM SIGMOD-SIGACT-SIGAI по принципам систем баз данных. – ACM, 2018. – С. 325-340.
7. Хеллерстейн Дж. М. и др. Аналитическая библиотека MADlib: или MAD навыки, SQL // Труды фонда VLDB. – 2012. – Т. 5. – №. 12. – С. 1700-1711.
8. Цинь Ч., Русу Ф. Спекулятивные аппроксимации для террафлопсного распределенного оптимизации градиентного спуска // Труды Четвертой конференции по аналитике данных в облаке. – ACM, 2015. – С. 1.
9. Мэнг X. и др. Mllib: Машинное обучение в apache spark // Журнал исследований машинного обучения. – 2016. – Т. 17. – №. 1. – С. 1235-1241.

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

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