Introduksjon til funksjonelle avhengigheter

I denne artikkelen vil vi snakke om funksjonelle avhengigheter i databaser - hva de er, hvor de brukes og hvilke algoritmer som finnes for å finne dem.

Vi vil vurdere funksjonelle avhengigheter i sammenheng med relasjonsdatabaser. For å si det veldig grovt, i slike databaser lagres informasjon i form av tabeller. Deretter bruker vi omtrentlige konsepter som ikke er utskiftbare i streng relasjonsteori: vi vil kalle selve tabellen en relasjon, kolonnene - attributter (deres sett - et relasjonsskjema), og settet med radverdier på et undersett av attributter - en tuppel.

For eksempel, i tabellen ovenfor, (Benson, M, M orgel) er en tuppel av attributter (pasient, Paul, lege).
Mer formelt skrives dette slik: [Pasient, kjønn, lege] = (Benson, M, M orgel).
Nå kan vi introdusere konseptet funksjonell avhengighet (FD):

Definisjon 1. Relasjonen R tilfredsstiller den føderale loven X → Y (hvor X, Y ⊆ R) hvis og bare hvis for noen tupler , ∈ R holder: if [X] = [X], da [Y] = [Y]. I dette tilfellet sier vi at X (determinanten, eller definerende sett med attributter) funksjonelt bestemmer Y (det avhengige settet).

Med andre ord, tilstedeværelsen av en føderal lov X → Y betyr at hvis vi har to tuples inn R og de samsvarer i attributter X, da vil de falle sammen i attributter Y.
Og nå, i rekkefølge. La oss se på attributtene En pasient и Kjønn som vi ønsker å finne ut om det er avhengigheter mellom dem eller ikke. For et slikt sett med attributter kan følgende avhengigheter eksistere:

1. Pasient → Kjønn
2. Kjønn → Pasient

Som definert ovenfor, for at den første avhengigheten skal holde, hver unike kolonneverdi En pasient bare én kolonneverdi må samsvare Kjønn. Og for eksempeltabellen er dette faktisk tilfelle. Dette fungerer imidlertid ikke i motsatt retning, det vil si at den andre avhengigheten ikke er oppfylt, og attributtet Kjønn er ikke en determinant for Pasient. Tilsvarende, hvis vi tar avhengigheten Lege → Pasient, kan du se at den brytes, siden verdien Robin denne egenskapen har flere forskjellige betydninger - Ellis og Graham.

Dermed gjør funksjonelle avhengigheter det mulig å bestemme de eksisterende relasjonene mellom sett med tabellattributter. Herfra og utover vil vi vurdere de mest interessante forbindelsene, eller snarere slike X → Yhva de er:

• ikke-trivielt, det vil si at høyre side av avhengigheten ikke er en undergruppe av venstre (Y ̸⊆ X);
• minimal, det vil si at det ikke er noen slik avhengighet Z → YAt Z ⊂ X.

Avhengighetene som ble vurdert frem til dette punktet var strenge, det vil si at de ikke sørget for noen brudd på bordet, men i tillegg til dem er det også de som tillater en viss inkonsekvens mellom verdiene til tuplene. Slike avhengigheter er plassert i en egen klasse, kalt omtrentlig, og tillates krenket for et visst antall tupler. Dette beløpet reguleres av maksimal feilindikator emax. For eksempel feilprosenten = 0.01 kan bety at avhengigheten kan brytes med 1 % av de tilgjengelige tuplene på det vurderte settet med attributter. Det vil si at for 1000 poster kan maksimalt 10 tuples bryte den føderale loven. Vi vil vurdere en litt annen beregning, basert på parvis forskjellige verdier av tuplene som sammenlignes. For avhengighet X → Y på holdning r det anses slik:

