Enkonduko al Funkciaj Dependecoj

En ĉi tiu artikolo ni parolos pri funkciaj dependecoj en datumbazoj - kio ili estas, kie ili estas uzataj kaj kiaj algoritmoj ekzistas por trovi ilin.

Ni konsideros funkciajn dependecojn en la kunteksto de interrilataj datumbazoj. Por diri tre malglate, en tiaj datumbazoj informoj estas konservitaj en formo de tabeloj. Poste, ni uzas proksimumajn konceptojn, kiuj ne estas interŝanĝeblaj en strikta interrilata teorio: ni nomos la tabelon mem rilato, la kolumnojn - atributojn (ilia aro - rilata skemo), kaj la aron de vicaj valoroj sur subaro de atributoj. - opo.

Ekzemple, en la supra tabelo, (Benson, M, M organo) estas opo de atributoj (Paciento, Paul, Doktoro).
Pli formale, ĉi tio estas skribita jene: [Paciento, Sekso, Doktoro] = (Benson, M, M-organo).
Nun ni povas enkonduki la koncepton de funkcia dependeco (FD):

Difino 1. La rilato R kontentigas la federacian leĝon X → Y (kie X, Y ⊆ R) se kaj nur se por iuj opoj , ∈ R validas: se [X] = [X], do [Y] = [Y]. En ĉi tiu kazo, ni diras ke X (la determinanto, aŭ difina aro de atributoj) funkcie determinas Y (la dependa aro).

Alivorte, la ĉeesto de federacia leĝo X → Y signifas ke se ni havas du opoj en R kaj ili kongruas en atributoj X, tiam ili koincidos en atributoj Y.
Kaj nun, en ordo. Ni rigardu la atributojn Paciento и Sekso por kiu ni volas ekscii, ĉu estas dependecoj inter ili aŭ ne. Por tia aro de atributoj, la sekvaj dependecoj povas ekzisti:

1. Paciento → Sekso
2. Sekso → Paciento

Kiel difinite supre, por ke la unua dependeco tenu, ĉiu unika kolumna valoro Paciento nur unu kolumna valoro devas kongrui Sekso. Kaj por la ekzemplotabelo tio ja estas la kazo. Tamen, ĉi tio ne funkcias en la kontraŭa direkto, tio estas, la dua dependeco ne estas kontentigita, kaj la atributo Sekso ne estas determinanto por Paciento. Simile, se ni prenas la dependecon Kuracisto → Paciento, Vi povas vidi ke ĝi estas malobservita, ekde la valoro Robin ĉi tiu eco havas plurajn malsamajn signifojn - Ellis kaj Graham.

Tiel, funkciaj dependecoj ebligas determini la ekzistantajn rilatojn inter aroj de tabelaj atributoj. De ĉi tie ni konsideros la plej interesajn ligojn, aŭ pli ĝuste tiajn X → Ykio ili estas:

• ne-banala, tio estas, la dekstra flanko de la dependeco ne estas subaro de la maldekstra (Y ̸⊆ X);
• minimuma, tio estas, tia dependeco ne ekzistas Z → Y, tio Z ⊂ X.

La dependecoj konsiderataj ĝis ĉi tiu punkto estis striktaj, tio estas, ili ne antaŭvidis iujn malobservojn sur la tablo, sed krom ili, ekzistas ankaŭ tiuj, kiuj permesas iun malkongruon inter la valoroj de la opoj. Tiaj dependecoj estas metitaj en apartan klason, nomatan proksimuma, kaj rajtas esti malobservitaj por certa nombro da opoj. Ĉi tiu kvanto estas reguligita de la maksimuma erara indikilo emax. Ekzemple, la eraroprocento = 0.01 povas signifi ke la dependeco povas esti malobservita de 1% de la disponeblaj opoj sur la konsiderita aro de atributoj. Tio estas, por 1000 rekordoj, maksimume 10 opoj povas malobservi la Federacian Leĝon. Ni konsideros iomete malsaman metrikon, bazitan sur duopaj malsamaj valoroj de la opoj komparitaj. Por toksomanio X → Y pri sinteno r ĝi estas konsiderata jene:

Ni kalkulu la eraron por Kuracisto → Paciento el la supra ekzemplo. Ni havas du opoj, kies valoroj malsamas laŭ la atributo Paciento, sed koincidas sur Doktoro: [Doktoro, Paciento] = (Robin, Ellis) kaj [Doktoro, Paciento] = (Robin, Graham). Sekvante la difinon de eraro, ni devas konsideri ĉiujn konfliktajn parojn, kio signifas, ke estos du el ili: (, ) kaj ĝia inverso (, ). Ni anstataŭigu ĝin en la formulon kaj ricevu:

