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

У овом чланку ћемо говорити о функционалним зависностима у базама података – шта су, где се користе и који алгоритми постоје да их пронађу.

Функционалне зависности ћемо размотрити у контексту релационих база података. Најгрубље речено, у таквим базама података информације се чувају у облику табела. Затим користимо приближне концепте који нису заменљиви у строгој теорији релација: саму табелу ћемо назвати релацијом, колоне - атрибутима (њихов скуп - шема релације), а скуп вредности редова на подскупу атрибута - тупле.

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

Дефиниција 1. Релација Р задовољава савезни закон Кс → И (где је Кс, И ⊆ Р) ако и само ако за било коју торбу , ∈ Р важи: ако [Кс] = [Кс], онда [И] = [И]. У овом случају кажемо да Кс (детерминанта или дефинишући скуп атрибута) функционално одређује И (зависни скуп).

Другим речима, присуство савезног закона Кс → И значи да ако имамо две тупле у R а по атрибутима се подударају X, онда ће се поклапати у атрибутима Y.
А сада, редом. Хајде да погледамо атрибуте Пацијент и Павле за које желимо да сазнамо да ли постоје зависности између њих или не. За такав скуп атрибута могу постојати следеће зависности:

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

Као што је горе дефинисано, да би се прва зависност држала, свака јединствена вредност колоне Пацијент само једна вредност колоне мора да се подудара Павле. А за табелу примера то је заиста случај. Међутим, ово не функционише у супротном смеру, то јест, друга зависност није задовољена, а атрибут Павле није одредница за Пацијент. Слично, ако узмемо зависност Доктор → Пацијент, можете видети да је прекршена, пошто је вредност Црвендаћ овај атрибут има неколико различитих значења - Елис и Грејем.

Дакле, функционалне зависности омогућавају утврђивање постојећих односа између скупова атрибута табеле. Одавде ћемо разматрати најзанимљивије везе, тачније такве Кс → Ионо што су:

• нетривијалан, односно десна страна зависности није подскуп леве (И ⊆ Кс);
• минимална, односно не постоји таква зависност З → ИДа З ⊂ Кс.

Зависности које су до сада разматране биле су строге, односно нису предвиђале никаква кршења на табели, али поред њих, постоје и оне које дозвољавају неку недоследност између вредности торки. Такве зависности су смештене у посебну класу, која се назива приближна, и дозвољено је да буду нарушене за одређени број торки. Овај износ је регулисан индикатором максималне грешке емак. На пример, стопа грешке = 0.01 може значити да зависност може бити нарушена за 1% доступних тупле-а на разматраном скупу атрибута. То јест, за 1000 записа, највише 10 тупле-а може прекршити савезни закон. Размотрићемо мало другачију метрику, засновану на паровима различитих вредности торки које се пореде. За зависност Кс → И на ставу r сматра се овако:

Хајде да израчунамо грешку за Доктор → Пацијент из горњег примера. Имамо две торке чије се вредности разликују по атрибуту Пацијент, али се поклапају на Докторе: [Доктор, пацијент] = (Робин, Елис) и [Доктор, пацијент] = (Робин, Грахам). Пратећи дефиницију грешке, морамо узети у обзир све конфликтне парове, што значи да ће их бити два: (, ) и његова инверзија (, ). Заменимо га у формулу и добићемо:

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

Други тип су зависности, које представљају „скривене“ податке и раније непознате односе између атрибута. Односно, о таквим зависностима се није размишљало у време пројектовања и оне се проналазе за постојећи скуп података, тако да се касније, на основу многих идентификованих савезних закона, могу извући било какви закључци о ускладиштеним информацијама. Управо са овим зависностима радимо. Њима се бави читава област рударења података са различитим техникама претраживања и алгоритмима изграђеним на њиховој основи. Хајде да схватимо како пронађене функционалне зависности (тачне или приближне) у било којим подацима могу бити корисне.

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

Пример грешке у подацима:

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

На пример, имамо табелу и скуп савезних закона који се морају извршити. Чишћење података у овом случају подразумева промену података како би савезни закони постали тачни. У овом случају, број модификација треба да буде минималан (ова процедура има своје алгоритме, на које се нећемо фокусирати у овом чланку). Испод је пример такве трансформације података. На левој страни је оригинални однос, у коме, очигледно, нису испуњени неопходни ФЛ (пример кршења једног од ФЛ-а је истакнут црвеном бојом). Десно је ажурирани однос, са зеленим ћелијама које показују измењене вредности. Након ове процедуре, потребне зависности су почеле да се одржавају.