La oss beregne feilen for Lege → Pasient fra eksempelet ovenfor. Vi har to tupler hvis verdier er forskjellige på attributtet En pasient, men sammenfaller Doktor: [Lege, pasient] = (Robin, Ellis) Og [Lege, pasient] = (Robin, Graham). Etter definisjonen av en feil må vi ta hensyn til alle motstridende par, noe som betyr at det vil være to av dem: (, ) og dens inverse (, ). La oss erstatte det med formelen og få:

La oss nå prøve å svare på spørsmålet: "Hvorfor er alt for?" Faktisk er føderale lover forskjellige. Den første typen er de avhengighetene som bestemmes av administratoren på databasedesignstadiet. De er vanligvis få i antall, strenge, og hovedapplikasjonen er datanormalisering og relasjonsskjemadesign.

Den andre typen er avhengigheter som representerer "skjulte" data og tidligere ukjente forhold mellom attributter. Det vil si at slike avhengigheter ikke ble tenkt på på utformingstidspunktet, og de finnes for det eksisterende datasettet, slik at det senere, basert på de mange identifiserte føderale lovene, kan trekkes noen konklusjoner om den lagrede informasjonen. Det er nettopp disse avhengighetene vi jobber med. De håndteres av et helt felt av data mining med ulike søketeknikker og algoritmer bygget på deres grunnlag. La oss finne ut hvordan funnfunksjonelle avhengigheter (eksakte eller omtrentlige) i data kan være nyttige.

I dag er en av hovedapplikasjonene for avhengigheter datarensing. Det innebærer å utvikle prosesser for å identifisere "skitne data" og deretter korrigere dem. Fremtredende eksempler på "skitne data" er duplikater, datafeil eller skrivefeil, manglende verdier, utdaterte data, ekstra mellomrom og lignende.

Eksempel på datafeil:

Eksempel på duplikater i data:

For eksempel har vi en tabell og et sett med føderale lover som må utføres. Datarensing innebærer i dette tilfellet å endre dataene slik at de føderale lovene blir korrekte. I dette tilfellet bør antallet modifikasjoner være minimalt (denne prosedyren har sine egne algoritmer, som vi ikke vil fokusere på i denne artikkelen). Nedenfor er et eksempel på en slik datatransformasjon. Til venstre er det opprinnelige forholdet, der de nødvendige FL-ene åpenbart ikke er oppfylt (et eksempel på brudd på en av FL-ene er uthevet i rødt). Til høyre er det oppdaterte forholdet, med de grønne cellene som viser de endrede verdiene. Etter denne prosedyren begynte de nødvendige avhengighetene å opprettholdes.

Et annet populært program er databasedesign. Her er det verdt å minne om normale former og normalisering. Normalisering er prosessen med å bringe et forhold i samsvar med et visst sett med krav, som hver er definert av normalformen på sin egen måte. Vi vil ikke beskrive kravene til ulike normale former (dette gjøres i en hvilken som helst bok om et databasekurs for nybegynnere), men vi vil bare merke oss at hver av dem bruker konseptet funksjonelle avhengigheter på sin egen måte. Tross alt er FL-er iboende integritetsbegrensninger som tas i betraktning når man designer en database (i sammenheng med denne oppgaven kalles FL-er noen ganger supernøkler).

La oss vurdere søknaden deres for de fire normale skjemaene på bildet nedenfor. Husk at Boyce-Codds normalform er strengere enn den tredje formen, men mindre streng enn den fjerde. Vi vurderer ikke sistnevnte foreløpig, siden formuleringen krever en forståelse av avhengigheter med flere verdier, som ikke er interessante for oss i denne artikkelen.

Et annet område der avhengigheter har funnet sin anvendelse er å redusere dimensjonaliteten til funksjonsrommet i oppgaver som å bygge en naiv Bayes-klassifiserer, identifisere betydelige funksjoner og reparametrisere en regresjonsmodell. I de originale artiklene kalles denne oppgaven bestemmelse av redundant og funksjonsrelevans [5, 6], og den løses med aktiv bruk av databasekonsepter. Med bruken av slike verk kan vi si at det i dag er etterspørsel etter løsninger som lar oss kombinere databasen, analyser og implementering av de ovennevnte optimaliseringsproblemene til ett verktøy [7, 8, 9].

