Introduktion til funktionelle afhængigheder

I denne artikel vil vi tale om funktionelle afhængigheder i databaser - hvad de er, hvor de bruges, og hvilke algoritmer der findes for at finde dem.

Vi vil overveje funktionelle afhængigheder i sammenhæng med relationelle databaser. For at sige det meget groft, i sådanne databaser er information lagret i form af tabeller. Dernæst bruger vi tilnærmede begreber, der ikke er udskiftelige i streng relationsteori: vi kalder selve tabellen en relation, kolonnerne - attributter (deres sæt - et relationsskema) og sættet af rækkeværdier på en delmængde af attributter - en tupel.

For eksempel i tabellen ovenfor, (Benson, M, M orgel) er en række attributter (Patient, Paul, læge).
Mere formelt skrives dette som følger: [Patient, køn, læge] = (Benson, M, M orgel).
Nu kan vi introducere begrebet funktionel afhængighed (FD):

Definition 1. Relationen R opfylder den føderale lov X → Y (hvor X, Y ⊆ R) hvis og kun hvis for nogen tupler , ∈ R holder: if [X] = [X], så [Y] = [Y]. I dette tilfælde siger vi, at X (determinanten eller definerende sæt af attributter) funktionelt bestemmer Y (det afhængige sæt).

Med andre ord, tilstedeværelsen af ​​en føderal lov X → Y betyder, at hvis vi har to tupler ind R og de matcher i egenskaber X, så vil de falde sammen i attributter Y.
Og nu i rækkefølge. Lad os se på egenskaberne Patient и Køn som vi ønsker at finde ud af, om der er afhængigheder mellem dem eller ej. For et sådant sæt attributter kan følgende afhængigheder eksistere:

1. Patient → Køn
2. Køn → Patient

Som defineret ovenfor, for at den første afhængighed skal holde, hver unik kolonneværdi Patient kun én kolonneværdi skal matche Køn. Og for eksempeltabellen er dette faktisk tilfældet. Dette virker dog ikke i den modsatte retning, det vil sige, at den anden afhængighed ikke er opfyldt, og attributten Køn er ikke en determinant for Patient. Tilsvarende, hvis vi tager afhængigheden Læge → Patient, kan du se, at den er overtrådt, da værdien Robin denne egenskab har flere forskellige betydninger - Ellis og Graham.

Funktionelle afhængigheder gør det således muligt at bestemme de eksisterende relationer mellem sæt af tabelattributter. Herfra vil vi overveje de mest interessante forbindelser, eller rettere sådan X → Yhvad de er:

• ikke-triviel, det vil sige, at højre side af afhængigheden ikke er en delmængde af venstre (Y ̸⊆ X);
• minimal, det vil sige, der er ingen sådan afhængighed Z → YDet Z ⊂ X.

De afhængigheder, der blev betragtet indtil dette punkt, var strenge, det vil sige, at de ikke sørgede for nogen overtrædelser på bordet, men ud over dem er der også dem, der tillader en vis uoverensstemmelse mellem tupernes værdier. Sådanne afhængigheder placeres i en separat klasse, kaldet omtrentlig, og har lov til at blive krænket for et vist antal tupler. Denne mængde reguleres af den maksimale fejlindikator emax. For eksempel fejlprocenten = 0.01 kan betyde, at afhængigheden kan overtrædes med 1% af de tilgængelige tuples på det betragtede sæt af attributter. Det vil sige, at for 1000 poster kan maksimalt 10 tupler overtræde den føderale lov. Vi vil overveje en lidt anderledes metrik, baseret på parvis forskellige værdier af de tupler, der sammenlignes. Til afhængighed X → Y på holdning r det betragtes sådan her:

Lad os beregne fejlen for Læge → Patient fra eksemplet ovenfor. Vi har to tuples, hvis værdier er forskellige på attributten Patient, men falder sammen Læge: [Læge, patient] = (Robin, Ellis) Og [Læge, patient] = (Robin, Graham). Efter definitionen af ​​en fejl skal vi tage højde for alle modstridende par, hvilket betyder, at der vil være to af dem: (, ) og dens omvendte (, ). Lad os erstatte det med formlen og få:

