Efektiivne funktsionaalsete sõltuvuste otsimine andmebaasides

Funktsionaalsete seoste otsimine andmetes rakendatakse erinevates andmeanalüüsi valdkondades: andmebaaside haldamine, andmete puhastamine, andmebaaside pöördestseerimine ja andmete uurimine. Me oleme juba avaldanud teavet nende seoste kohta. artiklit Anastasia Biirsja ja Nikita Bobrov. Seekord jagab Anastasia — käesoleva aasta arvutiteaduse keskuse lõpetaja — selle töö arendamisest uurimisprojekti raames, mille ta kaitses keskuses.

Ülesande valik

Arvutiteaduse keskuses õppimise ajal hakkasin süvitsi uurima andmebaase, nimelt funktsionaalsete ja erinevate seoste otsimist. See teema oli seotud minu ülikooli kursusetööga, seega hakkasin kursusetöö kirjutamise ajal lugema artikleid erinevate andmebaaside seoste kohta. Kirjutasin sellest valdkonnast ülevaate — oma esimesi kirjutisi. artikleid Inglise keeles ja saatsin selle SEIM-2017 konverentsile. Olin väga rõõmus, kui sain teada, et see võeti siiski vastu, ja otsustasin teemaga süvitsi minna. Kontseptsioon ise ei ole uus — seda on hakatud rakendama juba 90-ndatel, kuid ka praegu leidub sellel rakendust paljudes valdkondades.

Teise semestri jooksul keskuses alustasin teadusprojekti funktsionaalsete seoste otsimise algoritmide täiustamiseks. Tegin selle kallal koostööd Peterburi Riikliku Ülikooli doktorandi Nikita Bobroviga JetBrains Researchi baasil.

Funktsionaalsete seoste leidmise arvutustöö keerukus

Peamine probleem on arvutustöö keerukus. Võimalike minimaalsete ja ebatavaliste seoste arv on piiratud ülevalt niisuguse väärtusega. , kus — tabeli atribuutide arv. Algoritmide tööaeg sõltub mitte ainult atribuutide arvust, vaid ka ridade arvust. 90-ndatel aastatel suudsid tavapärased personaalarvutid funktsionaalsete seoste otsimise algoritmid töödelda andmesarju, mis sisaldasid kuni 20 atribuuti ja kümneid tuhandeid ridasid, mitme tunni jooksul. Kaasaegsed algoritmid, mis töötavad mitme tuumaga protsessoritel, tuvastavad seosed andmesarjades, mis koosnevad sadadest atribuutidest (kuni 200) ja sadadest tuhandetest ridadest, ligikaudu sama ajaga. Siiski on see ebapiisav: selline aeg on enamikus reaalsetes rakendustes vastuvõetamatu. Seetõttu töötasime välja lähenemisviise olemasolevate algoritmide kiirendamiseks.

Partitsioonide ristumiseks mõeldud vahemälustruktuurid

Esimese töö osas töötasime välja vahemälus hoidmise skeemid algoritmide klassile, mis kasutavad partisioonide ristmeetodit. Partisioon atribuudile esindab kogumit loetelu, kus iga loetelu sisaldab ridade numbreid, mis omavad sarnaseid väärtusi antud atribuudile. Iga sellist loetelu nimetatakse klastriks. Paljud kaasaegsed algoritmid kasutavad partisioone, et määratleda, kas sõltuvus on olemas või mitte, järgides just seda lemmat: Sõltuvus on olemas, kui . Siin tähistatakse partisioon ja kasutatakse mõiste partisiooni suurus - klastrite arvu määratlemiseks. Partitsioone kasutavad algoritmid, kui sõltuvus puruneb, lisavad vasakule poole sõltuvuse täiendavad atribuudid, mille järel nad arvutavad selle üle, tehes partisioonide ristamise operatsiooni. Sellist operatsiooni nimetatakse spetsialiseerimiseks. Kuid oleme märganud, et partisioonid sõltuvuste jaoks, mis jäävad alles alles pärast mitmeid spetsialiseerimise ringe, võivad olla aktiivselt taaskasutatud, mis võib märkimisväärselt vähendada algoritmide tööaega, kuna ristamisoperatsioon on kulukas.