Nun ni provu respondi la demandon: "Kial ĉio estas por?" Fakte, federaciaj leĝoj estas malsamaj. La unua tipo estas tiuj dependecoj, kiuj estas determinitaj de la administranto ĉe la datumbaza dezajnostadio. Ili estas kutime malmultaj en nombro, striktaj, kaj la ĉefa aplikaĵo estas datumnormaligo kaj interrilata skemdezajno.

La dua tipo estas dependecoj, kiuj reprezentas "kaŝitajn" datumojn kaj antaŭe nekonatajn rilatojn inter atributoj. Tio estas, tiaj dependecoj ne estis pripensitaj en la momento de la dezajno kaj ili estas trovitaj por la ekzistanta datumaro, tiel ke poste, surbaze de la multaj identigitaj federaciaj leĝoj, iuj konkludoj povas esti desegnitaj pri la stokitaj informoj. Ĝuste ĉi tiuj dependecoj ni laboras. Ili estas traktitaj de tuta kampo de datumminado kun diversaj serĉteknikoj kaj algoritmoj konstruitaj sur ilia bazo. Ni eltrovu kiel la trovitaj funkciaj dependecoj (precizaj aŭ proksimumaj) en iuj datumoj povas esti utilaj.

Hodiaŭ, unu el la ĉefaj aplikoj de dependecoj estas purigado de datumoj. Ĝi implikas disvolvi procezojn por identigi "malpurajn datumojn" kaj poste korekti ĝin. Elstaraj ekzemploj de "malpuraj datumoj" estas duplikatoj, dateneraroj aŭ tajperaroj, mankantaj valoroj, malnoviĝintaj datumoj, kromaj spacoj kaj similaj.

Ekzemplo de datuma eraro:

Ekzemplo de duplikatoj en datumoj:

Ekzemple, ni havas tablon kaj aron de federaciaj leĝoj, kiuj devas esti ekzekutitaj. Datumpurigado en ĉi tiu kazo implikas ŝanĝi la datumojn por ke la Federaciaj Leĝoj fariĝu ĝustaj. En ĉi tiu kazo, la nombro da modifoj estu minimuma (ĉi tiu proceduro havas siajn proprajn algoritmojn, pri kiuj ni ne fokusos en ĉi tiu artikolo). Malsupre estas ekzemplo de tia datuma transformo. Maldekstre estas la origina rilato, en kiu, evidente, la necesaj FL-oj ne estas renkontitaj (ekzemplo de malobservo de unu el la FL-oj estas reliefigita ruĝe). Dekstre estas la ĝisdatigita rilato, kun la verdaj ĉeloj montrantaj la ŝanĝitajn valorojn. Post ĉi tiu proceduro, la necesaj dependecoj komencis esti konservitaj.

Alia populara aplikaĵo estas datumbaza dezajno. Ĉi tie indas rememorigi normalajn formojn kaj normaligon. Normaligo estas la procezo de alportado de rilato en konformecon kun certa aro de postuloj, ĉiu el kiuj estas difinita per la normala formo laŭ sia propra maniero. Ni ne priskribos la postulojn de diversaj normalaj formoj (tio estas farita en iu ajn libro pri datumbaza kurso por komencantoj), sed ni nur rimarkos, ke ĉiu el ili uzas la koncepton de funkciaj dependecoj siamaniere. Post ĉio, FLoj estas esence integreclimoj kiuj estas enkalkulitaj dum dizajnado de datumbazo (en la kunteksto de tiu tasko, FLoj foje estas nomitaj superŝlosiloj).

Ni konsideru ilian peton por la kvar normalaj formoj en la suba bildo. Memoru, ke Boyce-Codd normala formo estas pli strikta ol la tria formo, sed malpli strikta ol la kvara. La lastan ni ne konsideras nuntempe, ĉar ĝia formuliĝo postulas komprenon de multvaloraj dependecoj, kiuj ne interesas al ni en ĉi tiu artikolo.

Alia areo en kiu dependencajoj trovis sian aplikiĝon reduktas la dimensiecon de la trajtospaco en taskoj kiel ekzemple konstruado de naiva Bayes-klasigilo, identigado de signifaj ecoj, kaj kompensado de regresmodelo. En la originaj artikoloj, ĉi tiu tasko estas nomita la determino de redunda kaj trajto graveco [5, 6], kaj ĝi estas solvita per la aktiva uzo de datumbazaj konceptoj. Kun la apero de tiaj verkoj, ni povas diri, ke hodiaŭ estas postulo pri solvoj, kiuj ebligas al ni kombini la datumbazon, analizon kaj efektivigon de ĉi-supraj optimumigo-problemoj en unu ilon [7, 8, 9].