Lad os nu prøve at besvare spørgsmålet: "Hvorfor er det hele til?" Faktisk er føderale love anderledes. Den første type er de afhængigheder, der bestemmes af administratoren på databasedesignstadiet. De er normalt få i antal, strenge, og hovedapplikationen er datanormalisering og relationelt skemadesign.

Den anden type er afhængigheder, som repræsenterer "skjulte" data og hidtil ukendte forhold mellem attributter. Det vil sige, at sådanne afhængigheder ikke var tænkt over på designtidspunktet, og de findes for det eksisterende datasæt, så der senere, baseret på de mange identificerede føderale love, kan drages eventuelle konklusioner om den lagrede information. Det er netop disse afhængigheder, vi arbejder med. De håndteres af et helt felt af datamining med forskellige søgeteknikker og algoritmer bygget på deres grundlag. Lad os finde ud af, hvordan de fundne funktionelle afhængigheder (nøjagtig eller omtrentlig) i data kan være nyttige.

I dag er en af ​​de vigtigste anvendelser af afhængigheder datarensning. Det involverer udvikling af processer til at identificere "beskidte data" og derefter rette dem. Fremtrædende eksempler på "beskidte data" er dubletter, datafejl eller slåfejl, manglende værdier, forældede data, ekstra mellemrum og lignende.

Eksempel på en datafejl:

Eksempel på dubletter i data:

For eksempel har vi en tabel og et sæt føderale love, der skal udføres. Datarensning involverer i dette tilfælde at ændre dataene, så de føderale love bliver korrekte. I dette tilfælde skal antallet af ændringer være minimalt (denne procedure har sine egne algoritmer, som vi ikke vil fokusere på i denne artikel). Nedenfor er et eksempel på en sådan datatransformation. Til venstre er det oprindelige forhold, hvor de nødvendige FL'er naturligvis ikke er opfyldt (et eksempel på en krænkelse af en af ​​FL'erne er fremhævet med rødt). Til højre er det opdaterede forhold, hvor de grønne celler viser de ændrede værdier. Efter denne procedure begyndte de nødvendige afhængigheder at blive vedligeholdt.

Et andet populært program er databasedesign. Her er det værd at huske normale former og normalisering. Normalisering er processen med at bringe en relation i overensstemmelse med et bestemt sæt krav, som hver er defineret af den normale form på sin egen måde. Vi vil ikke beskrive kravene til forskellige normale former (dette gøres i enhver bog om et databasekursus for begyndere), men vi vil kun bemærke, at hver af dem bruger begrebet funktionelle afhængigheder på sin egen måde. Når alt kommer til alt, er FL'er iboende integritetsbegrænsninger, der tages i betragtning, når du designer en database (i forbindelse med denne opgave kaldes FL'er nogle gange supernøgler).

Lad os overveje deres ansøgning til de fire normale formularer på billedet nedenfor. Husk på, at Boyce-Codds normale form er mere streng end den tredje form, men mindre streng end den fjerde. Vi overvejer ikke det sidste for nu, da dets formulering kræver en forståelse af afhængigheder med flere værdier, som ikke er interessante for os i denne artikel.

Et andet område, hvor afhængigheder har fundet deres anvendelse, er at reducere dimensionaliteten af ​​funktionsrummet i opgaver som at bygge en naiv Bayes-klassifikator, identificere væsentlige træk og reparametrisere en regressionsmodel. I de originale artikler kaldes denne opgave bestemmelse af redundant og funktionsrelevans [5, 6], og den løses med aktiv brug af databasekoncepter. Med fremkomsten af ​​sådanne værker kan vi sige, at der i dag er efterspørgsel efter løsninger, der giver os mulighed for at kombinere databasen, analyserne og implementeringen af ​​ovenstående optimeringsproblemer i ét værktøj [7, 8, 9].

