In hierdie artikel sal ons praat oor funksionele afhanklikhede in databasisse - wat dit is, waar dit gebruik word en watter algoritmes bestaan om dit te vind.
Ons sal funksionele afhanklikhede in die konteks van relasionele databasisse oorweeg. Om baie rofweg te praat, in sulke databasisse word inligting in die vorm van tabelle gestoor. Vervolgens gebruik ons benaderde konsepte wat nie uitruilbaar is in streng relasionele teorie nie: die tabel self sal 'n relasie genoem word, die kolomme sal eienskappe genoem word (hul stel is 'n relasieskema), en die stel rywaardes op 'n subset van eienskappe sal 'n tupel genoem word.
Byvoorbeeld, in die tabel hierbo, (Benson, M, Morgan) is 'n tupel volgens eienskappe (Pasiënt, Paul, Dokter).
Meer formeel word dit soos volg geskryf: [Pasiënt, Paul, Dokter]= (Benson, M, Morgan).
Nou kan ons die konsep van funksionele afhanklikheid (FC) bekendstel:
Definisie 1. Die verhouding R voldoen aan die FD X → Y (waar X, Y ⊆ R) indien en slegs indien vir enige tupels , ∈ R is tevrede: indien [x]= [X], dan [Y] = [Y]. In so 'n geval word gesê dat X (die determinant of definiërende stel eienskappe) Y (die afhanklike versameling) funksioneel bepaal.
Met ander woorde, die teenwoordigheid van 'n federale wet X→Y beteken dat as ons twee tupels in het R en hulle pas in eienskappe X, dan sal hulle ook ooreenstem met eienskappe Y.
En nou in orde. Oorweeg eienskappe Geduldig и Пол waarvoor ons wil weet of daar afhanklikhede tussen hulle is of nie. Vir so 'n stel eienskappe kan die volgende afhanklikhede bestaan:
- Pasiënt → Geslag
- Geslag → Pasiënt
Volgens die definisie hierbo, om die eerste afhanklikheid te behou, elke unieke waarde van die kolom Geduldig slegs een kolomwaarde moet ooreenstem Пол. En vir die voorbeeldtabel is dit waar. Dit werk egter nie in die teenoorgestelde rigting nie, dit wil sê, die tweede afhanklikheid word nie vervul nie, en die eienskap Пол is nie 'n determinant vir Geduldig. Net so, as ons die afhanklikheid neem Dokter → Pasiënt, kan jy sien dat dit geskend word, aangesien die waarde Robin op hierdie kenmerk het verskeie verskillende waardes - Ellis en Graham.
Dus, funksionele afhanklikhede laat jou toe om die bestaande verwantskappe tussen die stelle tabelkenmerke te bepaal. Van hier af en voortaan sal ons die interessantste verbande, of liewer, sulke, oorweeg X→Ywat hulle is:
- nie-triviaal, dit wil sê die regterkant van die afhanklikheid is nie 'n subset van die linkerkant nie (Y ⊆ X);
- minimaal, dit wil sê, daar is nie so 'n afhanklikheid nie Z → YWat Z ⊂ X.
Die afhanklikhede wat tot op hierdie stadium oorweeg is, was streng, dit wil sê, hulle het nie voorsiening gemaak vir enige oortredings op die tafel nie, maar benewens hulle, is daar ook diegene wat 'n mate van teenstrydigheid tussen die waardes van die tupels toelaat. Sulke afhanklikhede word uitgeneem in 'n aparte klas, genaamd benaderde, en dit word toegelaat om op 'n sekere aantal tupels geskend te word. Hierdie getal word aangepas deur die maksimum foutaanwyser emax. Byvoorbeeld, die foutkoers = 0.01 kan beteken dat die afhanklikheid geskend kan word deur 1% van die beskikbare tupels op die oorweegde stel eienskappe. Dit wil sê, vir 1000 rekords kan 'n maksimum van 10 tupels die Federale Wet oortree. Ons sal 'n effens ander maatstaf oorweeg gebaseer op paarsgewys verskillende waardes van die vergelykende tupels. Vir verslawing X→Y in verhouding r dit tel so:
Kom ons bereken die fout vir Dokter → Pasiënt uit die voorbeeld hierbo. Ons het twee tupels waarvan die waardes verskil op die eienskap Geduldig, maar saamval met dokter: [Dokter, pasiënt] = (Robin, Ellis) En [Dokter, pasiënt] = (Robin, Graham). Na aanleiding van die definisie van 'n fout, moet ons alle botsende pare in ag neem, wat beteken dat daar twee van hulle sal wees:(, ) en sy omgekeerde (, ). Vervang in die formule en kry:
En nou probeer ons die vraag beantwoord: "Hoekom is dit alles?". Trouens, die FZ is anders. Die eerste tipe is daardie afhanklikhede wat deur die administrateur in die databasisontwerpstadium gedefinieer word. Daar is gewoonlik min, hulle is streng, en die hooftoepassing is datanormalisering en verhoudingskema-ontwerp.
Die tweede tipe is afhanklikhede wat "versteekte" data en voorheen onbekende verwantskappe tussen eienskappe verteenwoordig. Dit wil sê, sulke afhanklikhede is nie gedink ten tyde van die ontwerp nie en dit word reeds gevind vir die bestaande datastel, sodat later, gebaseer op die stel geïdentifiseerde FD's, enige gevolgtrekkings oor die gestoorde inligting gemaak kan word. Dit is met sulke afhanklikhede dat ons werk. Hulle is besig met 'n hele veld van data-ontginning met verskeie soektegnieke en algoritmes wat op hul basis gebou is. Kom ons vind uit hoe die gevind funksionele afhanklikhede (presies of benaderd) in enige data nuttig kan wees.
Vandag, onder die hoofareas van toepassing van afhanklikhede, word dataskoonmaak onderskei. Dit behels die ontwikkeling van prosesse om "vuil data" te identifiseer en dan reg te stel. Helder verteenwoordigers van "vuil data" is duplikate, datafoute of tikfoute, ontbrekende waardes, verouderde data, ekstra spasies, en dies meer.
Data fout voorbeeld:
Voorbeeld van duplikate in data:
Ons het byvoorbeeld 'n tabel en 'n stel federale wette wat nagekom moet word. Data skoonmaak behels in hierdie geval die verandering van die data op so 'n manier dat die federale wette waar word. In hierdie geval moet die aantal wysigings minimaal wees (daar is algoritmes vir hierdie prosedure, waarop ons nie in hierdie artikel sal fokus nie). Hieronder is 'n voorbeeld van so 'n datatransformasie. Aan die linkerkant is die aanvanklike verhouding, waarin natuurlik nie aan die nodige FL's voldoen word nie ('n voorbeeld van 'n oortreding van een van die FL's word in rooi uitgelig). Aan die regterkant is die opgedateerde verhouding, met groen selle wat die veranderde waardes wys. Nadat so 'n prosedure uitgevoer is, is begin om die nodige afhanklikhede in stand te hou.
Nog 'n gewilde toepassingsarea is databasisontwerp. Hier is dit die moeite werd om te onthou oor normale vorms en normalisering. Normalisering is die proses om 'n verhouding in ooreenstemming te bring met een of ander stel vereistes, wat elkeen op sy eie manier deur die normale vorm gedefinieer word. Ons sal nie die vereistes van verskeie normale vorms beskryf nie (dit word in enige boek oor die databasiskursus vir beginners gedoen), maar net daarop let dat elkeen van hulle die konsep van funksionele afhanklikhede op sy eie manier gebruik. FD's is immers inherent integriteitsbeperkings wat in ag geneem word wanneer 'n databasis ontwerp word (in die konteks van hierdie taak word FD's soms supersleutels genoem).
Oorweeg hul aansoek vir die vier normale vorms in die prent hieronder. Onthou dat die Boyce-Codd-normale vorm strenger is as die derde vorm, maar minder streng as die vierde. Ons oorweeg laasgenoemde nog nie, aangesien die formulering daarvan 'n begrip van baie-waarde afhanklikhede vereis, wat nie vir ons in hierdie artikel van belang is nie.
Nog 'n gebied waarin afhanklikhede hul weg gevind het, is om die dimensie van die kenmerkruimte te verminder in probleme soos die bou van 'n naïewe Bayes-klassifiseerder, onttrekking van betekenisvolle kenmerke en herparametrisering van 'n regressiemodel. In die oorspronklike artikels word hierdie probleem die bepaling van oortollige kenmerke (kenmerkoortolligheid) en relevant (kenmerkrelevansie) genoem [5, 6], en dit word opgelos met die aktiewe gebruik van databasiskonsepte. Met die verskyning van sulke werke kan ons sê dat daar vandag 'n vraag is na oplossings wat dit moontlik maak om die databasis, analise en die implementering van bogenoemde optimaliseringsprobleme in een instrument te kombineer [7, 8, 9].
Daar is baie algoritmes (beide modern en nie baie modern nie) om na FD in 'n datastel te soek. Sulke algoritmes kan in drie groepe verdeel word:
- Roosterdeurkruisalgoritmes
- Algoritmes gebaseer op die soeke na konsekwente waardes (Verskil- en ooreenkoms-stel algoritmes)
- Algoritmes gebaseer op paarsgewyse vergelykings (Afhanklikheidsinduksiealgoritmes)
'n Kort beskrywing van elke tipe algoritme word in die tabel hieronder aangebied:
Meer besonderhede oor hierdie klassifikasie kan gevind word in [4]. Hieronder is voorbeelde van algoritmes vir elke tipe:
Tans kom nuwe algoritmes na vore wat verskeie benaderings kombineer om funksionele afhanklikhede tegelyk te vind. Voorbeelde van sulke algoritmes is Pyro [2] en HyFD [3]. 'n Ontleding van hul werk word in die volgende artikels van hierdie reeks verwag. In hierdie artikel gaan ons slegs die basiese konsepte en lemma ontleed wat nodig is om die tegnieke vir die identifisering van afhanklikhede te verstaan.
Kom ons begin met 'n eenvoudige een - verskil- en stem-stel, wat in die tweede tipe algoritmes gebruik word. Difference-set is 'n stel tupels wat nie ooreenstem in waarde nie, en ooreenstem-stel, inteendeel, is tupels wat ooreenstem in waarde. Daar moet kennis geneem word dat ons in hierdie geval slegs die linkerkant van die afhanklikheid oorweeg.
Ook 'n belangrike konsep wat hierbo teëgekom is, is die algebraïese rooster. Aangesien baie moderne algoritmes op hierdie konsep werk, moet ons 'n idee hê van wat dit is.
Om die konsep van 'n rooster bekend te stel, is dit nodig om 'n gedeeltelik geordende versameling (of gedeeltelik geordende versameling, of kortweg poset) te definieer.
Definisie 2. Daar word gesê dat 'n versameling S gedeeltelik georden word deur 'n binêre relasie ⩽ as die volgende eienskappe geld vir enige a, b, c ∈ S:
- Refleksiwiteit, dit wil sê a ⩽ a
- Antisimmetrie, dit wil sê as a ⩽ b en b ⩽ a, dan is a = b
- Transitiwiteit, dit wil sê vir a ⩽ b en b ⩽ c, volg dit dat a ⩽ c
So 'n verhouding word 'n verhouding van (nie-streng) gedeeltelike orde genoem, en die versameling self word 'n gedeeltelik geordende versameling genoem. Formele notasie: ⟨S, ⩽⟩.
As die eenvoudigste voorbeeld van 'n gedeeltelik-geordende versameling, kan ons die versameling van alle natuurlike getalle N neem met die gewone ordeverhouding ⩽. Dit is maklik om te kontroleer dat al die nodige aksiomas bevredig is.
Meer betekenisvolle voorbeeld. Beskou die versameling van alle subversamelings {1, 2, 3} gerangskik volgens die insluitingsverhouding ⊆. Inderdaad, hierdie verhouding voldoen aan alle gedeeltelike orde voorwaardes, dus ⟨P ({1, 2, 3}), ⊆⟩ is 'n gedeeltelik geordende versameling. Die figuur hieronder toon die struktuur van hierdie stel: as dit van een element moontlik is om langs die pyle na 'n ander element te loop, dan is hulle in 'n verhouding van orde.
Ons benodig nog twee eenvoudige definisies uit die veld van wiskunde - supremum (supremum) en infimum (infimum).
Definisie 3. Laat ⟨S, ⩽⟩ 'n poset wees, A ⊆ S. Die boonste grens van A is 'n element u ∈ S sodat ∀x ∈ S: x ⩽ u. Laat U die versameling van alle boonste grense van S wees. As U 'n kleinste element het, word dit die supremum genoem en as sup A aangedui.
Die idee van presiese ondergrens word op soortgelyke wyse bekendgestel.
Definisie 4. Laat ⟨S, ⩽⟩ 'n poset wees, A ⊆ S. Die ondergrens van A is 'n element l ∈ S sodat ∀x ∈ S: l ⩽ x. Laat L die versameling van alle ondergrense van S wees. As daar 'n grootste element in L is, word dit 'n infimum genoem en word dit as inf A aangedui.
As 'n voorbeeld, oorweeg die gedeeltelik-geordende versameling hierbo ⟨P ({1, 2, 3}), ⊆⟩ en vind die supremum en infimum daarin:
Nou kan ons die definisie van 'n algebraïese rooster formuleer.
Definisie 5. Laat ⟨P, ⩽⟩ 'n poset wees sodat elke twee-element subset skerp boonste en onderste grense het. Dan word P 'n algebraïese rooster genoem. In hierdie geval word sup{x, y} geskryf as x ∨ y, en inf {x, y} as x ∧ y.
Kom ons kyk dat ons werkvoorbeeld ⟨P ({1, 2, 3}), ⊆⟩ 'n rooster is. Inderdaad, vir enige a, b ∈ P ({1, 2, 3}), a∨b = a∪b en a∧b = a∩b. Beskou byvoorbeeld die stelle {1, 2} en {1, 3} en vind hul infimum en supremum. As ons hulle sny, kry ons die stel {1}, wat die infimum sal wees. Die oppergesag word verkry deur hul vakbond - {1, 2, 3}.
In FD-opsporingsalgoritmes word die soekruimte dikwels in die vorm van 'n rooster voorgestel, waar stelle van een element (lees die eerste vlak van die soekrooster, waar die linkerkant van die afhanklikhede uit een kenmerk bestaan) elke eienskap van die oorspronklike verhouding.
Aan die begin, afhanklikhede van die vorm ∅ → enkele kenmerk. Hierdie stap laat jou toe om te bepaal watter eienskappe primêre sleutels is (daar is geen determinante vir sulke eienskappe nie, en daarom is die linkerkant leeg). Verder beweeg sulke algoritmes op die rooster. Terselfdertyd is dit opmerklik dat nie die hele rooster omseil kan word nie, dit wil sê as die gewenste maksimum grootte van die linkerkant na die invoer oorgedra word, sal die algoritme nie verder gaan as die vlak met hierdie grootte nie.
Die figuur hieronder wys hoe jy die algebraïese rooster kan gebruik in die probleem om na 'n FD te soek. Hier, elke rand (X, XY) verteenwoordig die afhanklikheid X→Y. Ons het byvoorbeeld die eerste vlak geslaag en ons weet dat die afhanklikheid gehou word A→B (ons sal dit vertoon met 'n groen verband tussen die hoekpunte A и B). So verder, wanneer ons op die rooster beweeg, kan ons nie die afhanklikheid nagaan nie A, C → B, want dit sal nie meer minimaal wees nie. Net so sal ons dit nie nagaan as die afhanklikheid gehou word nie C→B.
Daarbenewens, as 'n reël, gebruik alle moderne algoritmes om na FD's te soek so 'n datastruktuur as 'n partisie (in die oorspronklike bron - gestroopte partisie [1]). Die formele definisie van 'n partisie is soos volg:
Definisie 6. Laat X ⊆ R 'n stel eienskappe vir verhouding r wees. 'n Tros is 'n stel indekse van tupels vanaf r wat dieselfde waarde vir X het, dit wil sê c(t) = {i|ti[X] = t[X]}. 'n Partisie is 'n stel trosse, uitgesluit trosse van eenheidslengte:
In eenvoudige terme, 'n partisie vir 'n kenmerk X is 'n stel lyste, waar elke lys reëlnommers bevat met dieselfde waardes vir X. In moderne literatuur word 'n struktuur wat partisies verteenwoordig 'n posisielysindeks (PLI) genoem. Enkellengte-klusters word uitgesluit vir PLI-kompressiedoeleindes omdat dit trosse is wat slegs 'n rekordnommer bevat met 'n unieke waarde wat altyd maklik sal wees om te stel.
Oorweeg 'n voorbeeld. Kom ons keer terug na dieselfde tabel met pasiënte en bou afskortings vir die kolomme Geduldig и Пол ('n nuwe kolom het aan die linkerkant verskyn, waarin die rynommers van die tabel gemerk is):
In hierdie geval, volgens die definisie, die partisie vir die kolom Geduldig sal eintlik leeg wees, aangesien enkelklusters van die partisie uitgesluit word.
Afskortings kan verkry word deur verskeie eienskappe. En hiervoor is daar twee maniere: deur deur die tabel te loop, bou 'n partisie op een slag deur al die nodige eienskappe, of bou dit deur gebruik te maak van die kruising van partisies deur 'n subset van eienskappe. FD-soekalgoritmes gebruik die tweede opsie.
In eenvoudige woorde, byvoorbeeld, om 'n partisie deur kolomme te kry ABC, jy kan partisies neem vir AC и B (of enige ander stel onsamehangende subversamelings) en sny hulle met mekaar. Die operasie om twee partisies te kruis, kies die trosse van die grootste lengte wat gemeen is aan beide partisies.
Kom ons kyk na 'n voorbeeld:
In die eerste geval het ons 'n leë partisie gekry. As jy noukeurig na die tabel kyk, dan is daar inderdaad geen identiese waardes vir twee eienskappe nie. As ons die tabel effens verander (die geval aan die regterkant), dan sal ons reeds 'n nie-leë kruising kry. Terselfdertyd bevat reëls 1 en 2 werklik dieselfde waardes vir eienskappe Пол и dokter.
Vervolgens benodig ons so 'n konsep soos die grootte van die partisie. Formeel:
Eenvoudig gestel, die partisiegrootte is die aantal trosse wat in die partisie ingesluit is (onthou dat enkele trosse nie by die partisie ingesluit is nie!):
Nou kan ons een van die sleutellemmas definieer, wat, vir gegewe partisies, ons toelaat om te bepaal of die afhanklikheid gehou word of nie:
Lemma 1. Afhanklikheid A, B → C word gehou as en slegs as
Volgens die lemma is daar vier stappe om te bepaal of 'n afhanklikheid gehou word:
- Bereken partisie vir linkerkant van afhanklikheid
- Bereken die partisie vir die regterkant van die afhanklikheid
- Bereken die produk van die eerste en tweede stappe
- Vergelyk die partisiegroottes wat in die eerste en derde stap verkry is
Hieronder is 'n voorbeeld om te kontroleer of die afhanklikheid deur hierdie lemma gehou word:
In hierdie artikel het ons konsepte soos funksionele afhanklikheid, benaderde funksionele afhanklikheid ontleed, ondersoek waar dit gebruik word, en ook watter algoritmes om na FD te soek bestaan. Ons het ook die basiese, maar belangrike konsepte wat aktief in moderne algoritmes gebruik word om na FD's te soek, in detail ontleed.
Skakels na literatuur:
- Huhtala Y. et al. TANE: 'n Doeltreffende algoritme om funksionele en benaderde afhanklikhede te ontdek //Die rekenaarjoernaal. - 1999. - T. 42. - No. 2. - S. 100-111.
- Kruse S., Naumann F. Doeltreffende ontdekking van benaderde afhanklikhede // Proceedings of the VLDB Endowment. - 2018. - T. 11. - Nee. 7. - S. 759-772.
- Papenbrock T., Naumann F. 'n Hibriede benadering tot funksionele afhanklikheid-ontdekking // Proceedings of the 2016 International Conference on Management of Data. - ACM, 2016. - P. 821-833.
- Papenbrock T. et al. Funksionele afhanklikheidsontdekking: 'n Eksperimentele evaluering van sewe algoritmes //Proceedings of the VLDB Endowment. - 2015. - T. 8. - Nee. 10. - S. 1082-1093.
- Kumar A. et al. Om aan te sluit of nie om aan te sluit nie?: Dink twee keer oor aansluitings voor kenmerkkeuse //Verrigtinge van die 2016 Internasionale Konferensie oor Bestuur van Data. - ACM, 2016. - S. 19-34.
- Abo Khamis M. et al. In-databasisleer met yl tensors //Verrigtinge van die 37ste ACM SIGMOD-SIGACT-SIGAI Simposium oor Beginsels van Databasisstelsels. - ACM, 2018. - P. 325-340.
- Hellerstein JM et al. Die MADlib-ontledingsbiblioteek: of MAD-vaardighede, die SQL //Proceedings of the VLDB Endowment. - 2012. - V. 5. - No. 12. - S. 1700-1711.
- Qin C., Rusu F. Spekulatiewe benaderings vir teraskaal verspreide gradiënt-afkomsoptimering // Verrigtinge van die vierde werkswinkel oor data-analise in die wolk. - ACM, 2015. - Bl. 1.
- Meng X. et al. Mllib: Masjienleer in apache vonk //The Journal of Machine Learning Research. - 2016. - T. 17. - No. 1. - S. 1235-1241.
Artikel skrywers: , navorser in , и , navorser in
Bron: will.com