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. Anastasia Birillo a Nikita Bobrov. Tentokrát se Anastasia, letošní absolventka Centra informatiky, podělí o vývoj tohoto výzkumného projektu, který v centru obhájila.
Výběr úkolu
Během studia na CS Center jsem se začal hlouběji zabývat databázemi, konkrétně hledáním funkčních a diferenciálních závislostí. Toto téma se vztahovalo k mému univerzitnímu kurzu, takže jsem při práci na něm začal číst články o různých závislostech v databázích. Napsal jsem recenzi na tento obor – jednu z mých prvních. v angličtině a předložil jsem ji na konferenci SEIM-2017. Byl jsem nadšený, když byla přijata, a rozhodl jsem se tomuto tématu hlouběji věnovat. Samotný koncept není nový – existuje už od 90. let 20. století – ale dodnes nachází uplatnění v mnoha oblastech.
Ve druhém semestru v centru jsem zahájil výzkumný projekt zaměřený na vylepšení algoritmů pro hledání funkčních závislostí. Pracoval jsem na něm s Nikitou Bobrovem, postgraduálním studentem na Petrohradské státní univerzitě, v JetBrains Research.
Výpočetní složitost hledání funkčních závislostí
Hlavním problémem je výpočetní složitost. Počet možných minimálních a netriviálních závislostí je shora omezen parametrem 
Kde 
— počet atributů tabulky. Doba běhu algoritmů nezávisí pouze na počtu atributů, ale také na počtu řádků. V 90. letech 20. století mohly algoritmy pro detekci federálního práva na typickém stolním počítači zpracovávat datové sady obsahující až 20 atributů a desítky tisíc řádků po dobu až několika hodin. Moderní algoritmy běžící na vícejádrových procesorech detekují závislosti u datových sad sestávajících ze stovek atributů (až 200) a stovek tisíc řádků přibližně ve stejnou dobu. To je však nedostatečné: taková doba je pro většinu reálných aplikací nepřijatelná. Proto jsme vyvinuli přístupy k urychlení stávajících algoritmů.
Schémata ukládání do mezipaměti pro průnik oddílů
V první části článku jsme vyvinuli schémata ukládání do mezipaměti pro třídu algoritmů pomocí metody průniku particí. Partice 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á partice k určení, zda platí závislost, konkrétně se řídí následujícím lemmatem: Závislost 
se zachová, pokud 
, zde 
Oddíl je označen a používá se koncept velikosti oddílu – počet shluků v něm. Algoritmy, které používají oddíly, přidávají na levou stranu závislosti další atributy, když je závislost narušena, a poté ji přepočítají provedením operace průniku oddílů. Tato operace se v článcích označuje jako specializace. Poznamenali jsme však, že oddíly pro závislosti, které budou 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 průniku je nákladná.
Proto jsme navrhli heuristiku založenou na Shannonově entropii a Giniho neurčitosti, a také naši vlastní metriku, kterou nazýváme inverzní entropie. Jedná se o mírnou modifikaci Shannonovy entropie a zvyšuje se s rostoucí jedinečností datové sady. Navrhovaná heuristika je následující:
Zde 
— stupeň jedinečnosti nedávno vypočítaného rozdělení 
a 
je medián stupňů jedinečnosti pro jednotlivé atributy. Všechny tři výše popsané metriky byly testovány jako metriky jedinečnosti. Lze také poznamenat, že heuristika obsahuje dva modifikátory. První udává, jak blízko je aktuální oddíl primárnímu klíči, a umožňuje větší ukládání do mezipaměti oddílů dále od kandidátského klíče. Druhý modifikátor monitoruje obsazenost mezipaměti, a tím podporuje přidání dalších oddílů do mezipaměti, když je k dispozici místo. Úspěšné vyřešení tohoto problému umožnilo algoritmu PYRO zrychlit práci o 10–40 % v závislosti na datové sadě. Stojí za zmínku, že algoritmus PYRO je v této oblasti nejúspěšnější.
Obrázek níže ukazuje výsledky aplikace navrhované heuristiky ve srovnání se základním přístupem k ukládání do mezipaměti založeným na hodu mincí. Osa x je logaritmická.
Alternativní způsob ukládání příček
Poté jsme navrhli alternativní metodu pro ukládání oddílů. Oddíly jsou sada shluků, z nichž každý ukládá čísla n-tic se shodnými hodnotami pro určité atributy. Tyto shluky mohou obsahovat dlouhé sekvence čísel n-tic, například pokud jsou data v tabulce seřazena. Proto jsme navrhli kompresní schéma pro ukládání oddílů, konkrétně intervalové ukládání hodnot ve shlukech oddílů:
$$display$$pi(X) = {{underbrace{1, 2, 3, 4, 5}_{První~interval}, underbrace{7, 8}_{Druhý~interval}, 10}}\ downarrow{Komprese}\ pi(X) = {{underbrace{$, 1, 5}_{První~interval}, underbrace{7, 8}_{Druhý~interval}, 10}}$$display$$
Tato metoda dokázala snížit spotřebu paměti během provádění algoritmu TANE o 1 až 25 %. Algoritmus TANE je klasický algoritmus pro vyhledávání logických zón; během své činnosti využívá oddíly. Z praktických důvodů byl algoritmus TANE zvolen, protože implementace intervalového ukládání byla pro vyhodnocení proveditelnosti navrhovaného přístupu výrazně snazší než například v PYRO. 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. Na 23. Evropské konferenci o pokroku v databázích a informačních systémech (ADBIS-2019) byla práce oceněna Bernhardem Thalheimem, významnou osobností v oblasti databází. Výsledky výzkumu tvořily základ mé disertační práce pro magisterský program na Fakultě matematiky a mechaniky Státní univerzity v Petrohradu, během kterého byly oba navrhované přístupy (ukládání do mezipaměti a komprese) implementovány v obou algoritmech: TANE a PYRO. Výsledky ukázaly, že navrhované přístupy jsou univerzální, protože oba algoritmy prokázaly významné snížení spotřeby paměti a významné zkrácení doby provádění.
Zdroj: www.habr.com