Der er mange algoritmer (både moderne og ikke så moderne) til at søge efter føderale love i et datasæt. Sådanne algoritmer kan opdeles i tre grupper:

• Algoritmer, der bruger traversal af algebraiske gitter (Gitter-traversal-algoritmer)
• Algoritmer baseret på søgningen efter aftalte værdier (Difference- og agree-set algoritmer)
• Algoritmer baseret på parvise sammenligninger (afhængighedsinduktionsalgoritmer)

En kort beskrivelse af hver type algoritme er præsenteret i tabellen nedenfor:


Du kan læse mere om denne klassifikation [4]. Nedenfor er eksempler på algoritmer for hver type:

I øjeblikket dukker der nye algoritmer op, der kombinerer flere tilgange til at finde funktionelle afhængigheder. Eksempler på sådanne algoritmer er Pyro [2] og HyFD [3]. En analyse af deres arbejde forventes i de følgende artikler i denne serie. I denne artikel vil vi kun undersøge de grundlæggende begreber og lemma, der er nødvendige for at forstå afhængighedsdetektionsteknikker.

Lad os starte med en simpel - forskel- og enig-sæt, brugt i den anden type algoritmer. Difference-sæt er et sæt af tupler, der ikke har de samme værdier, mens enig-sæt tværtimod er tupler, der har de samme værdier. Det er værd at bemærke, at vi i dette tilfælde kun overvejer den venstre side af afhængigheden.

Et andet vigtigt koncept, der blev stødt på ovenfor, er det algebraiske gitter. Da mange moderne algoritmer opererer på dette koncept, er vi nødt til at have en idé om, hvad det er.

For at introducere begrebet et gitter er det nødvendigt at definere et delvist ordnet sæt (eller delvist ordnet sæt, forkortet som poset).

Definition 2. Et sæt S siges at være delvist ordnet efter den binære relation ⩽ hvis for alle a, b, c ∈ S følgende egenskaber er opfyldt:

1. Refleksivitet, det vil sige a ⩽ a
2. Antisymmetri, det vil sige, hvis a ⩽ b og b ⩽ a, så er a = b
3. Transitivitet, det vil sige for a ⩽ b og b ⩽ c følger det, at a ⩽ c

En sådan relation kaldes en (løs) partiel ordensrelation, og selve mængden kaldes en delvis ordnet mængde. Formel notation: ⟨S, ⩽⟩.

Som det enkleste eksempel på en delvis ordnet mængde kan vi tage mængden af ​​alle naturlige tal N med den sædvanlige ordensrelation ⩽. Det er let at verificere, at alle de nødvendige aksiomer er opfyldt.

Et mere meningsfuldt eksempel. Overvej mængden af ​​alle delmængder {1, 2, 3}, sorteret efter inklusionsrelationen ⊆. Faktisk opfylder denne relation alle partielle ordensbetingelser, så ⟨P ({1, 2, 3}), ⊆⟩ er et delvist ordnet sæt. Nedenstående figur viser strukturen af ​​dette sæt: Hvis et element kan nås med pile til et andet element, så er de i en rækkefølge.

Vi får brug for yderligere to simple definitioner fra matematikområdet - supremum og infimum.

Definition 3. Lad ⟨S, ⩽⟩ være en delvis ordnet mængde, A ⊆ S. Den øvre grænse af A er et element u ∈ S således, at ∀x ∈ S: x ⩽ u. Lad U være mængden af ​​alle øvre grænser af S. Hvis der er et mindste element i U, så kaldes det supremum og betegnes sup A.

Begrebet en nøjagtig nedre grænse introduceres på samme måde.

Definition 4. Lad ⟨S, ⩽⟩ være en delvis ordnet mængde, A ⊆ S. Infimum af A er et element l ∈ S således, at ∀x ∈ S: l ⩽ x. Lad L være mængden af ​​alle nedre grænser af S. Hvis der er et største element i L, så kaldes det et infimum og betegnes som inf A.

Betragt som et eksempel ovenstående delvist ordnede sæt ⟨P ({1, 2, 3}), ⊆⟩ og find supremum og infimum i det:

