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

Во оваа статија ќе зборуваме за функционалните зависности во базите на податоци - што се тие, каде се користат и кои алгоритми постојат за да ги пронајдат.

Ќе ги разгледаме функционалните зависности во контекст на релационите бази на податоци. Многу грубо кажано, во такви бази на податоци информациите се чуваат во форма на табели. Следно, ние користиме приближни концепти кои не се заменливи во строгата релациона теорија: самата табела ќе ја наречеме врска, колоните - атрибути (нивното множество - шема на релации) и множество вредности на редови на подмножество атрибути. - торка.

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

Дефиниција 1. Релацијата R го задоволува федералниот закон X → Y (каде X, Y ⊆ R) ако и само ако за кои било торки , ∈ R важи: ако [X] = [X], тогаш [Y] = [Y]. Во овој случај, велиме дека X (детерминантата, или дефинирачкото множество на атрибути) функционално го одредува Y (зависното множество).

Со други зборови, присуство на федерален закон X → Y значи дека ако имаме две торки во R и тие се совпаѓаат во атрибути X, тогаш тие ќе се совпаѓаат во атрибути Y.
И сега, по ред. Ајде да ги погледнеме атрибутите Трпелив и Секс за кои сакаме да дознаеме дали меѓу нив има или не зависности. За таков сет на атрибути, може да постојат следните зависности:

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

Како што е дефинирано погоре, за да се одржи првата зависност, секоја единствена вредност на колоната Трпелив само една вредност на колоната мора да одговара Секс. И за примерната табела ова е навистина случај. Но, тоа не функционира во спротивна насока, односно втората зависност не е задоволена, а атрибутот Секс не е детерминанта за Трпелив. Слично, ако ја земеме зависноста Доктор → Пациент, може да се види дека е прекршена, бидејќи вредноста Робин овој атрибут има неколку различни значења - Елис и Греам.

Така, функционалните зависности овозможуваат да се одредат постоечките односи помеѓу множества на атрибути на табелата. Оттука па натаму ќе ги разгледуваме најинтересните врски, поточно такви X → Yкои се тие:

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

Зависностите што се разгледуваа до овој момент беа строги, односно не предвидуваа никакви прекршувања на масата, но покрај нив, има и такви што дозволуваат одредена недоследност помеѓу вредностите на торките. Ваквите зависности се сместени во посебна класа, наречена приближна, и дозволено е да се прекршат за одреден број торки. Оваа сума е регулирана со индикаторот за максимална грешка emax. На пример, стапката на грешка = 0.01 може да значи дека зависноста може да се наруши со 1% од достапните множества на разгледуваниот сет на атрибути. Односно, за 1000 записи, најмногу 10 торки може да го прекршат Федералниот закон. Ќе разгледаме малку поинаква метрика, заснована на пар различни вредности на споредените торки. За зависност X → Y на ставот r се смета вака:

Ајде да ја пресметаме грешката за Доктор → Пациент од примерот погоре. Имаме две торки чии вредности се разликуваат по атрибутот Трпелив, но се совпаѓаат на Доктор: [Доктор, пациент] = (Робин, Елис) И [Доктор, пациент] = (Робин, Греам). Следејќи ја дефиницијата за грешка, мора да ги земеме предвид сите конфликтни парови, што значи дека ќе има два од нив: (, ) и неговата инверзна (, ). Ајде да го замениме во формулата и да добиеме:

Сега да се обидеме да одговориме на прашањето: „Зошто е сето тоа? Всушност, федералните закони се различни. Првиот тип се оние зависности што ги одредува администраторот во фазата на дизајнирање на базата на податоци. Обично се малку на број, строги, а главната примена е нормализација на податоците и дизајн на релациона шема.

Вториот тип се зависности кои претставуваат „скриени“ податоци и претходно непознати врски помеѓу атрибутите. Односно, за таквите зависности не се размислувало во времето на дизајнирање и тие веќе се пронајдени за постојниот сет на податоци, така што подоцна, врз основа на многуте идентификувани федерални закони, може да се извлечат какви било заклучоци за складираните информации. Ние работиме токму со овие зависности. Со нив се занимава цело поле на ископување податоци со различни техники за пребарување и алгоритми изградени врз нивна основа. Ајде да откриеме како пронајдените функционални зависности (точни или приближни) во кој било податок можат да бидат корисни.

Денес, една од главните апликации на зависности е чистењето на податоците. Тоа вклучува развој на процеси за идентификување на „валканите податоци“ и потоа нивно коригирање. Истакнати примери на „валкани податоци“ се дупликати, грешки во податоците или печатни грешки, вредности што недостасуваат, застарени податоци, дополнителни празни места и слично.

