Pronalaženje funkcionalnih ovisnosti u podacima koristi se u raznim područjima analize podataka: upravljanju bazama podataka, čišćenju podataka, obrnutom inženjerstvu baza podataka i istraživanju podataka. Već smo objavili o samim ovisnostima. Anastasia Birillo i Nikita Bobrov. Ovaj put, Anastasia, koja je ove godine diplomirala na Centru za računalne znanosti, dijeli razvoj ovog istraživačkog projekta koji je obranila u centru.
Izbor zadatka
Tijekom studija na CS Centru, počeo sam detaljno proučavati baze podataka, posebno pronalaženje funkcionalnih i diferencijalnih ovisnosti. Ova tema bila je povezana s mojim sveučilišnim radom, pa sam dok sam radio na njoj počeo čitati članke o raznim ovisnostima u bazama podataka. Napisao sam pregled ovog područja - jedan od mojih prvih na engleskom jeziku i poslao sam ga na konferenciju SEIM-2017. Bio sam oduševljen kada je prihvaćen i odlučio sam dublje istražiti temu. Sam koncept nije nov - postoji od 90-ih - ali i danas pronalazi primjenu u mnogim područjima.
U drugom semestru u centru započeo sam istraživački projekt za poboljšanje algoritama za pronalaženje funkcionalnih ovisnosti. Na njemu sam radio s Nikitom Bobrovom, diplomiranim studentom na Državnom sveučilištu u Sankt Peterburgu, u JetBrains Researchu.
Računska složenost pretraživanja funkcionalnih ovisnosti
Glavni problem je računalna složenost. Broj mogućih minimalnih i netrivijalnih ovisnosti ograničen je odozgo s 
Gdje 
— broj atributa tablice. Vrijeme izvođenja algoritama ne ovisi samo o broju atributa već i o broju redaka. U 90-ima, algoritmi za otkrivanje saveznih zakona na tipičnom stolnom računalu mogli su obrađivati skupove podataka koji sadrže do 20 atributa i desetke tisuća redaka i do nekoliko sati. Moderni algoritmi koji se izvode na višejezgrenim procesorima otkrivaju ovisnosti za skupove podataka koji se sastoje od stotina atributa (do 200) i stotina tisuća redaka u približno istom vremenu. Međutim, to nije dovoljno: takvo vrijeme je neprihvatljivo za većinu stvarnih aplikacija. Stoga smo razvili pristupe za ubrzavanje postojećih algoritama.
Sheme keširanja za presjek particija
U prvom dijelu rada razvili smo sheme predmemoriranja za klasu algoritama koristeći metodu presjeka particija. Particija za atribut je skup popisa, gdje svaki popis sadrži brojeve redaka s istim vrijednostima za zadani atribut. Svaki takav popis naziva se klaster. Mnogi moderni algoritmi koriste particije kako bi utvrdili vrijedi li ovisnost, naime, pridržavaju se sljedeće leme: Ovisnost 
zadržava se ako 
... Ovdje 
Particija se označava s , a koristi se koncept veličine particije - broj klastera unutar nje. Algoritmi koji koriste particije dodaju dodatne atribute lijevoj strani ovisnosti kada se ovisnost prekrši, a zatim je ponovno izračunavaju izvođenjem operacije presjeka particije. Ova se operacija u člancima naziva specijalizacija. Međutim, primijetili smo da se particije za ovisnosti koje će se zadržati tek nakon nekoliko krugova specijalizacije mogu aktivno ponovno koristiti, što može značajno smanjiti vrijeme izvođenja algoritama, jer je operacija presjeka skupa.
Stoga smo predložili heuristiku temeljenu na Shannonovoj entropiji i Ginijevoj nesigurnosti, kao i vlastitu metriku koju nazivamo inverzna entropija. To je mala modifikacija Shannonove entropije i povećava se s povećanjem jedinstvenosti skupa podataka. Predložena heuristika je sljedeća:
Ovdje 
— stupanj jedinstvenosti nedavno izračunate particije 
I 
je medijan stupnjeva jedinstvenosti za pojedinačne atribute. Sve tri gore opisane metrike testirane su kao metrike jedinstvenosti. Također se može primijetiti da heuristika uključuje dva modifikatora. Prvi pokazuje koliko je trenutna particija blizu primarnog ključa i omogućuje veće keširanje particija dalje od kandidatskog ključa. Drugi modifikator prati zauzetost predmemorije, potičući time dodavanje više particija u predmemoriju kada je prostor dostupan. Uspješno rješavanje ovog problema omogućilo je PYRO algoritmu ubrzanje za 10-40%, ovisno o skupu podataka. Vrijedi napomenuti da je PYRO algoritam najuspješniji u ovom području.
Donja slika prikazuje rezultate primjene predložene heuristike u usporedbi s osnovnim pristupom keširanja temeljenim na bacanju novčića. X-os je logaritamska.
Alternativni način pohranjivanja particija
Zatim smo predložili alternativnu metodu za pohranu particija. Particije su skup klastera, od kojih svaki pohranjuje brojeve nabora s identičnim vrijednostima za određene atribute. Ovi klasteri mogu sadržavati duge nizove brojeva nabora, na primjer, ako su podaci u tablici uređeni. Stoga smo predložili shemu kompresije za pohranu particija, naime intervalno pohranjivanje vrijednosti u klasterima particija:
$$display$$pi(X) = {{podzagrada{1, 2, 3, 4, 5}_{Prvi~interval}, podzagrada{7, 8}_{Drugi~interval}, 10}}\ downarrow{Kompresija}\ pi(X) = {{podzagrada{$, 1, 5}_{Prvi~interval}, podzagrada{7, 8}_{Drugi~interval}, 10}}$$display$$
Ova metoda je uspjela smanjiti potrošnju memorije tijekom izvršavanja TANE algoritma za 1 do 25%. TANE algoritam je klasični algoritam za pretraživanje logičkih zona; koristi particije tijekom svog rada. Iz praktičnih razloga, TANE algoritam je odabran jer je implementacija intervalnog pohranjivanja bila znatno lakša nego, na primjer, u PYRO-u kako bi se procijenila izvedivost predloženog pristupa. Rezultati su prikazani na slici ispod. X-os je logaritamska.
Konferencija ADBIS-2019
Na temelju rezultata istraživanja objavio sam članak u rujnu 2019. Na 23. Europskoj konferenciji o napretku u bazama podataka i informacijskim sustavima (ADBIS-2019), rad je prepoznao Bernhard Thalheim, istaknuta osoba u području baza podataka. Rezultati istraživanja činili su osnovu moje disertacije za magistarski program na Fakultetu za matematiku i mehaniku Državnog sveučilišta u Sankt Peterburgu, tijekom kojeg su oba predložena pristupa (predmemorija i kompresija) implementirana u oba algoritma: TANE i PYRO. Rezultati su pokazali da su predloženi pristupi univerzalni, jer su oba algoritma pokazala značajno smanjenje potrošnje memorije i značajno smanjenje vremena izvršavanja.
Izvor: www.habr.com
