Učinkovito pronađite funkcionalne ovisnosti u bazama podataka

Pronalaženje funkcionalnih ovisnosti u podacima koristi se u različitim područjima analize podataka: upravljanje bazom podataka, čišćenje podataka, obrnuti inženjering baze podataka i istraživanje podataka. O samim ovisnostima smo već objavili članak Anastasia Birillo i Nikita Bobrov. Ovoga puta Anastasia, ovogodišnja diplomantica Centra za informatiku, dijeli razvoj ovog rada u sklopu znanstvenog rada koji je obranila u centru.

Izbor zadatka

Tijekom studija na CS centru počeo sam dublje proučavati baze podataka, odnosno traženje funkcionalnih i diferencijalnih ovisnosti. Ova tema bila je povezana s temom mog kolegija na fakultetu, pa sam tijekom rada na kolegiju počeo čitati članke o raznim ovisnostima u bazama podataka. Napisao sam recenziju ovog područja - jednu od svojih prvih članci na engleskom jeziku i prijavio ga na SEIM-2017 konferenciju. Bila sam jako sretna kad sam saznala da je ipak primljena i odlučila dublje istražiti temu. Sam koncept nije nov - počeo se koristiti još 90-ih, ali i sada se koristi u mnogim područjima.

Tijekom drugog semestra u centru započeo sam istraživački projekt za poboljšanje algoritama za pronalaženje funkcionalnih ovisnosti. Radila je na tome zajedno s diplomiranim studentom Državnog sveučilišta St. Petersburg Nikitom Bobrovom u JetBrains Researchu.

Računalna složenost traženja funkcionalnih ovisnosti

Glavni problem je složenost računanja. Broj mogućih minimalnih i netrivijalnih ovisnosti ograničen je gore navedenom vrijednošću Gdje — broj atributa tablice. Vrijeme rada algoritama ne ovisi samo o broju atributa, već i o broju redaka. U 90-ima, savezni zakonski algoritmi pretraživanja na običnom stolnom računalu mogli su obraditi skupove podataka koji sadrže do 20 atributa i desetke tisuća redaka u roku od nekoliko sati. Moderni algoritmi koji rade 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 je vrijeme neprihvatljivo za većinu aplikacija u stvarnom svijetu. Stoga smo razvili pristupe za ubrzavanje postojećih algoritama.

Sheme predmemoriranja za raskrižja particija

U prvom dijelu rada razvili smo sheme predmemoriranja za klasu algoritama koji koriste metodu particionog presjeka. Particija za atribut je skup popisa, gdje svaki popis sadrži brojeve redaka s istim vrijednostima za dati atribut. Svaki takav popis naziva se klaster. Mnogi moderni algoritmi koriste particije kako bi odredili je li ovisnost zadržana ili ne, naime, pridržavaju se leme: Ovisnost održan ako ... Ovdje označava se particija i koristi se koncept veličine particije - broj klastera u njoj. Algoritmi koji koriste particije, kada je ovisnost narušena, dodaju dodatne atribute na lijevu stranu zavisnosti, a zatim je ponovno izračunavaju, izvodeći operaciju presjeka particija. Ova se operacija u člancima naziva specijalizacija. Ali primijetili smo da se particije za ovisnosti koje bi se zadržale samo nakon nekoliko krugova specijalizacije mogu aktivno ponovno koristiti, što može znatno smanjiti vrijeme rada algoritama, budući da je operacija presjeka skupa.

Stoga smo predložili heuristiku temeljenu na Shannonovoj entropiji i Ginny nesigurnosti, kao i našu metriku koju smo nazvali Reverzna entropija. To je blaga modifikacija Shannonove entropije i povećava se kako se povećava jedinstvenost 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 metrika jedinstvenosti. Također možete primijetiti da postoje dva modifikatora u heuristici. Prvi pokazuje koliko je trenutna particija blizu primarnog ključa i omogućuje vam da u većoj mjeri predmemorišete one particije koje su daleko od potencijalnog ključa. Drugi modifikator omogućuje vam praćenje zauzetosti predmemorije i time potiče dodavanje više particija u predmemoriju ako je slobodan prostor dostupan. Uspješno rješenje ovog problema omogućilo nam je da ubrzamo PYRO algoritam za 10-40%, ovisno o skupu podataka. Vrijedno je napomenuti da je PYRO algoritam najuspješniji u ovom području.

Na donjoj slici možete vidjeti rezultate primjene predložene heuristike u usporedbi s osnovnim pristupom predmemoriranja bacanja novčića. X os je logaritamska.

Alternativni način pohranjivanja particija

Zatim smo predložili alternativni način pohranjivanja particija. Particije su skup klastera, od kojih svaki pohranjuje brojne torke s identičnim vrijednostima za određene atribute. Ovi klasteri mogu sadržavati duge sekvence tuple brojeva, na primjer ako su podaci u tablici poredani. Stoga smo predložili shemu kompresije za pohranu particija, odnosno intervalnu pohranu vrijednosti u klastere particija:

$$display$$pi(X) = {{podbrace{1, 2, 3, 4, 5}_{Prvi interval}, podbrace{7, 8}_{Drugi interval}, 10}}\ downarrow{ Kompresija} \ pi(X) = {{podbrace{$, 1, 5}_{First~interval}, underbrace{7, 8}_{Second~interval}, 10}}$$prikaz$$

Ova metoda je uspjela smanjiti potrošnju memorije tijekom rada TANE algoritma od 1 do 25%. TANE algoritam je klasičan algoritam za traženje saveznih zakona, au svom radu koristi particije. U sklopu prakse odabran je TANE algoritam, jer je u njemu bilo mnogo lakše implementirati intervalno pohranjivanje nego npr. u PYRO kako bi se ocijenilo funkcionira li predloženi pristup. Dobiveni rezultati prikazani su na donjoj slici. X os je logaritamska.

Konferencija ADBIS-2019

Na temelju rezultata istraživanja u rujnu 2019. objavio sam članak Pametno predmemoriranje za učinkovito otkrivanje funkcionalnih ovisnosti na 23. Europskoj konferenciji o napretku u bazama podataka i informacijskim sustavima (ADBIS-2019). Tijekom prezentacije rad je istaknuo Bernhard Thalheim, značajna osoba na području baza podataka. Rezultati istraživanja bili su temelj moje disertacije na magisteriju iz matematike i mehanike na St. Petersburg State University, tijekom koje su oba predložena pristupa (caching i kompresija) implementirana u oba algoritma: TANE i PYRO. Štoviše, rezultati su pokazali da su predloženi pristupi univerzalni, jer je na oba algoritma, s oba pristupa, uočeno značajno smanjenje potrošnje memorije, kao i značajno smanjenje vremena rada algoritama.

Izvor: www.habr.com