Att hitta funktionella beroenden i data används inom olika områden av dataanalys: databashantering, datarensning, databasreverse engineering och datautforskning. Vi har redan publicerat om själva beroenden Anastasia Birillo och Nikita Bobrov. Den här gången delar Anastasia, en examen från Computer Science Center i år, utvecklingen av detta arbete som en del av det forskningsarbete som hon försvarade vid centret.
Uppgiftsval
När jag studerade på CS-centret började jag studera databaser på djupet, nämligen sökandet efter funktions- och skillnadsberoenden. Det här ämnet var relaterat till ämnet för mina kurser på universitetet, så när jag arbetade med kurserna började jag läsa artiklar om olika beroenden i databaser. Jag skrev en recension av detta område - en av mina första på engelska och lämnade in den till SEIM-2017-konferensen. Jag blev väldigt glad när jag fick reda på att hon trots allt blev accepterad och bestämde mig för att fördjupa mig i ämnet. Konceptet i sig är inte nytt – det började användas redan på 90-talet, men redan nu används det inom många områden.
Under min andra termin på centret startade jag ett forskningsprojekt för att förbättra algoritmer för att hitta funktionella beroenden. Hon arbetade på det tillsammans med doktoranden Nikita Bobrov vid St. Petersburg State University vid JetBrains Research.
Beräkningskomplexitet för att söka efter funktionella beroenden
Huvudproblemet är beräkningskomplexitet. Antalet möjliga minimala och icke-triviala beroenden begränsas ovan av värdet var — Antal tabellattribut. Drifttiden för algoritmerna beror inte bara på antalet attribut, utan också på antalet rader. På 90-talet kunde federala lagars sökalgoritmer på en vanlig stationär PC bearbeta datamängder som innehåller upp till 20 attribut och tiotusentals rader på upp till flera timmar. Moderna algoritmer som körs på flerkärniga processorer upptäcker beroenden för datamängder som består av hundratals attribut (upp till 200) och hundratusentals rader på ungefär samma tid. Detta är dock inte tillräckligt: en sådan tid är oacceptabel för de flesta verkliga tillämpningar. Därför utvecklade vi metoder för att påskynda befintliga algoritmer.
Cachingscheman för partitionskorsningar
I den första delen av arbetet utvecklade vi cachingscheman för en klass av algoritmer som använder partitionsskärningsmetoden. En partition för ett attribut är en uppsättning listor, där varje lista innehåller radnummer med samma värden för ett givet attribut. Varje sådan lista kallas ett kluster. Många moderna algoritmer använder partitioner för att avgöra om ett beroende hålls eller inte, de följer nämligen lemmat: Beroende hålls om . här en partition utses och begreppet partitionsstorlek används - antalet kluster i den. Algoritmer som använder partitioner, när beroendet kränks, lägger till ytterligare attribut till vänster sida av beroendet och beräknar sedan om det och utför operationen för skärningspunkten mellan partitioner. Denna operation kallas specialisering i artiklarna. Men vi märkte att partitioner för beroenden som bara skulle behållas efter några specialiseringsrundor aktivt kan återanvändas, vilket avsevärt kan minska körtiden för algoritmerna, eftersom korsningsoperationen är dyr.
Därför föreslog vi en heuristik baserad på Shannon Entropy och Ginny Uncertainty, samt vår metrik, som vi kallade Reverse Entropy. Det är en liten modifiering av Shannon Entropy och ökar när datauppsättningens unika karaktär ökar. Den föreslagna heuristiken är följande:
Här — graden av unikhet hos den nyligen beräknade partitionen Och är medianen för graderna av unikhet för individuella attribut. Alla tre mått som beskrivs ovan testades som ett unikt mått. Du kan också märka att det finns två modifierare i heuristiken. Den första indikerar hur nära den aktuella partitionen är den primära nyckeln och låter dig cachelagra i större utsträckning de partitioner som är långt från den potentiella nyckeln. Den andra modifieraren låter dig övervaka cachebeläggning och uppmuntrar därigenom att lägga till fler partitioner till cachen om ledigt utrymme finns tillgängligt. Den framgångsrika lösningen av detta problem gjorde det möjligt för oss att snabba upp PYRO-algoritmen med 10-40%, beroende på datasetet. Det är värt att notera att PYRO-algoritmen är den mest framgångsrika inom detta område.
I figuren nedan kan du se resultaten av att tillämpa den föreslagna heuristiken jämfört med en grundläggande coin-flip-cache-metod. X-axeln är logaritmisk.
Ett alternativt sätt att lagra partitioner
Vi föreslog sedan ett alternativt sätt att lagra partitioner. Partitioner är en uppsättning kluster, som var och en lagrar antal tupler med identiska värden för vissa attribut. Dessa kluster kan innehålla långa sekvenser av tupelnummer, till exempel om data i en tabell är ordnade. Därför föreslog vi ett komprimeringsschema för att lagra partitioner, nämligen intervalllagring av värden i kluster av 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$$
Denna metod kunde minska minnesförbrukningen under driften av TANE-algoritmen från 1 till 25 %. TANE-algoritmen är en klassisk algoritm för att söka efter federala lagar; den använder partitioner under sitt arbete. Som en del av praktiken valdes TANE-algoritmen, eftersom det var mycket lättare att implementera intervalllagring i den än till exempel i PYRO för att utvärdera om det föreslagna tillvägagångssättet fungerar. De erhållna resultaten presenteras i figuren nedan. X-axeln är logaritmisk.
Konferens ADBIS-2019
Baserat på resultaten av forskningen publicerade jag i september 2019 en artikel vid den 23:e europeiska konferensen om framsteg inom databaser och informationssystem (ADBIS-2019). Under presentationen uppmärksammades arbetet av Bernhard Thalheim, en betydande person inom databaserområdet. Forskningsresultaten låg till grund för min avhandling vid masterexamen i matematik och mekanik vid St. Petersburg State University, under vilken båda föreslagna tillvägagångssätten (caching och komprimering) implementerades i båda algoritmerna: TANE och PYRO. Dessutom visade resultaten att de föreslagna tillvägagångssätten är universella, eftersom på båda algoritmerna, med båda tillvägagångssätten, observerades en signifikant minskning av minnesförbrukningen, såväl som en signifikant minskning av algoritmernas drifttid.
Källa: will.com