Пример за грешка во податоците:

Пример за дупликати во податоците:

На пример, имаме табела и збир на федерални закони кои мора да се извршат. Чистењето на податоците во овој случај вклучува промена на податоците за да станат точни Федералните закони. Во овој случај, бројот на модификации треба да биде минимален (оваа постапка има свои алгоритми, на кои нема да се фокусираме во оваа статија). Подолу е пример за таква трансформација на податоци. Лево е оригиналниот однос, во кој, очигледно, не се исполнети потребните FL (пример за прекршување на еден од FL е означен со црвено). На десната страна е ажурираната врска, со зелените ќелии кои ги покажуваат променетите вредности. По оваа постапка почнаа да се одржуваат потребните зависности.

Друга популарна апликација е дизајнот на базата на податоци. Тука вреди да се потсетиме на нормалните форми и нормализацијата. Нормализацијата е процес на усогласување на врската со одреден сет на барања, од кои секоја е дефинирана со нормалната форма на свој начин. Ние нема да ги опишуваме барањата на различни нормални форми (ова е направено во која било книга за курс за база на податоци за почетници), но само ќе забележиме дека секој од нив го користи концептот на функционални зависности на свој начин. На крајот на краиштата, FL се инхерентно ограничувања на интегритетот кои се земаат предвид при дизајнирање на база на податоци (во контекст на оваа задача, FL понекогаш се нарекуваат суперклучеви).

Да ја разгледаме нивната примена за четирите нормални форми на сликата подолу. Потсетете се дека нормалната форма на Бојс-Код е построга од третата форма, но помалку строга од четвртата. Засега не го разгледуваме второто, бидејќи неговата формулација бара разбирање на повеќевредни зависности, кои не ни се интересни во оваа статија.

Друга област во која зависностите ја нашле својата примена е намалувањето на димензионалноста на просторот на карактеристиките во задачи како што се градење наивен Bayes класификатор, идентификување значајни карактеристики и репараметризирање на регресивен модел. Во оригиналните статии, оваа задача се нарекува определување на релевантност на редундантни и карактеристики [5, 6] и се решава со активно користење на концепти на база на податоци. Со појавата на такви дела, можеме да кажеме дека денес има побарувачка за решенија кои ни овозможуваат да ја комбинираме базата на податоци, аналитиката и имплементацијата на горенаведените оптимизациски проблеми во една алатка [7, 8, 9].

Постојат многу алгоритми (и модерни и не толку модерни) за пребарување на федерални закони во збир на податоци.

• Алгоритми кои користат траверсирање на алгебарски решетки
• Алгоритми засновани на пребарување на договорени вредности (алгоритми со различни и согласни поставени)
• Алгоритми базирани на парни споредби (Алгоритми за индукција на зависност)

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


Можете да прочитате повеќе за оваа класификација [4]. Подолу се дадени примери на алгоритми за секој тип:

Во моментов, се појавуваат нови алгоритми кои комбинираат неколку пристапи за пронаоѓање на функционални зависности. Примери за такви алгоритми се Pyro [2] и HyFD [3]. Се очекува анализа на нивната работа во следните написи од оваа серија. Во оваа статија ќе ги испитаме само основните концепти и леми кои се неопходни за да се разберат техниките за откривање зависност.

Да почнеме со едноставно - множество за разлика и согласување, што се користи во вториот тип на алгоритми. Множество за разлика е множество од торки кои немаат исти вредности, додека согласно множество, напротив, се множества кои имаат исти вредности. Вреди да се напомене дека во овој случај ја разгледуваме само левата страна на зависноста.

Друг важен концепт со кој се сретнавме погоре е алгебарската решетка. Бидејќи многу современи алгоритми работат на овој концепт, треба да имаме идеја за што е тоа.

За да се воведе концептот на решетка, неопходно е да се дефинира делумно подредено множество (или делумно подредено множество, скратено како посет).

Дефиниција 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, тогаш тој се нарекува supremum и се означува sup A.

Концептот на точна долна граница е воведен слично.

Дефиниција 4. Нека ⟨S, ⩽⟩ е делумно подредено множество, A ⊆ S. Инфимумот на A е елемент l ∈ S таков што ∀x ∈ S: l ⩽ x. Нека L е множеството од сите долни граници на S. Ако има најголем елемент во L, тогаш тој се нарекува infimum и се означува како inf A.

Разгледајте го како пример горенаведеното делумно подредено множество ⟨P ({1, 2, 3}), ⊆⟩ и пронајдете ги supremum и infimum во него:

Сега можеме да ја формулираме дефиницијата за алгебарска решетка.