Det finnes mange algoritmer (både moderne og ikke så moderne) for å søke etter føderale lover i et datasett. Slike algoritmer kan deles inn i tre grupper:

• Algoritmer som bruker traversering av algebraiske gitter (Gitter-traversal-algoritmer)
• Algoritmer basert på søk etter avtalte verdier (Differanse- og enig-sett algoritmer)
• Algoritmer basert på parvise sammenligninger (avhengighetsinduksjonsalgoritmer)

En kort beskrivelse av hver type algoritme er presentert i tabellen nedenfor:


Du kan lese mer om denne klassifiseringen [4]. Nedenfor er eksempler på algoritmer for hver type:

For tiden dukker det opp nye algoritmer som kombinerer flere tilnærminger for å finne funksjonelle avhengigheter. Eksempler på slike algoritmer er Pyro [2] og HyFD [3]. En analyse av arbeidet deres forventes i de følgende artiklene i denne serien. I denne artikkelen vil vi bare undersøke de grunnleggende konseptene og lemmaet som er nødvendige for å forstå teknikker for avhengighetsdeteksjon.

La oss starte med en enkel - forskjell- og enig-sett, brukt i den andre typen algoritmer. Differansesett er et sett med tupler som ikke har de samme verdiene, mens enig-sett tvert imot er tupler som har samme verdier. Det er verdt å merke seg at i dette tilfellet vurderer vi bare venstre side av avhengigheten.

Et annet viktig konsept som ble møtt ovenfor er det algebraiske gitteret. Siden mange moderne algoritmer opererer på dette konseptet, må vi ha en ide om hva det er.

For å introdusere konseptet med et gitter, er det nødvendig å definere et delvis ordnet sett (eller delvis ordnet sett, forkortet som poset).

Definisjon 2. Et sett S sies å være delvis ordnet etter den binære relasjonen ⩽ hvis for alle a, b, c ∈ S følgende egenskaper er oppfylt:

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

En slik relasjon kalles en (løs) partiell ordensrelasjon, og selve settet kalles et delvis ordnet sett. Formell notasjon: ⟨S, ⩽⟩.

Som det enkleste eksemplet på et delvis ordnet sett, kan vi ta settet med alle naturlige tall N med den vanlige rekkefølgerelasjonen ⩽. Det er lett å verifisere at alle nødvendige aksiomer er oppfylt.

Et mer meningsfylt eksempel. Tenk på settet med alle delmengder {1, 2, 3}, sortert etter inklusjonsrelasjonen ⊆. Faktisk tilfredsstiller denne relasjonen alle delordrebetingelser, så ⟨P ({1, 2, 3}), ⊆⟩ er et delvis ordnet sett. Figuren nedenfor viser strukturen til dette settet: hvis ett element kan nås med piler til et annet element, er de i en rekkefølge.

Vi vil trenge ytterligere to enkle definisjoner fra matematikkfeltet - supremum og infimum.

Definisjon 3. La ⟨S, ⩽⟩ være et delvis ordnet sett, A ⊆ S. Den øvre grensen til A er et element u ∈ S slik at ∀x ∈ S: x ⩽ u. La U være mengden av alle øvre grenser for S. Hvis det er et minste element i U, kalles det supremum og betegnes sup A.

Konseptet med en eksakt nedre grense introduseres på samme måte.

Definisjon 4. La ⟨S, ⩽⟩ være et delvis ordnet sett, A ⊆ S. Infimumet til A er et element l ∈ S slik at ∀x ∈ S: l ⩽ x. La L være mengden av alle nedre grenser for S. Hvis det er et største element i L, kalles det et infimum og betegnes som inf A.

