In dit artikel zullen we het hebben over functionele afhankelijkheden in databases: wat ze zijn, waar ze worden gebruikt en welke algoritmen er zijn om ze te vinden.
We zullen functionele afhankelijkheden beschouwen in de context van relationele databases. Om het heel grof te zeggen: in dergelijke databases wordt informatie opgeslagen in de vorm van tabellen. Vervolgens gebruiken we benaderende concepten die niet uitwisselbaar zijn in de strikte relationele theorie: we zullen de tabel zelf een relatie noemen, de kolommen - attributen (hun set - een relatieschema) en de set rijwaarden op een subset van attributen - een tupel.
In de bovenstaande tabel staat bijvoorbeeld (Benson, M, M orgel) is een tuple van attributen (Patiënt, Paul, Dokter).
Meer formeel wordt dit als volgt geschreven: [Patiënt, geslacht, dokter] = (Benson, M, M orgel).
Nu kunnen we het concept van functionele afhankelijkheid (FD) introduceren:
Definitie 1. De relatie R voldoet aan de federale wet X → Y (waarbij X, Y ⊆ R) dan en slechts dan als voor alle tupels , ∈ R geldt: als [X] = [X] dus [J] = [Y]. In dit geval zeggen we dat X (de determinant of definiërende set attributen) Y (de afhankelijke set) functioneel bepaalt.
Met andere woorden: de aanwezigheid van een federale wet X → Y betekent dat als we twee tupels in hebben R en ze komen qua attributen overeen X, dan zullen ze qua attributen samenvallen Y.
En nu, in volgorde. Laten we naar de attributen kijken patiënt и Geslacht waarvoor we willen weten of er afhankelijkheden tussen hen bestaan of niet. Voor een dergelijke set attributen kunnen de volgende afhankelijkheden bestaan:
- Patiënt → Geslacht
- Geslacht → Patiënt
Zoals hierboven gedefinieerd, moet elke unieke kolomwaarde behouden blijven om de eerste afhankelijkheid te behouden patiënt er mag slechts één kolomwaarde overeenkomen Geslacht. En voor de voorbeeldtabel is dit inderdaad het geval. Dit werkt echter niet in de tegenovergestelde richting, dat wil zeggen dat aan de tweede afhankelijkheid en het attribuut niet wordt voldaan Geslacht is niet bepalend voor Geduldig. Op dezelfde manier, als we de afhankelijkheid nemen Dokter → Patiënt, je kunt zien dat het wordt geschonden, aangezien de waarde roodborstje dit attribuut heeft verschillende betekenissen - Ellis en Graham.
Functionele afhankelijkheden maken het dus mogelijk om de bestaande relaties tussen sets tabelattributen te bepalen. Vanaf hier zullen we de meest interessante verbindingen bekijken, of beter gezegd dergelijke X → Ywat zij zijn:
- niet-triviaal, dat wil zeggen dat de rechterkant van de afhankelijkheid geen subset van de linkerkant is (Y ̸⊆ X);
- minimaal, dat wil zeggen dat er geen dergelijke afhankelijkheid bestaat Z → YDat Z ⊂ X.
De tot nu toe beschouwde afhankelijkheden waren strikt, dat wil zeggen dat ze niet voorzagen in overtredingen op tafel, maar daarnaast zijn er ook afhankelijkheden die enige inconsistentie tussen de waarden van de tupels mogelijk maken. Dergelijke afhankelijkheden worden in een aparte klasse geplaatst, genaamd approximatief, en mogen voor een bepaald aantal tupels worden geschonden. Dit bedrag wordt geregeld door de maximale foutindicator emax. Het foutenpercentage bijvoorbeeld = 0.01 kan betekenen dat de afhankelijkheid kan worden geschonden door 1% van de beschikbare tupels op de beschouwde set attributen. Dat wil zeggen dat voor 1000 records maximaal 10 tupels de federale wet kunnen schenden. We zullen een iets andere metriek overwegen, gebaseerd op paarsgewijze verschillende waarden van de tupels die worden vergeleken. Voor verslaving X → Y op houding r het wordt als volgt beschouwd:
Laten we de fout berekenen voor Dokter → Patiënt uit het bovenstaande voorbeeld. We hebben twee tupels waarvan de waarden verschillen op het attribuut patiënt, maar vallen samen Arts: [Dokter, patiënt] = (Robin, Ellis) En [Dokter, patiënt] = (Robin, Graham). Volgens de definitie van een fout moeten we rekening houden met alle conflicterende paren, wat betekent dat er twee zullen zijn: (, ) en zijn omgekeerde (, ). Laten we het in de formule vervangen en krijgen:
Laten we nu proberen de vraag te beantwoorden: "Waarom is dit allemaal bedoeld?" In feite zijn federale wetten anders. Het eerste type zijn de afhankelijkheden die door de beheerder worden bepaald in de databaseontwerpfase. Ze zijn meestal klein in aantal, strikt, en de belangrijkste toepassing is datanormalisatie en het ontwerpen van relationele schema's.
Het tweede type zijn afhankelijkheden, die ‘verborgen’ gegevens en voorheen onbekende relaties tussen attributen vertegenwoordigen. Dat wil zeggen dat er bij het ontwerp niet aan dergelijke afhankelijkheden is gedacht en dat ze voor de bestaande dataset worden gevonden, zodat later, op basis van de vele geïdentificeerde federale wetten, eventuele conclusies kunnen worden getrokken over de opgeslagen informatie. Het zijn juist deze afhankelijkheden waarmee wij werken. Ze worden behandeld door een heel gebied van datamining, met verschillende zoektechnieken en algoritmen die op hun basis zijn gebouwd. Laten we eens kijken hoe de gevonden functionele afhankelijkheden (exact of bij benadering) in gegevens nuttig kunnen zijn.
Tegenwoordig is een van de belangrijkste toepassingen van afhankelijkheden het opschonen van gegevens. Het gaat om het ontwikkelen van processen om ‘vuile gegevens’ te identificeren en deze vervolgens te corrigeren. Prominente voorbeelden van ‘vuile gegevens’ zijn duplicaten, gegevensfouten of typefouten, ontbrekende waarden, verouderde gegevens, extra spaties en dergelijke.
Voorbeeld van een gegevensfout:
Voorbeeld van duplicaten in gegevens:
We hebben bijvoorbeeld een tabel en een reeks federale wetten die moeten worden uitgevoerd. Het opschonen van gegevens houdt in dit geval in dat de gegevens worden gewijzigd, zodat de federale wetten correct worden. In dit geval moet het aantal wijzigingen minimaal zijn (deze procedure heeft zijn eigen algoritmen, waar we ons in dit artikel niet op zullen concentreren). Hieronder ziet u een voorbeeld van een dergelijke datatransformatie. Aan de linkerkant staat de oorspronkelijke relatie, waarbij uiteraard niet aan de noodzakelijke FL's wordt voldaan (een voorbeeld van een overtreding van een van de FL's is rood gemarkeerd). Aan de rechterkant ziet u de bijgewerkte relatie, waarbij de groene cellen de gewijzigde waarden weergeven. Na deze procedure begonnen de noodzakelijke afhankelijkheden in stand te blijven.
Een andere populaire toepassing is databaseontwerp. Hier is het de moeite waard om normale vormen en normalisatie te herinneren. Normalisatie is het proces waarbij een relatie in overeenstemming wordt gebracht met een bepaald stel eisen, die elk op hun eigen manier door de normaalvorm worden gedefinieerd. We zullen de vereisten van verschillende normaalvormen niet beschrijven (dit wordt in elk boek over een databasecursus voor beginners gedaan), maar we zullen alleen opmerken dat elk van hen het concept van functionele afhankelijkheden op zijn eigen manier gebruikt. FL's zijn immers inherent integriteitsbeperkingen waarmee rekening wordt gehouden bij het ontwerpen van een database (in de context van deze taak worden FL's soms superkeys genoemd).
Laten we hun toepassing voor de vier normaalvormen in de onderstaande afbeelding bekijken. Bedenk dat de normale vorm van Boyce-Codd strenger is dan de derde vorm, maar minder streng dan de vierde. Op dit laatste houden we voorlopig geen rekening, omdat de formulering ervan inzicht vereist in meerwaardige afhankelijkheden, die voor ons in dit artikel niet interessant zijn.
Een ander gebied waarop afhankelijkheden hun toepassing hebben gevonden, is het verminderen van de dimensionaliteit van de kenmerkruimte bij taken zoals het bouwen van een naïeve Bayes-classificator, het identificeren van significante kenmerken en het opnieuw parametriseren van een regressiemodel. In de originele artikelen wordt deze taak het bepalen van redundantie en functierelevantie genoemd [5, 6], en wordt opgelost met het actieve gebruik van databaseconcepten. Met de komst van dergelijke werken kunnen we zeggen dat er tegenwoordig vraag is naar oplossingen waarmee we de database, analyses en implementatie van de bovengenoemde optimalisatieproblemen kunnen combineren in één tool [7, 8, 9].
Er zijn veel algoritmen (zowel moderne als minder moderne) voor het zoeken naar federale wetten in een dataset. Dergelijke algoritmen kunnen in drie groepen worden verdeeld:
- Algoritmen die gebruik maken van het doorlopen van algebraïsche roosters (Lattice traversal-algoritmen)
- Algoritmen gebaseerd op het zoeken naar afgesproken waarden (Difference- en consensus-set-algoritmen)
- Algoritmen gebaseerd op paarsgewijze vergelijkingen (algoritmen voor afhankelijkheidsinductie)
Een korte beschrijving van elk type algoritme wordt weergegeven in de onderstaande tabel:
U kunt meer lezen over deze classificatie [4]. Hieronder staan voorbeelden van algoritmen voor elk type:
Momenteel verschijnen er nieuwe algoritmen die verschillende benaderingen combineren om functionele afhankelijkheden te vinden. Voorbeelden van dergelijke algoritmen zijn Pyro [2] en HyFD [3]. Een analyse van hun werk wordt verwacht in de volgende artikelen van deze serie. In dit artikel zullen we alleen de basisconcepten en het lemma onderzoeken die nodig zijn om technieken voor afhankelijkheidsdetectie te begrijpen.
Laten we beginnen met een eenvoudige: verschil- en akkoord-set, die wordt gebruikt in het tweede type algoritmen. Difference-set is een set tupels die niet dezelfde waarden hebben, terwijl eens-set daarentegen tupels is die dezelfde waarden hebben. Het is vermeldenswaard dat we in dit geval alleen de linkerkant van de afhankelijkheid beschouwen.
Een ander belangrijk concept dat hierboven werd aangetroffen, is het algebraïsche rooster. Omdat veel moderne algoritmen op dit concept werken, moeten we een idee hebben van wat het is.
Om het concept van een rooster te introduceren, is het noodzakelijk om een gedeeltelijk geordende set (of gedeeltelijk geordende set, afgekort als poset) te definiëren.
Definitie 2. Er wordt gezegd dat een verzameling S gedeeltelijk geordend is door de binaire relatie ⩽ als voor alle a, b, c ∈ S aan de volgende eigenschappen is voldaan:
- Reflexiviteit, dat wil zeggen een ⩽ a
- Antisymmetrie, dat wil zeggen: als a ⩽ b en b ⩽ a, dan is a = b
- Transitiviteit, dat wil zeggen, voor a ⩽ b en b ⩽ c volgt dat a ⩽ c
Zo'n relatie wordt een (losse) deelorderelatie genoemd, en de verzameling zelf wordt een gedeeltelijk geordende verzameling genoemd. Formele notatie: ⟨S, ⩽⟩.
Als het eenvoudigste voorbeeld van een gedeeltelijk geordende verzameling kunnen we de verzameling van alle natuurlijke getallen N nemen met de gebruikelijke orderelatie ⩽. Het is gemakkelijk om te verifiëren dat aan alle noodzakelijke axioma’s is voldaan.
Een betekenisvoller voorbeeld. Beschouw de verzameling van alle deelverzamelingen {1, 2, 3}, geordend op basis van de inclusierelatie ⊆. Deze relatie voldoet inderdaad aan alle voorwaarden voor gedeeltelijke ordening, dus ⟨P ({1, 2, 3}), ⊆⟩ is een gedeeltelijk geordende verzameling. Onderstaande figuur laat de structuur van deze set zien: als een element kan worden bereikt door pijlen naar een ander element, dan staan ze in een volgorderelatie.
We hebben nog twee eenvoudige definities uit de wiskunde nodig: supremum en infimum.
Definitie 3. Laat ⟨S, ⩽⟩ een gedeeltelijk geordende verzameling zijn, A ⊆ S. De bovengrens van A is een element u ∈ S zodat ∀x ∈ S: x ⩽ u. Laat U de verzameling zijn van alle bovengrenzen van S. Als er een kleinste element in U zit, dan heet dat het supremum en wordt het sup A genoemd.
Het concept van een exacte ondergrens wordt op soortgelijke wijze geïntroduceerd.
Definitie 4. Laat ⟨S, ⩽⟩ een gedeeltelijk geordende verzameling zijn, A ⊆ S. Het infimum van A is een element l ∈ S zodat ∀x ∈ S: l ⩽ x. Laat L de verzameling zijn van alle ondergrenzen van S. Als er een grootste element in L zit, dan wordt dit een infimum genoemd en aangeduid als inf A.
Beschouw als voorbeeld de bovenstaande gedeeltelijk geordende verzameling ⟨P ({1, 2, 3}), ⊆⟩ en vind daarin het supremum en infimum:
Nu kunnen we de definitie van een algebraïsch rooster formuleren.
Definitie 5. Laat ⟨P,⩽⟩ een gedeeltelijk geordende set zijn, zodat elke subset van twee elementen een boven- en ondergrens heeft. Dan wordt P een algebraïsch rooster genoemd. In dit geval wordt sup{x, y} geschreven als x ∨ y, en inf {x, y} als x ∧ y.
Laten we eens kijken of ons werkvoorbeeld ⟨P ({1, 2, 3}), ⊆⟩ een rooster is. Voor elke a, b ∈ P ({1, 2, 3}), a∨b = a∪b, en a∧b = a∩b. Beschouw bijvoorbeeld de verzamelingen {1, 2} en {1, 3} en vind hun infimum en supremum. Als we ze snijden, krijgen we de verzameling {1}, wat het infimum zal zijn. We krijgen het supremum door ze te combineren: {1, 2, 3}.
In algoritmen voor het identificeren van fysieke problemen wordt de zoekruimte vaak weergegeven in de vorm van een rooster, waarbij sets van één element (lees het eerste niveau van het zoekrooster, waar de linkerkant van de afhankelijkheden uit één attribuut bestaat) elk attribuut vertegenwoordigen. van de oorspronkelijke relatie.
Eerst beschouwen we afhankelijkheden van de vorm ∅ → Enkel attribuut. Met deze stap kunt u bepalen welke attributen primaire sleutels zijn (voor dergelijke attributen zijn er geen determinanten en daarom is de linkerkant leeg). Verder bewegen dergelijke algoritmen zich langs het rooster omhoog. Het is vermeldenswaard dat niet het hele rooster kan worden doorlopen, dat wil zeggen dat als de gewenste maximale grootte van de linkerkant aan de invoer wordt doorgegeven, het algoritme niet verder zal gaan dan een niveau met die grootte.
De onderstaande figuur laat zien hoe een algebraïsch rooster kan worden gebruikt bij het vinden van een FZ. Hier elke rand (X, XY) vertegenwoordigt een afhankelijkheid X → Y. We zijn bijvoorbeeld het eerste niveau gepasseerd en weten dat de verslaving in stand blijft EEN → B (we zullen dit weergeven als een groene verbinding tussen de hoekpunten A и B). Dit betekent dat we verder, als we langs het rooster omhoog gaan, de afhankelijkheid mogelijk niet controleren A, C → B, omdat het niet langer minimaal zal zijn. Op dezelfde manier zouden we het niet controleren als de afhankelijkheid behouden bleef C → B.
Bovendien gebruiken alle moderne algoritmen voor het zoeken naar federale wetten in de regel een datastructuur zoals een partitie (in de oorspronkelijke bron - gestripte partitie [1]). De formele definitie van een partitie is als volgt:
Definitie 6. Laat X ⊆ R een set attributen zijn voor relatie r. Een cluster is een verzameling indices van tupels in r die dezelfde waarde hebben voor X, dat wil zeggen c(t) = {i|ti[X] = t[X]}. Een partitie is een set clusters, met uitzondering van clusters met eenheidslengte:
In eenvoudige woorden: een partitie voor een attribuut X is een set lijsten, waarbij elke lijst regelnummers bevat met dezelfde waarden voor X. In de moderne literatuur wordt de structuur die partities vertegenwoordigt positielijstindex (PLI) genoemd. Clusters met een eenheidslengte zijn uitgesloten voor PLI-compressiedoeleinden, omdat het clusters zijn die alleen een recordnummer bevatten met een unieke waarde die altijd gemakkelijk te identificeren is.
Laten we eens kijken naar een voorbeeld. Laten we terugkeren naar dezelfde tabel met patiënten en partities voor de kolommen bouwen patiënt и Geslacht (aan de linkerkant is een nieuwe kolom verschenen, waarin de tabelrijnummers zijn gemarkeerd):
Bovendien, volgens de definitie, de partitie voor de kolom patiënt zal feitelijk leeg zijn, omdat afzonderlijke clusters van de partitie worden uitgesloten.
Partities kunnen worden verkregen door verschillende attributen. En er zijn twee manieren om dit te doen: door de tabel te doorlopen, een partitie te bouwen met alle benodigde attributen tegelijk, of deze te bouwen met behulp van de bewerking van het kruisen van partities met behulp van een subset van attributen. Zoekalgoritmen op federaal recht gebruiken de tweede optie.
In eenvoudige bewoordingen: om bijvoorbeeld een partitie per kolommen te krijgen ABC, waar je partities voor kunt nemen AC и B (of een andere reeks onsamenhangende deelverzamelingen) en snijden ze met elkaar. De bewerking van het kruisen van twee partities selecteert clusters met de grootste lengte die gemeenschappelijk zijn voor beide partities.
Laten we eens kijken naar een voorbeeld:
In het eerste geval ontvingen we een lege partitie. Als je goed naar de tabel kijkt, zijn er inderdaad geen identieke waarden voor de twee attributen. Als we de tabel enigszins aanpassen (het geval aan de rechterkant), krijgen we al een niet-lege kruising. Bovendien bevatten regel 1 en 2 feitelijk dezelfde waarden voor de attributen Geslacht и Dokter.
Vervolgens hebben we een concept als partitiegrootte nodig. Formeel:
Simpel gezegd is de partitiegrootte het aantal clusters in de partitie (onthoud dat afzonderlijke clusters niet in de partitie zijn opgenomen!):
Nu kunnen we een van de belangrijkste lemma’s definiëren, waarmee we voor bepaalde partities kunnen bepalen of er sprake is van een afhankelijkheid of niet:
Lemma 1. De afhankelijkheid A, B → C geldt dan en slechts dan als
Om te bepalen of er sprake is van een afhankelijkheid moeten volgens het lemma vier stappen worden uitgevoerd:
- Bereken de partitie voor de linkerkant van de afhankelijkheid
- Bereken de partitie voor de rechterkant van de afhankelijkheid
- Bereken het product van de eerste en tweede stap
- Vergelijk de afmetingen van de partities verkregen in de eerste en derde stap
Hieronder ziet u een voorbeeld van hoe wordt gecontroleerd of de afhankelijkheid geldt volgens dit lemma:
In dit artikel hebben we concepten als functionele afhankelijkheid en geschatte functionele afhankelijkheid onderzocht, gekeken waar ze worden gebruikt en welke algoritmen er bestaan voor het zoeken naar fysieke functies. We hebben ook in detail de fundamentele maar belangrijke concepten onderzocht die actief worden gebruikt in moderne algoritmen voor het zoeken naar federale wetten.
Referenties:
- Huhtala Y. et al. TANE: Een efficiënt algoritme voor het ontdekken van functionele en geschatte afhankelijkheden //Het computerjournaal. – 1999. – T. 42. – Nr. 2. – blz. 100-111.
- Kruse S., Naumann F. Efficiënte ontdekking van geschatte afhankelijkheden // Proceedings of the VLDB Endowment. – 2018. – T. 11. – Nee. 7. – blz. 759-772.
- Papenbrock T., Naumann F. Een hybride benadering van het ontdekken van functionele afhankelijkheid //Proceedings of the 2016 International Conference on Management of Data. – ACM, 2016. – blz. 821-833.
- Papenbrock T. et al. Ontdekking van functionele afhankelijkheid: een experimentele evaluatie van zeven algoritmen //Proceedings of the VLDB Endowment. – 2015. – T. 8. – Nee. 10. – blz. 1082-1093.
- Kumar A. et al. Wel of niet meedoen?: Twee keer nadenken over joins voordat functies worden geselecteerd //Proceedings of the 2016 International Conference on Management of Data. – ACM, 2016. – blz. 19-34.
- Abo Khamis M. et al. In-database leren met schaarse tensoren //Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems. – ACM, 2018. – blz. 325-340.
- Hellerstein J.M. et al. De MADlib-analysebibliotheek: of MAD-vaardigheden, de SQL //Proceedings of the VLDB Endowment. – 2012. – T. 5. – Nee. 12. – blz. 1700-1711.
- Qin C., Rusu F. Speculatieve benaderingen voor terascale gedistribueerde gradiëntdalingoptimalisatie //Proceedings of the Fourth Workshop on Data analytics in the Cloud. – ACM, 2015. – Blz. 1.
- Meng X. et al. Mllib: Machine learning in apache spark //The Journal of Machine Learning Research. – 2016. – T. 17. – Nee. 1. – blz. 1235-1241.
Auteurs van artikelen: , onderzoeker bij , и , onderzoeker bij
Bron: www.habr.com