Дефиниција 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}, кое ќе биде infimum. Супреумот го добиваме со нивно комбинирање - {1, 2, 3}.

Во алгоритмите за идентификување физички проблеми, просторот за пребарување често е претставен во форма на решетка, каде множества од еден елемент (читај првото ниво на решетката за пребарување, каде што левата страна на зависностите се состои од еден атрибут) го претставуваат секој атрибут на оригиналниот однос.
Прво, ги разгледуваме зависностите од формата ∅ → Единствен атрибут. Овој чекор ви овозможува да одредите кои атрибути се примарни клучеви (за такви атрибути нема детерминанти и затоа левата страна е празна). Понатаму, таквите алгоритми се движат нагоре по должината на решетката. Вреди да се напомене дека не може да се помине целата решетка, односно, ако саканата максимална големина на левата страна се пренесе на влезот, тогаш алгоритмот нема да оди подалеку од ниво со таа големина.

Сликата подолу покажува како алгебарската решетка може да се користи во проблемот со наоѓање FZ. Тука секој раб (X, XY) претставува зависност X → Y. На пример, го поминавме првото ниво и знаеме дека зависноста се одржува А → Б (ова ќе го прикажеме како зелена врска помеѓу темињата A и B). Ова значи дека понатаму, кога се движиме нагоре по решетката, можеби нема да ја провериме зависноста A, C → B, бидејќи веќе нема да биде минимално. Слично на тоа, ние не би го провериле доколку се одржи зависноста C → B.

Покрај тоа, по правило, сите модерни алгоритми за пребарување на федерални закони користат структура на податоци како што е партиција (во оригиналниот извор - соголена партиција [1]). Формалната дефиниција за партиција е како што следува:

Дефиниција 6. Нека X ⊆ R е збир на атрибути за релацијата r. Кластерот е збир на индекси на торки во r кои имаат иста вредност за X, односно c(t) = {i|ti[X] = t[X]}. Партицијата е збир од кластери, со исклучок на кластери со единечна должина:

Со едноставни зборови, партиција за атрибут X е збир на списоци, каде што секоја листа содржи броеви на линии со исти вредности за X. Во модерната литература, структурата што ги претставува партициите се нарекува индекс на листа на позиции (PLI). Кластерите со должина на единицата се исклучени за целите на компресија на PLI бидејќи тие се кластери што содржат само рекорден број со единствена вредност што секогаш ќе биде лесно да се идентификува.

Ајде да погледнеме на пример. Да се ​​вратиме на истата табела со пациентите и да изградиме партиции за колоните Трпелив и Секс (лево се појави нова колона, во која се означени броевите на редовите на табелата):

Притоа, според дефиницијата, партицијата за колоната Трпелив всушност ќе биде празна, бидејќи единечните кластери се исклучени од партицијата.

Партициите може да се добијат по неколку атрибути. И постојат два начина да го направите ова: со одење низ табелата, изградете партиција користејќи ги сите потребни атрибути одеднаш или изградете ја користејќи ја операцијата на пресек на партиции користејќи подмножество атрибути. Алгоритмите за пребарување на федералните закони ја користат втората опција.

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

Ајде да погледнеме на пример:

Во првиот случај добивме празна партиција. Ако внимателно ја погледнете табелата, тогаш навистина, нема идентични вредности за двата атрибути. Ако малку ја измениме табелата (случајот десно), веќе ќе добиеме непразна раскрсница. Покрај тоа, линиите 1 и 2 всушност ги содржат истите вредности за атрибутите Секс и Лекар.

Следно, ќе ни треба таков концепт како големина на партицијата. Формално:

Едноставно кажано, големината на партицијата е бројот на кластери вклучени во партицијата (запомнете дека единечните кластери не се вклучени во партицијата!):

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

Лема 1. Зависноста A, B → C важи ако и само ако

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

1. Пресметајте ја партицијата за левата страна на зависноста
2. Пресметајте ја партицијата за десната страна на зависноста
3. Пресметајте го производот од првиот и вториот чекор
4. Споредете ги големините на партициите добиени во првиот и третиот чекор

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

Во оваа статија, ги испитавме концептите како што се функционална зависност, приближна функционална зависност, погледнавме каде се користат, како и кои алгоритми за пребарување на физички функции постојат. Ние, исто така, детално ги испитавме основните, но важни концепти кои активно се користат во современите алгоритми за пребарување на федералните закони.

Референци:

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

Автори на статијата: Анастасија Бирило, истражувач во Истражување на JetBrains, Студент на ЦС центар и Никита Бобров, истражувач во Истражување на JetBrains

Извор: www.habr.com