At finde funktionelle afhængigheder i data bruges inden for forskellige områder af dataanalyse: databasestyring, datarensning, database reverse engineering og dataudforskning. Vi har allerede offentliggjort om selve afhængighederne Anastasia Birillo og Nikita Bobrov. Denne gang deler Anastasia, en kandidat fra Computer Science Center i år, udviklingen af dette arbejde som en del af det forskningsarbejde, hun forsvarede på centret.
Valg af opgave
Mens jeg studerede på CS-centret, begyndte jeg at studere databaser i dybden, nemlig søgen efter funktionelle og forskelsafhængige afhængigheder. Dette emne var relateret til emnet for mine kurser på universitetet, så mens jeg arbejdede med kurserne, begyndte jeg at læse artikler om forskellige afhængigheder i databaser. Jeg skrev en anmeldelse af dette område - en af mine første på engelsk og indsendte den til SEIM-2017-konferencen. Jeg blev meget glad, da jeg fandt ud af, at hun trods alt blev accepteret, og besluttede mig for at dykke dybere ned i emnet. Konceptet i sig selv er ikke nyt – det begyndte at blive brugt tilbage i 90'erne, men allerede nu bruges det på mange områder.
I løbet af mit andet semester på centret startede jeg et forskningsprojekt for at forbedre algoritmer til at finde funktionelle afhængigheder. Hun arbejdede på det sammen med St. Petersburg State University kandidatstuderende Nikita Bobrov ved JetBrains Research.
Beregningsmæssig kompleksitet ved at søge efter funktionelle afhængigheder
Hovedproblemet er beregningsmæssig kompleksitet. Antallet af mulige minimale og ikke-trivielle afhængigheder er begrænset ovenfor af værdien Hvor — antal tabelattributter. Algoritmernes driftstid afhænger ikke kun af antallet af attributter, men også af antallet af rækker. I 90'erne kunne føderal lov søgealgoritmer på en almindelig stationær pc behandle datasæt indeholdende op til 20 attributter og titusindvis af rækker på op til flere timer. Moderne algoritmer, der kører på multi-core processorer, registrerer afhængigheder for datasæt bestående af hundredvis af attributter (op til 200) og hundredtusindvis af rækker på omtrent samme tid. Dette er dog ikke nok: sådan et tidspunkt er uacceptabelt for de fleste applikationer i den virkelige verden. Derfor udviklede vi tilgange til at fremskynde eksisterende algoritmer.
Caching-skemaer for partitionskrydsninger
I den første del af arbejdet udviklede vi caching-skemaer til en klasse af algoritmer, der bruger partitionsskæringsmetoden. En partition for en attribut er et sæt lister, hvor hver liste indeholder linjenumre med samme værdier for en given attribut. Hver sådan liste kaldes en klynge. Mange moderne algoritmer bruger partitioner til at bestemme, om en afhængighed holdes eller ej, nemlig de overholder lemmaet: Afhængighed afholdt hvis . her en partition er udpeget, og begrebet partitionsstørrelse bruges - antallet af klynger i den. Algoritmer, der bruger partitioner, når afhængigheden er overtrådt, tilføjer yderligere attributter til venstre side af afhængigheden, og genberegner den derefter, udfører operationen af skæringspunktet mellem partitioner. Denne operation kaldes specialisering i artiklerne. Men vi har bemærket, at partitioner for afhængigheder, der først vil blive bibeholdt efter et par runder med specialisering, aktivt kan genbruges, hvilket kan reducere algoritmernes køretid betydeligt, da skæringsoperationen er dyr.
Derfor foreslog vi en heuristik baseret på Shannon Entropy og Ginny Uncertainty, samt vores metrik, som vi kaldte Reverse Entropy. Det er en lille ændring af Shannon Entropy og øges, efterhånden som datasættets unikke karakter øges. Den foreslåede heuristik er som følger:
Her — graden af unikhed af den nyligt beregnede partition Og er medianen af graderne af unikhed for individuelle egenskaber. Alle tre metrics beskrevet ovenfor blev testet som en unikhedsmetrik. Du kan også bemærke, at der er to modifikatorer i heuristikken. Den første angiver, hvor tæt den aktuelle partition er på den primære nøgle og giver dig mulighed for i højere grad at cache de partitioner, der er langt fra den potentielle nøgle. Den anden modifikator giver dig mulighed for at overvåge cachebelægning og opfordrer derved til at tilføje flere partitioner til cachen, hvis der er ledig plads. Den vellykkede løsning af dette problem tillod os at fremskynde PYRO-algoritmen med 10-40%, afhængigt af datasættet. Det er værd at bemærke, at PYRO-algoritmen er den mest succesrige på dette område.
I figuren nedenfor kan du se resultaterne af at anvende den foreslåede heuristik sammenlignet med en grundlæggende mønt-flip-cache-tilgang. X-aksen er logaritmisk.
En alternativ måde at gemme partitioner på
Vi foreslog derefter en alternativ måde at gemme partitioner på. Partitioner er et sæt af klynger, som hver lagrer antallet af tuples med identiske værdier for visse attributter. Disse klynger kan indeholde lange sekvenser af tupeltal, for eksempel hvis dataene i en tabel er ordnet. Derfor foreslog vi et komprimeringsskema til lagring af partitioner, nemlig intervallagring af værdier i klynger af partitioner:
$$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 metode var i stand til at reducere hukommelsesforbruget under driften af TANE-algoritmen fra 1 til 25%. TANE-algoritmen er en klassisk algoritme til at søge efter føderale love; den bruger partitioner under sit arbejde. Som en del af praksis blev TANE-algoritmen valgt, da det var meget nemmere at implementere intervallagring i den end f.eks. i PYRO for at vurdere om den foreslåede tilgang virker. De opnåede resultater er vist i figuren nedenfor. X-aksen er logaritmisk.
Konference ADBIS-2019
Baseret på resultaterne af forskningen publicerede jeg i september 2019 en artikel på den 23. europæiske konference om fremskridt inden for databaser og informationssystemer (ADBIS-2019). Under præsentationen blev arbejdet noteret af Bernhard Thalheim, en betydningsfuld person inden for databaser. Forskningsresultaterne dannede grundlag for min afhandling på kandidatgraden i matematik og mekanik ved St. Petersburg State University, hvor begge foreslåede tilgange (caching og komprimering) blev implementeret i begge algoritmer: TANE og PYRO. Desuden viste resultaterne, at de foreslåede tilgange er universelle, da der på begge algoritmer, med begge tilgange, blev observeret en signifikant reduktion i hukommelsesforbrug, samt en signifikant reduktion i algoritmernes driftstid.
Kilde: www.habr.com