Pronalaženje funkcionalnih zavisnosti u podacima koristi se u različitim oblastima analize podataka: upravljanje bazom podataka, čišćenje podataka, obrnuti inženjering baze podataka i istraživanje podataka. O samim zavisnostima smo već objavili Anastasia Birillo i Nikita Bobrov. Ovog puta Anastasija, koja je ove godine diplomirala na Centru za računarske nauke, dijeli razvoj ovog rada u okviru istraživačkog rada koji je odbranila u centru.
Izbor zadataka
Dok sam studirao u CS centru, počeo sam dublje da proučavam baze podataka, odnosno potragu za funkcionalnim i razlikama zavisnosti. Ova tema je bila vezana za temu mog rada na fakultetu, tako da sam, radeći na kursu, počeo da čitam članke o raznim zavisnostima u bazama podataka. Napisao sam recenziju ove oblasti – jednu od mojih prvih na engleskom jeziku i predao na konferenciju SEIM-2017. Bio sam jako sretan kada sam saznao da je ipak prihvaćena i odlučio da se dublje udubim u temu. Sam koncept nije nov - počeo se koristiti još 90-ih godina, ali se i sada koristi u mnogim područjima.
Tokom mog drugog semestra u centru, započeo sam istraživački projekat za poboljšanje algoritama za pronalaženje funkcionalnih zavisnosti. Radila je na tome zajedno sa diplomiranim studentom St. Petersburg State University Nikitom Bobrovom u JetBrains Research.
Računska složenost traženja funkcionalnih zavisnosti
Glavni problem je računska složenost. Broj mogućih minimalnih i netrivijalnih zavisnosti iznad je ograničen vrednošću gde — broj atributa tabele. Vrijeme rada algoritama ne zavisi samo od broja atributa, već i od broja redova. Tokom 90-ih, algoritmi za pretraživanje saveznog zakona na običnom desktop računaru mogli su da obrađuju skupove podataka koji sadrže do 20 atributa i desetine hiljada redova u roku od nekoliko sati. Moderni algoritmi koji rade na višejezgarnim procesorima otkrivaju zavisnosti za skupove podataka koji se sastoje od stotina atributa (do 200) i stotina hiljada redova u približno istom vremenu. Međutim, to nije dovoljno: takvo vrijeme je neprihvatljivo za većinu primjena u stvarnom svijetu. Stoga smo razvili pristupe za ubrzavanje postojećih algoritama.
Šeme keširanja za raskrsnice particija
U prvom dijelu rada razvili smo šeme keširanja za klasu algoritama koji koriste metodu presjeka particija. Particija za atribut je skup lista, gdje svaka lista sadrži brojeve redova s istim vrijednostima za dati atribut. Svaka takva lista naziva se klaster. Mnogi moderni algoritmi koriste particije da odrede da li se zavisnost drži ili ne, naime, pridržavaju se leme: Zavisnost održan ako . Evo određena je particija i koristi se koncept veličine particije - broja klastera u njoj. Algoritmi koji koriste particije, kada je zavisnost narušena, dodaju dodatne atribute na lijevu stranu zavisnosti, a zatim je ponovo izračunavaju, izvodeći operaciju ukrštanja particija. Ova operacija se naziva specijalizacija u člancima. Ali primijetili smo da se particije za ovisnosti koje bi se zadržale tek nakon nekoliko rundi specijalizacije mogu aktivno ponovo koristiti, što može značajno smanjiti vrijeme rada algoritama, budući da je operacija ukrštanja skupa.
Stoga smo predložili heuristiku baziranu na Shanon Entropy i Ginny Uncertainty, kao i našu metriku, koju smo nazvali Reverzna Entropija. To je mala modifikacija Šenonove entropije i raste kako se povećava jedinstvenost skupa podataka. Predložena heuristika je sljedeća:
to je — stepen jedinstvenosti nedavno izračunate particije i je medijan stepena 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 označava koliko je trenutna particija bliska primarnom ključu i omogućava vam da u većoj mjeri keširate one particije koje su daleko od potencijalnog ključa. Drugi modifikator vam omogućava da nadgledate zauzetost keša i na taj način potiče dodavanje više particija u keš ako je slobodan prostor dostupan. Uspješno rješenje ovog problema nam je omogućilo da ubrzamo PYRO algoritam za 10-40%, ovisno o skupu podataka. Vrijedi napomenuti da je PYRO algoritam najuspješniji u ovoj oblasti.
Na donjoj slici možete vidjeti rezultate primjene predložene heuristike u poređenju sa osnovnim pristupom keširanja za bacanje novčića. X osa je logaritamska.
Alternativni način pohranjivanja particija
Zatim smo predložili alternativni način pohranjivanja particija. Particije su skup klastera, od kojih svaki pohranjuje brojeve torki sa identičnim vrijednostima za određene atribute. Ovi klasteri mogu sadržavati duge nizove brojeva tuple, na primjer ako su podaci u tablici poređani. Stoga smo predložili šemu kompresije za pohranjivanje particija, odnosno intervalno skladištenje vrijednosti u klasterima particija:
$$display$$pi(X) = {{underbrace{1, 2, 3, 4, 5}_{Prvi interval}, underbrace{7, 8}_{Drugi interval}, 10}}\ downarrow{ Compression} \ pi(X) = {{underbrace{$, 1, 5}_{Prvi~interval}, underbrace{7, 8}_{Drugi~interval}, 10}}$$display$$
Ova metoda je uspjela smanjiti potrošnju memorije tokom rada TANE algoritma sa 1 na 25%. TANE algoritam je klasičan algoritam za traženje federalnih zakona, koji koristi particije tokom svog rada. Kao dio prakse odabran je TANE algoritam, jer je u njemu bilo mnogo lakše implementirati intervalno skladištenje nego, na primjer, u PYRO kako bi se ocijenilo da li predloženi pristup funkcionira. Dobijeni rezultati prikazani su na donjoj slici. X osa je logaritamska.
Konferencija ADBIS-2019
Na osnovu rezultata istraživanja, u septembru 2019. objavio sam članak na 23. Evropskoj konferenciji o napretku u bazama podataka i informacionim sistemima (ADBIS-2019). Tokom prezentacije, rad je zapazio Bernhard Thalheim, značajna ličnost u oblasti baza podataka. Rezultati istraživanja činili su osnovu moje disertacije na master studijama matematike i mehanike na Državnom univerzitetu u Sankt Peterburgu, tokom koje su oba predložena pristupa (keširanje i kompresija) implementirana u oba algoritma: TANE i PYRO. Štaviše, rezultati su pokazali da su predloženi pristupi univerzalni, jer je na oba algoritma, kod oba pristupa, uočeno značajno smanjenje potrošnje memorije, kao i značajno smanjenje vremena rada algoritama.
izvor: www.habr.com