Betrakt som et eksempel det ovenfor delvis ordnede settet ⟨P ({1, 2, 3}), ⊆⟩ og finn supremum og infimum i det:

Nå kan vi formulere definisjonen av et algebraisk gitter.

Definisjon 5. La ⟨P,⩽⟩ være et delvis ordnet sett slik at hver delmengde med to elementer har en øvre og nedre grense. Da kalles P et algebraisk gitter. I dette tilfellet skrives sup{x, y} som x ∨ y, og inf {x, y} som x ∧ y.

La oss sjekke at arbeidseksemplet vårt ⟨P ({1, 2, 3}), ⊆⟩ er et gitter. Faktisk, for enhver a, b ∈ P ({1, 2, 3}), a∨b = a∪b og a∧b = a∩b. Tenk for eksempel på settene {1, 2} og {1, 3} og finn deres infimum og supremum. Hvis vi krysser dem, får vi settet {1}, som vil være infimum. Vi får det høyeste ved å kombinere dem - {1, 2, 3}.

I algoritmer for å identifisere fysiske problemer er søkerommet ofte representert i form av et gitter, der sett med ett element (les det første nivået i søkegitteret, hvor venstre side av avhengighetene består av ett attributt) representerer hvert attributt av det opprinnelige forholdet.
Først tar vi for oss avhengigheter av formen ∅ → Enkelt attributt. Dette trinnet lar deg bestemme hvilke attributter som er primærnøkler (for slike attributter er det ingen determinanter, og derfor er venstre side tom). Videre beveger slike algoritmer seg oppover langs gitteret. Det er verdt å merke seg at ikke hele gitteret kan krysses, det vil si at hvis den ønskede maksimale størrelsen på venstre side sendes til inngangen, vil ikke algoritmen gå lenger enn et nivå med den størrelsen.

Figuren under viser hvordan et algebraisk gitter kan brukes i problemet med å finne en FZ. Her hver kant (X, XY) representerer en avhengighet X → Y. For eksempel har vi passert første nivå og vet at avhengigheten opprettholdes A → B (vi vil vise dette som en grønn forbindelse mellom toppunktene A и B). Dette betyr at videre, når vi beveger oss opp langs gitteret, kan det hende vi ikke sjekker avhengigheten A, C → B, fordi det ikke lenger vil være minimalt. På samme måte ville vi ikke sjekke det hvis avhengigheten ble holdt C → B.

I tillegg, som regel, bruker alle moderne algoritmer for å søke etter føderale lover en datastruktur som en partisjon (i den opprinnelige kilden - strippet partisjon [1]). Den formelle definisjonen av en partisjon er som følger:

Definisjon 6. La X ⊆ R være et sett med attributter for relasjonen r. En klynge er et sett med indekser av tupler i r som har samme verdi for X, det vil si c(t) = {i|ti[X] = t[X]}. En partisjon er et sett med klynger, unntatt klynger med enhetslengde:

Med enkle ord, en partisjon for et attributt X er et sett med lister, der hver liste inneholder linjenummer med samme verdier for X. I moderne litteratur kalles strukturen som representerer partisjoner posisjonslisteindeks (PLI). Enhetslengdeklynger er ekskludert for PLI-komprimeringsformål fordi de er klynger som bare inneholder et postnummer med en unik verdi som alltid vil være lett å identifisere.

La oss se på et eksempel. La oss gå tilbake til samme tabell med pasienter og bygge partisjoner for kolonnene En pasient и Kjønn (en ny kolonne har dukket opp til venstre, der tabellradnumrene er markert):

Dessuten, i henhold til definisjonen, partisjonen for kolonnen En pasient vil faktisk være tom, siden enkeltklynger er ekskludert fra partisjonen.

Partisjoner kan oppnås av flere attributter. Og det er to måter å gjøre dette på: ved å gå gjennom tabellen, bygg en partisjon ved å bruke alle de nødvendige attributtene samtidig, eller bygg den ved å bruke operasjonen til skjæringspunktet mellom partisjoner ved å bruke et undersett av attributter. Søkealgoritmer for føderal lov bruker det andre alternativet.

