Úvod do funkčních závislostí

V tomto článku budeme hovořit o funkčních závislostech v databázích - co to jsou, kde se používají a jaké existují algoritmy k jejich nalezení.

Funkční závislosti budeme uvažovat v kontextu relačních databází. Velmi zhruba řečeno, v takových databázích jsou informace uloženy ve formě tabulek. Dále použijeme přibližné koncepty, které nejsou zaměnitelné v přísné relační teorii: samotnou tabulku budeme nazývat relací, sloupce - atributy (jejich množina - relační schéma) a množinu řádkových hodnot na podmnožině atributů. - n-tice.

Například v tabulce výše (Benson, M, M varhany) je n-tice atributů (Pacient, Paul, doktor).
Formálněji se to píše takto: [Pacient, pohlaví, lékař] = (Benson, M, M varhany).
Nyní můžeme představit koncept funkční závislosti (FD):

Definice 1. Relace R splňuje federální zákon X → Y (kde X, Y ⊆ R) právě tehdy, když pro libovolné n-tice , ∈ R platí: jestliže [X] = [X] tedy [Y] = [Y]. V tomto případě říkáme, že X (determinant nebo definující množina atributů) funkčně určuje Y (závislou množinu).

Jinými slovy, přítomnost federálního zákona X → Y znamená, že pokud máme dvě n-tice R a shodují se v atributech X, pak se budou shodovat v atributech Y.
A teď popořadě. Podívejme se na atributy Pacient и Pohlaví u kterých chceme zjistit, zda mezi nimi existují závislosti nebo ne. Pro takovou sadu atributů mohou existovat následující závislosti:

1. Pacient → Pohlaví
2. Pohlaví → Pacient

Jak je definováno výše, aby první závislost držela, každá jedinečná hodnota sloupce Pacient musí odpovídat pouze jedna hodnota sloupce Pohlaví. A pro ukázkovou tabulku tomu tak skutečně je. To však nefunguje v opačném směru, to znamená, že druhá závislost není splněna a atribut Pohlaví není určující pro Trpěliví. Podobně, když vezmeme závislost Lékař → Pacient, můžete vidět, že je porušena, protože hodnota červenka tento atribut má několik různých významů - Ellis a Graham.

Funkční závislosti tedy umožňují určit existující vztahy mezi sadami atributů tabulky. Odtud budeme dále uvažovat o nejzajímavějších souvislostech, nebo spíše takových X → Yco jsou zač:

• netriviální, to znamená, že pravá strana závislosti není podmnožinou levé (Y ̸⊆ X);
• minimální, to znamená, že žádná taková závislost neexistuje Z → YŽe Z ⊂ X.

Závislosti zvažované až do tohoto bodu byly přísné, to znamená, že nezajišťovaly žádná porušení na stole, ale kromě nich existují také ty, které umožňují určitou nekonzistenci mezi hodnotami n-tic. Takové závislosti jsou umístěny v samostatné třídě, nazývané přibližné, a je povoleno je narušit pro určitý počet n-tic. Toto množství je regulováno ukazatelem maximální chyby emax. Například chybovost = 0.01 může znamenat, že závislost může být narušena o 1 % dostupných n-tic na uvažované sadě atributů. To znamená, že na 1000 záznamů může federální zákon porušit maximálně 10 n-tic. Budeme uvažovat mírně odlišnou metriku založenou na párově odlišných hodnotách porovnávaných n-tic. Pro závislost X → Y na postoji r uvažuje se to takto:

Pojďme vypočítat chybu pro Lékař → Pacient z výše uvedeného příkladu. Máme dvě n-tice, jejichž hodnoty se v atributu liší Pacient, ale shodují se Doktor: [Doktor, pacient] = (Robine, Ellis) A [Doktor, pacient] = (Robine, Grahame). Po definici chyby musíme vzít v úvahu všechny konfliktní páry, což znamená, že budou dva: (, ) a jeho inverzní (, ). Dosadíme to do vzorce a dostaneme:

Nyní se pokusme odpovědět na otázku: „Proč to všechno je?“ Ve skutečnosti jsou federální zákony odlišné. Prvním typem jsou závislosti, které určuje správce ve fázi návrhu databáze. Obvykle je jich málo, jsou striktní a hlavní aplikací je normalizace dat a návrh relačních schémat.

Druhým typem jsou závislosti, které představují „skrytá“ data a dříve neznámé vztahy mezi atributy. To znamená, že o takových závislostech se v době návrhu neuvažovalo a jsou nalezeny pro existující soubor dat, takže později, na základě mnoha identifikovaných federálních zákonů, lze vyvodit jakékoli závěry o uložených informacích. Přesně s těmito závislostmi pracujeme. Zabývá se jimi celá oblast data miningu s různými vyhledávacími technikami a algoritmy postavenými na jejich základě. Pojďme zjistit, jak mohou být nalezené funkční závislosti (přesné nebo přibližné) v jakýchkoli datech užitečné.

Dnes je jednou z hlavních aplikací závislostí čištění dat. Zahrnuje vývoj procesů pro identifikaci „špinavých dat“ a jejich následnou opravu. Nápadnými příklady „špinavých dat“ jsou duplikáty, datové chyby nebo překlepy, chybějící hodnoty, zastaralá data, mezery navíc a podobně.

Příklad datové chyby:

Příklad duplicit v datech:

Máme například tabulku a sadu federálních zákonů, které musí být provedeny. Čištění dat v tomto případě zahrnuje změnu dat tak, aby byly federální zákony správné. V tomto případě by měl být počet úprav minimální (tento postup má své vlastní algoritmy, kterým se v tomto článku nebudeme věnovat). Níže je uveden příklad takové transformace dat. Vlevo je původní vztah, ve kterém evidentně nejsou splněny potřebné FL (červeně je zvýrazněn příklad porušení jednoho z FL). Vpravo je aktualizovaný vztah se zelenými buňkami zobrazujícími změněné hodnoty. Po tomto postupu se začaly udržovat potřebné závislosti.

Další oblíbenou aplikací je návrh databáze. Zde stojí za to připomenout normální formy a normalizaci. Normalizace je proces uvedení vztahu do souladu s určitým souborem požadavků, z nichž každý je definován svým vlastním způsobem normální formou. Nebudeme popisovat požadavky různých normálních forem (to se dělá v kterékoli knize na databázovém kurzu pro začátečníky), ale pouze poznamenáme, že každý z nich používá koncept funkčních závislostí po svém. Koneckonců, FL jsou ze své podstaty omezení integrity, která se berou v úvahu při navrhování databáze (v kontextu tohoto úkolu se FL někdy nazývají superklíče).

Zvažme jejich aplikaci pro čtyři normální formy na obrázku níže. Připomeňme, že normální forma Boyce-Codda je přísnější než třetí forma, ale méně přísná než čtvrtá. O tom druhém zatím neuvažujeme, protože jeho formulace vyžaduje pochopení vícehodnotových závislostí, které nás v tomto článku nezajímají.

Další oblastí, ve které závislosti našly své uplatnění, je snížení dimenzionality prostoru prvků v úlohách, jako je vytvoření naivního Bayesova klasifikátoru, identifikace významných prvků a reparametrizace regresního modelu. V původních článcích se tato úloha nazývá stanovení redundance a relevance funkcí [5, 6] a je řešena s aktivním využitím databázových konceptů. S nástupem takovýchto prací lze říci, že dnes existuje poptávka po řešeních, která nám umožní spojit databázi, analytiku a implementaci výše uvedených optimalizačních problémů do jednoho nástroje [7, 8, 9].

Existuje mnoho algoritmů (moderních i méně moderních) pro vyhledávání federálních zákonů v souboru dat. Takové algoritmy lze rozdělit do tří skupin:

