Funktsionaalsete sõltuvuste leidmist andmetest kasutatakse erinevates andmeanalüüsi valdkondades: andmebaaside haldamine, andmete puhastamine, andmebaaside pöördprojekteerimine ja andmete uurimine. Oleme juba avaldanud sõltuvuste endi kohta Anastasia Birillo ja Nikita Bobrov. Sel korral jagab arvutiteaduse keskuse tänavune lõpetaja Anastasia selle töö arendust osana oma keskuses kaitstud uurimistööst.
Ülesande valik
CS keskuses õppides hakkasin andmebaasidega süvitsi tegelema, nimelt funktsionaalsete ja erinevussõltuvuste otsimisega. See teema oli seotud minu ülikooli kursusetöö teemaga, mistõttu kursusetööga tegeledes hakkasin lugema andmebaasides artikleid erinevatest sõltuvustest. Kirjutasin selle valdkonna kohta ülevaate – ühe oma esimestest inglise keeles ja esitas selle SEIM-2017 konverentsile. Mul oli väga hea meel, kui sain teada, et ta siiski aktsepteeriti, ja otsustasin teemasse süveneda. Kontseptsioon ise pole uus - seda hakati kasutama juba 90ndatel, kuid isegi praegu kasutatakse seda paljudes valdkondades.
Teisel semestril keskuses alustasin uurimisprojektiga, et täiustada funktsionaalsete sõltuvuste leidmise algoritme. Ta töötas selle kallal koos Peterburi Riikliku Ülikooli magistrandi Nikita Bobroviga JetBrains Researchis.
Funktsionaalsete sõltuvuste otsimise arvutuslik keerukus
Peamine probleem on arvutuslik keerukus. Võimalike minimaalsete ja mittetriviaalsete sõltuvuste arv on ülalpool piiratud väärtusega Kus — tabeli atribuutide arv. Algoritmide tööaeg ei sõltu ainult atribuutide arvust, vaid ka ridade arvust. 90ndatel suutsid föderaalseaduse otsingualgoritmid tavalises lauaarvutis töödelda kuni 20 atribuuti ja kümneid tuhandeid ridu sisaldavaid andmekogumeid kuni mitme tunni jooksul. Kaasaegsed mitmetuumalistel protsessoritel töötavad algoritmid tuvastavad sadadest atribuutidest (kuni 200) ja sadadest tuhandetest ridadest koosnevate andmekogumite sõltuvused ligikaudu sama aja jooksul. Sellest aga ei piisa: selline aeg on enamiku reaalmaailma rakenduste jaoks vastuvõetamatu. Seetõttu töötasime välja lähenemisviisid olemasolevate algoritmide kiirendamiseks.
Vahemälu skeemid partitsioonide ristumiskohtade jaoks
Töö esimeses osas töötasime välja vahemällu salvestamise skeemid algoritmide klassi jaoks, mis kasutavad partitsioonide lõikumise meetodit. Atribuudi partitsioon on loendite kogum, kus iga loend sisaldab antud atribuudi jaoks samade väärtustega reanumbreid. Iga sellist loendit nimetatakse klastriks. Paljud kaasaegsed algoritmid kasutavad sektsioone, et teha kindlaks, kas sõltuvus on olemas või mitte, nimelt järgivad nad lemmat: Sõltuvus peetud kui . Siin määratakse partitsioon ja kasutatakse partitsiooni suuruse mõistet - selles olevate klastrite arv. Sektsioonid kasutavad algoritmid, kui sõltuvust rikutakse, lisavad sõltuvuse vasakule küljele täiendavaid atribuute ja seejärel arvutavad selle ümber, sooritades partitsioonide ristumisoperatsiooni. Seda toimingut nimetatakse artiklites spetsialiseerumiseks. Kuid märkasime, et sõltuvuste partitsioone, mis säilivad alles pärast paari spetsialiseerumisringi, saab aktiivselt uuesti kasutada, mis võib oluliselt lühendada algoritmide tööaega, kuna ristumisoperatsioon on kallis.
Seetõttu pakkusime välja heuristika, mis põhineb Shannoni entroopial ja Ginny ebakindlusel, samuti meie mõõdikul, mida nimetasime pöördentroopiaks. See on Shannon Entropy väike modifikatsioon ja suureneb koos andmekogumi ainulaadsuse suurenemisega. Kavandatud heuristika on järgmine:
see on — hiljuti arvutatud partitsiooni unikaalsusaste Ja on üksikute atribuutide kordumatuse astme mediaan. Kõiki kolme ülalkirjeldatud mõõdikut testiti unikaalsuse mõõdikuna. Samuti võite märgata, et heuristikas on kaks modifikaatorit. Esimene näitab, kui lähedal on praegune partitsioon primaarvõtmele ja võimaldab suuremal määral vahemällu salvestada need partitsioonid, mis on potentsiaalsest võtmest kaugel. Teine modifikaator võimaldab teil jälgida vahemälu hõivatust ja julgustab seeläbi vaba ruumi olemasolul vahemällu rohkem partitsioone lisama. Selle probleemi edukas lahendamine võimaldas meil kiirendada PYRO algoritmi sõltuvalt andmekogumist 10-40%. Väärib märkimist, et PYRO algoritm on selles valdkonnas kõige edukam.
Alloleval joonisel näete pakutud heuristika rakendamise tulemusi võrreldes põhilise mündiviskamise vahemällu salvestamise lähenemisviisiga. X-telg on logaritmiline.
Alternatiivne viis vaheseinte salvestamiseks
Seejärel pakkusime välja alternatiivse viisi vaheseinte salvestamiseks. Partitsioonid on klastrite komplekt, millest igaüks salvestab teatud atribuutide jaoks identsete väärtustega korteežide arvu. Need klastrid võivad sisaldada pikki arvude jadasid, näiteks kui andmed tabelis on järjestatud. Seetõttu pakkusime välja pakkimisskeemi partitsioonide salvestamiseks, nimelt väärtuste intervallide salvestamiseks partitsioonide klastritesse:
$$display$$pi(X) = {{alussulg{1, 2, 3, 4, 5}_{Esimene intervall}, alaksulg{7, 8}_{Teine intervall}, 10}}\ allanool{ Tihendamine} \ pi(X) = {{alussulg{$, 1, 5}_{Esimene~intervall}, alaksulg{7, 8}_{Second~interval}, 10}}$$kuva$$
See meetod suutis TANE algoritmi töötamise ajal mälukulu vähendada 1-25%. TANE algoritm on klassikaline föderaalseaduste otsimise algoritm, mis kasutab oma töö käigus partitsioone. Praktika osana valiti TANE algoritm, kuna selles oli palju lihtsam rakendada intervallsalvestust kui näiteks PYRO-s, et hinnata, kas pakutud lähenemisviis töötab. Saadud tulemused on toodud alloleval joonisel. X-telg on logaritmiline.
Konverents ADBIS-2019
Uuringu tulemuste põhjal avaldasin 2019. aasta septembris artikli 23. Euroopa andmebaaside ja infosüsteemide edusammude konverentsil (ADBIS-2019). Ettekandel märkis tööd Bernhard Thalheim, andmebaaside valdkonnas märkimisväärne inimene. Uurimistulemused võtsid aluseks minu Peterburi Riikliku Ülikooli matemaatika ja mehaanika magistriõppe lõputöö, mille käigus realiseeriti mõlemad pakutud lähenemised (vahemällu salvestamine ja tihendamine) mõlemas algoritmis: TANE ja PYRO. Lisaks näitasid tulemused, et pakutud lähenemisviisid on universaalsed, kuna mõlema algoritmi puhul täheldati mõlema lähenemisviisi puhul mälutarbimise olulist vähenemist, samuti algoritmide tööaja olulist vähenemist.
Allikas: www.habr.com