Efektivně najděte funkční závislosti v databázích

Hledání funkčních závislostí v datech se používá v různých oblastech analýzy dat: správa databází, čištění dat, reverzní inženýrství databází a průzkum dat. O samotných závislostech jsme již publikovali Článek Anastasia Birillo a Nikita Bobrov. Anastasia, letošní absolventka Centra výpočetní techniky, tentokrát sdílí vývoj této práce v rámci výzkumné práce, kterou v centru obhájila.

Výběr úkolu

Při studiu na CS centru jsem začal do hloubky studovat databáze, konkrétně hledání funkčních a rozdílových závislostí. Toto téma souviselo s tématem mé ročníkové práce na univerzitě, a tak jsem při práci na kurzu začal číst články o různých závislostech v databázích. Napsal jsem recenzi této oblasti - jednu z mých prvních články v angličtině a předložil jej na konferenci SEIM-2017. Byla jsem moc ráda, když jsem zjistila, že byla přeci jen přijata, a rozhodla se pustit do tématu hlouběji. Samotný koncept není nový – začal se používat již v 90. letech, ale dodnes se používá v mnoha oblastech.

Během mého druhého semestru v centru jsem zahájil výzkumný projekt na zlepšení algoritmů pro hledání funkčních závislostí. Pracovala na něm společně s postgraduálním studentem St. Petersburg State University Nikitou Bobrovem z JetBrains Research.

Výpočetní náročnost hledání funkčních závislostí

Hlavním problémem je výpočetní náročnost. Počet možných minimálních a netriviálních závislostí je omezen výše hodnotou Kde — počet atributů tabulky. Provozní doba algoritmů závisí nejen na počtu atributů, ale také na počtu řádků. V 90. letech dokázaly federální zákonné vyhledávací algoritmy na běžném stolním počítači zpracovat datové sady obsahující až 20 atributů a desítky tisíc řádků až za několik hodin. Moderní algoritmy běžící na vícejádrových procesorech detekují závislosti pro datové sady sestávající ze stovek atributů (až 200) a stovek tisíc řádků přibližně ve stejnou dobu. To však nestačí: taková doba je pro většinu aplikací v reálném světě nepřijatelná. Proto jsme vyvinuli přístupy k urychlení stávajících algoritmů.

Schémata ukládání do mezipaměti pro průsečíky oddílů

V první části práce jsme vyvinuli schémata ukládání do mezipaměti pro třídu algoritmů, které využívají metodu průniku oddílů. Oddíl pro atribut je sada seznamů, kde každý seznam obsahuje čísla řádků se stejnými hodnotami pro daný atribut. Každý takový seznam se nazývá shluk. Mnoho moderních algoritmů používá oddíly k určení, zda je závislost držena nebo ne, jmenovitě dodržují lemma: Závislost konat, kdyby , zde je určen oddíl a je použit koncept velikosti oddílu - počet clusterů v něm. Algoritmy, které používají oddíly, když je závislost narušena, přidávají další atributy na levou stranu závislosti a pak ji přepočítají, přičemž provádějí operaci průniku oddílů. Tato operace se v článcích nazývá specializace. Ale všimli jsme si, že oddíly pro závislosti, které by zůstaly zachovány až po několika kolech specializace, lze aktivně znovu použít, což může výrazně zkrátit dobu běhu algoritmů, protože operace křižovatky je drahá.

Proto jsme navrhli heuristiku založenou na Shannonově entropii a Ginny Uncertainty, stejně jako naši metriku, kterou jsme nazvali Reverzní entropie. Je to mírná modifikace Shannon Entropy a zvyšuje se s tím, jak se zvyšuje jedinečnost souboru dat. Navrhovaná heuristika je následující:

Zde — stupeň jedinečnosti nedávno vypočítaného oddílu a je medián stupňů jedinečnosti pro jednotlivé atributy. Všechny tři výše popsané metriky byly testovány jako metrika jedinečnosti. Můžete si také všimnout, že v heuristice jsou dva modifikátory. První udává, jak blízko je aktuální oddíl k primárnímu klíči, a umožňuje ukládat do mezipaměti ve větší míře ty oddíly, které jsou daleko od potenciálního klíče. Druhý modifikátor vám umožňuje sledovat obsazenost mezipaměti a tím podporuje přidání dalších oddílů do mezipaměti, pokud je k dispozici volné místo. Úspěšné vyřešení tohoto problému nám umožnilo zrychlit PYRO algoritmus o 10-40% v závislosti na datové sadě. Stojí za zmínku, že PYRO algoritmus je v této oblasti nejúspěšnější.

Na obrázku níže můžete vidět výsledky použití navržené heuristiky v porovnání se základním přístupem coin-flip caching. Osa X je logaritmická.

Alternativní způsob ukládání oddílů

Poté jsme navrhli alternativní způsob ukládání oddílů. Oddíly jsou sada shluků, z nichž každý ukládá počet n-tic se stejnými hodnotami pro určité atributy. Tyto shluky mohou obsahovat dlouhé sekvence n-ticových čísel, například pokud jsou data v tabulce uspořádána. Proto jsme navrhli schéma komprese pro ukládání oddílů, konkrétně intervalové ukládání hodnot do shluků oddílů:

$$display$$pi(X) = {{pod závorkou{1, 2, 3, 4, 5}_{První interval}, pod závorkou{7, 8}_{Second interval}, 10}}\ downarrow{ Komprese} \ pi(X) = {{závorka{$, 1, 5}_{První~interval}, závorka{7, 8}_{Second~interval}, 10}}$$display$$

Tato metoda dokázala snížit spotřebu paměti při provozu algoritmu TANE z 1 na 25 %. Algoritmus TANE je klasický algoritmus pro vyhledávání federálních zákonů, při své práci využívá oddíly. V rámci praxe byl zvolen algoritmus TANE, protože v něm bylo mnohem jednodušší implementovat intervalové ukládání než např. v PYRO, aby bylo možné vyhodnotit, zda navržený přístup funguje. Získané výsledky jsou uvedeny na obrázku níže. Osa X je logaritmická.

Konference ADBIS-2019

Na základě výsledků výzkumu jsem v září 2019 publikoval článek Inteligentní ukládání do mezipaměti pro efektivní zjišťování funkčních závislostí na 23. evropské konferenci o pokroku v databázích a informačních systémech (ADBIS-2019). Během prezentace práce poznamenala významná osobnost v oblasti databází Bernhard Thalheim. Výsledky výzkumu se staly základem mé disertační práce na magisterském stupni matematiky a mechaniky na St. Petersburg State University, během níž byly oba navržené přístupy (cachování a komprese) implementovány v obou algoritmech: TANE a PYRO. Výsledky navíc ukázaly, že navrhované přístupy jsou univerzální, protože na obou algoritmech, u obou přístupů, bylo pozorováno výrazné snížení spotřeby paměti a také výrazné zkrácení provozní doby algoritmů.

Zdroj: www.habr.com