• Algoritmy využívající procházení algebraických svazů (algoritmy procházení mřížek)
• Algoritmy založené na hledání dohodnutých hodnot (algoritmy množiny rozdílů a shody)
• Algoritmy založené na párovém porovnání (Algoritmy indukce závislosti)

Stručný popis každého typu algoritmu je uveden v tabulce níže:


Více o této klasifikaci si můžete přečíst [4]. Níže jsou uvedeny příklady algoritmů pro každý typ:

V současné době se objevují nové algoritmy, které kombinují několik přístupů k nalezení funkčních závislostí. Příklady takových algoritmů jsou Pyro [2] a HyFD [3]. Analýza jejich práce se očekává v následujících článcích této série. V tomto článku prozkoumáme pouze základní pojmy a lemma, které jsou nezbytné k pochopení technik detekce závislostí.

Začněme jednoduchým – množinou rozdílů a souhlasů, používanými ve druhém typu algoritmů. Difference-set je množina n-tic, které nemají stejné hodnoty, zatímco agreement-set jsou naopak n-tice, které mají stejné hodnoty. Stojí za zmínku, že v tomto případě uvažujeme pouze levou stranu závislosti.

Dalším důležitým konceptem, se kterým jsme se setkali výše, je algebraická mřížka. Protože mnoho moderních algoritmů pracuje na tomto konceptu, musíme mít představu o tom, co to je.

Aby bylo možné zavést pojem mříž, je nutné definovat částečně uspořádanou množinu (nebo částečně uspořádanou množinu, zkráceně poset).

Definice 2. O množině S se říká, že je částečně uspořádaná binární relací ⩽, pokud jsou pro všechna a, b, c ∈ S splněny následující vlastnosti:

1. Reflexivita, tedy a ⩽ a
2. Antisymetrie, tedy pokud a ⩽ b a b ⩽ a, pak a = b
3. Tranzitivita, tedy pro a ⩽ b a b ⩽ c z toho vyplývá, že a ⩽ c

Takový vztah se nazývá (volný) relace částečného řádu a množina samotná se nazývá částečně uspořádaná množina. Formální zápis: ⟨S, ⩽⟩.

Jako nejjednodušší příklad částečně uspořádané množiny můžeme vzít množinu všech přirozených čísel N s obvyklým řádovým vztahem ⩽. Je snadné ověřit, že jsou splněny všechny potřebné axiomy.

Smysluplnější příklad. Uvažujme množinu všech podmnožin {1, 2, 3} seřazených podle inkluzní relace ⊆. Tento vztah skutečně splňuje všechny podmínky dílčího řádu, takže ⟨P ({1, 2, 3}), ⊆⟩ je částečně uspořádaná množina. Obrázek níže ukazuje strukturu této množiny: pokud lze k jednomu prvku dosáhnout pomocí šipek k jinému prvku, pak jsou ve vztahu pořadí.

Budeme potřebovat ještě dvě jednoduché definice z oblasti matematiky – supremum a infimum.

Definice 3. Nechť ⟨S, ⩽⟩ je částečně uspořádaná množina, A ⊆ S. Horní mez A je prvek u ∈ S takový, že ∀x ∈ S: x ⩽ u. Nechť U je množina všech horních hranic S. Pokud je v U nejmenší prvek, pak se nazývá supremum a označuje se sup A.

Koncept přesné dolní hranice je zaveden podobně.

Definice 4. Nechť ⟨S, ⩽⟩ je částečně uspořádaná množina, A ⊆ S. Infimum A je prvek l ∈ S takový, že ∀x ∈ S: l ⩽ x. Nechť L je množina všech dolních hranic S. Pokud je v L největší prvek, pak se nazývá infimum a označuje se jako inf A.

Vezměme si jako příklad výše částečně uspořádanou množinu ⟨P ({1, 2, 3}), ⊆⟩ a najděte v ní supremum a infimum:

Nyní můžeme formulovat definici algebraické mřížky.

