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

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

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

Например в таблицата по-горе (Бенсън, М, Морган) е кортеж по атрибути (Пациент, Пол, доктор).
По-официално това е написано по следния начин: [Пациент, Пол, доктор] = (Бенсън, М, Морган).
Сега можем да въведем понятието функционална зависимост (FC):

Определение 1. Отношението R удовлетворява FD X → Y (където X, Y ⊆ R) тогава и само ако за всякакви кортежи , ∈ R е изпълнено: ако [x]= [X], тогава [Y] = [Y]. В такъв случай се казва, че X (детерминантата или определящият набор от атрибути) функционално определя Y (зависимото множество).

С други думи, наличието на федерален закон X→Y означава, че ако имаме два кортежа в R и съвпадат по атрибути X, тогава те също ще съвпадат по атрибути Y.
А сега по ред. Помислете за атрибути пациент и Paul за които искаме да знаем има ли зависимости между тях или не. За такъв набор от атрибути може да съществуват следните зависимости:

1. Пациент → Пол
2. Пол → Пациент

Съгласно дефиницията по-горе, за да се задържи първата зависимост, всяка уникална стойност на колоната пациент само една стойност на колона трябва да съвпада Paul. И за примерната таблица това е вярно. Това обаче не работи в обратната посока, тоест втората зависимост не е изпълнена и атрибутът Paul не е определящо за Търпелив. По същия начин, ако вземем зависимостта Лекар → Пациент, можете да видите, че е нарушено, тъй като стойността червеношийка на този атрибут има няколко различни стойности − Елис и Греъм.

По този начин функционалните зависимости ви позволяват да определите съществуващите връзки между наборите от атрибути на таблицата. Оттук нататък ще разгледаме най-интересните връзки или по-скоро такива X→Yкакво са те:

• нетривиална, тоест дясната страна на зависимостта не е подмножество на лявата (Y ⊆ X);
• минимална, тоест няма такава зависимост Z → YЧе Z ⊂ X.

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

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

А сега нека се опитаме да отговорим на въпроса: "Защо е всичко това?". Всъщност FZ са различни. Първият тип са тези зависимости, които са дефинирани от администратора на етапа на проектиране на базата данни. Обикновено са малко, те са стриктни и основното приложение е нормализирането на данни и проектирането на схема на връзката.

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

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

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

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

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

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

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

Друга област, в която зависимостите са намерили своя път, е намаляването на измерението на пространството на характеристиките в такива проблеми като изграждане на наивен класификатор на Бейс, извличане на значими характеристики и повторно параметризиране на регресионен модел. В оригиналните статии този проблем се нарича определяне на излишни характеристики (feature redundancy) и релевантни (feature relevancy) [5, 6] и се решава с активно използване на концепции за бази данни. С появата на такива произведения можем да кажем, че днес има търсене на решения, които позволяват комбиниране на базата данни, анализите и изпълнението на горните оптимизационни проблеми в един инструмент [7, 8, 9].

Има много алгоритми (модерни и не много модерни) за търсене на FD в набор от данни.Такива алгоритми могат да бъдат разделени на три групи:

• Алгоритми за обхождане на решетка
• Алгоритми, базирани на търсене на последователни стойности (алгоритми за разлика и съгласуване)
• Алгоритми, базирани на сравнения по двойки (алгоритми за индукция на зависимост)

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


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

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

Нека започнем с един прост - набор от разлики и съгласие, използвани във втория тип алгоритми. Difference-set е набор от кортежи, които не съвпадат по стойност, а accept-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}.

В алгоритмите за откриване на FD пространството за търсене често се представя под формата на решетка, където набори от един елемент (прочетете първото ниво на решетката за търсене, където лявата страна на зависимостите се състои от един атрибут) представляват всеки атрибут на първоначална връзка.
В началото зависимости от формата ∅ → един атрибут. Тази стъпка ви позволява да определите кои атрибути са първични ключове (няма детерминанти за такива атрибути и следователно лявата страна е празна). Освен това такива алгоритми се придвижват нагоре по решетката. В същото време си струва да се отбележи, че не цялата решетка може да бъде заобиколена, т.е. ако желаният максимален размер на лявата страна се предаде на входа, тогава алгоритъмът няма да надхвърли нивото с този размер.

