V tem članku bomo govorili o funkcionalnih odvisnostih v bazah podatkov – kaj so, kje se uporabljajo in kakšni algoritmi obstajajo za njihovo iskanje.
Funkcionalne odvisnosti bomo obravnavali v kontekstu relacijskih baz podatkov. Zelo grobo povedano, v takih podatkovnih zbirkah so informacije shranjene v obliki tabel. Nato uporabimo približne koncepte, ki v strogi relacijski teoriji niso zamenljivi: samo tabelo bomo imenovali relacija, stolpce - atribute (njihov niz - relacijsko shemo) in niz vrednosti vrstic na podmnožici atributov - tuple.
Na primer, v zgornji tabeli (Benson, M, M orgle) je niz atributov (Pacient, Paul, zdravnik).
Bolj formalno je to zapisano takole: [Pacient, spol, zdravnik] = (Benson, M, M orgle).
Zdaj lahko uvedemo koncept funkcionalne odvisnosti (FD):
Definicija 1. Relacija R zadošča zveznemu zakonu X → Y (kjer je X, Y ⊆ R), če in samo če za katere koli , ∈ R velja: če [X] = [X], torej [Y] = [Y]. V tem primeru pravimo, da X (determinanta ali določajoč niz atributov) funkcionalno določa Y (odvisni niz).
Z drugimi besedami, prisotnost zveznega zakona X → Y pomeni, da če imamo notri dve torki R in se ujemajo po atributih X, potem bodo sovpadali v atributih Y.
In zdaj po vrsti. Poglejmo atribute Bolnik и Paul za katere želimo ugotoviti, ali med njimi obstajajo odvisnosti ali ne. Za tak niz atributov lahko obstajajo naslednje odvisnosti:
- Pacient → Spol
- Spol → Bolnik
Kot je definirano zgoraj, je za obdržanje prve odvisnosti vsaka edinstvena vrednost stolpca Bolnik ujemati se mora le ena vrednost stolpca Paul. In za primer tabele je to res tako. Vendar to ne deluje v nasprotni smeri, to je, da druga odvisnost ni izpolnjena in atribut Paul ni odločilno za Bolnik. Podobno, če vzamemo odvisnost Zdravnik → Pacient, lahko vidite, da je kršena, saj vrednost Robin ta atribut ima več različnih pomenov - Ellis in Graham.
Tako funkcionalne odvisnosti omogočajo določitev obstoječih odnosov med nizi atributov tabele. Od tu naprej bomo obravnavali najbolj zanimive povezave oz X → Ykaj so:
- netrivialno, kar pomeni, da desna stran odvisnosti ni podmnožica leve (Y ̸⊆ X);
- minimalna, torej te odvisnosti ni Z → YTo Z ⊂ X.
Do te točke obravnavane odvisnosti so bile stroge, to pomeni, da niso predvidevale nobenih kršitev na mizi, vendar poleg njih obstajajo tudi tiste, ki dopuščajo določeno neskladnost med vrednostmi tork. Takšne odvisnosti so uvrščene v ločen razred, imenovan približne, in jih je dovoljeno kršiti za določeno število tulp. Ta znesek je reguliran z indikatorjem največje napake emax. Na primer stopnja napak = 0.01 lahko pomeni, da je odvisnost lahko kršena za 1 % razpoložljivih tupl na obravnavanem nizu atributov. To pomeni, da lahko za 1000 zapisov največ 10 tuplov krši zvezni zakon. Upoštevali bomo nekoliko drugačno metriko, ki temelji na parih različnih vrednosti tork, ki jih primerjamo. Za zasvojenost X → Y na odnos r velja takole:
Izračunajmo napako za Zdravnik → Pacient iz zgornjega primera. Imamo dve torki, katerih vrednosti se razlikujejo glede na atribut Bolnik, vendar sovpadajo na zdravnik: [Zdravnik, bolnik] = (Robin, Ellis) In [Zdravnik, bolnik] = (Robin, Graham). Po definiciji napake moramo upoštevati vse konfliktne pare, kar pomeni, da bosta dva: (, ) in njegov obrat (, ). Nadomestimo ga v formulo in dobimo:
Zdaj pa poskusimo odgovoriti na vprašanje: "Zakaj je vse to?" Pravzaprav so zvezni zakoni drugačni. Prva vrsta so tiste odvisnosti, ki jih določi skrbnik v fazi načrtovanja baze podatkov. Običajno jih je malo, strogi, njihova glavna uporaba pa je normalizacija podatkov in načrtovanje relacijskih shem.
Druga vrsta so odvisnosti, ki predstavljajo "skrite" podatke in prej neznana razmerja med atributi. To pomeni, da se o takšnih odvisnostih ni razmišljalo v času načrtovanja in so najdene za obstoječi nabor podatkov, tako da je pozneje na podlagi številnih identificiranih zveznih zakonov mogoče sklepati o shranjenih informacijah. Ravno s temi odvisnostmi delamo. Z njimi se ukvarja celo področje podatkovnega rudarjenja z različnimi iskalnimi tehnikami in algoritmi, zgrajenimi na njihovi osnovi. Ugotovimo, kako so lahko najdene funkcionalne odvisnosti (natančne ali približne) v katerem koli podatku uporabne.
Danes je ena glavnih aplikacij odvisnosti čiščenje podatkov. Vključuje razvoj procesov za prepoznavanje "umazanih podatkov" in njihovo nato popravljanje. Izraziti primeri »umazanih podatkov« so dvojniki, podatkovne napake ali tipkarske napake, manjkajoče vrednosti, zastareli podatki, dodatni presledki in podobno.
Primer podatkovne napake:
Primer dvojnikov v podatkih:
Na primer, imamo tabelo in nabor zveznih zakonov, ki jih je treba izvršiti. Čiščenje podatkov v tem primeru vključuje spreminjanje podatkov, tako da zvezni zakoni postanejo pravilni. V tem primeru mora biti število sprememb minimalno (ta postopek ima svoje algoritme, na katere se v tem članku ne bomo osredotočali). Spodaj je primer takšne transformacije podatkov. Na levi je prvotno razmerje, v katerem očitno niso izpolnjeni potrebni FL (primer kršitve enega od FL je označen z rdečo). Na desni je posodobljeno razmerje, pri čemer zelene celice prikazujejo spremenjene vrednosti. Po tem postopku so se začele vzdrževati potrebne odvisnosti.
Druga priljubljena aplikacija je oblikovanje baze podatkov. Tukaj je vredno spomniti na normalne oblike in normalizacijo. Normalizacija je proces usklajevanja relacije z določenim nizom zahtev, od katerih je vsaka definirana z normalno obliko na svoj način. Ne bomo opisovali zahtev različnih normalnih oblik (to je storjeno v kateri koli knjigi o tečaju baze podatkov za začetnike), vendar bomo le opazili, da vsaka od njih uporablja koncept funkcionalnih odvisnosti na svoj način. Navsezadnje so FL-ji sami po sebi omejitve celovitosti, ki se upoštevajo pri načrtovanju baze podatkov (v kontekstu te naloge se FL-ji včasih imenujejo superključi).
Oglejmo si njihovo uporabo za štiri normalne oblike na spodnji sliki. Spomnimo se, da je Boyce-Coddova normalna oblika strožja od tretje oblike, a manj stroga od četrte. Slednjega zaenkrat ne obravnavamo, saj njegova formulacija zahteva razumevanje večvrednostnih odvisnosti, ki nas v tem članku ne zanimajo.
Drugo področje, na katerem so odvisnosti našle svojo uporabo, je zmanjševanje dimenzionalnosti prostora funkcij pri nalogah, kot je izgradnja naivnega Bayesovega klasifikatorja, prepoznavanje pomembnih značilnosti in ponovna parametrizacija regresijskega modela. V izvirnih člankih se ta naloga imenuje določanje redundantnosti in relevantnosti lastnosti [5, 6] in se rešuje z aktivno uporabo konceptov baz podatkov. S pojavom tovrstnih del lahko rečemo, da se danes pojavlja povpraševanje po rešitvah, ki nam omogočajo združiti bazo podatkov, analitiko in implementacijo zgornjih optimizacijskih problemov v eno orodje [7, 8, 9].
Obstaja veliko algoritmov (sodobnih in malo manj) za iskanje zveznih zakonov v naboru podatkov.Takšne algoritme lahko razdelimo v tri skupine:
- Algoritmi, ki uporabljajo prečkanje algebrskih mrež (algoritmi prečkanja mreže)
- Algoritmi, ki temeljijo na iskanju dogovorjenih vrednosti (algoritmi razlik in soglasja)
- Algoritmi, ki temeljijo na parnih primerjavah (algoritmi indukcije odvisnosti)
Kratek opis vsake vrste algoritma je predstavljen v spodnji tabeli:
Več o tej klasifikaciji lahko preberete [4]. Spodaj so primeri algoritmov za vsako vrsto:
Trenutno se pojavljajo novi algoritmi, ki združujejo več pristopov k iskanju funkcionalnih odvisnosti. Primera takih algoritmov sta Pyro [2] in HyFD [3]. Analizo njihovega dela pričakujemo v naslednjih člankih te serije. V tem članku bomo preučili le osnovne koncepte in leme, ki so potrebni za razumevanje tehnik odkrivanja odvisnosti.
Začnimo s preprostim nizom razlik in strinjanja, ki se uporabljata v drugi vrsti algoritmov. Nabor razlik je nabor tork, ki nimajo enakih vrednosti, medtem ko so nabor soglasij, nasprotno, nabori, ki imajo enake vrednosti. Omeniti velja, da v tem primeru upoštevamo le levo stran odvisnosti.
Drug pomemben koncept, ki smo ga srečali zgoraj, je algebraična mreža. Ker veliko sodobnih algoritmov deluje na tem konceptu, moramo imeti predstavo o tem, kaj je.
Za uvedbo koncepta mreže je potrebno definirati delno urejeno množico (ali delno urejeno množico, skrajšano kot poset).
Definicija 2. Za množico S pravimo, da je delno urejena z binarno relacijo ⩽, če so za vse a, b, c ∈ S izpolnjene naslednje lastnosti:
- Refleksivnost, to je a ⩽ a
- Antisimetrija, to je, če je a ⩽ b in b ⩽ a, potem je a = b
- Tranzitivnost, to je za a ⩽ b in b ⩽ c sledi a ⩽ c
Takšno relacijo imenujemo (ohlapna) relacija delnega reda, množico samo pa delno urejeno množico. Uradni zapis: ⟨S, ⩽⟩.
Kot najenostavnejši primer delno urejene množice lahko vzamemo množico vseh naravnih števil N z običajno urejenostjo ⩽. Preprosto je preveriti, ali so izpolnjeni vsi potrebni aksiomi.
Bolj pomenljiv primer. Razmislite o množici vseh podmnožic {1, 2, 3}, urejenih z inkluzijsko relacijo ⊆. Ta relacija dejansko izpolnjuje vse pogoje delnega reda, tako da je ⟨P ({1, 2, 3}), ⊆⟩ delno urejena množica. Spodnja slika prikazuje strukturo tega nabora: če lahko en element dosežete s puščicami do drugega elementa, potem sta v vrstnem redu.
Potrebovali bomo še dve preprosti definiciji s področja matematike - supremum in infimum.
Definicija 3. Naj bo ⟨S, ⩽⟩ delno urejena množica, A ⊆ S. Zgornja meja A je element u ∈ S, tako da ∀x ∈ S: x ⩽ u. Naj bo U množica vseh zgornjih meja S. Če je v U najmanjši element, se imenuje supremum in je označen kot sup A.
Podobno uvedemo koncept natančne spodnje meje.
Definicija 4. Naj bo ⟨S, ⩽⟩ delno urejena množica, A ⊆ S. Infimum A je element l ∈ S, tako da ∀x ∈ S: l ⩽ x. Naj bo L množica vseh spodnjih meja S. Če je v L največji element, se imenuje infimum in je označen kot inf A.
Kot primer upoštevajte zgornjo delno urejeno množico ⟨P ({1, 2, 3}), ⊆⟩ in v njej poiščite supremum in infimum:
Sedaj lahko oblikujemo definicijo algebraične mreže.
Definicija 5. Naj bo ⟨P,⩽⟩ delno urejena množica, tako da ima vsaka dvoelementna podmnožica zgornjo in spodnjo mejo. Potem P imenujemo algebraična mreža. V tem primeru je sup{x, y} zapisan kot x ∨ y, inf {x, y} pa kot x ∧ y.
Preverimo, ali je naš delovni primer ⟨P ({1, 2, 3}), ⊆⟩ mreža. Dejansko je za vsak a, b ∈ P ({1, 2, 3}) a∨b = a∪b in a∧b = a∩b. Na primer, razmislite o množici {1, 2} in {1, 3} ter poiščite njuno infimumo in supremum. Če ju presekamo, dobimo množico {1}, ki bo infimum. Supremem dobimo tako, da jih združimo - {1, 2, 3}.
V algoritmih za identifikacijo fizičnih problemov je iskalni prostor pogosto predstavljen v obliki mreže, kjer nizi enega elementa (beri prvi nivo iskalne mreže, kjer levo stran odvisnosti sestavlja en atribut) predstavljajo vsak atribut prvotnega odnosa.
Najprej obravnavamo odvisnosti oblike ∅ → Enotni atribut. Ta korak vam omogoča, da določite, kateri atributi so primarni ključi (za take atribute ni determinant, zato je leva stran prazna). Nadalje se takšni algoritmi premikajo navzgor vzdolž mreže. Omeniti velja, da ni mogoče prečkati celotne mreže, to je, če je želena največja velikost leve strani posredovana vhodu, potem algoritem ne bo šel dlje od ravni s to velikostjo.
Spodnja slika prikazuje, kako lahko algebraično mrežo uporabimo pri problemu iskanja FZ. Tukaj vsak rob (X, XY) predstavlja odvisnost X → Y. Na primer, prešli smo prvo stopnjo in vemo, da se zasvojenost ohranja A → B (to bomo prikazali kot zeleno povezavo med vozlišči A и B). To pomeni, da nadalje, ko se premikamo navzgor po rešetki, morda ne bomo preverjali odvisnosti A, C → B, ker ne bo več minimalen. Podobno tega ne bi preverili, če bi bila odvisnost zadržana C → B.
Poleg tega praviloma vsi sodobni algoritmi za iskanje zveznih zakonov uporabljajo podatkovno strukturo, kot je particija (v izvirnem viru - stripped partition [1]). Formalna definicija particije je naslednja:
Definicija 6. Naj bo X ⊆ R niz atributov za relacijo r. Grozd je niz indeksov tulp v r, ki imajo enako vrednost za X, to je c(t) = {i|ti[X] = t[X]}. Particija je niz gruč, razen gruč enotne dolžine:
Preprosto povedano, particija za atribut X je niz seznamov, kjer vsak seznam vsebuje številke vrstic z enakimi vrednostmi za X. V sodobni literaturi se struktura, ki predstavlja particije, imenuje indeks seznama položajev (PLI). Gruče dolžine enote so izključene za namene stiskanja PLI, ker gre za gruče, ki vsebujejo samo številko zapisa z edinstveno vrednostjo, ki jo je vedno enostavno prepoznati.
Poglejmo si primer. Vrnimo se k isti mizi z bolniki in zgradimo predelne stene za stolpce Bolnik и Paul (na levi se je pojavil nov stolpec, v katerem so označene številke vrstic tabele):
Poleg tega je po definiciji pregrada za stolpec Bolnik bo dejansko prazen, ker so posamezne gruče izključene iz particije.
Particije je mogoče pridobiti z več atributi. To lahko storite na dva načina: s pregledovanjem tabele zgradite particijo z uporabo vseh potrebnih atributov hkrati ali pa jo zgradite z operacijo presečišča particij z uporabo podmnožice atributov. Algoritmi iskanja po zvezni zakonodaji uporabljajo drugo možnost.
Preprosto povedano, da bi na primer dobili particijo po stolpcih ABC, lahko vzamete particije za AC и B (ali katero koli drugo množico disjunktnih podmnožic) in jih sekajo med seboj. Operacija presečišča dveh particij izbere gruče največje dolžine, ki so skupne obema particijama.
Vzemimo primer:
V prvem primeru smo prejeli prazno particijo. Če natančno pogledate tabelo, potem res ni enakih vrednosti za oba atributa. Če tabelo nekoliko spremenimo (primer desno), bomo že dobili neprazno križišče. Poleg tega vrstici 1 in 2 dejansko vsebujeta enake vrednosti za atribute Paul и Zdravnik.
Nato bomo potrebovali tak koncept, kot je velikost particije. Formalno:
Preprosto povedano, velikost particije je število gruč, vključenih v particijo (ne pozabite, da posamezne gruče niso vključene v particijo!):
Zdaj lahko definiramo eno od ključnih lem, ki nam za dane particije omogoča, da ugotovimo, ali je odvisnost zadržana ali ne:
Lema 1. Odvisnost A, B → C velja, če in samo če
V skladu z lemo je treba za določitev, ali odvisnost drži, izvesti štiri korake:
- Izračunajte particijo za levo stran odvisnosti
- Izračunajte particijo za desno stran odvisnosti
- Izračunajte zmnožek prvega in drugega koraka
- Primerjajte velikosti predelnih sten, dobljenih v prvem in tretjem koraku
Spodaj je primer preverjanja, ali odvisnost drži glede na to lemo:
V tem članku smo preučili koncepte, kot so funkcionalna odvisnost, približna funkcionalna odvisnost, pogledali, kje se uporabljajo, pa tudi kakšni algoritmi za iskanje fizičnih funkcij obstajajo. Podrobno smo preučili tudi osnovne, a pomembne koncepte, ki se aktivno uporabljajo v sodobnih algoritmih za iskanje zveznih zakonov.
Reference:
- Huhtala Y. et al. TANE: Učinkovit algoritem za odkrivanje funkcijskih in približnih odvisnosti // Računalniški časopis. – 1999. – T. 42. – Št. 2. – str. 100-111.
- Kruse S., Naumann F. Učinkovito odkrivanje približnih odvisnosti // Proceedings of the VLDB Endowment. – 2018. – T. 11. – Št. 7. – str. 759-772.
- Papenbrock T., Naumann F. Hibridni pristop k odkrivanju funkcionalne odvisnosti // Zbornik Mednarodne konference o upravljanju podatkov 2016. – ACM, 2016. – pp. 821-833.
- Papenbrock T. et al. Funkcionalno odkrivanje odvisnosti: eksperimentalna ocena sedmih algoritmov // Proceedings of the VLDB Endowment. – 2015. – T. 8. – Št. 10. – 1082-1093 strani.
- Kumar A. et al. Pridružiti se ali ne pridružiti se?: dvakrat premisliti o združitvah pred izbiro funkcij // Zbornik mednarodnih konferenc o upravljanju podatkov 2016. – ACM, 2016. – Str. 19-34.
- Abo Khamis M. et al. Učenje v bazi podatkov z redkimi tenzorji //Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems. – ACM, 2018. – pp. 325-340.
- Hellerstein J. M. et al. Analitična knjižnica MADlib: ali spretnosti MAD, SQL //Proceedings of the VLDB Endowment. – 2012. – T. 5. – Št. 12. – str. 1700-1711.
- Qin C., Rusu F. Špekulativne aproksimacije za optimizacijo spuščanja porazdeljenega gradienta na teraskali // Zbornik četrte delavnice o podatkovni analitiki v oblaku. – ACM, 2015. – Str. 1.
- Meng X. et al. Mllib: Strojno učenje v apache spark // The Journal of Machine Learning Research. – 2016. – T. 17. – Št. 1. – str. 1235-1241.
Avtorji članka: , raziskovalec na , и , raziskovalec na
Vir: www.habr.com