Iskanje funkcionalnih odvisnosti v podatkih se uporablja na različnih področjih analize podatkov: upravljanje baz podatkov, čiščenje podatkov, obratno inženirstvo baz podatkov in raziskovanje podatkov. O samih odvisnostih smo že objavili nekaj. Anastasia Birillo in Nikita Bobrov. Tokrat Anastasia, letos diplomantka Centra za računalništvo, deli razvoj tega raziskovalnega projekta, ki ga je zagovarjala v centru.
Izbor nalog
Med študijem na Centru za računalništvo sem začel poglobljeno preučevati podatkovne baze, natančneje iskanje funkcionalnih in diferencialnih odvisnosti. Ta tema je bila povezana z mojim univerzitetnim študijem, zato sem med delom na njej začel brati članke o različnih odvisnostih v podatkovnih bazah. Napisal sem pregledno delo na tem področju – eno mojih prvih v angleščini in ga predložil konferenci SEIM-2017. Bil sem navdušen, ko je bil sprejet, in sem se odločil, da se s temo poglobim. Sam koncept ni nov – obstaja že od devetdesetih let prejšnjega stoletja – vendar se še danes uporablja na številnih področjih.
V drugem semestru v centru sem začel raziskovalni projekt za izboljšanje algoritmov za iskanje funkcionalnih odvisnosti. Pri njem sem sodeloval z Nikito Bobrovom, podiplomskim študentom na Državni univerzi v Sankt Peterburgu, pri JetBrains Research.
Računska zahtevnost iskanja funkcionalnih odvisnosti
Glavni problem je računska kompleksnost. Število možnih minimalnih in netrivialnih odvisnosti je od zgoraj omejeno z 
Če 
— število atributov tabele. Čas delovanja algoritmov ni odvisen le od števila atributov, temveč tudi od števila vrstic. V devetdesetih letih prejšnjega stoletja so lahko algoritmi za zaznavanje zvezne zakonodaje na tipičnem namiznem računalniku obdelovali nabore podatkov, ki so vsebovali do 20 atributov in več deset tisoč vrstic, do nekaj ur. Sodobni algoritmi, ki delujejo na večjedrnih procesorjih, zaznavajo odvisnosti za nabore podatkov, ki so sestavljeni iz več sto atributov (do 200) in več sto tisoč vrstic, v približno enakem času. Vendar to ni dovolj: tak čas je za večino resničnih aplikacij nesprejemljiv. Zato smo razvili pristope za pospešitev obstoječih algoritmov.
Sheme predpomnjenja za presečišče particij
V prvem delu članka smo razvili sheme predpomnjenja za razred algoritmov z uporabo metode preseka particij. Particija za atribut je niz seznamov, kjer vsak seznam vsebuje številke vrstic z enakimi vrednostmi za dani atribut. Vsak tak seznam se imenuje gruča. Mnogi sodobni algoritmi uporabljajo particije za ugotavljanje, ali odvisnost velja, in sicer se držijo naslednje leme: Odvisnost 
se ohrani, če 
Tukaj 
Particija je označena z , uporabljen pa je koncept velikosti particije – število gruč znotraj nje. Algoritmi, ki uporabljajo particije, dodajo dodatne atribute na levo stran odvisnosti, ko je odvisnost kršena, nato pa jo ponovno izračunajo z izvedbo operacije preseka particij. Ta operacija se v člankih imenuje specializacija. Vendar smo opazili, da je mogoče particije za odvisnosti, ki se bodo ohranile šele po več krogih specializacije, aktivno ponovno uporabiti, kar lahko znatno skrajša čas izvajanja algoritmov, saj je operacija preseka draga.
Zato smo predlagali hevristiko, ki temelji na Shannonovi entropiji in Ginijevi negotovosti, ter lastno metriko, ki jo imenujemo inverzna entropija. Gre za rahlo modifikacijo Shannonove entropije in se povečuje z naraščajočo edinstvenostjo nabora podatkov. Predlagana hevristika je naslednja:
Tukaj 
— stopnja edinstvenosti nedavno izračunane particije 
In 
je mediana stopenj edinstvenosti za posamezne atribute. Vse tri zgoraj opisane metrike so bile preizkušene kot metrike edinstvenosti. Omeniti velja tudi, da hevristika vključuje dva modifikatorja. Prvi označuje, kako blizu je trenutna particija primarnemu ključu, in omogoča večje predpomnjenje particij, ki so dlje od kandidatnega ključa. Drugi modifikator spremlja zasedenost predpomnilnika in s tem spodbuja dodajanje več particij v predpomnilnik, ko je na voljo prostor. Uspešna rešitev te težave je omogočila, da se je algoritem PYRO pospešil za 10–40 %, odvisno od nabora podatkov. Omeniti velja, da je algoritem PYRO na tem področju najuspešnejši.
Spodnja slika prikazuje rezultate uporabe predlagane hevristike v primerjavi z osnovnim pristopom predpomnjenja, ki temelji na metanju kovancev. Os x je logaritemska.
Alternativni način shranjevanja predelnih sten
Nato smo predlagali alternativno metodo za shranjevanje particij. Particije so niz gruč, od katerih vsaka shranjuje številke naborov z enakimi vrednostmi za določene atribute. Te gruče lahko vsebujejo dolga zaporedja številk naborov, na primer, če so podatki v tabeli urejeni. Zato smo predlagali shemo stiskanja za shranjevanje particij, in sicer intervalno shranjevanje vrednosti v gručah particij:
$$display$$pi(X) = {{podvezica{1, 2, 3, 4, 5}_{Prvi~interval}, podvezica{7, 8}_{Drugi~interval}, 10}}\ downarrow{Stisnitev}\ pi(X) = {{podvezica{$, 1, 5}_{Prvi~interval}, podvezica{7, 8}_{Drugi~interval}, 10}}$$display$$
Ta metoda je uspela zmanjšati porabo pomnilnika med izvajanjem algoritma TANE za 1 do 25 %. Algoritem TANE je klasičen algoritem za iskanje logičnih con; med svojim delovanjem uporablja particije. Za praktične namene je bil algoritem TANE izbran, ker je bila implementacija intervalnega shranjevanja bistveno lažja kot na primer v PYRO za oceno izvedljivosti predlaganega pristopa. Rezultati so predstavljeni na spodnji sliki. Os x je logaritemska.
Konferenca ADBIS-2019
Na podlagi rezultatov raziskave sem septembra 2019 objavil članek. Na 23. evropski konferenci o napredku v podatkovnih bazah in informacijskih sistemih (ADBIS-2019) je delo prepoznal Bernhard Thalheim, ugledna osebnost na področju podatkovnih baz. Rezultati raziskave so bili osnova za mojo disertacijo za magistrski program na Fakulteti za matematiko in mehaniko Državne univerze v Sankt Peterburgu, v okviru katerega sta bila oba predlagana pristopa (predpomnjenje in stiskanje) implementirana v oba algoritma: TANE in PYRO. Rezultati so pokazali, da sta predlagana pristopa univerzalna, saj sta oba algoritma pokazala znatno zmanjšanje porabe pomnilnika in znatno zmanjšanje časa izvajanja.
Vir: www.habr.com
