Funkcionālo atkarību atrašana datos tiek izmantota dažādās datu analīzes jomās: datubāzu pārvaldībā, datu attīrīšanā, datubāzu reversajā inženierijā un datu izpētē. Mēs jau esam publicējuši rakstus par pašām atkarībām. Anastasija Birillo un Ņikita Bobrovs. Šoreiz Anastasija, šī gada Datorzinātņu centra absolvente, dalās ar šī pētniecības projekta attīstību, kuru viņa aizstāvēja centrā.
Uzdevuma atlase
Studējot CS centrā, es sāku padziļināti pētīt datubāzes, īpaši meklējot funkcionālās un diferenciālās atkarības. Šī tēma bija saistīta ar manu universitātes studiju darbu, tāpēc, strādājot pie tā, sāku lasīt rakstus par dažādām atkarībām datubāzēs. Es uzrakstīju apskatu par šo jomu — vienu no saviem pirmajiem. angļu valodā un iesniedzu to SEIM-2017 konferencei. Es biju sajūsmā, kad tas tika pieņemts, un nolēmu iedziļināties šajā tēmā. Pati koncepcija nav jauna — tā pastāv jau kopš 90. gs. deviņdesmitajiem gadiem —, taču tā joprojām tiek pielietota daudzās jomās arī mūsdienās.
Otrajā semestrī centrā es uzsāku pētniecības projektu, lai uzlabotu algoritmus funkcionālo atkarību atrašanai. Es pie tā strādāju kopā ar Ņikitu Bobrovu, Sanktpēterburgas Valsts universitātes maģistrantu, JetBrains Research.
Funkcionālo atkarību meklēšanas skaitļošanas sarežģītība
Galvenā problēma ir skaitļošanas sarežģītība. Iespējamo minimālo un netriviālo atkarību skaits ir ierobežots no augšas ar 
Kur 
— tabulas atribūtu skaits. Algoritmu izpildes laiks ir atkarīgs ne tikai no atribūtu skaita, bet arī no rindu skaita. 20. gs. 90. gados algoritmi federālo likumu noteikšanai tipiskā galddatorā varēja apstrādāt datu kopas, kas saturēja līdz 20 atribūtiem un desmitiem tūkstošu rindu, pat vairākas stundas. Mūsdienu algoritmi, kas darbojas uz vairāku kodolu procesoriem, aptuveni vienā laikā nosaka atkarības datu kopām, kas sastāv no simtiem atribūtu (līdz 200) un simtiem tūkstošu rindu. Tomēr ar to nepietiek: šāds laiks nav pieņemams lielākajai daļai reālās pasaules lietojumprogrammu. Tāpēc mēs izstrādājām pieejas esošo algoritmu paātrināšanai.
Kešatmiņas shēmas nodalījumu krustošanai
Raksta pirmajā daļā mēs izstrādājām kešatmiņas shēmas algoritmu klasei, izmantojot nodalījumu krustošanās metodi. Atribūta nodalījums ir sarakstu kopa, kur katrs saraksts satur rindu numurus ar vienādām vērtībām dotajam atribūtam. Katru šādu sarakstu sauc par klasteri. Daudzi mūsdienu algoritmi izmanto nodalījumus, lai noteiktu, vai pastāv atkarība, proti, tie ievēro šādu lemmu: Atkarība 
tiek saglabāts, ja 
. Šeit 
Nodalījumu apzīmē ar , un tiek izmantots nodalījuma lieluma jēdziens — klasteru skaits tajā. Algoritmi, kas izmanto nodalījumus, atkarības kreisajā pusē pievieno papildu atribūtus, ja atkarība tiek pārkāpta, un pēc tam to pārrēķina, veicot nodalījuma krustošanās operāciju. Rakstos šī operācija tiek saukta par specializāciju. Tomēr mēs esam atzīmējuši, ka nodalījumus atkarībām, kas tiks saglabātas tikai pēc vairākām specializācijas kārtām, var aktīvi atkārtoti izmantot, kas var ievērojami samazināt algoritmu darbības laiku, jo krustošanās operācija ir dārga.
Tāpēc mēs piedāvājām heiristiku, kuras pamatā ir Šenona entropija un Džini nenoteiktība, kā arī mūsu pašu metrika, ko saucam par inverso entropiju. Tā ir neliela Šenona entropijas modifikācija un palielinās, palielinoties datu kopas unikalitātei. Piedāvātā heiristiku var raksturot šādi:
Šeit 
— nesen aprēķinātā sadalījuma unikalitātes pakāpe 
Un 
ir atsevišķu atribūtu unikalitātes pakāpju mediāna. Visi trīs iepriekš aprakstītie rādītāji tika pārbaudīti kā unikalitātes rādītāji. Var arī atzīmēt, ka heiristikā ir iekļauti divi modifikatori. Pirmais norāda, cik tuvu pašreizējais nodalījums atrodas primārajai atslēgai, un ļauj labāk kešatmiņā saglabāt nodalījumus, kas atrodas tālāk no kandidāta atslēgas. Otrais modifikators uzrauga kešatmiņas aizņemtību, tādējādi veicinot papildu nodalījumu pievienošanu kešatmiņai, ja ir pieejama vieta. Šīs problēmas veiksmīga risināšana ļāva PYRO algoritmam paātrināties par 10–40 % atkarībā no datu kopas. Ir vērts atzīmēt, ka PYRO algoritms šajā jomā ir visveiksmīgākais.
Zemāk redzamajā attēlā parādīti piedāvātās heiristiskās metodes piemērošanas rezultāti, salīdzinot ar pamata kešatmiņas pieeju, kuras pamatā ir monētu mešana. X ass ir logaritmiska.
Alternatīvs veids, kā uzglabāt starpsienas
Pēc tam mēs piedāvājām alternatīvu metodi nodalījumu glabāšanai. Nodalījumi ir klasteru kopums, no kuriem katrs glabā kortežu numurus ar identiskām vērtībām noteiktiem atribūtiem. Šie klasteri var saturēt garas kortežu numuru secības, piemēram, ja tabulas dati ir sakārtoti. Tāpēc mēs piedāvājām saspiešanas shēmu nodalījumu glabāšanai, proti, vērtību intervālu glabāšanu nodalījumu klasteros:
$$display$$pi(X) = {{underbrace{1, 2, 3, 4, 5}_{Pirmais~intervāls}, underbrace{7, 8}_{Otrais~intervāls}, 10}}\ downarrow{Saspiešana}\ pi(X) = {{underbrace{$, 1, 5}_{Pirmais~intervāls}, underbrace{7, 8}_{Otrais~intervāls}, 10}}$$display$$
Šī metode spēja samazināt atmiņas patēriņu TANE algoritma izpildes laikā par 1 līdz 25 %. TANE algoritms ir klasisks algoritms loģisko zonu meklēšanai; tā darbības laikā tas izmanto nodalījumus. Praktiskiem nolūkiem TANE algoritms tika izvēlēts, jo intervālu glabāšanas ieviešana bija ievērojami vienkāršāka nekā, piemēram, PYRO, lai novērtētu piedāvātās pieejas iespējamību. Rezultāti ir parādīti zemāk esošajā attēlā. X ass ir logaritmiska.
Konference ADBIS-2019
Pamatojoties uz pētījuma rezultātiem, es publicēju rakstu 2019. gada septembrī. 23. Eiropas datubāzu un informācijas sistēmu attīstības konferencē (ADBIS-2019) darbu atzinīgi novērtēja Bernhards Tālheims, ievērojama persona datubāzu jomā. Pētījuma rezultāti veidoja pamatu manai disertācijai maģistra programmā Sanktpēterburgas Valsts universitātes Matemātikas un mehānikas fakultātē, kuras laikā abas piedāvātās pieejas (kešatmiņa un saspiešana) tika ieviestas abos algoritmos: TANE un PYRO. Rezultāti parādīja, ka piedāvātās pieejas ir universālas, jo abi algoritmi demonstrēja ievērojamu atmiņas patēriņa samazinājumu un ievērojamu izpildes laika samazinājumu.
Avots: www.habr.com
