Artikulu honetan datu-baseetako mendekotasun funtzionalei buruz hitz egingo dugu: zer diren, non erabiltzen diren eta zer algoritmo dauden aurkitzeko.
Dependentzia funtzionalak datu-base erlazionalen testuinguruan hartuko ditugu kontuan. Oso gutxi gora behera esateko, horrelako datu-baseetan informazioa taulen moduan gordetzen da. Ondoren, teoria erlazional zorrotzean trukagarriak ez diren gutxi gorabeherako kontzeptuak erabiltzen ditugu: taulari berari erlazio bat deituko diogu, zutabeei - atributuak (haien multzoa - erlazio eskema) eta errenkada-balioen multzoari atributu azpimultzo batean. - tupla bat.
Adibidez, goiko taulan, (Benson, M, M organo) atributuen tupla bat da (Pazientea, Paul, medikua).
Forma formalean, hau honela idatzita dago: [Pazientea, Generoa, Medikua] = (Benson, M, M organoa).
Orain menpekotasun funtzionalaren (FD) kontzeptua sartu dezakegu:
Definizioa 1. R erlazioak X → Y lege federala betetzen du (non X, Y ⊆ R) baldin eta baldin eta soilik tuplaren batentzat. , ∈ R-k betetzen du: bada [X] = [X], orduan [Y] = [Y]. Kasu honetan, X (atributu-multzo determinatzailea edo definitzailea) Y (menpeko multzoa) funtzionalki zehazten duela esaten dugu.
Beste era batera esanda, lege federal baten presentzia X → Y esan nahi du bi tupla baditugu R eta atributuetan bat datoz X, orduan bat egingo dute atributuetan Y.
Eta orain, ordenan. Ikus ditzagun atributuak Gaixoa и Paul horretarako haien artean menpekotasunak dauden edo ez jakin nahi dugu. Atributu multzo baterako, menpekotasun hauek egon daitezke:
- Pazientea → Generoa
- Generoa → Pazientea
Goian zehaztu bezala, lehen menpekotasunari eusteko, zutabe bakoitzaren balio bakarra Gaixoa zutabe-balio bakarrak bat etorri behar du Paul. Eta adibide-taularako hori da hain zuzen ere. Hala ere, honek ez du kontrako norabidean funtzionatzen, hau da, bigarren menpekotasuna ez da betetzen, eta atributua Paul ez da erabakigarria Gaixoa. Era berean, menpekotasuna hartzen badugu Medikua → Gaixoa, urratzen dela ikus dezakezu, balioa geroztik Robin atributu honek hainbat esanahi ditu - Ellis eta Graham.
Horrela, menpekotasun funtzionalek taula-atributu multzoen artean dauden erlazioak zehaztea ahalbidetzen dute. Hemendik aurrera loturarik interesgarrienak, edo hobeto esanda, kontuan hartuko ditugu X → Yzer diren:
- ez hutsala, hau da, mendekotasunaren eskuineko aldea ez da ezkerreko azpimultzo bat (Y ̸⊆ X);
- minimoa, hau da, ez dago halako menpekotasunik Z → YThat Z ⊂ X.
Ordura arte kontuan hartutako menpekotasunak zorrotzak ziren, hau da, ez zuten mahai gainean urraketarik ematen, baina horiez gain, tuplen balioen arteko koherentziaren bat onartzen dutenak ere badaude. Menpekotasun horiek klase bereizi batean kokatzen dira, gutxi gorabehera izenekoa, eta tupla kopuru jakin baterako urratzea onartzen da. Zenbateko hori gehienezko errore-adierazleak emax arautzen du. Adibidez, errore tasa = 0.01ek esan nahi du atributu multzoan erabilgarri dauden tuplen %1ek menpekotasuna urratu dezakeela. Hau da, 1000 erregistrotarako, gehienez 10 tuplak urratu dezakete Lege Federala. Apur bat desberdina den metrika bat hartuko dugu kontuan, konparatzen ari diren tuplen balio ezberdinetan oinarrituta. Mendekotasunagatik X → Y jarreran r honela kontsideratzen da:
Kalkula dezagun errorea Medikua → Gaixoa goiko adibidetik. Bi tupla ditugu, zeinen balioak desberdinak diren atributuan Gaixoa, baina bat datoz Medikua: [Medikua, Pazientea] = (Robin, Ellis) Eta [Medikua, Pazientea] = (Robin, Graham). Errore baten definizioaren ondoren, bikote gatazkatsu guztiak hartu behar ditugu kontuan, hau da, bi izango dira: (, ) eta bere alderantzizkoa (, ). Ordezka dezagun formulan eta lortu:
Orain saia gaitezen galderari erantzuten: "Zergatik da dena?" Izan ere, lege federalak desberdinak dira. Lehenengo mota administratzaileak datu-basearen diseinu-fasean zehazten dituen mendekotasun horiek dira. Gutxiak izan ohi dira, zorrotzak, eta aplikazio nagusia datuen normalizazioa eta erlazio-eskema diseinua da.
Bigarren mota menpekotasunak dira, "ezkutuko" datuak eta atributuen arteko harremanak lehenago ezezagunak adierazten dituztenak. Hau da, horrelako menpekotasunak ez ziren pentsatu diseinuaren garaian eta dauden datu multzorako aurkitzen dira, gero, identifikatutako hainbat lege federaletan oinarrituta, biltegiratutako informazioari buruzko edozein ondorio atera ahal izateko. Hain zuzen, menpekotasun horiekin lan egiten dugu. Datu-meatzaritzaren eremu oso batek jorratzen ditu haien oinarrian eraikitako hainbat bilaketa-teknika eta algoritmoekin. Azter dezagun edozein datutan aurkitutako mendekotasun funtzionalak (zehatzak edo gutxi gorabeherakoak) nola erabilgarriak izan daitezkeen.
Gaur egun, mendekotasunen aplikazio nagusietako bat datuen garbiketa da. “Datu zikinak” identifikatzeko eta gero zuzentzeko prozesuak garatzea dakar. "Datu zikinen" adibide nabarmenak bikoiztuak, datu-akatsak edo akatsak, falta diren balioak, datu zaharkituak, espazio gehigarriak eta antzekoak dira.
Datu-errore baten adibidea:
Datu bikoiztuen adibidea:
Adibidez, exekutatu beharreko taula eta lege federal multzo bat ditugu. Datuen garbiketak kasu honetan datuak aldatzea dakar, Lege Federalak zuzenak izan daitezen. Kasu honetan, aldaketa-kopurua minimoa izan behar da (prozedura honek algoritmo propioak ditu, artikulu honetan arreta jarriko ez ditugunak). Jarraian, datu-eraldaketa horren adibide bat dago. Ezkerrean jatorrizko erlazioa dago, zeinetan, bistan denez, beharrezko FLak betetzen ez diren (FLren baten urraketaren adibide bat gorriz nabarmentzen da). Eskuinean eguneratutako erlazioa dago, gelaxka berdeek aldatutako balioak erakutsiz. Prozedura honen ostean, beharrezko mendekotasunak mantentzen hasi ziren.
Beste aplikazio ezagun bat datu-baseen diseinua da. Hemen forma normalak eta normalizazioa gogoratzea merezi du. Normalizazioa erlazio bat baldintza-multzo jakin batekin bat etortzeko prozesua da, eta horietako bakoitza forma normalak bere erara definitzen du. Ez ditugu hainbat forma arrunten eskakizunak deskribatuko (hasiberrientzako datu-baseko ikastaroko edozein liburutan egiten da), baina ohartuko gara bakoitzak bere erara erabiltzen duela mendekotasun funtzionalaren kontzeptua. Azken finean, FLak berez datu-base bat diseinatzerakoan kontuan hartzen diren osotasun mugak dira (zeregin honen testuinguruan, FLak supergakoak deitzen dira batzuetan).
Azter dezagun beheko irudiko lau forma normaletarako duten eskaera. Gogoratu Boyce-Codd forma normala hirugarren forma baino zorrotzagoa dela, baina laugarrena baino zorrotzagoa dela. Azken hau ez dugu kontuan hartzen oraingoz, bere formulazioak balio anitzeko menpekotasunak ulertzea eskatzen baitu, artikulu honetan interesgarriak ez zaizkigunak.
Mendekotasunek beren aplikazioa aurkitu duten beste eremu bat ezaugarri-espazioaren dimentsioa murriztea da Bayes-en sailkatzaile inozoa eraikitzea, ezaugarri esanguratsuak identifikatzea eta erregresio-eredu bat erreparametrizatzea bezalako zereginetan. Jatorrizko artikuluetan, zeregin horri erredundantearen eta ezaugarrien garrantziaren determinazioa deitzen zaio [5, 6], eta datu-baseen kontzeptuen erabilera aktiboarekin konpontzen da. Horrelako lanen etorrerarekin, esan dezakegu gaur egun datu-basea, analisia eta goiko optimizazio-arazoen ezarpena tresna batean konbinatzeko aukera ematen duten irtenbideen eskaera dagoela [7, 8, 9].
Algoritmo asko daude (modernoak eta ez hain modernoak) datu multzo batean lege federalak bilatzeko. Algoritmo hauek hiru taldetan bana daitezke:
- Sare aljebraikoen zeharkaldia erabiltzen duten algoritmoak (Lattice traversal algorithms)
- Adostutako balioen bilaketan oinarritutako algoritmoak (Algoritmo ezberdinen eta adostasun-multzoak)
- Bikoteka konparaketetan oinarritutako algoritmoak (Mendekotasunaren indukzio algoritmoak)
Algoritmo mota bakoitzaren deskribapen laburra beheko taulan aurkezten da:
Sailkapen honi buruz gehiago irakur dezakezu [4]. Jarraian, mota bakoitzerako algoritmoen adibideak daude:
Gaur egun, dependentzia funtzionalak aurkitzeko hainbat ikuspegi konbinatzen dituzten algoritmo berriak agertzen ari dira. Algoritmo horien adibideak Pyro [2] eta HyFD [3] dira. Haien lanaren analisia espero da sail honetako hurrengo artikuluetan. Artikulu honetan dependentzia detektatzeko teknikak ulertzeko beharrezkoak diren oinarrizko kontzeptuak eta lema soilik aztertuko ditugu.
Has gaitezen sinple batekin - desberdintasuna- eta adostasun-multzoa, bigarren algoritmo motan erabiltzen dena. Diferentzia-multzoa balio berdina ez duten tupla multzoa da, eta ados-multzoa, berriz, balio berdina duten tuplak dira. Azpimarratzekoa da kasu honetan menpekotasunaren ezkerreko aldea soilik kontuan hartzen ari garela.
Goian topatu zen beste kontzeptu garrantzitsu bat sare aljebraikoa da. Algoritmo moderno askok kontzeptu honekin funtzionatzen dutenez, zer den ideia bat izan behar dugu.
Sarearen kontzeptua sartzeko, partzialki ordenatutako multzoa (edo partzialki ordenatutako multzoa, poset gisa laburtua) definitu behar da.
Definizioa 2. S multzo bat ⩽ erlazio bitarraren arabera partzialki ordenatuta dagoela esaten da a, b, c ∈ S guztietarako propietate hauek betetzen badira:
- Erreflexibitatea, hau da, a ⩽ a
- Antisimetria, hau da, a ⩽ b eta b ⩽ a bada, orduan a = b
- Iragankortasuna, hau da, a ⩽ b eta b ⩽ c-entzat a ⩽ c
Erlazio horri ordena partzialeko erlazio (soltea) deitzen zaio, eta multzoari berari partzialki ordenatua deritzo. Adierazpen formala: ⟨S, ⩽⟩.
Partzialki ordenatutako multzo baten adibiderik errazena den aldetik, N zenbaki natural guztien multzoa har dezakegu ⩽ ohiko ordena erlazioarekin. Erraza da egiaztatzea beharrezko axioma guztiak betetzen direla.
Adibide esanguratsuagoa. Demagun {1, 2, 3} azpimultzo guztien multzoa, ⊆ inklusio erlazioaren arabera ordenatuta. Izan ere, erlazio honek ordena partzialaren baldintza guztiak betetzen ditu, beraz ⟨P ({1, 2, 3}), ⊆⟩ partzialki ordenatutako multzoa da. Beheko irudiak multzo honen egitura erakusten du: elementu batera gezien bidez beste elementu batera irits badaiteke, orduan ordena erlazioan daude.
Matematika arloko bi definizio sinple gehiago beharko ditugu - supremum eta infimum-.
Definizioa 3. Izan bedi ⟨S, ⩽⟩ partzialki ordenatutako multzo bat, A ⊆ S. A-ren goiko muga u ∈ S elementu bat da, ∀x ∈ S: x ⩽ u. Izan bedi U S-ren goi-muga guztien multzoa. U-n elementurik txikiena baldin badago, supremum deritzo eta sup A adierazten da.
Beheko muga zehatzaren kontzeptua antzera sartzen da.
Definizioa 4. Izan bedi ⟨S, ⩽⟩ partzialki ordenatutako multzo bat, A ⊆ S. A-ren infimoa l ∈ S elementu bat da, ∀x ∈ S: l ⩽ x. Izan bedi L S-ren behe-muga guztien multzoa. L-en elementurik handiena baldin badago, infimo deritzo eta inf A bezala adierazten da.
Demagun adibide gisa goiko partzialki ordenatutako multzoa ⟨P ({1, 2, 3}), ⊆⟩ eta aurkitu bertan supremum eta infimum:
Orain sare aljebraikoaren definizioa formula dezakegu.
Definizioa 5. Izan bedi ⟨P,⩽⟩ partzialki ordenatutako multzo bat, bi elementuko azpimultzo bakoitzak goiko eta beheko muga bat izan dezan. Orduan P sare aljebraiko deritzo. Kasu honetan, sup{x, y} x ∨ y gisa idazten da eta inf {x, y} x ∧ y gisa.
Egiaztatu dezagun gure lan-adibidea ⟨P ({1, 2, 3}), ⊆⟩ sare bat dela. Izan ere, edozein a, b ∈ P ({1, 2, 3}), a∨b = a∪b eta a∧b = a∩b. Adibidez, kontuan hartu {1, 2} eta {1, 3} multzoak eta aurkitu haien infimo eta supremum. Ebakitzen baditugu, {1} multzoa lortuko dugu, infimoa izango dena. Supremuma lortzen dugu horiek konbinatuz - {1, 2, 3}.
Arazo fisikoak identifikatzeko algoritmoetan, bilaketa-espazioa sare baten moduan irudikatzen da sarritan, non elementu baten multzoak (irakur ezazu bilaketa-sarearen lehen maila, non mendekotasunen ezkerraldea atributu batez osatuta dagoen) atributu bakoitza adierazten baitu. jatorrizko erlazioarena.
Lehenik eta behin, ∅ → formako menpekotasunak kontuan hartuko ditugu Atributu bakarra. Urrats honek gako nagusiak zein atributu diren zehaztea ahalbidetzen du (halako atributuetarako ez dago determinatzailerik, eta, beraz, ezkerraldea hutsik dago). Gainera, halako algoritmoak gora egiten dute sarean zehar. Azpimarratzekoa da sare osoa ezin dela zeharkatu, hau da, ezkerreko aldean nahi den tamaina maximoa sarrerara pasatzen bada, orduan algoritmoa ez da tamaina horrekin maila bat baino urrunago joango.
Beheko irudian sare aljebraiko bat FZ bat aurkitzeko arazoan nola erabil daitekeen erakusten da. Hemen ertz bakoitza (X, XY) mendekotasuna adierazten du X → Y. Esaterako, lehen maila gainditu dugu eta badakigu menpekotasuna mantentzen dela A → B (Hau erpinen arteko konexio berde gisa bistaratuko dugu A и B). Horrek esan nahi du, gainera, sarean gora goazenean, agian ez dugula menpekotasuna egiaztatu A, C → B, jada ez baita minimoa izango. Era berean, ez genuke egiaztatuko menpekotasuna mantenduko balitz C → B.
Gainera, oro har, lege federalak bilatzeko algoritmo moderno guztiek datu-egitura bat erabiltzen dute, hala nola partizioa (jatorrizko iturrian - kendutako partizioa [1]). Partizio baten definizio formala honako hau da:
Definizioa 6. Izan bedi X ⊆ R r erlaziorako atributu multzo bat. Kluster bat X-ren balio bera duten r-ko tuplaen indizeen multzoa da, hau da, c(t) = {i|ti[X] = t[X]}. Partizioa kluster multzo bat da, luzera unitateko klusterrak kenduta:
Hitz sinpleetan, atributu baten partizioa X zerrenda multzo bat da, non zerrenda bakoitzak balio bereko lerro-zenbakiak dituen X. Literatura modernoan, partizioak adierazten dituen egiturari posizio zerrendaren indizea (PLI) deitzen zaio. Unitate-luzera-klusterrak PLI konpresio-helburuetarako baztertzen dira, beti identifikatzeko erraza izango den balio esklusiboko erregistro-zenbaki bat baino ez duten klusterrak direlako.
Ikus dezagun adibide bat. Itzuli gaitezen mahai berera eta eraiki gaitezen zutabeetarako partizioak Gaixoa и Paul (ezkerrean zutabe berri bat agertu da, eta bertan taulako errenkada-zenbakiak markatuta daude):
Gainera, definizioaren arabera, zutabearen partizioa Gaixoa benetan hutsik egongo da, kluster bakarrak partiziotik kanpo geratzen baitira.
Partizioak hainbat atributuren bidez lor daitezke. Eta horretarako bi modu daude: taulatik pasatuz, partizio bat eraiki behar diren atributu guztiak aldi berean erabiliz, edo partizioen ebakidura eragiketa erabiliz, atributu azpimultzo bat erabiliz. Lege federalaren bilaketa-algoritmoek bigarren aukera erabiltzen dute.
Hitz sinpleetan, adibidez, zutabeen araberako partizioa lortzeko ABC, partizioak har ditzakezu AC и B (edo beste edozein azpimultzo disjuntuen) eta elkar ebaki. Bi partizioen gurutzaketaren eragiketak bi partizioetarako komunak diren luzera handieneko multzoak hautatzen ditu.
Ikus dezagun adibide bat:
Lehenengo kasuan, partizio huts bat jaso genuen. Taulari arretaz begiratuz gero, ez dago bi atributuentzako balio berdin-berdinak. Taula apur bat aldatzen badugu (eskuineko kasua), jada hutsik gabeko elkargune bat lortuko dugu. Gainera, 1 eta 2 lerroek benetan balio berdinak dituzte atributuetarako Paul и medikua.
Ondoren, partizioaren tamaina bezalako kontzeptu bat beharko dugu. Formalki:
Besterik gabe, partizioaren tamaina partizioan sartutako kluster kopurua da (gogoratu kluster bakarrak ez daudela partizioan sartzen!):
Orain lema gakoetako bat definitu dezakegu, partizio jakin batzuetarako menpekotasun bat mantentzen den ala ez zehazteko:
1. lema. A, B → C menpekotasuna baldin eta bada bakarrik betetzen da
Lemaren arabera, mendekotasuna betetzen den zehazteko, lau urrats egin behar dira:
- Kalkulatu mendekotasunaren ezkerraldeko partizioa
- Kalkulatu mendekotasunaren eskuineko partizioa
- Kalkulatu lehen eta bigarren urratsaren produktua
- Alderatu lehenengo eta hirugarren urratsetan lortutako partizioen tamainak
Jarraian, mendekotasuna lema honen arabera betetzen den egiaztatzeko adibide bat dago:
Artikulu honetan, mendekotasun funtzionala, gutxi gorabeherako mendekotasun funtzional bezalako kontzeptuak aztertu ditugu, non erabiltzen diren aztertu dugu, baita funtzio fisikoak bilatzeko zer algoritmo dauden ere. Lege federalak bilatzeko algoritmo modernoetan aktiboki erabiltzen diren oinarrizko baina garrantzitsuak diren kontzeptuak ere zehatz-mehatz aztertu ditugu.
Erreferentziak:
- Huhtala Y. et al. TANE: Dependentzia funtzionalak eta gutxi gorabeherakoak ezagutzeko algoritmo eraginkorra //The computer journal. – 1999. – T. 42. – zk. 2. – 100-111 orr.
- Kruse S., Naumann F. Gutxi gorabeherako dependentzien aurkikuntza eraginkorra // Proceedings of the VLDB Endowment. – 2018. – T. 11. – zk. 7. – 759-772 orr.
- Papenbrock T., Naumann F. A hybrid approach to functional dependency discovery // Datuen kudeaketari buruzko 2016ko Nazioarteko Konferentziaren aktak. – ACM, 2016. – 821-833 or.
- Papenbrock T. et al. Mendekotasun funtzionalaren aurkikuntza: zazpi algoritmoen ebaluazio esperimentala //VLDB Endowment-aren aktak. – 2015. – T. 8. – Ez. 10. – 1082-1093 orr.
- Kumar A. et al. Sartu ala ez batu?: Bi aldiz pentsatu elkartzeetan ezaugarriak hautatu aurretik //Datuen Kudeaketari buruzko 2016ko Nazioarteko Konferentziaren aktak. – ACM, 2016. – 19-34 or.
- Abo Khamis M. et al. Datu-baseko ikaskuntza tentsore eskasekin //Datubase Sistemen Printzipioei buruzko ACM SIGMOD-SIGACT-SIGAI 37. Jardunaldiak. – ACM, 2018. – 325-340 or.
- Hellerstein JM et al. MADlib analitika liburutegia: edo MAD trebetasunak, SQL //VLDB Endowment-aren izapideak. – 2012. – T. 5. – Ez. 12. – 1700-1711 orr.
- Qin C., Rusu F. Especulative aproximations for terascale distributed gradient descent optimization //Datuen analisia Hodeian laugarren Tailerren Aktak. – ACM, 2015. – 1. or.
- Meng X. et al. Mllib: Machine learning in apache spark //The Journal of Machine Learning Research. – 2016. – T. 17. – zk. 1. – 1235-1241 orr.
Artikuluaren egileak: , at ikertzailea , и , at ikertzailea
Iturria: www.habr.com