Găsirea dependențelor funcționale în date este utilizată în diferite domenii ale analizei datelor: managementul bazei de date, curățarea datelor, inginerie inversă a bazei de date și explorarea datelor. Am publicat deja despre dependențe în sine Anastasia Birillo și Nikita Bobrov. De data aceasta, Anastasia, absolventă a Centrului de Informatică din acest an, împărtășește dezvoltarea acestei lucrări ca parte a lucrării de cercetare pe care a susținut-o la centru.
Selectarea sarcinilor
În timp ce studiam la centrul CS, am început să studiez în profunzime bazele de date, și anume căutarea dependențelor funcționale și diferențiale. Acest subiect era legat de subiectul cursului meu de la universitate, așa că în timp ce lucram la curs, am început să citesc articole despre diferite dependențe din bazele de date. Am scris o recenzie a acestei zone - una dintre primele mele în limba engleză și l-a depus la conferința SEIM-2017. Am fost foarte fericit când am aflat că ea a fost acceptată până la urmă și am decis să aprofundez subiectul. Conceptul în sine nu este nou - a început să fie folosit încă din anii 90, dar chiar și acum este folosit în multe domenii.
În timpul celui de-al doilea semestru la centru, am început un proiect de cercetare pentru a îmbunătăți algoritmii pentru găsirea dependențelor funcționale. Ea a lucrat la el împreună cu studentul absolvent al Universității de Stat din Sankt Petersburg, Nikita Bobrov, la JetBrains Research.
Complexitatea computațională a căutării dependențelor funcționale
Problema principală este complexitatea de calcul. Numărul de dependențe minime și netriviale posibile este limitat mai sus de valoare 
Unde 
— numărul de atribute ale tabelului. Timpul de funcționare al algoritmilor depinde nu numai de numărul de atribute, ci și de numărul de rânduri. În anii '90, algoritmii de căutare a legilor federale de pe un computer desktop obișnuit puteau procesa seturi de date care conțineau până la 20 de atribute și zeci de mii de rânduri în până la câteva ore. Algoritmii moderni care rulează pe procesoare multi-core detectează dependențe pentru seturile de date constând din sute de atribute (până la 200) și sute de mii de rânduri aproximativ în același timp. Cu toate acestea, acest lucru nu este suficient: un astfel de timp este inacceptabil pentru majoritatea aplicațiilor din lumea reală. Prin urmare, am dezvoltat abordări pentru a accelera algoritmii existenți.
Scheme de stocare în cache pentru intersecțiile partițiilor
În prima parte a lucrării, am dezvoltat scheme de stocare în cache pentru o clasă de algoritmi care utilizează metoda de intersecție a partițiilor. O partiție pentru un atribut este un set de liste, în care fiecare listă conține numere de linie cu aceleași valori pentru un anumit atribut. Fiecare astfel de listă se numește cluster. Mulți algoritmi moderni folosesc partiții pentru a determina dacă o dependență este deținută sau nu, și anume, aderă la lema: Dependență 
ţinut dacă 
... Aici 
o partiție este desemnată și se utilizează conceptul de dimensiune a partiției - numărul de clustere din ea. Algoritmii care folosesc partiții, atunci când dependența este încălcată, adaugă atribute suplimentare în partea stângă a dependenței și apoi le recalculează, efectuând operația de intersecție a partițiilor. Această operațiune se numește specializare în articole. Dar am observat că partițiile pentru dependențe care ar fi reținute doar după câteva runde de specializare pot fi reutilizate în mod activ, ceea ce poate reduce semnificativ timpul de rulare a algoritmilor, deoarece operația de intersecție este costisitoare.
Prin urmare, am propus o euristică bazată pe Shannon Entropy și Ginny Uncertainty, precum și metrica noastră, pe care am numit-o Reverse Entropie. Este o modificare ușoară a Shannon Entropy și crește pe măsură ce unicitatea setului de date crește. Euristica propusă este următoarea:
Aici 
— gradul de unicitate al partiției recent calculate 
Și 
este mediana gradelor de unicitate pentru atributele individuale. Toate cele trei valori descrise mai sus au fost testate ca măsură de unicitate. De asemenea, puteți observa că există doi modificatori în euristică. Primul indică cât de aproape este partiția curentă de cheia primară și vă permite să stocați în cache într-o măsură mai mare acele partiții care sunt departe de cheia potențială. Al doilea modificator vă permite să monitorizați ocuparea memoriei cache și, prin urmare, încurajează adăugarea mai multor partiții în cache dacă spațiul liber este disponibil. Rezolvarea cu succes a acestei probleme ne-a permis să accelerăm algoritmul PYRO cu 10-40%, în funcție de setul de date. Este de remarcat faptul că algoritmul PYRO este cel mai de succes în acest domeniu.
În figura de mai jos puteți vedea rezultatele aplicării euristicii propuse în comparație cu o abordare de bază a stocării în cache a monedelor. Axa X este logaritmică.
O modalitate alternativă de stocare a partițiilor
Am propus apoi o modalitate alternativă de stocare a partițiilor. Partițiile sunt un set de clustere, fiecare dintre ele stochează numere de tupluri cu valori identice pentru anumite atribute. Aceste grupuri pot conține secvențe lungi de numere tuple, de exemplu dacă datele dintr-un tabel sunt ordonate. Prin urmare, am propus o schemă de compresie pentru stocarea partițiilor, și anume stocarea pe intervale a valorilor în clustere de partiții:
$$display$$pi(X) = {{acodată{1, 2, 3, 4, 5}_{Primul interval}, acodată{7, 8}_{Al doilea interval}, 10}}\ în jos{ Compresie} \ pi(X) = {{acodată{$, 1, 5}_{Primul ~interval}, acodată{7, 8}_{Al doilea ~interval}, 10}}$$afișare$$
Această metodă a reușit să reducă consumul de memorie în timpul funcționării algoritmului TANE de la 1 la 25%. Algoritmul TANE este un algoritm clasic pentru căutarea legilor federale, folosește partiții în timpul lucrului său. Ca parte a practicii, a fost ales algoritmul TANE, deoarece a fost mult mai ușor de implementat stocarea intervalului în acesta decât, de exemplu, în PYRO pentru a evalua dacă abordarea propusă funcționează. Rezultatele obţinute sunt prezentate în figura de mai jos. Axa X este logaritmică.
Conferința ADBIS-2019
Pe baza rezultatelor cercetării, în septembrie 2019 am publicat un articol la cea de-a 23-a Conferință europeană privind progresele în baze de date și sisteme informaționale (ADBIS-2019). În cadrul prezentării, lucrarea a fost remarcată de Bernhard Thalheim, o persoană semnificativă în domeniul bazelor de date. Rezultatele cercetării au stat la baza tezei mele la masterul în matematică și mecanică de la Universitatea de Stat din Sankt Petersburg, timp în care ambele abordări propuse (caching și compresie) au fost implementate în ambii algoritmi: TANE și PYRO. Mai mult, rezultatele au arătat că abordările propuse sunt universale, întrucât pe ambii algoritmi, cu ambele abordări, s-a observat o reducere semnificativă a consumului de memorie, precum și o reducere semnificativă a timpului de operare al algoritmilor.
Sursa: www.habr.com