Estas multaj algoritmoj (kaj modernaj kaj ne tiel modernaj) por serĉi federaciajn leĝojn en datuma aro. Tiaj algoritmoj povas esti dividitaj en tri grupojn:

• Algoritmoj uzantaj krucadon de algebraj kradoj (Krado-traversaj algoritmoj)
• Algoritmoj bazitaj sur la serĉo de interkonsentitaj valoroj (Algoritmoj de diferenco kaj konsento)
• Algoritmoj bazitaj sur duopaj komparoj (Algoritmoj de indukto de dependeco)

Mallonga priskribo de ĉiu tipo de algoritmo estas prezentita en la suba tabelo:


Vi povas legi pli pri ĉi tiu klasifiko [4]. Malsupre estas ekzemploj de algoritmoj por ĉiu tipo:

Nuntempe, novaj algoritmoj aperas, kiuj kombinas plurajn alirojn por trovi funkciajn dependecojn. Ekzemploj de tiaj algoritmoj estas Pyro [2] kaj HyFD [3]. Analizo de ilia laboro estas atendata en la sekvaj artikoloj de ĉi tiu serio. En ĉi tiu artikolo ni nur ekzamenos la bazajn konceptojn kaj lemon, kiuj estas necesaj por kompreni dependecajn detektajn teknikojn.

Ni komencu per simpla - diferenco- kaj konsento-aro, uzata en la dua speco de algoritmoj. Diferenc-aro estas aro de opoj kiuj ne havas la samajn valorojn, dum konsento-aro, male, estas opoj kiuj havas la samajn valorojn. Indas noti, ke en ĉi tiu kazo ni konsideras nur la maldekstran flankon de la dependeco.

Alia grava koncepto kiu estis renkontita supre estas la algebra krado. Ĉar multaj modernaj algoritmoj funkcias laŭ ĉi tiu koncepto, ni devas havi ideon pri kio ĝi estas.

Por enkonduki la koncepton de krado, estas necese difini parte ordigitan aron (aŭ parte ordigitan aron, mallongigitan kiel poset).

Difino 2. Aro S laŭdire estas parte ordigita per la binara rilato ⩽ se por ĉio a, b, c ∈ S la sekvaj trajtoj estas kontentigitaj:

1. Refleksiveco, tio estas, a ⩽ a
2. Kontraŭsimetrio, tio estas, se a ⩽ b kaj b ⩽ a, tiam a = b
3. Transitiveco, tio estas, por a ⩽ b kaj b ⩽ c sekvas ke a ⩽ c

Tia rilato estas nomita (malstrikta) parta orda rilato, kaj la aro mem estas nomita parte ordigita aro. Formala skribmaniero: ⟨S, ⩽⟩.

Kiel la plej simpla ekzemplo de parte ordigita aro, ni povas preni la aron de ĉiuj naturaj nombroj N kun la kutima orda rilato ⩽. Estas facile kontroli, ke ĉiuj necesaj aksiomoj estas kontentigitaj.

Pli signifa ekzemplo. Konsideru la aron de ĉiuj subaroj {1, 2, 3}, ordigitaj per la inkluziva rilato ⊆. Efektive, ĉi tiu rilato kontentigas ĉiujn partajn ordkondiĉojn, do ⟨P ({1, 2, 3}), ⊆⟩ estas parte ordigita aro. La suba figuro montras la strukturon de ĉi tiu aro: se unu elemento povas esti atingita per sagoj al alia elemento, tiam ili estas en orda rilato.

Ni bezonos du pliajn simplajn difinojn el la kampo de matematiko - supremum kaj infimum.

Difino 3. Estu ⟨S, ⩽⟩ parte ordigita aro, A ⊆ S. La supera limo de A estas elemento u ∈ S tia ke ∀x ∈ S: x ⩽ u. Estu U la aro de ĉiuj supraj baroj de S. Se estas plej malgranda elemento en U, tiam ĝi estas nomita la supremo kaj estas indikita sup A.

La koncepto de preciza malsupera limo estas enkondukita simile.

Difino 4. Estu ⟨S, ⩽⟩ parte ordigita aro, A ⊆ S. La infimumo de A estas elemento l ∈ S tia ke ∀x ∈ S: l ⩽ x. Estu L la aro de ĉiuj malsuperaj limoj de S. Se estas plej granda elemento en L, tiam ĝi estas nomita infimum kaj estas indikita kiel inf A.