Definice 5. Nechť ⟨P,⩽⟩ je částečně uspořádaná množina tak, že každá dvouprvková podmnožina má horní a dolní hranici. Pak se P nazývá algebraická mřížka. V tomto případě se sup{x, y} zapíše jako x ∨ y a inf {x, y} jako x ∧ y.

Zkontrolujeme, že náš pracovní příklad ⟨P ({1, 2, 3}), ⊆⟩ je mřížka. Ve skutečnosti pro libovolné a, b ∈ P ({1, 2, 3}) platí a∨b = a∪b a a∧b = a∩b. Uvažujme například množiny {1, 2} a {1, 3} a najděte jejich infimum a supremum. Pokud je protneme, dostaneme množinu {1}, která bude infimum. Supremum získáme jejich kombinací – {1, 2, 3}.

V algoritmech pro identifikaci fyzikálních problémů je vyhledávací prostor často reprezentován ve formě mřížky, kde množiny jednoho prvku (čti první úroveň vyhledávací mřížky, kde levá strana závislostí sestává z jednoho atributu) představují každý atribut. původního vztahu.
Nejprve uvažujeme závislosti tvaru ∅ → Jediný atribut. Tento krok vám umožňuje určit, které atributy jsou primární klíče (pro takové atributy neexistují žádné determinanty, a proto je levá strana prázdná). Dále se takové algoritmy pohybují nahoru podél mřížky. Stojí za zmínku, že nelze procházet celou mřížkou, to znamená, že pokud je na vstup předána požadovaná maximální velikost levé strany, algoritmus nepůjde dále než na úroveň s touto velikostí.

Obrázek níže ukazuje, jak lze použít algebraickou mřížku v problému hledání FZ. Zde každá hrana (X, XY) představuje závislost X → Y. Například jsme prošli první úrovní a víme, že závislost je udržována A → B (zobrazíme to jako zelené spojení mezi vrcholy A и B). To znamená, že když se dále pohybujeme po mříži, nemusíme závislost kontrolovat A, C → B, protože už nebude minimální. Podobně bychom to nekontrolovali, pokud by závislost byla držena C → B.

Kromě toho zpravidla všechny moderní algoritmy pro vyhledávání federálních zákonů používají datovou strukturu, jako je oddíl (v původním zdroji - stripovaný oddíl [1]). Formální definice oddílu je následující:

Definice 6. Nechť X ⊆ R je množina atributů pro relaci r. Shluk je množina indexů n-tic v r, které mají stejnou hodnotu pro X, tedy c(t) = {i|ti[X] = t[X]}. Oddíl je sada shluků s výjimkou shluků o jednotkové délce:

Jednoduše řečeno, oddíl pro atribut X je sada seznamů, kde každý seznam obsahuje čísla řádků se stejnými hodnotami pro X. V moderní literatuře se struktura představující oddíly nazývá index seznamu pozic (PLI). Clustery jednotkové délky jsou pro účely komprese PLI vyloučeny, protože se jedná o klastry, které obsahují pouze číslo záznamu s jedinečnou hodnotou, kterou bude vždy snadné identifikovat.

Podívejme se na příklad. Vraťme se ke stejnému stolu s pacienty a postavme oddíly pro sloupce Pacient и Pohlaví (vlevo se objevil nový sloupec, ve kterém jsou vyznačena čísla řádků tabulky):

Navíc podle definice přepážka pro sloup Pacient bude ve skutečnosti prázdný, protože jednotlivé clustery jsou z oddílu vyloučeny.

Oddíly lze získat několika atributy. A to lze provést dvěma způsoby: procházením tabulky vytvořte oddíl pomocí všech nezbytných atributů najednou nebo jej vytvořte pomocí operace průniku oddílů pomocí podmnožiny atributů. Algoritmy pro vyhledávání federálních zákonů používají druhou možnost.