Још једна популарна апликација је дизајн базе података. Овде вреди подсетити се нормалних облика и нормализације. Нормализација је процес довођења односа у складу са одређеним скупом захтева, од којих је сваки дефинисан нормалним обликом на свој начин. Нећемо описивати захтеве разних нормалних облика (ово се ради у било којој књизи курса базе података за почетнике), али ћемо само приметити да сваки од њих користи концепт функционалних зависности на свој начин. На крају крајева, ФЛ-ови су инхерентно ограничења интегритета која се узимају у обзир приликом дизајнирања базе података (у контексту овог задатка, ФЛ-ови се понекад називају суперкључевима).

Хајде да размотримо њихову примену за четири нормална облика на слици испод. Подсетимо се да је Бојс-Код нормалан облик строжији од трећег облика, али мање строг од четвртог. Ово друго за сада не разматрамо, јер његово формулисање захтева разумевање вишевредносних зависности, које нам у овом чланку нису занимљиве.

Још једна област у којој су зависности нашле своју примену је смањење димензионалности простора карактеристика у задацима као што су изградња наивног Бајесовог класификатора, идентификација значајних карактеристика и репараметаризација регресионог модела. У оригиналним чланцима овај задатак се назива одређивање редундантне и релевантности карактеристика [5, 6], а решава се уз активну употребу концепата базе података. Са појавом оваквих радова, можемо рећи да данас постоји потражња за решењима која нам омогућавају да комбинујемо базу података, аналитику и имплементацију наведених проблема оптимизације у један алат [7, 8, 9].

Постоји много алгоритама (и модерних и не тако модерних) за тражење савезних закона у скупу података. Такви алгоритми се могу поделити у три групе:

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

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


Више о овој класификацији можете прочитати [4]. Испод су примери алгоритама за сваки тип:

Тренутно се појављују нови алгоритми који комбинују неколико приступа проналажењу функционалних зависности. Примери таквих алгоритама су Пиро [2] и ХиФД [3]. Анализа њиховог рада очекује се у наредним чланцима ове серије. У овом чланку ћемо испитати само основне концепте и лему који су неопходни за разумевање техника детекције зависности.

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

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

Да би се увео појам решетке, потребно је дефинисати делимично уређен скуп (или делимично уређен скуп, скраћено посет).

Дефиниција 2. За скуп С се каже да је делимично уређен бинарном релацијом ⩽ ако су за све а, б, ц ∈ С задовољена следећа својства:

1. Рефлексивност, односно а ⩽ а
2. Антисиметрија, то јест, ако је а ⩽ б и б ⩽ а, онда је а = б
3. Транзитивност, односно за а ⩽ б и б ⩽ ц следи да је а ⩽ ц

Таква релација се назива (лабава) релација делимичног реда, а сам скуп се назива делимично уређен скуп. Формална нотација: ⟨С, ⩽⟩.

Као најједноставнији пример делимично уређеног скупа можемо узети скуп свих природних бројева Н са уобичајеном релацијом реда ⩽. Лако је проверити да ли су сви неопходни аксиоми задовољени.

Смисленији пример. Размотримо скуп свих подскупова {1, 2, 3}, поређаних инклузивном релацијом ⊆. Заиста, ова релација задовољава све услове делимичног поретка, тако да је ⟨П ({1, 2, 3}), ⊆⟩ делимично уређен скуп. Слика испод приказује структуру овог скупа: ако се до једног елемента може доћи стрелицама до другог елемента, онда су они у односу редоследа.

Биће нам потребне још две једноставне дефиниције из области математике – супремум и инфимум.

Дефиниција 3. Нека је ⟨С, ⩽⟩ делимично уређен скуп, А ⊆ С. Горња граница А је елемент у ∈ С такав да је ∀к ∈ С: к ⩽ у. Нека је У скуп свих горњих граница С. Ако постоји најмањи елемент у У, онда се он назива супремум и означава се као суп А.

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

Дефиниција 4. Нека је ⟨С, ⩽⟩ делимично уређен скуп, А ⊆ С. Инфимум од А је елемент л ∈ С такав да је ∀к ∈ С: л ⩽ к. Нека је Л скуп свих доњих граница С. Ако постоји највећи елемент у Л, онда се он назива инфимум и означава се као инф А.

Размотримо као пример горњи делимично уређен скуп ⟨П ({1, 2, 3}), ⊆⟩ и пронађимо супремум и инфимум у њему:

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

Дефиниција 5. Нека је ⟨П,⩽⟩ делимично уређен скуп такав да сваки подскуп од два елемента има горњу и доњу границу. Тада се П назива алгебарска решетка. У овом случају, суп{к, и} се записује као к ∨ и, а инф {к, и} као к ∧ и.

Хајде да проверимо да ли је наш радни пример ⟨П ({1, 2, 3}), ⊆⟩ решетка. Заиста, за било које а, б ∈ П ({1, 2, 3}), а∨б = а∪б, и а∧б = а∩б. На пример, размотрите скупове {1, 2} и {1, 3} и пронађите њихов инфимум и супремум. Ако их пресечемо, добићемо скуп {1}, који ће бити инфимум. Добијамо супремум тако што их комбинујемо - {1, 2, 3}.

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

