Funktionaalisten riippuvuuksien löytämistä tiedosta käytetään useilla data-analyysin osa-alueilla: tietokannan hallinnassa, tietojen puhdistuksessa, tietokannan käänteisessä suunnittelussa ja tietojen etsinnässä. Olemme jo julkaisseet itse riippuvuuksista Anastasia Birillo ja Nikita Bobrov. Tällä kertaa Tietojenkäsittelytieteen keskuksesta tänä vuonna valmistunut Anastasia jakaa tämän työn kehittämisen osana keskuksessa puolustamaansa tutkimustyötä.
Tehtävävalinta
CS-keskuksessa opiskellessani aloin tutkia tietokantoja syvällisesti, eli toiminnallisten ja eroriippuvuuksien etsimistä. Tämä aihe liittyi yliopiston työselostustyöni aiheeseen, joten työskennellessäni aloin lukemaan tietokannoista artikkeleita erilaisista riippuvuuksista. Kirjoitin arvostelun tästä alueesta - yhden ensimmäisistäni englanniksi ja toimitti sen SEIM-2017 konferenssiin. Olin erittäin iloinen, kun sain tietää, että hänet lopulta hyväksyttiin, ja päätin syventyä aiheeseen. Konsepti itsessään ei ole uusi - sitä alettiin käyttää jo 90-luvulla, mutta nykyäänkin sitä käytetään monilla alueilla.
Toisella lukukaudellani keskuksessa aloitin tutkimusprojektin parantaakseni algoritmeja toiminnallisten riippuvuuksien löytämiseksi. Hän työskenteli sen parissa yhdessä Pietarin osavaltion yliopiston jatko-opiskelijan Nikita Bobrovin kanssa JetBrains Researchissa.
Toiminnallisten riippuvuuksien etsimisen laskennallinen monimutkaisuus
Suurin ongelma on laskennan monimutkaisuus. Mahdollisten minimaalisten ja ei-triviaalien riippuvuuksien lukumäärää rajoittaa yllä oleva arvo Missä — taulukon attribuuttien lukumäärä. Algoritmien toiminta-aika ei riipu pelkästään attribuuttien, vaan myös rivien lukumäärästä. 90-luvulla liittovaltion lain hakualgoritmit tavallisessa pöytätietokoneessa pystyivät käsittelemään tietojoukkoja, jotka sisälsivät jopa 20 attribuuttia ja kymmeniä tuhansia rivejä jopa useissa tunneissa. Nykyaikaiset moniytimisillä prosessoreilla toimivat algoritmit havaitsevat sadoista attribuuteista (jopa 200) ja sadoista tuhansista riveistä koostuvien tietojoukkojen riippuvuudet suunnilleen samassa ajassa. Tämä ei kuitenkaan riitä: tällaista aikaa ei voida hyväksyä useimmissa tosielämän sovelluksissa. Siksi kehitimme lähestymistapoja olemassa olevien algoritmien nopeuttamiseksi.
Välimuistikaaviot osion risteyksissä
Työn ensimmäisessä osassa kehitimme välimuistimalleja osion leikkausmenetelmää käyttäville algoritmeille. Attribuutin osio on joukko luetteloita, joissa jokainen luettelo sisältää rivinumeroita, joilla on samat arvot tietylle attribuutille. Jokaista tällaista luetteloa kutsutaan klusteriksi. Monet nykyaikaiset algoritmit käyttävät osioita määrittääkseen, onko riippuvuus säilytetty vai ei, eli ne noudattavat lemmaa: Riippuvuus pidetään jos . täällä nimetään osio ja käytetään osion koon käsitettä - siinä olevien klustereiden lukumäärää. Osioita käyttävät algoritmit, kun riippuvuutta rikotaan, lisäävät lisämääritteitä riippuvuuden vasemmalle puolelle ja laskevat sen sitten uudelleen suorittamalla osioiden leikkaustoiminnon. Tätä toimintoa kutsutaan erikoistumiseksi artikkeleihin. Mutta huomasimme, että riippuvuuksien osiot, jotka säilytetään vasta muutaman erikoistumiskierroksen jälkeen, voidaan käyttää uudelleen aktiivisesti, mikä voi lyhentää merkittävästi algoritmien ajoaikaa, koska leikkaustoiminto on kallis.
Siksi ehdotimme heuristia, joka perustuu Shannon-entropiaan ja Ginny-epätietoisuuteen, sekä metriikkaamme, jota kutsuimme käänteiseksi entropiaksi. Se on pieni muunnos Shannon Entropysta ja kasvaa tietojoukon ainutlaatuisuuden kasvaessa. Ehdotettu heuristiikka on seuraava:
Täällä — äskettäin lasketun osion ainutlaatuisuus Ja on yksittäisten attribuuttien ainutlaatuisuusasteiden mediaani. Kaikki kolme edellä kuvattua mittaria testattiin ainutlaatuisuusmittarina. Voit myös huomata, että heuristiikassa on kaksi muuntajaa. Ensimmäinen osoittaa, kuinka lähellä nykyinen osio on ensisijaista avainta, ja antaa sinun tallentaa välimuistiin suuremmassa määrin ne osiot, jotka ovat kaukana mahdollisesta avaimesta. Toisen muokkaimen avulla voit seurata välimuistin käyttöastetta ja kannustaa siten lisäämään välimuistiin lisää osioita, jos vapaata tilaa on käytettävissä. Tämän ongelman onnistunut ratkaisu antoi meille mahdollisuuden nopeuttaa PYRO-algoritmia 10-40 % datajoukosta riippuen. On syytä huomata, että PYRO-algoritmi on menestynein tällä alueella.
Alla olevassa kuvassa näet tulokset ehdotetun heuristiikan soveltamisesta verrattuna peruskolikonheittovälimuistiin. X-akseli on logaritminen.
Vaihtoehtoinen tapa tallentaa osiot
Sitten ehdotimme vaihtoehtoista tapaa osioiden tallentamiseen. Osiot ovat joukko klustereita, joista kukin tallentaa useita monikkoja, joilla on samat arvot tietyille määritteille. Nämä klusterit voivat sisältää pitkiä monikkonumerosarjoja, esimerkiksi jos taulukon tiedot on järjestetty. Siksi ehdotimme pakkausmallia osioiden tallentamiseksi, nimittäin arvojen intervallitallennusta osioryhmissä:
$$näyttö$$pi(X) = {{aliviiva{1, 2, 3, 4, 5}_{Ensimmäinen väli}, alleviivaus{7, 8}_{Toinen väli}, 10}}\ alasaukko{ pakkaus} \ pi(X) = {{aliviiva{$, 1, 5}_{Ensimmäinen~väli}, aliviiva{7, 8}_{Second~interval}, 10}}$$näyttö$$
Tämä menetelmä pystyi vähentämään muistin kulutusta TANE-algoritmin toiminnan aikana 1 prosentista 25 prosenttiin. TANE-algoritmi on klassinen algoritmi liittovaltion lakien etsimiseen; se käyttää työssään osioita. Osaksi harjoitusta valittiin TANE-algoritmi, koska siinä oli paljon helpompi toteuttaa intervallitallennus kuin esimerkiksi PYROssa arvioidakseen, toimiiko ehdotettu lähestymistapa. Saadut tulokset on esitetty alla olevassa kuvassa. X-akseli on logaritminen.
Konferenssi ADBIS-2019
Tutkimuksen tulosten perusteella julkaisin artikkelin syyskuussa 2019 23. eurooppalaisessa tietokantojen ja tietojärjestelmien edistymistä käsittelevässä konferenssissa (ADBIS-2019). Esitelmän aikana työn huomioi tietokanta-alalla merkittävä henkilö Bernhard Thalheim. Tutkimustulokset muodostivat perustan Pietarin osavaltion yliopiston matematiikan ja mekaniikan maisterintutkinnon väitöskirjalle, jonka aikana molemmat ehdotetut lähestymistavat (välimuisti ja pakkaus) toteutettiin molemmissa algoritmeissa: TANE ja PYRO. Lisäksi tulokset osoittivat, että ehdotetut lähestymistavat ovat universaaleja, koska molemmilla algoritmeilla, molemmilla lähestymistavoilla, havaittiin merkittävä muistinkulutuksen väheneminen sekä algoritmien toiminta-ajan merkittävä väheneminen.
Lähde: will.com