Seetõttu pakkusime välja heuristiku, mis põhineb Shannon'i entropial ja Ginny ebakindlusel, samuti meie meetril, mille me nimetasime Tagasi Entroopiaks. See on väike muudatus Shannon'i entropiast ja kasvab koos andmekogu ainulaadsuse suurenemisega. Pakutud heuristika näeb välja järgmine:

Siin — hiljuti arvutatud partisiooni ainulaadsuse aste , vaid on unikalsuse määra median, mis kehtib üksikutele omadustele. Unikalsuse mõõdikutena on proovitud kõiki kolme ülaltoodud mõõdikut. Samuti on märgata, et heuristikasse kuuluvad kaks modifikaatorit. Esimene näitab, kui lähedal on praegune partitsioon algsele võtmele, ja võimaldab rohkem neid partitsioone vahemälus hoida, mis on kaugel potentsiaalsest võtmest. Teine modifikaator võimaldab jälgida vahemälu kasutamist, edendades seeläbi suuremate partitsioonide lisamist vahemällu, kui ruumi on vaba. Selle ülesande edukas lahendamine võimaldas kiirendada algoritmi PYRO 10-40% sõltuvalt andmestikust. Tuleb märkida, et algoritm PYRO on selles valdkonnas kõige edukam.

Alloleval pildil on näha ettepanekut heuristika rakendamise tulemused võrreldes põhiettekandega, mis põhineb mündi viskamisel. X telg on logaritmiline.

Alternatiivne viis partitsioonide salvestamiseks

K seejärel pakkusime välja alternatiivse viisi partitsioonide salvestamiseks. Partitsioonid esindavad klastrite komplekti, milles igaühes on salvestatud tuplike numbrid, millel on sama väärtus teatud omadustes. Need klastrid võivad sisaldada pikki järjestusi tuplite numbri, näiteks kui tabelis on andmed järjestatud. Seetõttu pakkusime partitsioonide salvestamiseks tihendamisstrateegiat, nimelt väärtuste intervallide hoidmine partitsioonide klastri sees:

$$display$$pi(X) = {{underbrace{1, 2, 3, 4, 5}_{Esimene~intervall}, underbrace{7, 8}_{Teine~intervall}, 10}}\ downarrow{Tihendamine}\ pi(X) = {{underbrace{$, 1, 5}_{Esimene~intervall}, underbrace{7, 8}_{Teine~intervall}, 10}}$$display$$

See meetod suutis vähendada algoritmi TANE ajaloo käigus mälutarbimist 1 kuni 25%. Algoritm TANE on klassikaline algoritm funktsionaalsete sõltuvuste otsimiseks, mis kasutab oma töös partitsioone. Praktika raames valiti just algoritm TANE, kuna intervallide salvestamise rakendamine oli sellel palju lihtsam kui näiteks PYRO, et hinnata, kas pakutud lähenemine töötab. Saadud tulemused on esitatud alloleval pildil. X telg on logaritmiline.

Konverents ADBIS-2019

2019. aasta septembris esitasin oma uuringu tulemuste põhjal artikli Nutikas vahemälu efektiivseks funktsionaalsete sõltuvuste avastamiseks 23. Euroopa andmebaaside ja teabe süsteemide konverentsil (ADBIS-2019) märkis Bernhard Thalheim, kes on andmebaaside valdkonnas silmapaistev isik, et minu uurimistöö tulemused moodustasid aluse minu magistritööle matemaatika ja mehhaanika erialal SPbGU-s. Sellest tulenevalt viidi mõlemad pakutud lähenemisviisid (vahemälu ja kompressioon) ellu mõlemas algoritmis: TANE ja PYRO. Uuringute tulemused näitasid, et pakutud lähenemisviisid on universaalsed, kuna mõlema algoritmi puhul mõlema lähenemise korral täheldati märgatavat mälu tarbimise vähenemist ja oluliselt lühenenud algoritmide tööaega.

Allikas: habr.com