Nu kan vi formulere definitionen af ​​et algebraisk gitter.

Definition 5. Lad ⟨P,⩽⟩ være en delvist ordnet mængde, således at hver to-element undergruppe har en øvre og nedre grænse. Så kaldes P et algebraisk gitter. I dette tilfælde skrives sup{x, y} som x ∨ y, og inf {x, y} som x ∧ y.

Lad os kontrollere, at vores arbejdseksempel ⟨P ({1, 2, 3}), ⊆⟩ er et gitter. For enhver a, b ∈ P ({1, 2, 3}), a∨b = a∪b og a∧b = a∩b. Overvej f.eks. sættene {1, 2} og {1, 3} og find deres infimum og supremum. Hvis vi krydser dem, får vi sættet {1}, som vil være det infimum. Vi får det højeste ved at kombinere dem - {1, 2, 3}.

I algoritmer til at identificere fysiske problemer er søgerummet ofte repræsenteret i form af et gitter, hvor sæt af ét element (læs det første niveau af søgegitteret, hvor venstre side af afhængighederne består af én egenskab) repræsenterer hver egenskab af det oprindelige forhold.
Først overvejer vi afhængigheder af formen ∅ → Enkelt attribut. Dette trin giver dig mulighed for at bestemme, hvilke attributter der er primære nøgler (for sådanne attributter er der ingen determinanter, og derfor er venstre side tom). Yderligere bevæger sådanne algoritmer sig opad langs gitteret. Det er værd at bemærke, at ikke hele gitteret kan krydses, det vil sige, hvis den ønskede maksimale størrelse af venstre side sendes til input, så vil algoritmen ikke gå længere end et niveau med den størrelse.

Figuren nedenfor viser, hvordan et algebraisk gitter kan bruges i problemet med at finde en FZ. Her hver kant (X, XY) repræsenterer en afhængighed X → Y. For eksempel har vi bestået første niveau og ved, at afhængigheden opretholdes A → B (vi vil vise dette som en grøn forbindelse mellem hjørnerne A и B). Det betyder, at længere, når vi bevæger os op langs gitteret, kan vi muligvis ikke kontrollere afhængigheden A, C → B, fordi den ikke længere vil være minimal. På samme måde ville vi ikke kontrollere det, hvis afhængigheden blev holdt C → B.

Derudover bruger alle moderne algoritmer til at søge efter føderale love en datastruktur såsom en partition (i den originale kilde - strippet partition [1]). Den formelle definition af en partition er som følger:

Definition 6. Lad X ⊆ R være et sæt attributter for relation r. En klynge er et sæt af indekser af tupler i r, der har samme værdi for X, det vil sige c(t) = {i|ti[X] = t[X]}. En partition er et sæt af klynger, eksklusive klynger med enhedslængde:

Med enkle ord, en partition for en attribut X er et sæt lister, hvor hver liste indeholder linjenumre med samme værdier for X. I moderne litteratur kaldes strukturen, der repræsenterer partitioner, positionslisteindeks (PLI). Enhedslængde-klynger er udelukket til PLI-komprimeringsformål, fordi de er klynger, der kun indeholder et postnummer med en unik værdi, som altid vil være let at identificere.

Lad os se på et eksempel. Lad os vende tilbage til den samme tabel med patienter og bygge partitioner til kolonnerne Patient и Køn (en ny kolonne er dukket op til venstre, hvori tabelrækkenumrene er markeret):

Desuden, ifølge definitionen, partitionen for kolonnen Patient vil faktisk være tom, da enkelte klynger er udelukket fra partitionen.

Skillevægge kan opnås af flere attributter. Og der er to måder at gøre dette på: ved at gå gennem tabellen, byg en partition ved hjælp af alle de nødvendige attributter på én gang, eller byg den ved at bruge operationen af ​​skæringspunktet mellem partitioner ved hjælp af en undergruppe af attributter. Føderale lov søgealgoritmer bruger den anden mulighed.

