Funktionaalisten riippuvuuksien löytämistä datasta käytetään data-analyysin eri osa-alueilla: tietokannan hallinnassa, datan puhdistuksessa, tietokannan käänteisessä suunnittelussa ja datan tutkimisessa. Olemme jo julkaisseet tietoa riippuvuuksista itsestään. Anastasia Birillo ja Nikita Bobrov. Tällä kertaa Anastasia, joka valmistui tänä vuonna Tietojenkäsittelytieteen keskuksesta, kertoo tutkimusprojektinsa kehityksestä, jota hän puolusti keskuksessa.
Tehtävävalinta
Opiskellessani CS Centerissä aloin tutkia tietokantoja syvällisesti, erityisesti etsien funktionaalisia ja differentiaalisia riippuvuuksia. Tämä aihe liittyi yliopiston kurssityöhöni, joten työskennellessäni sen parissa aloin lukea artikkeleita erilaisista tietokantojen riippuvuuksista. Kirjoitin alan katsauksen – yhden ensimmäisistäni. englanniksi ja lähetin sen SEIM-2017-konferenssiin. Olin innoissani, kun se hyväksyttiin, ja päätin perehtyä aiheeseen syvällisemmin. Käsite itsessään ei ole uusi – se on ollut olemassa 90-luvulta lähtien – mutta sitä sovelletaan edelleen monilla aloilla.
Toisella lukukaudellani keskuksessa aloitin tutkimusprojektin, jonka tavoitteena oli parantaa funktionaalisten riippuvuuksien löytämiseen tarkoitettuja algoritmeja. Työskentelin sen parissa Nikita Bobrovin, Pietarin valtionyliopiston jatko-opiskelijan, kanssa JetBrains Researchissa.
Funktionaalisten riippuvuuksien etsimisen laskennallinen monimutkaisuus
Pääongelma on laskennallinen monimutkaisuus. Mahdollisten minimaalisten ja ei-triviaalien riippuvuuksien määrää rajoittaa yllä oleva ominaisuus 
Missä 
— taulukon attribuuttien lukumäärä. Algoritmien suoritusaika riippuu paitsi attribuuttien lukumäärästä myös rivien lukumäärästä. 90-luvulla tyypillisellä pöytätietokoneella liittovaltion lain havaitsemiseen tarkoitetut algoritmit pystyivät käsittelemään jopa 20 attribuutin ja kymmeniätuhansia rivejä sisältäviä tietojoukkoja jopa useiden tuntien ajan. Nykyaikaiset moniydinprosessoreilla toimivat algoritmit havaitsevat satojen attribuuttien (jopa 200) ja satojen tuhansien rivien tietojoukkojen riippuvuuksia suunnilleen samassa ajassa. Tämä ei kuitenkaan riitä: tällainen aika on mahdotonta hyväksyä useimmissa tosielämän sovelluksissa. Siksi kehitimme lähestymistapoja olemassa olevien algoritmien nopeuttamiseksi.
Välimuistijärjestelmät osioiden leikkauspisteille
Artikkelin ensimmäisessä osassa kehitimme välimuistimenetelmiä algoritmiluokalle käyttäen osioiden leikkausmenetelmää. Attribuutin osio on joukko listoja, joissa jokainen lista sisältää rivinumerot, joilla on samat arvot tietylle attribuutille. Kutakin tällaista listaa kutsutaan klusteriksi. Monet nykyaikaiset algoritmit käyttävät osioita määrittääkseen, onko riippuvuus voimassa, eli ne noudattavat seuraavaa lemmaa: Riippuvuus 
säilyy, jos 
. täällä 
Osiota merkitään symbolilla , ja käytetään osion koon käsitettä – sen sisällä olevien klustereiden lukumäärää. Osioita käyttävät algoritmit lisäävät riippuvuuden vasemmalle puolelle lisäattribuutteja, kun riippuvuus rikotaan, ja laskevat sen sitten uudelleen suorittamalla osioiden leikkausoperaation. Tätä operaatiota kutsutaan artikkeleissa erikoistumiseksi. Olemme kuitenkin huomanneet, että riippuvuuksien osioita, jotka säilyvät vasta useiden erikoistumiskierrosten jälkeen, voidaan käyttää aktiivisesti uudelleen, mikä voi merkittävästi lyhentää algoritmien suoritusaikaa, koska leikkausoperaatio on kallis.
Siksi ehdotimme heuristiikkaa, joka perustuu Shannonin entropiaan ja Gini-epävarmuuteen sekä omaan metriikkaamme, jota kutsumme käänteiseksi entropiaksi. Se on Shannonin entropian pieni muunnelma ja kasvaa aineiston ainutlaatuisuuden kasvaessa. Ehdotettu heuristiikka on seuraava:
Täällä 
— äskettäin lasketun osion ainutlaatuisuusaste 
Ja 
on yksittäisten attribuuttien ainutlaatuisuusasteiden mediaani. Kaikkia kolmea edellä kuvattua mittaria testattiin ainutlaatuisuusmittareina. Voidaan myös huomata, että heuristiikka sisältää kaksi muokkaajaa. Ensimmäinen ilmaisee, kuinka lähellä nykyinen osio on ensisijaista avainta, ja mahdollistaa kauempana kandidaattiavaimesta olevien osioiden suuremman välimuistitallennuksen. Toinen muokkaaja valvoo välimuistin käyttöastetta, kannustaen siten lisäämään välimuistiin lisää osioita, kun tilaa on saatavilla. Tämän ongelman onnistunut ratkaiseminen mahdollisti PYRO-algoritmin nopeutumisen 10–40 % tietojoukosta riippuen. On syytä huomata, että PYRO-algoritmi on tällä alueella menestynein.
Alla oleva kuva näyttää ehdotetun heuristiikan soveltamisen tulokset verrattuna kolikonheittoihin perustuvaan perusvälimuistimenetelmään. X-akseli on logaritminen.
Vaihtoehtoinen tapa tallentaa osioita
Sitten ehdotimme vaihtoehtoista menetelmää osioiden tallentamiseen. Osiot ovat joukko klustereita, joista jokainen tallentaa tuple-numeroita, joilla on identtiset arvot tietyille ominaisuuksille. Nämä klusterit voivat sisältää pitkiä tuple-numerosarjoja, esimerkiksi jos taulukon tiedot on järjestetty. Siksi ehdotimme pakkausmenetelmää osioiden tallentamiseksi, nimittäin arvojen intervallitallennusta osioklustereihin:
$$display$$pi(X) = {{underbrace{1, 2, 3, 4, 5}_{Ensimmäinen~väli}, underbrace{7, 8}_{Toinen~väli}, 10}}\ downarrow{Pakkaus}\ pi(X) = {{underbrace{$, 1, 5}_{Ensimmäinen~väli}, underbrace{7, 8}_{Toinen~väli}, 10}}$$display$$
Tämä menetelmä pystyi vähentämään muistin kulutusta TANE-algoritmin suorituksen aikana 1–25 %. TANE-algoritmi on klassinen algoritmi loogisten vyöhykkeiden etsimiseen; se käyttää osioita toimintansa aikana. Käytännön syistä TANE-algoritmi valittiin, koska intervallitallennuksen toteuttaminen oli huomattavasti helpompaa kuin esimerkiksi PYRO:ssa ehdotetun lähestymistavan toteutettavuuden arvioimiseksi. Tulokset on esitetty alla olevassa kuvassa. X-akseli on logaritminen.
ADBIS-2019-konferenssi
Tutkimustulosten pohjalta julkaisin artikkelin syyskuussa 2019. 23. eurooppalaisessa tietokantojen ja tietojärjestelmien kehityksen konferenssissa (ADBIS-2019) työ sai tunnustusta Bernhard Thalheimilta, tietokanta-alan merkittävältä hahmolta. Tutkimustulokset muodostivat pohjan väitöskirjalleni Pietarin valtionyliopiston matematiikan ja mekaniikan tiedekunnan maisteriohjelmassa, jossa molemmat ehdotetut lähestymistavat (välimuisti ja pakkaus) toteutettiin molemmissa algoritmeissa: TANE ja PYRO. Tulokset osoittivat, että ehdotetut lähestymistavat ovat universaaleja, sillä molemmat algoritmit osoittivat merkittävää muistinkulutuksen vähenemistä ja merkittävää suoritusajan lyhenemistä.
Lähde: will.com
