Introduktion till funktionella beroenden

I den här artikeln kommer vi att prata om funktionella beroenden i databaser - vad de är, var de används och vilka algoritmer som finns för att hitta dem.

Vi kommer att överväga funktionella beroenden i samband med relationsdatabaser. För att uttrycka det väldigt grovt, i sådana databaser lagras information i form av tabeller. Därefter använder vi ungefärliga begrepp som inte är utbytbara i strikt relationsteori: vi kallar själva tabellen för en relation, kolumnerna - attribut (deras uppsättning - ett relationsschema) och uppsättningen radvärden på en delmängd av attribut - en tuppel.

Till exempel, i tabellen ovan, (Benson, M, M orgel) är en tuppel av attribut (Patient, Paul, läkare).
Mer formellt skrivs detta så här: [Patient, kön, läkare🇧🇷 (Benson, M, M orgel).
Nu kan vi introducera begreppet funktionellt beroende (FD):

Definition 1. Relationen R uppfyller den federala lagen X → Y (där X, Y ⊆ R) om och endast om för några tupler , ∈ R håller: if [X] = [X], alltså [Y] = [Y]. I det här fallet säger vi att X (determinanten eller definierande uppsättningen av attribut) funktionellt bestämmer Y (den beroende uppsättningen).

Med andra ord, närvaron av en federal lag X → Y betyder att om vi har två tuplar in R och de matchar i attribut X, då kommer de att sammanfalla i attribut Y.
Och nu, i ordning. Låt oss titta på attributen Patient и Kön som vi vill ta reda på om det finns beroenden mellan dem eller inte. För en sådan uppsättning attribut kan följande beroenden finnas:

1. Patient → Kön
2. Kön → Patient

Som definierats ovan, för att det första beroendet ska hålla, varje unikt kolumnvärde Patient endast ett kolumnvärde måste matcha Kön. Och för exempeltabellen är detta verkligen fallet. Detta fungerar dock inte i motsatt riktning, det vill säga att det andra beroendet inte är uppfyllt, och attributet Kön är inte en avgörande faktor för Patient. Likaså om vi tar beroendet Läkare → Patient, kan du se att det bryts, eftersom värdet robin detta attribut har flera olika betydelser - Ellis och Graham.

Således gör funktionella beroenden det möjligt att bestämma de befintliga relationerna mellan uppsättningar av tabellattribut. Härifrån och framåt kommer vi att överväga de mest intressanta kopplingarna, eller snarare sådana X → Yvad de är:

• icke-trivial, det vill säga den högra sidan av beroendet är inte en delmängd av den vänstra (Y ̸⊆ X);
• minimal, det vill säga det finns inget sådant beroende Z → YAtt Z ⊂ X.

De beroenden som ansågs fram till denna punkt var strikta, det vill säga att de inte gav några kränkningar på bordet, men utöver dem finns det också de som tillåter viss inkonsekvens mellan tuplarnas värden. Sådana beroenden placeras i en separat klass, som kallas ungefärlig, och tillåts kränkas för ett visst antal tupler. Denna mängd regleras av den maximala felindikatorn emax. Till exempel felfrekvensen = 0.01 kan betyda att beroendet kan kränkas av 1% av de tillgängliga tuplarna på den betraktade uppsättningen attribut. Det vill säga, för 1000 poster kan maximalt 10 tupler bryta mot den federala lagen. Vi kommer att överväga ett lite annorlunda mått, baserat på parvis olika värden på tuplarna som jämförs. För beroende X → Y på attityd r det anses så här:

Låt oss beräkna felet för Läkare → Patient från exemplet ovan. Vi har två tupler vars värden skiljer sig åt på attributet Patient, men sammanfaller Läkare: [Läkare, patient] = (Robin, Ellis) Och [Läkare, patient] = (Robin, Graham). Efter definitionen av ett fel måste vi ta hänsyn till alla motstridiga par, vilket innebär att det kommer att finnas två av dem: (, ) och dess inversion (, ). Låt oss ersätta det i formeln och få:

Låt oss nu försöka svara på frågan: "Varför är allt för?" Faktum är att federala lagar är annorlunda. Den första typen är de beroenden som bestäms av administratören vid databasdesignstadiet. De är vanligtvis få till antalet, strikta, och huvudapplikationen är datanormalisering och relationsschemadesign.

Den andra typen är beroenden, som representerar "dolda" data och tidigare okända relationer mellan attribut. Det vill säga att sådana beroenden inte tänktes på vid designtillfället och de återfinns för den befintliga datamängden, så att man senare, baserat på de många identifierade federala lagarna, kan dra några slutsatser om den lagrade informationen. Det är just dessa beroenden vi jobbar med. De hanteras av ett helt område av datautvinning med olika söktekniker och algoritmer byggda på deras bas. Låt oss ta reda på hur de funna funktionella beroenden (exakta eller ungefärliga) i alla data kan vara användbara.

Idag är en av de viktigaste tillämpningarna för beroenden datarensning. Det handlar om att utveckla processer för att identifiera "smutsiga data" och sedan korrigera dem. Framträdande exempel på "smutsig data" är dubbletter, datafel eller stavfel, saknade värden, inaktuella data, extra mellanslag och liknande.

Exempel på ett datafel:

Exempel på dubbletter i data:

Till exempel har vi en tabell och en uppsättning federala lagar som måste verkställas. Datarensning i detta fall innebär att data ändras så att de federala lagarna blir korrekta. I det här fallet bör antalet ändringar vara minimalt (denna procedur har sina egna algoritmer, som vi inte kommer att fokusera på i den här artikeln). Nedan är ett exempel på en sådan datatransformation. Till vänster är det ursprungliga förhållandet, där de nödvändiga FLs uppenbarligen inte är uppfyllda (ett exempel på en kränkning av en av FLs markeras med rött). Till höger är det uppdaterade förhållandet, med de gröna cellerna som visar de ändrade värdena. Efter denna procedur började de nödvändiga beroenden upprätthållas.

En annan populär applikation är databasdesign. Här är det värt att påminna om normala former och normalisering. Normalisering är processen att bringa en relation i överensstämmelse med en viss uppsättning krav, som var och en definieras av den normala formen på sitt eget sätt. Vi kommer inte att beskriva kraven för olika normala former (detta görs i vilken bok som helst om en databaskurs för nybörjare), men vi kommer bara att notera att var och en av dem använder begreppet funktionella beroenden på sitt eget sätt. När allt kommer omkring är FL:er i sig integritetsbegränsningar som tas med i beräkningen när du designar en databas (i sammanhanget för denna uppgift kallas FLs ibland för supernycklar).

Låt oss överväga deras ansökan för de fyra normala formerna på bilden nedan. Kom ihåg att Boyce-Codds normala form är mer strikt än den tredje formen, men mindre strikt än den fjärde. Vi överväger inte det senare för tillfället, eftersom dess formulering kräver en förståelse för multi-värderade beroenden, som inte är intressanta för oss i den här artikeln.

Ett annat område där beroenden har hittat sin tillämpning är att reducera dimensionaliteten hos funktionsutrymmet i uppgifter som att bygga en naiv Bayes-klassificerare, identifiera signifikanta egenskaper och omparametrisera en regressionsmodell. I originalartiklarna kallas denna uppgift bestämning av redundant och funktionsrelevans [5, 6], och den löses med aktiv användning av databaskoncept. Med tillkomsten av sådana verk kan vi säga att det idag finns en efterfrågan på lösningar som gör att vi kan kombinera databasen, analysen och implementeringen av ovanstående optimeringsproblem till ett verktyg [7, 8, 9].

Det finns många algoritmer (både moderna och inte så moderna) för att söka efter federala lagar i en datamängd. Sådana algoritmer kan delas in i tre grupper:

• Algoritmer som använder traversering av algebraiska gitter (Lattic traversal algoritmer)
• Algoritmer baserade på sökningen efter överenskomna värden (Difference- och agree-set algoritmer)
• Algoritmer baserade på parvisa jämförelser (beroendeinduktionsalgoritmer)

En kort beskrivning av varje typ av algoritm presenteras i tabellen nedan:


Du kan läsa mer om denna klassificering [4]. Nedan finns exempel på algoritmer för varje typ:

För närvarande dyker det upp nya algoritmer som kombinerar flera metoder för att hitta funktionella beroenden. Exempel på sådana algoritmer är Pyro [2] och HyFD [3]. En analys av deras arbete förväntas i följande artiklar i denna serie. I den här artikeln kommer vi bara att undersöka de grundläggande begreppen och lemma som är nödvändiga för att förstå tekniker för detektering av beroende.

Låt oss börja med en enkel - skillnad- och överens-uppsättning, som används i den andra typen av algoritmer. Differensmängd är en uppsättning tupler som inte har samma värden, medan överens-mängd tvärtom är tupler som har samma värden. Det är värt att notera att vi i det här fallet endast överväger den vänstra sidan av beroendet.

Ett annat viktigt koncept som man stötte på ovan är det algebraiska gittret. Eftersom många moderna algoritmer fungerar på detta koncept måste vi ha en uppfattning om vad det är.

För att introducera begreppet ett gitter är det nödvändigt att definiera en delvis ordnad mängd (eller delvis ordnad mängd, förkortad som poset).

Definition 2. En mängd S sägs vara delvis ordnad av den binära relationen ⩽ om för alla a, b, c ∈ S följande egenskaper är uppfyllda:

1. Reflexivitet, det vill säga a ⩽ a
2. Antisymmetri, det vill säga om a ⩽ b och b ⩽ a, då a = b
3. Transitivitet, det vill säga för a ⩽ b och b ⩽ c följer det att a ⩽ c

En sådan relation kallas en (lös) partiell ordningsrelation, och själva mängden kallas en delvis ordnad mängd. Formell notation: ⟨S, ⩽⟩.

Som det enklaste exemplet på en delvis ordnad mängd kan vi ta mängden av alla naturliga tal N med den vanliga ordningsrelationen ⩽. Det är lätt att verifiera att alla nödvändiga axiom är uppfyllda.

Ett mer meningsfullt exempel. Betrakta mängden av alla delmängder {1, 2, 3}, ordnade efter inklusionsrelationen ⊆. Faktum är att denna relation uppfyller alla delordningsvillkor, så ⟨P ({1, 2, 3}), ⊆⟩ är en partiellt ordnad mängd. Bilden nedan visar strukturen för denna uppsättning: om ett element kan nås med pilar till ett annat element, är de i en ordningsrelation.

Vi kommer att behöva ytterligare två enkla definitioner från matematikområdet - supremum och infimum.

Definition 3. Låt ⟨S, ⩽⟩ vara en delvis ordnad mängd, A ⊆ S. Den övre gränsen för A är ett element u ∈ S så att ∀x ∈ S: x ⩽ u. Låt U vara mängden av alla övre gränser för S. Om det finns ett minsta element i U, så kallas det supremum och betecknas sup A.

Konceptet med en exakt nedre gräns introduceras på liknande sätt.

Definition 4. Låt ⟨S, ⩽⟩ vara en delvis ordnad mängd, A ⊆ S. Infimum av A är ett element l ∈ S så att ∀x ∈ S: l ⩽ x. Låt L vara mängden av alla nedre gränser för S. Om det finns ett största element i L, så kallas det ett infimum och betecknas som inf A.

Betrakta som ett exempel den ovan delvis ordnade uppsättningen ⟨P ({1, 2, 3}), ⊆⟩ och hitta supremum och infimum i den:

Nu kan vi formulera definitionen av ett algebraiskt gitter.

Definition 5. Låt ⟨P,⩽⟩ vara en delvis ordnad mängd så att varje delmängd med två element har en övre och nedre gräns. Då kallas P ett algebraiskt gitter. I det här fallet skrivs sup{x, y} som x ∨ y, och inf {x, y} som x ∧ y.

Låt oss kontrollera att vårt arbetsexempel ⟨P ({1, 2, 3}), ⊆⟩ är ett gitter. För alla a, b ∈ P ({1, 2, 3}), a∨b = a∪b och a∧b = a∩b. Tänk till exempel på uppsättningarna {1, 2} och {1, 3} och hitta deras infimum och supremum. Om vi ​​skär dem kommer vi att få uppsättningen {1}, som kommer att vara infimum. Vi får det högsta genom att kombinera dem - {1, 2, 3}.

I algoritmer för att identifiera fysiska problem representeras sökutrymmet ofta i form av ett gitter, där uppsättningar av ett element (läs den första nivån i söknätverket, där den vänstra sidan av beroenden består av ett attribut) representerar varje attribut av den ursprungliga relationen.
Först betraktar vi beroenden av formen ∅ → Enstaka attribut. Det här steget låter dig bestämma vilka attribut som är primärnycklar (för sådana attribut finns det inga determinanter, och därför är den vänstra sidan tom). Vidare rör sig sådana algoritmer uppåt längs gallret. Det är värt att notera att inte hela gittret kan korsas, det vill säga om den önskade maximala storleken på vänster sida skickas till ingången, kommer algoritmen inte att gå längre än en nivå med den storleken.

Figuren nedan visar hur ett algebraiskt gitter kan användas i problemet med att hitta en FZ. Här varje kant (X, XY) representerar ett beroende X → Y. Vi har till exempel klarat den första nivån och vet att missbruket bibehålls A → B (vi kommer att visa detta som en grön koppling mellan hörnen A и B). Detta innebär att ytterligare, när vi rör oss upp längs gallret, kanske vi inte kontrollerar beroendet A, C → B, eftersom det inte längre kommer att vara minimalt. På samma sätt skulle vi inte kontrollera det om beroendet hölls C → B.

Dessutom använder som regel alla moderna algoritmer för att söka efter federala lagar en datastruktur som en partition (i den ursprungliga källan - avskalad partition [1]). Den formella definitionen av en partition är följande:

Definition 6. Låt X ⊆ R vara en uppsättning attribut för relation r. Ett kluster är en uppsättning index av tupler i r som har samma värde för X, det vill säga c(t) = {i|ti[X] = t[X]}. En partition är en uppsättning kluster, exklusive kluster med enhetslängd:

Med enkla ord, en partition för ett attribut X är en uppsättning listor, där varje lista innehåller radnummer med samma värden för X. I modern litteratur kallas strukturen som representerar partitioner position list index (PLI). Enhetslängdkluster utesluts för PLI-komprimeringsändamål eftersom de är kluster som bara innehåller ett postnummer med ett unikt värde som alltid är lätt att identifiera.

Låt oss titta på ett exempel. Låt oss återgå till samma tabell med patienter och bygga partitioner för kolumnerna Patient и Kön (en ny kolumn har dykt upp till vänster, där tabellens radnummer är markerade):

Dessutom, enligt definitionen, partitionen för kolumnen Patient kommer faktiskt att vara tom, eftersom enstaka kluster exkluderas från partitionen.

Partitioner kan erhållas av flera attribut. Och det finns två sätt att göra detta: genom att gå igenom tabellen, bygga en partition med alla nödvändiga attribut på en gång, eller bygga den genom att använda operationen för skärningspunkten av partitioner med hjälp av en delmängd av attribut. Sökalgoritmer för federal lag använder det andra alternativet.

Med enkla ord, för att till exempel få en partition efter kolumner ABC, kan du ta partitioner för AC и B (eller någon annan uppsättning disjunkta delmängder) och skär dem med varandra. Operationen av skärningspunkten mellan två partitioner väljer kluster med den största längden som är gemensamma för båda partitionerna.

Låt oss titta på ett exempel:

I det första fallet fick vi en tom partition. Om du tittar noga på tabellen, så finns det faktiskt inga identiska värden för de två attributen. Om vi ​​ändrar tabellen något (fallet till höger) får vi redan en icke-tom korsning. Dessutom innehåller raderna 1 och 2 faktiskt samma värden för attributen Kön и Doctor.

Därefter kommer vi att behöva ett sådant koncept som partitionsstorlek. Formellt:

Enkelt uttryckt är partitionsstorleken antalet kluster som ingår i partitionen (kom ihåg att enstaka kluster inte ingår i partitionen!):

Nu kan vi definiera ett av nyckellemman, som för givna partitioner tillåter oss att avgöra om ett beroende hålls eller inte:

Lemma 1. Beroendet A, B → C gäller om och endast om

Enligt lemma måste fyra steg utföras för att avgöra om ett beroende gäller:

1. Beräkna partitionen för den vänstra sidan av beroendet
2. Beräkna partitionen för höger sida av beroendet
3. Beräkna produkten av det första och andra steget
4. Jämför storlekarna på partitionerna som erhålls i det första och tredje steget

Nedan är ett exempel på att kontrollera om beroendet håller enligt detta lemma:

I den här artikeln har vi undersökt begrepp som funktionellt beroende, ungefärligt funktionsberoende, tittat på var de används, samt vilka algoritmer för att söka efter fysiska funktioner som finns. Vi undersökte också i detalj de grundläggande men viktiga begreppen som aktivt används i moderna algoritmer för att söka efter federala lagar.

Referenser:

1. Huhtala Y. et al. TANE: En effektiv algoritm för att upptäcka funktionella och ungefärliga beroenden //Datorjournalen. – 1999. – T. 42. – Nej. 2. – s. 100-111.
2. Kruse S., Naumann F. Effektiv upptäckt av ungefärliga beroenden // Proceedings of the VLDB Endowment. – 2018. – T. 11. – Nej. 7. – s. 759-772.
3. Papenbrock T., Naumann F. A hybrid approach to functional dependency discovery //Proceedings of the 2016 International Conference on Management of Data. – ACM, 2016. – s. 821-833.
4. Papenbrock T. et al. Functional dependency discovery: En experimentell utvärdering av sju algoritmer //Proceedings of the VLDB Endowment. – 2015. – T. 8. – Nej. 10. – s. 1082-1093.
5. Kumar A. et al. Att gå med eller inte gå med?: Funderar du två gånger på att gå med innan du väljer funktioner //Proceedings of the 2016 International Conference on Management of Data. – ACM, 2016. – s. 19-34.
6. Abo Khamis M. et al. Inlärning i databasen med glesa tensorer //Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems. – ACM, 2018. – s. 325-340.
7. Hellerstein J.M. et al. MADlib-analysbiblioteket: eller MAD-färdigheter, SQL //Proceedings of the VLDB Endowment. – 2012. – T. 5. – Nej. 12. – s. 1700-1711.
8. Qin C., Rusu F. Spekulativa approximationer för terascale distribuerad gradient descent optimering //Proceedings of the Fourth Workshop on Data analytics in the Cloud. – ACM, 2015. – P. 1.
9. Meng X. et al. Mllib: Machine learning in apache spark //The Journal of Machine Learning Research. – 2016. – T. 17. – Nej. 1. – s. 1235-1241.

Artikelförfattare: Anastasia Birillo, forskare vid JetBrains forskning, CS center student и Nikita Bobrov, forskare vid JetBrains forskning

Källa: will.com