Фигурата по-долу показва как можете да използвате алгебричната решетка в задачата за търсене на FD. Тук всеки ръб (X, XY) представлява зависимостта X→Y. Например, преминали сме първото ниво и знаем, че зависимостта се поддържа А → Б (ще покажем това със зелена връзка между върховете A и B). По-нататък, когато се движим нагоре по решетката, не можем да проверим зависимостта A, C → B, защото вече няма да е минимален. По същия начин не бихме го проверили, ако зависимостта беше задържана C→B.

Освен това, като правило, всички съвременни алгоритми за търсене на FD използват такава структура от данни като дял (в оригиналния източник - stripped partition [1]). Официалната дефиниция на дял е следната:

Определение 6. Нека X ⊆ R е набор от атрибути за релация r. Клъстерът е набор от индекси на кортежи от r, които имат една и съща стойност за X, т.е. c(t) = {i|ti[X] = t[X]}. Дялът е набор от клъстери, с изключение на клъстери с единична дължина:

С прости думи, дял за атрибут X е набор от списъци, където всеки списък съдържа номера на редове с еднакви стойности за X. В съвременната литература структура, представляваща дялове, се нарича индекс на списък с позиции (PLI). Клъстерите с единична дължина са изключени за целите на PLI компресията, тъй като те са клъстери, съдържащи само номер на запис с уникална стойност, която винаги ще бъде лесна за настройка.

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

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

Разделите могат да бъдат получени по няколко атрибута. И за това има два начина: като преминете през таблицата, изградете дял наведнъж по всички необходими атрибути или го изградете, като използвате операцията за кръстосване на дялове по подмножество от атрибути. FD алгоритмите за търсене използват втората опция.

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

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

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

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

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

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

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

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

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

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

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

Линкове към литература:

1. Huhtala Y. и др. TANE: Ефективен алгоритъм за откриване на функционални и приблизителни зависимости // Компютърният журнал. - 1999. - Т. 42. - Бр. 2. - С. 100-111.
2. Kruse S., Naumann F. Ефективно откриване на приблизителни зависимости // Proceedings of the VLDB Endowment. - 2018. - Т. 11. - бр. 7. - С. 759-772.
3. Папенброк Т., Науман Ф. Хибриден подход за откриване на функционални зависимости // Доклади на Международната конференция за управление на данни през 2016 г. - ACM, 2016. - С. 821-833.
4. Papenbrock T. et al. Откриване на функционална зависимост: Експериментална оценка на седем алгоритма // Сборници на VLDB Endowment. - 2015. - Т. 8. - бр. 10. - С. 1082-1093.
5. Kumar A. и др. Да се ​​присъедините или да не се присъедините?: Помислете два пъти за присъединяванията преди избора на функция // Сборник на Международната конференция за управление на данни от 2016 г. - ACM, 2016. - С. 19-34.
6. Abo Khamis M. и др. Обучение в база данни с редки тензори // Сборници на 37-ия симпозиум на ACM SIGMOD-SIGACT-SIGAI относно принципите на системите за бази данни. - ACM, 2018. - С. 325-340.
7. Hellerstein JM et al. Библиотеката за анализ на MADlib: или MAD умения, SQL //Proceedings of the VLDB Endowment. - 2012. - Т. 5. - бр. 12. - С. 1700-1711.
8. Qin C., Rusu F. Спекулативни приближения за terascale разпределена градиентна оптимизация на спускане // Доклади на Четвъртия семинар за анализ на данни в облака. - ACM, 2015. - С. 1.
9. Meng X. и др. Mllib: Машинно обучение в apache spark // The Journal of Machine Learning Research. - 2016. - Т. 17. - бр. 1. - С. 1235-1241.

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

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