Med enkle ord, for å for eksempel få en partisjon etter kolonner ABC, kan du ta partisjoner for AC и B (eller et hvilket som helst annet sett med usammenhengende delmengder) og krysser dem med hverandre. Operasjonen av skjæringspunktet mellom to partisjoner velger klynger med størst lengde som er felles for begge partisjonene.

La oss se på et eksempel:

I det første tilfellet mottok vi en tom partisjon. Hvis du ser nøye på tabellen, er det faktisk ingen identiske verdier for de to attributtene. Hvis vi endrer tabellen litt (saken til høyre), vil vi allerede få et ikke-tomt kryss. Dessuten inneholder linjene 1 og 2 faktisk de samme verdiene for attributtene Kjønn и Doctor.

Deretter trenger vi et slikt konsept som partisjonsstørrelse. Formelt:

Enkelt sagt er partisjonsstørrelsen antall klynger som er inkludert i partisjonen (husk at enkeltklynger ikke er inkludert i partisjonen!):

Nå kan vi definere et av nøkkellemmaene, som for gitte partisjoner lar oss bestemme om en avhengighet holdes eller ikke:

Lemma 1. Avhengigheten A, B → C gjelder hvis og bare hvis

I følge lemmaet, for å avgjøre om en avhengighet holder, må fire trinn utføres:

1. Beregn partisjonen for venstre side av avhengigheten
2. Beregn partisjonen for høyre side av avhengigheten
3. Beregn produktet av første og andre trinn
4. Sammenlign størrelsene på partisjonene oppnådd i det første og tredje trinnet

Nedenfor er et eksempel på å sjekke om avhengigheten holder i henhold til dette lemmaet:

I denne artikkelen har vi undersøkt begreper som funksjonell avhengighet, omtrentlig funksjonell avhengighet, sett på hvor de brukes, samt hvilke algoritmer for å søke etter fysiske funksjoner som finnes. Vi undersøkte også i detalj de grunnleggende, men viktige konseptene som brukes aktivt i moderne algoritmer for å søke etter føderale lover.

Referanser:

1. Huhtala Y. et al. TANE: En effektiv algoritme for å oppdage funksjonelle og omtrentlige avhengigheter //Datajournalen. – 1999. – T. 42. – Nei. 2. – s. 100-111.
2. Kruse S., Naumann F. Effektiv oppdagelse av omtrentlige avhengigheter // Proceedings of the VLDB Endowment. – 2018. – T. 11. – Nei. 7. – s. 759-772.
3. Papenbrock T., Naumann F. En hybrid tilnærming til funksjonell avhengighetsoppdagelse //Proceedings of the 2016 International Conference on Management of Data. – ACM, 2016. – s. 821-833.
4. Papenbrock T. et al. Functional dependency discovery: En eksperimentell evaluering av syv algoritmer //Proceedings of the VLDB Endowment. – 2015. – T. 8. – Nei. 10. – s. 1082-1093.
5. Kumar A. et al. Å bli med eller ikke å bli med?: Tenker to ganger på bli med før funksjonsvalg //Proceedings of the 2016 International Conference on Management of Data. – ACM, 2016. – s. 19-34.
6. Abo Khamis M. et al. In-database læring med sparsomme 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-analysebiblioteket: eller MAD-ferdigheter, SQL //Proceedings of the VLDB Endowment. – 2012. – T. 5. – Nei. 12. – s. 1700-1711.
8. Qin C., Rusu F. Spekulative tilnærminger for terascale distribuert gradient descent-optimalisering //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. – Nei. 1. – s. 1235-1241.

Forfattere av artikkelen: Anastasia Birillo, forsker ved JetBrains forskning, CS-senterstudent и Nikita Bobrov, forsker ved JetBrains forskning

Kilde: www.habr.com