Jednoduše řečeno, například získat oddíl podle sloupců ABC, můžete vzít oddíly pro AC и B (nebo jakoukoli jinou množinu disjunktních podmnožin) a vzájemně je protínají. Operace průniku dvou oddílů vybere shluky největší délky, které jsou společné oběma oddílům.

Podívejme se na příklad:

V prvním případě jsme obdrželi prázdný oddíl. Pokud se podíváte pozorně na tabulku, pak skutečně neexistují žádné identické hodnoty pro dva atributy. Pokud tabulku mírně upravíme (případ vpravo), dostaneme již neprázdnou křižovatku. Navíc řádky 1 a 2 ve skutečnosti obsahují stejné hodnoty atributů Pohlaví и Lékař.

Dále budeme potřebovat takový koncept jako velikost oddílu. Formálně:

Jednoduše řečeno, velikost oddílu je počet clusterů zahrnutých v oddílu (nezapomeňte, že jednotlivé clustery nejsou zahrnuty v oddílu!):

Nyní můžeme definovat jedno z klíčových lemmat, které nám pro dané oddíly umožňuje určit, zda je závislost držena nebo ne:

Lemma 1. Závislost A, B → C platí tehdy a jen tehdy

Podle lemmatu je k určení, zda závislost platí, nutné provést čtyři kroky:

1. Vypočítejte oddíl pro levou stranu závislosti
2. Vypočítejte oddíl pro pravou stranu závislosti
3. Vypočítejte součin prvního a druhého kroku
4. Porovnejte velikosti oddílů získaných v prvním a třetím kroku

Níže je uveden příklad kontroly, zda závislost platí podle tohoto lemmatu:

V tomto článku jsme zkoumali pojmy jako funkční závislost, přibližná funkční závislost, podívali jsme se na to, kde se používají, a také na to, jaké existují algoritmy pro hledání fyzikálních funkcí. Také jsme podrobně prozkoumali základní, ale důležité koncepty, které se aktivně používají v moderních algoritmech pro hledání federálních zákonů.

Reference:

1. Huhtala Y. a kol. TANE: Efektivní algoritmus pro objevování funkčních a přibližných závislostí //Počítačový deník. – 1999. – T. 42. – Č. 2. – s. 100-111.
2. Kruse S., Naumann F. Efektivní zjišťování přibližných závislostí // Proceedings of the VLDB Endowment. – 2018. – T. 11. – No. 7. – s. 759-772.
3. Papenbrock T., Naumann F. Hybridní přístup k objevování funkčních závislostí //Proceedings of the 2016 International Conference on Management of Data. – ACM, 2016. – s. 821-833.
4. Papenbrock T. a kol. Zjišťování funkčních závislostí: Experimentální vyhodnocení sedmi algoritmů //Proceedings of the VLDB Endowment. – 2015. – T. 8. – Č. 10. – s. 1082-1093.
5. Kumar A. a kol. Připojit se, či nepřipojit se?: Před výběrem funkce si dvakrát rozmyslete připojení //Sborník z mezinárodní konference o správě dat 2016. – ACM, 2016. – s. 19-34.
6. Abo Khamis M. a kol. Výuka v databázi s řídkými tenzory //Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems. – ACM, 2018. – s. 325-340.
7. Hellerstein JM a kol. Analytická knihovna MADlib: nebo dovednosti MAD, SQL //Proceedings of the VLDB Endowment. – 2012. – T. 5. – No. 12. – s. 1700-1711.
8. Qin C., Rusu F. Spekulativní aproximace pro optimalizaci sestupu distribuovaného gradientu terascale //Proceedings of the Fourth Workshop on Data analytics in the Cloud. – ACM, 2015. – S. 1.
9. Meng X. a kol. Mllib: Machine learning in apache spark //The Journal of Machine Learning Research. – 2016. – T. 17. – Č. 1. – s. 1235-1241.

Autoři článku: Anastasia Birillo, výzkumník v Výzkum JetBrains, student CS centra и Nikita Bobrov, výzkumník v Výzkum JetBrains

Zdroj: www.habr.com