Funkcinių duomenų priklausomybių radimas naudojamas įvairiose duomenų analizės srityse: duomenų bazių valdyme, duomenų valyme, duomenų bazių atvirkštinėje inžinerijoje ir duomenų tyrinėjimuose. Apie pačias priklausomybes jau paskelbėme Anastasija Birillo ir Nikita Bobrovas. Šį kartą Anastasija, šių metų Kompiuterių centro absolventė, dalijasi šio darbo kūrimu, kaip centre apgynimo tiriamojo darbo dalimi.
Užduočių pasirinkimas
Studijuodamas CS centre pradėjau gilintis į duomenų bazes, būtent funkcinių ir skirtumų priklausomybių paiešką. Ši tema buvo susijusi su mano kursinių darbų tema universitete, todėl dirbdama kursinius pradėjau skaityti straipsnius apie įvairias priklausomybes duomenų bazėse. Parašiau šios srities apžvalgą – vieną pirmųjų anglų kalba ir pateikė SEIM-2017 konferencijai. Labai apsidžiaugiau, kai sužinojau, kad ji vis dėlto priimta, ir nusprendžiau pasigilinti į temą. Pati koncepcija nėra nauja – ji pradėta naudoti dar 90-aisiais, tačiau net ir dabar ji naudojama daugelyje sričių.
Per antrąjį semestrą centre pradėjau tyrimo projektą, skirtą funkcinių priklausomybių paieškos algoritmams tobulinti. Ji dirbo kartu su Sankt Peterburgo valstybinio universiteto absolventu Nikita Bobrov „JetBrains Research“.
Funkcinių priklausomybių paieškos skaičiavimo sudėtingumas
Pagrindinė problema yra skaičiavimo sudėtingumas. Galimų minimalių ir nereikšmingų priklausomybių skaičius ribojamas aukščiau verte 
Kur 
— lentelės atributų skaičius. Algoritmų veikimo laikas priklauso ne tik nuo atributų, bet ir nuo eilučių skaičiaus. Dešimtajame dešimtmetyje federalinio įstatymo paieškos algoritmai įprastame staliniame kompiuteryje galėjo apdoroti duomenų rinkinius, kuriuose buvo iki 90 atributų ir dešimtis tūkstančių eilučių per kelias valandas. Šiuolaikiniai algoritmai, veikiantys kelių branduolių procesoriuose, aptinka duomenų rinkinių, susidedančių iš šimtų atributų (iki 20) ir šimtų tūkstančių eilučių, priklausomybes maždaug per tą patį laiką. Tačiau to nepakanka: toks laikas yra nepriimtinas daugeliui realaus pasaulio programų. Todėl sukūrėme metodus, kaip pagreitinti esamus algoritmus.
Skylių sankirtų talpyklos schemos
Pirmoje darbo dalyje sukūrėme talpyklos schemas algoritmų klasei, kuriai naudojamas skaidinio susikirtimo metodas. Atributo skaidinys yra sąrašų rinkinys, kuriame kiekviename sąraše yra eilučių numeriai su tomis pačiomis tam tikro atributo reikšmėmis. Kiekvienas toks sąrašas vadinamas klasteriumi. Daugelis šiuolaikinių algoritmų naudoja skaidinius, kad nustatytų, ar priklausomybė yra, ar ne, būtent, jie laikosi lemos: Priklausomybė 
vyks jeigu 
. čia 
nurodoma skaidinys ir vartojama skaidinio dydžio sąvoka – joje esančių grupių skaičius. Algoritmai, naudojantys skaidinius, kai pažeidžiama priklausomybė, prideda papildomų atributų į kairę priklausomybės pusę, o vėliau ją perskaičiuoja, atlikdami skaidinių susikirtimo operaciją. Ši operacija vadinama specializacija straipsniuose. Tačiau pastebėjome, kad priklausomybių skaidiniai, kurie būtų išsaugoti tik po kelių specializacijos etapų, gali būti aktyviai naudojami pakartotinai, o tai gali žymiai sutrumpinti algoritmų veikimo laiką, nes susikirtimo operacija yra brangi.
Todėl pasiūlėme euristiką, pagrįstą Shannon Entropy ir Ginny Uncertainty, taip pat mūsų metriką, kurią pavadinome atvirkštine entropija. Tai nedidelis Shannon Entropy modifikavimas ir didėja didėjant duomenų rinkinio unikalumui. Siūloma euristika yra tokia:
Čia 
— neseniai apskaičiuotos skaidinio unikalumo laipsnis 
Ir 
yra atskirų požymių unikalumo laipsnių mediana. Visos trys aukščiau aprašytos metrikos buvo išbandytos kaip unikalumo metrika. Taip pat galite pastebėti, kad euristikoje yra du modifikatoriai. Pirmasis rodo, kaip arti dabartinis skaidinys yra nuo pirminio rakto, ir leidžia talpykloje didinti tuos skaidinius, kurie yra toli nuo potencialaus rakto. Antrasis modifikatorius leidžia stebėti talpyklos užimtumą ir taip skatina prie talpyklos pridėti daugiau skaidinių, jei yra laisvos vietos. Sėkmingas šios problemos sprendimas leido mums pagreitinti PYRO algoritmą 10-40%, priklausomai nuo duomenų rinkinio. Verta paminėti, kad PYRO algoritmas šioje srityje yra sėkmingiausias.
Žemiau esančiame paveikslėlyje galite pamatyti siūlomos euristikos taikymo rezultatus, palyginti su pagrindiniu monetų apvertimo talpyklos metodu. X ašis yra logaritminė.
Alternatyvus būdas saugoti pertvaras
Tada pasiūlėme alternatyvų skaidinių saugojimo būdą. Skirsniai yra grupių rinkinys, iš kurių kiekvienas saugo skaičių kortelių su identiškomis tam tikrų atributų reikšmėmis. Šiose grupėse gali būti ilgų sekų skaičių sekų, pavyzdžiui, jei lentelės duomenys yra išdėstyti tvarka. Todėl mes pasiūlėme skaidinių saugojimo glaudinimo schemą, būtent intervalinį reikšmių saugojimą skaidinių grupėse:
$$display$$pi(X) = {{apatinis skliaustas{1, 2, 3, 4, 5}_{Pirmasis intervalas}, apatinis skliaustas{7, 8}_{Antras intervalas}, 10}}\ Downarrow{ Suspaudimas} \ pi(X) = {{apatinis skliaustas{$, 1, 5}_{Pirmasis~intervalas}, apatinis skliaustas{7, 8}_{Antras~intervalas}, 10}}$$display$$
Šis metodas sugebėjo sumažinti atminties sąnaudas TANE algoritmo veikimo metu nuo 1 iki 25%. TANE algoritmas yra klasikinis federalinių įstatymų paieškos algoritmas, kuris savo darbo metu naudoja skaidinius. Praktikos metu buvo pasirinktas TANE algoritmas, nes jame buvo daug lengviau įdiegti intervalų saugyklą nei, pavyzdžiui, PYRO, siekiant įvertinti, ar siūlomas metodas veikia. Gauti rezultatai pateikti paveikslėlyje žemiau. X ašis yra logaritminė.
Konferencija ADBIS-2019
Remdamasis tyrimo rezultatais, 2019 metų rugsėjį paskelbiau straipsnį 23-iojoje Europos duomenų bazių ir informacinių sistemų pažangos konferencijoje (ADBIS-2019). Pristatymo metu darbą pažymėjo duomenų bazių srityje reikšmingas žmogus Bernhardas Thalheimas. Tyrimo rezultatai sudarė pagrindą mano baigiamajam darbui matematikos ir mechanikos magistrantūros studijose Sankt Peterburgo valstybiniame universitete, kurio metu abu pasiūlyti požiūriai (caching ir suspaudimas) buvo įgyvendinti abiejuose algoritmuose: TANE ir PYRO. Be to, rezultatai parodė, kad siūlomi metodai yra universalūs, nes abiejuose algoritmuose, naudojant abu metodus, buvo pastebėtas reikšmingas atminties suvartojimo sumažėjimas, taip pat reikšmingas algoritmų veikimo trukmės sumažėjimas.
Šaltinis: www.habr.com
