Het vinden van functionele afhankelijkheden in data wordt gebruikt op verschillende gebieden van data-analyse: databasebeheer, data-opschoning, database reverse engineering en data-exploratie. Over de afhankelijkheden zelf hebben we al gepubliceerd Anastasia Birillo en Nikita Bobrov. Deze keer deelt Anastasia, dit jaar afgestudeerd aan het Computer Science Center, de ontwikkeling van dit werk als onderdeel van het onderzoekswerk dat ze in het centrum verdedigde.
Taakselectie
Tijdens mijn studie aan het CS-centrum begon ik databases diepgaand te bestuderen, namelijk de zoektocht naar functionele en verschilafhankelijkheden. Dit onderwerp hield verband met het onderwerp van mijn cursussen aan de universiteit, dus terwijl ik aan de cursussen werkte, begon ik artikelen te lezen over verschillende afhankelijkheden in databases. Ik heb een recensie over dit gebied geschreven - een van mijn eerste in het Engels en voorgelegd aan de SEIM-2017-conferentie. Ik was heel blij toen ik hoorde dat ze toch aangenomen was, en besloot me verder in het onderwerp te verdiepen. Het concept zelf is niet nieuw: het werd al in de jaren 90 gebruikt, maar zelfs nu wordt het op veel gebieden gebruikt.
Tijdens mijn tweede semester bij het centrum startte ik een onderzoeksproject om algoritmen voor het vinden van functionele afhankelijkheden te verbeteren. Ze werkte eraan samen met Nikita Bobrov, afgestudeerd aan de St. Petersburg State University bij JetBrains Research.
Computationele complexiteit van het zoeken naar functionele afhankelijkheden
Het grootste probleem is de rekencomplexiteit. Het aantal mogelijke minimale en niet-triviale afhankelijkheden wordt hierboven beperkt door de waarde Waar — aantal tabelattributen. De werkingstijd van de algoritmen hangt niet alleen af van het aantal attributen, maar ook van het aantal rijen. In de jaren negentig konden federale zoekalgoritmen op een gewone desktop-pc datasets met maximaal twintig attributen en tienduizenden rijen in enkele uren verwerken. Moderne algoritmen die op multi-coreprocessors draaien, detecteren afhankelijkheden voor datasets die uit honderden attributen (tot 90) en honderdduizenden rijen bestaan in ongeveer dezelfde tijd. Dit is echter niet genoeg: zo'n tijd is onaanvaardbaar voor de meeste toepassingen in de echte wereld. Daarom hebben we benaderingen ontwikkeld om bestaande algoritmen te versnellen.
Cachingschema's voor partitie-kruisingen
In het eerste deel van het werk hebben we caching-schema's ontwikkeld voor een klasse algoritmen die de partitie-intersectiemethode gebruiken. Een partitie voor een attribuut is een set lijsten, waarbij elke lijst regelnummers bevat met dezelfde waarden voor een bepaald attribuut. Elke dergelijke lijst wordt een cluster genoemd. Veel moderne algoritmen gebruiken partities om te bepalen of een afhankelijkheid bestaat of niet, ze houden zich namelijk aan het lemma: Afhankelijkheid gehouden als . hier er wordt een partitie aangewezen en het concept van partitiegrootte wordt gebruikt: het aantal clusters daarin. Algoritmen die partities gebruiken, voegen, wanneer de afhankelijkheid wordt geschonden, extra attributen toe aan de linkerkant van de afhankelijkheid en berekenen deze vervolgens opnieuw, waarbij de bewerking van het kruisen van partities wordt uitgevoerd. Deze bewerking wordt specialisatie in de artikelen genoemd. Maar we hebben gemerkt dat partities voor afhankelijkheden die pas na een paar specialisatierondes behouden blijven, actief kunnen worden hergebruikt, wat de looptijd van de algoritmen aanzienlijk kan verkorten, omdat de intersectie-operatie duur is.
Daarom hebben we een heuristiek voorgesteld op basis van Shannon Entropy en Ginny Uncertainty, evenals onze metriek, die we Reverse Entropy noemden. Het is een kleine wijziging van Shannon Entropy en neemt toe naarmate het unieke karakter van de dataset toeneemt. De voorgestelde heuristiek is als volgt:
Hier — mate van uniciteit van de recent berekende partitie En is de mediaan van de mate van uniciteit voor individuele attributen. Alle drie de hierboven beschreven statistieken zijn getest als een uniciteitsstatistiek. Je kunt ook opmerken dat er twee modifiers in de heuristiek zitten. De eerste geeft aan hoe dicht de huidige partitie bij de primaire sleutel ligt en stelt u in staat om de partities die ver van de potentiële sleutel verwijderd zijn, in grotere mate in de cache op te slaan. Met de tweede modifier kunt u de cachebezetting controleren en wordt het toevoegen van meer partities aan de cache gestimuleerd als er vrije ruimte beschikbaar is. Dankzij de succesvolle oplossing van dit probleem konden we het PYRO-algoritme met 10-40% versnellen, afhankelijk van de dataset. Het is vermeldenswaard dat het PYRO-algoritme op dit gebied het meest succesvol is.
In de onderstaande afbeelding kunt u de resultaten zien van het toepassen van de voorgestelde heuristiek in vergelijking met een standaard aanpak voor het opgooien van munten. De X-as is logaritmisch.
Een alternatieve manier om partities op te slaan
Vervolgens hebben we een alternatieve manier voorgesteld om partities op te slaan. Partities zijn een reeks clusters, die elk een aantal tupels opslaan met identieke waarden voor bepaalde attributen. Deze clusters kunnen lange reeksen tupelgetallen bevatten, bijvoorbeeld als de gegevens in een tabel geordend zijn. Daarom hebben we een compressieschema voorgesteld voor het opslaan van partities, namelijk intervalopslag van waarden in clusters van partities:
$$display$$pi(X) = {{onderbeugel{1, 2, 3, 4, 5}_{Eerste interval}, onderbeugel{7, 8}_{Tweede interval}, 10}}\ downarrow{ Compressie} \ pi(X) = {{onderbeugel{$, 1, 5}_{Eerste~interval}, onderbeugel{7, 8}_{Tweede~interval}, 10}}$$display$$
Deze methode kon het geheugenverbruik tijdens de werking van het TANE-algoritme verminderen van 1 naar 25%. Het TANE-algoritme is een klassiek algoritme voor het zoeken naar federale wetten; het gebruikt partities tijdens zijn werk. Als onderdeel van de praktijk werd gekozen voor het TANE-algoritme, omdat het veel eenvoudiger was om daarin intervalopslag te implementeren dan bijvoorbeeld in PYRO om te evalueren of de voorgestelde aanpak werkt. De verkregen resultaten worden weergegeven in de onderstaande figuur. De X-as is logaritmisch.
Conferentie ADBIS-2019
Op basis van de resultaten van het onderzoek heb ik in september 2019 een artikel gepubliceerd op de 23e Europese conferentie over vooruitgang in databases en informatiesystemen (ADBIS-2019). Tijdens de presentatie werd het werk opgemerkt door Bernhard Thalheim, een belangrijk persoon op het gebied van databases. De onderzoeksresultaten vormden de basis van mijn proefschrift aan de masteropleiding wiskunde en mechanica aan de St. Petersburg State University, waarin beide voorgestelde benaderingen (caching en compressie) werden geïmplementeerd in beide algoritmen: TANE en PYRO. Bovendien toonden de resultaten aan dat de voorgestelde benaderingen universeel zijn, omdat bij beide algoritmen, met beide benaderingen, een significante vermindering van het geheugenverbruik werd waargenomen, evenals een significante vermindering van de werkingstijd van de algoritmen.
Bron: www.habr.com