Hľadanie funkčných závislostí v dátach sa používa v rôznych oblastiach analýzy dát: správa databáz, čistenie dát, reverzné inžinierstvo databáz a prieskum dát. O samotných závislostiach sme už publikovali Anastasia Birillo a Nikita Bobrov. Anastasia, tohtoročná absolventka Centra výpočtovej techniky, tentoraz zdieľa vývoj tejto práce v rámci výskumnej práce, ktorú v centre obhájila.
Výber úlohy
Počas štúdia v CS centre som začal do hĺbky študovať databázy, konkrétne hľadanie funkčných a rozdielových závislostí. Táto téma súvisela s témou mojej ročníkovej práce na univerzite, a tak som pri práci na kurze začal čítať články o rôznych závislostiach v databázach. Napísal som recenziu tejto oblasti - jednu z mojich prvých v angličtine a predložili ho na konferenciu SEIM-2017. Bol som veľmi rád, keď som zistil, že ju predsa len prijali, a rozhodol som sa téme hlbšie venovať. Samotný koncept nie je nový – začal sa používať už v 90-tych rokoch, no dodnes sa používa v mnohých oblastiach.
Počas môjho druhého semestra v centre som začal výskumný projekt na zlepšenie algoritmov na hľadanie funkčných závislostí. Pracovala na ňom spolu s postgraduálnym študentom Petrohradskej štátnej univerzity Nikitom Bobrovom z JetBrains Research.
Výpočtová náročnosť hľadania funkčných závislostí
Hlavným problémom je výpočtová náročnosť. Počet možných minimálnych a netriviálnych závislostí je limitovaný vyššie hodnotou Kde — počet atribútov tabuľky. Prevádzkový čas algoritmov závisí nielen od počtu atribútov, ale aj od počtu riadkov. V 90-tych rokoch mohli vyhľadávacie algoritmy podľa federálnych zákonov na bežnom stolnom počítači spracovať súbory údajov obsahujúce až 20 atribútov a desiatky tisíc riadkov až za niekoľko hodín. Moderné algoritmy bežiace na viacjadrových procesoroch zisťujú závislosti pre množiny údajov pozostávajúce zo stoviek atribútov (až 200) a stoviek tisícov riadkov približne v rovnakom čase. To však nestačí: takýto čas je pre väčšinu reálnych aplikácií neprijateľný. Preto sme vyvinuli prístupy na urýchlenie existujúcich algoritmov.
Schémy ukladania do vyrovnávacej pamäte pre priesečníky oddielov
V prvej časti práce sme vyvinuli schémy ukladania do vyrovnávacej pamäte pre triedu algoritmov, ktoré využívajú metódu prieniku oddielov. Oddiel pre atribút je množina zoznamov, kde každý zoznam obsahuje čísla riadkov s rovnakými hodnotami pre daný atribút. Každý takýto zoznam sa nazýva klaster. Mnoho moderných algoritmov používa oddiely na určenie, či je závislosť zachovaná alebo nie, konkrétne dodržiavajú lemu: závislosť držané ak ... Tu je určený oddiel a používa sa pojem veľkosť oddielu - počet klastrov v ňom. Algoritmy, ktoré používajú oddiely, keď je závislosť narušená, pridajú ďalšie atribúty na ľavú stranu závislosti a potom ju prepočítajú, pričom vykonajú operáciu priesečníka oddielov. Táto operácia sa v článkoch nazýva špecializácia. Všimli sme si však, že oddiely pre závislosti, ktoré by sa zachovali až po niekoľkých kolách špecializácie, sa dajú aktívne znova použiť, čo môže výrazne skrátiť čas chodu algoritmov, pretože operácia križovatiek je drahá.
Preto sme navrhli heuristiku založenú na Shannonovej entropii a neistote Ginny, ako aj na našej metrike, ktorú sme nazvali Reverzná entropia. Je to mierna modifikácia Shannon Entropy a zvyšuje sa so zvyšujúcou sa jedinečnosťou súboru údajov. Navrhovaná heuristika je takáto:
Tu — stupeň jedinečnosti nedávno vypočítanej oblasti A je medián stupňov jedinečnosti pre jednotlivé atribúty. Všetky tri metriky opísané vyššie boli testované ako metrika jedinečnosti. Môžete si tiež všimnúť, že v heuristike sú dva modifikátory. Prvý ukazuje, ako blízko je aktuálny oddiel k primárnemu kľúču a umožňuje vám ukladať do vyrovnávacej pamäte vo väčšej miere tie oddiely, ktoré sú ďaleko od potenciálneho kľúča. Druhý modifikátor vám umožňuje sledovať obsadenosť vyrovnávacej pamäte a tým podporuje pridávanie ďalších oddielov do vyrovnávacej pamäte, ak je k dispozícii voľné miesto. Úspešné vyriešenie tohto problému nám umožnilo zrýchliť PYRO algoritmus o 10-40% v závislosti od súboru údajov. Stojí za zmienku, že PYRO algoritmus je v tejto oblasti najúspešnejší.
Na obrázku nižšie môžete vidieť výsledky použitia navrhovanej heuristiky v porovnaní so základným prístupom ukladania mincí do vyrovnávacej pamäte. Os X je logaritmická.
Alternatívny spôsob ukladania oddielov
Potom sme navrhli alternatívny spôsob ukladania oddielov. Oddiely sú množinou klastrov, z ktorých každý ukladá počet n-tic s rovnakými hodnotami pre určité atribúty. Tieto klastre môžu obsahovať dlhé sekvencie n-ticových čísel, napríklad ak sú údaje v tabuľke usporiadané. Preto sme navrhli schému kompresie na ukladanie oddielov, konkrétne intervalové ukladanie hodnôt do zhlukov oddielov:
$$display$$pi(X) = {{zátvorka{1, 2, 3, 4, 5}_{Prvý interval}, zátvorka{7, 8}_{druhý interval}, 10}}\ šípka nadol{ Kompresia} \ pi(X) = {{zátvorka{$, 1, 5}_{prvý~interval}, zátvorka{7, 8}_{druhý~interval}, 10}}$$zobraziť$$
Táto metóda dokázala znížiť spotrebu pamäte počas prevádzky algoritmu TANE z 1 na 25%. Algoritmus TANE je klasický algoritmus na vyhľadávanie federálnych zákonov, pri svojej práci využíva partície. V rámci praxe bol zvolený algoritmus TANE, keďže v ňom bolo oveľa jednoduchšie implementovať intervalové ukladanie ako napríklad v PYRO, aby bolo možné vyhodnotiť, či navrhovaný prístup funguje. Získané výsledky sú uvedené na obrázku nižšie. Os X je logaritmická.
Konferencia ADBIS-2019
Na základe výsledkov výskumu som v septembri 2019 publikoval článok na 23. európskej konferencii o pokroku v databázach a informačných systémoch (ADBIS-2019). Počas prezentácie práce poznamenal Bernhard Thalheim, významná osobnosť v oblasti databáz. Výsledky výskumu tvorili základ mojej dizertačnej práce na magisterskom stupni matematiky a mechaniky na Štátnej univerzite v Petrohrade, počas ktorej boli implementované oba navrhované prístupy (cachovanie a kompresia) v oboch algoritmoch: TANE a PYRO. Okrem toho výsledky ukázali, že navrhované prístupy sú univerzálne, keďže na oboch algoritmoch, pri oboch prístupoch, bolo pozorované výrazné zníženie spotreby pamäte, ako aj výrazné skrátenie prevádzkového času algoritmov.
Zdroj: hab.com