Konsideru kiel ekzemplon la ĉi-supran parte ordigitan aron ⟨P ({1, 2, 3}), ⊆⟩ kaj trovu la supremumon kaj infimumon en ĝi:

Nun ni povas formuli la difinon de algebra krado.

Difino 5. Estu ⟨P,⩽⟩ parte ordigita aro tia ke ĉiu duelementa subaro havas superan kaj malsupran baron. Tiam P estas nomita algebra krado. En ĉi tiu kazo, sup{x, y} estas skribita kiel x ∨ y, kaj inf {x, y} kiel x ∧ y.

Ni kontrolu, ke nia laborekzemplo ⟨P ({1, 2, 3}), ⊆⟩ estas krado. Efektive, por iu ajn a, b ∈ P ({1, 2, 3}), a∨b = a∪b, kaj a∧b = a∩b. Ekzemple, konsideru la arojn {1, 2} kaj {1, 3} kaj trovu ilian infimumon kaj superumon. Se ni intersekcas ilin, ni ricevos la aron {1}, kiu estos la infimumo. Ni ricevas la supremumon kombinante ilin - {1, 2, 3}.

En algoritmoj por identigi fizikajn problemojn, la serĉspaco ofte estas reprezentita en la formo de krado, kie aroj de unu elemento (legu la unuan nivelon de la serĉa krado, kie la maldekstra flanko de la dependecoj konsistas el unu atributo) reprezentas ĉiun atributon. de la origina rilato.
Unue, ni konsideras dependecojn de la formo ∅ → Ununura atributo. Ĉi tiu paŝo permesas al vi determini, kiuj atributoj estas ĉefaj ŝlosiloj (por tiaj atributoj ne ekzistas determinantoj, kaj tial la maldekstra flanko estas malplena). Plue, tiaj algoritmoj moviĝas supren laŭ la krado. Indas noti, ke la tuta krado ne povas esti trapasita, tio estas, se la dezirata maksimuma grandeco de la maldekstra flanko estas transdonita al la enigo, tiam la algoritmo ne iros pli ol nivelon kun tiu grandeco.

La figuro malsupre montras kiel algebra krado povas esti uzita en la problemo de trovado de FZ. Ĉi tie ĉiu rando (X, XY) reprezentas dependecon X → Y. Ekzemple, ni pasis la unuan nivelon kaj scias, ke la toksomanio estas konservita A → B (ni montros ĉi tion kiel verdan konekton inter la verticoj A и B). Ĉi tio signifas, ke plue, kiam ni supreniras laŭ la krado, ni eble ne kontrolas la dependecon A, C → B, ĉar ĝi ne plu estos minimuma. Simile, ni ne kontrolus ĝin se la dependeco estus tenita C → B.

Krome, kiel regulo, ĉiuj modernaj algoritmoj por serĉi federaciajn leĝojn uzas datumstrukturon kiel ekzemple sekcio (en la origina fonto - nudigita sekcio [1]). La formala difino de sekcio estas kiel sekvas:

Difino 6. Estu X ⊆ R aro de atributoj por rilato r. Areto estas aro de indeksoj de opoj en r kiuj havas la saman valoron por X, tio estas, c(t) = {i|ti[X] = t[X]}. Sekcio estas aro de aretoj, ekskludante aretojn de unulongo:

En simplaj vortoj, dispartigo por atributo X estas aro de listoj, kie ĉiu listo enhavas linionumeroj kun la samaj valoroj por X. En moderna literaturo, la strukturo reprezentanta sekciojn estas nomita pozicilista indekso (PLI). Unuo-longaj aretoj estas ekskluditaj por PLI-kunpremadceloj ĉar ili estas aretoj kiuj enhavas nur rekordnumeron kun unika valoro kiu ĉiam estos facile identigebla.

Ni rigardu ekzemplon. Ni revenu al la sama tablo kun pacientoj kaj konstruu sekciojn por la kolumnoj Paciento и Sekso (maldekstre aperis nova kolumno, en kiu estas markitaj la tabelvicnumeroj):

Krome, laŭ la difino, la vando por la kolono Paciento efektive estos malplena, ĉar unuopaj aretoj estas ekskluditaj de la sekcio.

Dispartigoj povas esti akiritaj per pluraj atributoj. Kaj estas du manieroj fari tion: trairante la tabelon, konstrui subdiskon uzante ĉiujn necesajn atributojn samtempe, aŭ konstrui ĝin uzante la operacion de intersekco de subdiskoj uzante subaron de atributoj. Federaciaj juraj serĉalgoritmoj uzas la duan opcion.