Слика испод показује како се алгебарска решетка може користити у проблему проналажења ФЗ. Овде свака ивица (Кс, КСИ) представља зависност Кс → И. На пример, прошли смо први ниво и знамо да се зависност одржава А → Б (ово ћемо приказати као зелену везу између врхова A и B). То значи да даље, када се крећемо горе дуж решетке, можда нећемо проверити зависност А, Ц → Б, јер више неће бити минималан. Слично томе, не бисмо га проверавали да је зависност одржана Ц → Б.

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

Дефиниција 6. Нека је Кс ⊆ Р скуп атрибута за релацију р. Кластер је скуп индекса торки у р који имају исту вредност за Кс, односно ц(т) = {и|ти[Кс] = т[Кс]}. Партиција је скуп кластера, искључујући кластере јединичне дужине:

Једноставним речима, партиција за атрибут X је скуп листа, где свака листа садржи бројеве редова са истим вредностима за X. У савременој литератури, структура која представља партиције назива се индекс листе позиција (ПЛИ). Кластери дужине јединице су искључени за потребе ПЛИ компресије јер су то кластери који садрже само број записа са јединственом вредношћу коју ће увек бити лако идентификовати.

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

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

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

Једноставним речима, да, на пример, добијете партицију по колонама АБЦ, можете узети партиције за AC и B (или било који други скуп дисјунктних подскупова) и секу их један са другим. Операцијом пресека две партиције се бирају кластери највеће дужине који су заједнички за обе партиције.

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

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

Затим ће нам требати такав концепт као што је величина партиције. Формално:

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

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

Лема 1. Зависност А, Б → Ц важи ако и само ако

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

1. Израчунајте партицију за леву страну зависности
2. Израчунајте партицију за десну страну зависности
3. Израчунајте производ првог и другог корака
4. Упоредите величине партиција добијених у првом и трећем кораку

Испод је пример провере да ли зависност важи према овој леми:

У овом чланку смо испитали појмове као што су функционална зависност, приближна функционална зависност, погледали где се користе, као и који алгоритми за тражење физичких функција постоје. Такође смо детаљно испитали основне, али важне концепте који се активно користе у савременим алгоритмима за тражење савезних закона.

Референце:

1. Хухтала И. ет ал. ТАНЕ: Ефикасан алгоритам за откривање функционалних и приближних зависности //Тхе цомпутер јоурнал. – 1999. – Т. 42. – Бр. 2. – стр. 100-111.
2. Крусе С., Науманн Ф. Ефикасно откривање приближних зависности // Процеедингс оф тхе ВЛДБ Ендовмент. – 2018. – Т. 11. – Бр. 7. – стр. 759-772.
3. Папенброцк Т., Науманн Ф. Хибридни приступ откривању функционалне зависности //Процеедингс оф тхе 2016 Интернатионал Цонференце он Манагемент оф Дата. – АЦМ, 2016. – стр. 821-833.
4. Папенброцк Т. ет ал. Откривање функционалне зависности: Експериментална евалуација седам алгоритама //Процеедингс оф тхе ВЛДБ Ендовмент. – 2015. – Т. 8. – Бр. 10. – стр. 1082-1093.
5. Кумар А. ет ал. Придружити се или не придружити се?: Двапут размишљам о спајањима пре избора карактеристика //Процеедингс оф тхе 2016 Интернатионал Цонференце он Манагемент оф Дата. – АЦМ, 2016. – стр. 19-34.
6. Або Кхамис М. ет ал. Учење у бази података са ретким тензорима //Процеедингс оф тхе 37тх АЦМ СИГМОД-СИГАЦТ-СИГАИ Симпосиум он Принциплес оф Датабасе Системс. – АЦМ, 2018. – стр. 325-340.
7. Хеллерстеин ЈМ ет ал. МАДлиб аналитичка библиотека: или МАД вештине, СКЛ //Процеедингс оф тхе ВЛДБ Ендовмент. – 2012. – Т. 5. – Бр. 12. – стр. 1700-1711.
8. Кин Ц., Русу Ф. Спекулативне апроксимације за оптимизацију тераскалног дистрибуираног градијента спуштања //Процеедингс оф тхе Фоуртх Ворксхоп он Дата аналитицс ин тхе Цлоуд. – АЦМ, 2015. – С. 1.
9. Менг Кс. ет ал. Мллиб: Машинско учење у апацхе искри //Тхе Јоурнал оф Мацхине Леарнинг Ресеарцх. – 2016. – Т. 17. – Бр. 1. – стр. 1235-1241.

Аутори чланка: Анастасиа Бирилло, истраживач у ЈетБраинс Ресеарцх, Студент ЦС центра и Никита Бобров, истраживач у ЈетБраинс Ресеарцх

Извор: ввв.хабр.цом