Finn effektivt funksjonelle avhengigheter i databaser

Å finne funksjonelle avhengigheter i data brukes i ulike områder av dataanalyse: databaseadministrasjon, datarensing, databaseomvendt utvikling og datautforskning. Vi har allerede publisert om selve avhengighetene artikkel Anastasia Birillo og Nikita Bobrov. Denne gangen deler Anastasia, utdannet ved Datavitenskapssenteret i år, utviklingen av dette arbeidet som en del av forskningsarbeidet hun forsvarte ved senteret.

Oppgavevalg

Mens jeg studerte ved CS-senteret, begynte jeg å studere databaser i dybden, nemlig søket etter funksjonelle og forskjellsavhengigheter. Dette emnet var relatert til emnet for kursene mine på universitetet, så mens jeg jobbet med kursene begynte jeg å lese artikler om ulike avhengigheter i databaser. Jeg skrev en anmeldelse av dette området - en av mine første Artikkel på engelsk og sendte den til SEIM-2017-konferansen. Jeg ble veldig glad da jeg fant ut at hun tross alt ble akseptert, og bestemte meg for å gå dypere inn i temaet. Konseptet i seg selv er ikke nytt - det begynte å bli brukt tilbake på 90-tallet, men selv nå brukes det på mange områder.

I løpet av mitt andre semester ved senteret startet jeg et forskningsprosjekt for å forbedre algoritmer for å finne funksjonelle avhengigheter. Hun jobbet med det sammen med St. Petersburg State University-student Nikita Bobrov ved JetBrains Research.

Beregningsmessig kompleksitet ved å søke etter funksjonelle avhengigheter

Hovedproblemet er beregningsmessig kompleksitet. Antall mulige minimale og ikke-trivielle avhengigheter er begrenset ovenfor av verdien Der — antall tabellattributter. Driftstiden til algoritmene avhenger ikke bare av antall attributter, men også av antall rader. På 90-tallet kunne føderale lovsøkealgoritmer på en vanlig stasjonær PC behandle datasett som inneholder opptil 20 attributter og titusenvis av rader på opptil flere timer. Moderne algoritmer som kjører på flerkjerneprosessorer oppdager avhengigheter for datasett som består av hundrevis av attributter (opptil 200) og hundretusenvis av rader på omtrent samme tid. Dette er imidlertid ikke nok: en slik tid er uakseptabel for de fleste applikasjoner i den virkelige verden. Derfor utviklet vi tilnærminger for å øke hastigheten på eksisterende algoritmer.

Bufferskjemaer for partisjonskryss

I den første delen av arbeidet utviklet vi caching-skjemaer for en klasse algoritmer som bruker partisjonsskjæringsmetoden. En partisjon for et attributt er et sett med lister, der hver liste inneholder linjenumre med samme verdier for et gitt attributt. Hver slik liste kalles en klynge. Mange moderne algoritmer bruker partisjoner for å bestemme om en avhengighet holdes eller ikke, nemlig de følger lemmaet: Avhengighet holdt hvis . Her en partisjon er utpekt og konseptet med partisjonsstørrelse brukes - antall klynger i den. Algoritmer som bruker partisjoner, når avhengigheten er brutt, legger til flere attributter til venstre side av avhengigheten, og deretter beregner den på nytt, og utfører operasjonen for skjæringspunktet mellom partisjoner. Denne operasjonen kalles spesialisering i artiklene. Men vi la merke til at partisjoner for avhengigheter som bare vil bli beholdt etter noen få runder med spesialisering aktivt kan gjenbrukes, noe som kan redusere kjøretiden til algoritmene betydelig, siden skjæringsoperasjonen er kostbar.

Derfor foreslo vi en heuristikk basert på Shannon Entropy og Ginny Uncertainty, samt metrikken vår, som vi kalte omvendt entropi. Det er en liten modifikasjon av Shannon Entropy og øker etter hvert som datasettets unikhet øker. Den foreslåtte heuristikken er som følger:

Her — grad av unikhet til den nylig beregnede partisjonen Og er medianen av graden av unikhet for individuelle attributter. Alle de tre verdiene beskrevet ovenfor ble testet som en unikhetsmåling. Du kan også legge merke til at det er to modifikatorer i heuristikken. Den første indikerer hvor nær den gjeldende partisjonen er primærnøkkelen, og lar deg i større grad bufre de partisjonene som er langt fra den potensielle nøkkelen. Den andre modifikatoren lar deg overvåke cache-belegget og oppmuntrer dermed til å legge til flere partisjoner i cachen hvis ledig plass er tilgjengelig. Den vellykkede løsningen på dette problemet tillot oss å øke hastigheten på PYRO-algoritmen med 10-40 %, avhengig av datasettet. Det er verdt å merke seg at PYRO-algoritmen er den mest vellykkede på dette området.

I figuren nedenfor kan du se resultatene av å bruke den foreslåtte heuristikken sammenlignet med en grunnleggende coin-flip caching-tilnærming. X-aksen er logaritmisk.

En alternativ måte å lagre partisjoner på

Vi foreslo deretter en alternativ måte å lagre partisjoner på. Partisjoner er et sett med klynger, som hver lagrer antall tupler med identiske verdier for visse attributter. Disse klyngene kan inneholde lange sekvenser av tuppeltall, for eksempel hvis dataene i en tabell er ordnet. Derfor foreslo vi et komprimeringsskjema for lagring av partisjoner, nemlig intervalllagring av verdier i klynger av partisjoner:

$$display$$pi(X) = {{underbrace{1, 2, 3, 4, 5}_{First interval}, underbrace{7, 8}_{Second interval}, 10}}\ downarrow{ Compression} \ pi(X) = {{underbrace{$, 1, 5}_{First~interval}, underbrace{7, 8}_{Second~interval}, 10}}$$display$$

Denne metoden var i stand til å redusere minneforbruket under driften av TANE-algoritmen fra 1 til 25 %. TANE-algoritmen er en klassisk algoritme for å søke etter føderale lover; den bruker partisjoner under arbeidet. Som en del av praksisen ble TANE-algoritmen valgt, siden det var mye enklere å implementere intervalllagring i den enn for eksempel i PYRO for å evaluere om den foreslåtte tilnærmingen fungerer. Resultatene som er oppnådd er presentert i figuren nedenfor. X-aksen er logaritmisk.

Konferanse ADBIS-2019

Basert på resultatene av forskningen publiserte jeg i september 2019 en artikkel Smart caching for effektiv funksjonell avhengighetsoppdagelse på den 23. europeiske konferansen om fremskritt innen databaser og informasjonssystemer (ADBIS-2019). Under presentasjonen ble arbeidet bemerket av Bernhard Thalheim, en betydelig person innen databasefeltet. Forskningsresultatene dannet grunnlaget for avhandlingen min ved mastergraden i matematikk og mekanikk ved St. Petersburg State University, hvor begge foreslåtte tilnærminger (caching og komprimering) ble implementert i begge algoritmene: TANE og PYRO. Samtidig viste resultatene at de foreslåtte tilnærmingene er universelle, siden det på begge algoritmene, med begge tilnærmingene, ble observert en betydelig reduksjon i minneforbruk, samt en betydelig reduksjon i driftstiden til algoritmene.

Kilde: www.habr.com