Med enkle ord, for for eksempel at få en partition efter kolonner ABC, kan du tage partitioner til AC и B (eller ethvert andet sæt af usammenhængende delmængder) og skærer dem med hinanden. Operationen af ​​skæringspunktet mellem to partitioner vælger klynger af den største længde, der er fælles for begge partitioner.

Lad os se på et eksempel:

I det første tilfælde modtog vi en tom partition. Hvis du ser nærmere på tabellen, så er der faktisk ingen identiske værdier for de to attributter. Hvis vi ændrer lidt i tabellen (sagen til højre), får vi allerede et ikke-tomt kryds. Desuden indeholder linje 1 og 2 faktisk de samme værdier for attributterne Køn и Læge.

Dernæst skal vi bruge et sådant koncept som partitionsstørrelse. Formelt:

Enkelt sagt er partitionsstørrelsen antallet af klynger inkluderet i partitionen (husk at enkelte klynger ikke er inkluderet i partitionen!):

Nu kan vi definere et af nøglelemmaerne, som for givne partitioner giver os mulighed for at bestemme, om en afhængighed holdes eller ej:

Lemma 1. Afhængigheden A, B → C gælder hvis og kun hvis

Ifølge lemmaet skal der udføres fire trin for at afgøre, om en afhængighed gælder:

1. Beregn partitionen for venstre side af afhængigheden
2. Beregn partitionen for højre side af afhængigheden
3. Beregn produktet af første og andet trin
4. Sammenlign størrelserne på partitionerne opnået i første og tredje trin

Nedenfor er et eksempel på kontrol af, om afhængigheden holder i henhold til dette lemma:

I denne artikel har vi undersøgt begreber som funktionel afhængighed, tilnærmet funktionel afhængighed, set på hvor de bruges, samt hvilke algoritmer til at søge efter fysiske funktioner der findes. Vi undersøgte også i detaljer de grundlæggende, men vigtige begreber, der aktivt bruges i moderne algoritmer til at søge efter føderale love.

Referencer:

1. Huhtala Y. et al. TANE: En effektiv algoritme til at opdage funktionelle og omtrentlige afhængigheder //Computerjournalen. – 1999. – T. 42. – Nr. 2. – s. 100-111.
2. Kruse S., Naumann F. Effektiv opdagelse af omtrentlige afhængigheder // Proceedings of the VLDB Endowment. – 2018. – T. 11. – Nr. 7. – s. 759-772.
3. Papenbrock T., Naumann F. En hybrid tilgang til opdagelse af funktionel afhængighed //Proceedings of the 2016 International Conference on Management of Data. – ACM, 2016. – s. 821-833.
4. Papenbrock T. et al. Functional dependency discovery: En eksperimentel evaluering af syv algoritmer //Proceedings of the VLDB Endowment. – 2015. – T. 8. – Nej. 10. – s. 1082-1093.
5. Kumar A. et al. At deltage eller ikke at deltage?: Tænker du to gange om tilmeldinger før funktionsvalg //Proceedings of the 2016 International Conference on Management of Data. – ACM, 2016. – s. 19-34.
6. Abo Khamis M. et al. Indlæring i databasen med sparsomme tensorer //Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems. – ACM, 2018. – s. 325-340.
7. Hellerstein JM et al. MADlib-analysebiblioteket: eller MAD-færdigheder, SQL //Proceedings of the VLDB Endowment. – 2012. – T. 5. – Nej. 12. – s. 1700-1711.
8. Qin C., Rusu F. Spekulative tilnærmelser til optimering af terascale distribueret gradientnedstigning //Proceedings of the Fourth Workshop on Data analytics in the Cloud. – ACM, 2015. – S. 1.
9. Meng X. et al. Mllib: Machine learning in apache spark //The Journal of Machine Learning Research. – 2016. – T. 17. – Nr. 1. – s. 1235-1241.

Artiklens forfattere: Anastasia Birillo, forsker ved JetBrains Research, CS center elev и Nikita Bobrov, forsker ved JetBrains Research

Kilde: www.habr.com