En simplaj vortoj, por, ekzemple, akiri subdiskon per kolumnoj ABC, vi povas preni sekciojn por AC и B (aŭ ajna alia aro de disaj subaroj) kaj intersekcu ilin unu kun la alia. La operacio de intersekco de du sekcioj elektas aretojn de la plej granda longo kiuj estas komunaj al ambaŭ sekcioj.

Ni rigardu ekzemplon:

En la unua kazo, ni ricevis malplenan sekcion. Se vi rigardas atente la tabelon, do ne ekzistas identaj valoroj por la du atributoj. Se ni iomete modifas la tabelon (la kazon dekstre), ni jam ricevos nemalplenan intersekciĝon. Krome, linioj 1 kaj 2 fakte enhavas la samajn valorojn por la atributoj Sekso и Doktoro.

Poste, ni bezonos tian koncepton kiel subdiskograndeco. Formale:

Simple dirite, la sekciograndeco estas la nombro da aretoj inkluzivitaj en la sekcio (memoru, ke unuopaj aretoj ne estas inkluditaj en la sekcio!):

Nun ni povas difini unu el la ŝlosilaj lemoj, kiuj por donitaj sekcioj permesas al ni determini ĉu dependeco estas tenita aŭ ne:

Lemo 1. La dependeco A, B → C validas se kaj nur se

Laŭ la lemo, por determini ĉu dependeco validas, kvar paŝoj devas esti faritaj:

1. Kalkulu la subdiskon por la maldekstra flanko de la dependeco
2. Kalkulu la subdiskon por la dekstra flanko de la dependeco
3. Kalkulu la produkton de la unua kaj dua paŝo
4. Komparu la grandecojn de la sekcioj akiritaj en la unua kaj tria paŝoj

Malsupre estas ekzemplo de kontrolado ĉu la dependeco validas laŭ ĉi tiu lemo:

En ĉi tiu artikolo, ni ekzamenis konceptojn kiel funkcia dependeco, proksimuma funkcia dependeco, rigardis kie ili estas uzataj, same kiel kiaj algoritmoj por serĉi fizikajn funkciojn ekzistas. Ni ankaŭ detale ekzamenis la bazajn sed gravajn konceptojn, kiuj estas aktive uzataj en modernaj algoritmoj por serĉi federaciajn leĝojn.

Referencoj:

1. Huhtala Y. et al. TANE: efika algoritmo por malkovri funkciajn kaj proksimumajn dependecojn //La komputila revuo. – 1999. – T. 42. – Nr. 2. – p. 100-111.
2. Kruse S., Naumann F. Efficient discovery of proksimuma dependencies // Proceedings of the VLDB Endowment. – 2018. – T. 11. – Nr. 7. – paĝoj 759-772.
3. Papenbrock T., Naumann F. A hybrid approach to functional dependency discovery //Procedoj de la 2016-datita Internacia Konferenco pri Administrado de Datumoj. – ACM, 2016. – pp 821-833.
4. Papenbrock T. et al. Funkcia dependecmalkovro: eksperimenta taksado de sep algoritmoj //Proceedings of the VLDB Endowment. – 2015. – T. 8. – Nr. 10. – pp 1082-1093.
5. Kumar A. et al. Aliĝi aŭ ne aliĝi?: Pripensante dufoje pri aliĝoj antaŭ la elekto de funkcioj //Procedoj de la Internacia Konferenco pri Administrado de Datumoj 2016. – ACM, 2016. – p. 19-34.
6. Abo Khamis M. et al. En-datumbaza lernado kun maldensaj tensoroj //Procedoj de la 37-a ACM SIGMOD-SIGACT-SIGAI-Simpozio pri Principoj de Datumaro-Sistemoj. – ACM, 2018. – p. 325-340.
7. Hellerstein JM et al. La MADlib-analitika biblioteko: aŭ MAD-kapabloj, la SQL //Procedoj de la VLDB Endowment. – 2012. – T. 5. – Nr. 12. – pp 1700-1711.
8. Qin C., Rusu F. Speculative aproximations for terascale distribuita gradienta deveno-optimumigo //Proceedings of the Fourth Workshop on Data analytics in the Cloud. – ACM, 2015. – P. 1.
9. Meng X. et al. Mllib: Maŝinlernado en apaĉa sparko //The Journal of Machine Learning Research. – 2016. – T. 17. – Nr. 1. – pp 1235-1241.

Artikolo-aŭtoroj: Anastazio Birillo, esploristo ĉe JetBrains Research, CS-centrostudento и Nikita Bobrov, esploristo ĉe JetBrains Research

fonto: www.habr.com