Í þessari grein munum við tala um hagnýtar ósjálfstæði í gagnagrunnum - hvað þær eru, hvar þær eru notaðar og hvaða reiknirit eru til til að finna þær.
Við munum íhuga hagnýtar ósjálfstæði í samhengi við tengslagagnagrunna. Í grófum dráttum eru upplýsingar geymdar í töfluformi í slíkum gagnagrunnum. Næst notum við áætluð hugtök sem ekki er hægt að skipta um í ströngum venslafræði: við munum kalla töfluna sjálfa tengsl, dálkana - eiginleika (mengi þeirra - tengslaskema) og mengi línugilda á undirmengi eiginda - túpel.
Til dæmis, í töflunni hér að ofan, (Benson, M, M orgel) er hópur af eiginleikum (sjúklingur, Páll, læknir).
Meira formlega er þetta skrifað á eftirfarandi hátt: [Sjúklingur, kyn, læknir] = (Benson, M, M orgel).
Nú getum við kynnt hugtakið virknifíkn (FD):
Skilgreining 1. Tengslin R uppfylla sambandslögin X → Y (þar sem X, Y ⊆ R) ef og aðeins ef fyrir einhverja tuple , ∈ R heldur: ef [X] = [X], þá [Y] = [Y]. Í þessu tilviki segjum við að X (ákvörðunarþátturinn, eða skilgreiningarmengi eiginda) ákvarði Y (háða mengið).
Með öðrum orðum, tilvist alríkislaga X → Y þýðir að ef við erum með tvo tuple inn R og þeir passa saman í eiginleikum X, þá munu þeir falla saman í eiginleikum Y.
Og nú, í röð. Við skulum skoða eiginleikana Sjúklingur и Paul þar sem við viljum komast að því hvort það séu ósjálfstæði á milli þeirra eða ekki. Fyrir slíkt safn af eiginleikum geta eftirfarandi ósjálfstæði verið til staðar:
- Sjúklingur → Kyn
- Kyn → Sjúklingur
Eins og skilgreint er hér að ofan, til þess að fyrsta ósjálfstæði haldi, hvert einstakt dálkgildi Sjúklingur aðeins eitt dálkgildi verður að passa Paul. Og fyrir dæmitöfluna er þetta svo sannarlega raunin. Hins vegar virkar þetta ekki í þveröfuga átt, það er að annarri ósjálfstæði er ekki fullnægt, og eiginleiki Paul er ekki ákvarðandi fyrir Sjúklingur. Á sama hátt, ef við tökum ósjálfstæði Læknir → Sjúklingur, þú getur séð að það er brotið, þar sem gildi Robin þessi eiginleiki hefur nokkra mismunandi merkingu - Ellis og Graham.
Þannig gera starfrænar ósjálfstæðir það mögulegt að ákvarða núverandi tengsl milli setta af töflueigindum. Héðan í frá munum við líta á áhugaverðustu tengslin, eða réttara sagt slík X → Yhvað þeir eru:
- ekki léttvæg, það er að segja að hægri hlið ósjálfstæðisins er ekki hlutmengi vinstri (Y ̸⊆ X);
- lágmark, það er, það er engin slík ósjálfstæði Z → YÞað Z ⊂ X.
Ósjálfstæðin sem talin voru fram til þessa voru ströng, það er að segja að þau hafi ekki gert ráð fyrir neinum brotum á borðinu, en auk þeirra eru einnig þau sem leyfa nokkurt ósamræmi á milli gilda tuples. Slíkar ósjálfstæðir eru settir í sérstakan flokk, sem kallast áætluð, og leyfilegt er að brjóta þær fyrir ákveðinn fjölda tuples. Þessari upphæð er stjórnað af hámarksvilluvísinum emax. Til dæmis villuhlutfallið = 0.01 getur þýtt að ósjálfstæði getur verið brotið af 1% af tiltækum tuples á íhuguðu mengi eiginda. Það er, fyrir 1000 færslur, að hámarki 10 tuples geta brotið sambandslögin. Við munum íhuga örlítið mismunandi mælikvarða, byggt á mismunandi gildum túplanna sem bornir eru saman. Fyrir fíkn X → Y um viðhorf r það er talið svona:
Við skulum reikna villuna fyrir Læknir → Sjúklingur úr dæminu hér að ofan. Við erum með tvo túlla þar sem gildin eru mismunandi á eigindinni Sjúklingur, en falla að Læknir: [Læknir, sjúklingur] = (Robin, Ellis) Og [Læknir, sjúklingur] = (Robin, Graham). Eftir skilgreiningu á villu verðum við að taka tillit til allra pöra sem stangast á, sem þýðir að þau verða tvö: (, ) og snúningur þess (, ). Við skulum skipta því út í formúluna og fá:
Nú skulum við reyna að svara spurningunni: "Af hverju er þetta allt fyrir?" Reyndar eru alríkislögin önnur. Fyrsta tegundin er þau ósjálfstæði sem eru ákvörðuð af stjórnanda á hönnunarstigi gagnagrunnsins. Þeir eru yfirleitt fáir, strangir, og aðalforritið er gagnastilling og tengslakerfishönnun.
Önnur tegundin er ósjálfstæði, sem tákna „falin“ gögn og áður óþekkt tengsl milli eiginleika. Það er að segja að slíkar ósjálfstæðir voru ekki hugsaðar um við hönnunina og þær finnast fyrir núverandi gagnasett, svo að síðar, byggt á mörgum tilgreindum sambandslögum, er hægt að draga einhverjar ályktanir um geymdar upplýsingar. Það eru einmitt þessi ósjálfstæði sem við vinnum með. Þeir eru teknir af heilu sviði gagnavinnslu með ýmsum leitartækni og reikniritum byggðum á þeim. Við skulum reikna út hvernig starfrænar ósjálfstæðir (nákvæmar eða áætlaðar) í hvaða gögnum sem er geta verið gagnlegar.
Í dag er eitt helsta forrit ósjálfstæðis gagnahreinsun. Það felur í sér að þróa ferla til að bera kennsl á „óhrein gögn“ og leiðrétta þau síðan. Áberandi dæmi um „óhrein gögn“ eru afrit, gagnavillur eða innsláttarvillur, gildi sem vantar, úrelt gögn, aukabil og þess háttar.
Dæmi um gagnavillu:
Dæmi um afrit í gögnum:
Til dæmis höfum við töflu og sett af alríkislögum sem þarf að framkvæma. Gagnahreinsun í þessu tilfelli felur í sér að breyta gögnunum þannig að sambandslögin verði rétt. Í þessu tilviki ætti fjöldi breytinga að vera í lágmarki (þessi aðferð hefur sína eigin reiknirit, sem við munum ekki einblína á í þessari grein). Hér að neðan er dæmi um slíka gagnabreytingu. Vinstra megin er upprunalega sambandið, þar sem augljóslega er ekki uppfyllt nauðsynleg FL (dæmi um brot á einum FL er auðkennt með rauðu). Hægra megin er uppfært samband, með grænu reitunum sem sýna breytt gildi. Eftir þessa aðferð fór að viðhalda nauðsynlegum ósjálfstæði.
Annað vinsælt forrit er gagnagrunnshönnun. Hér er rétt að rifja upp eðlileg form og normalization. Normalization er ferlið við að koma tengslum í samræmi við ákveðnar kröfur, sem hver um sig er skilgreind af eðlilegu formi á sinn hátt. Við munum ekki lýsa kröfum ýmissa venjulegra forma (þetta er gert í hvaða bók sem er um gagnagrunnsnámskeið fyrir byrjendur), en við munum aðeins taka fram að hvert þeirra notar hugtakið starfrænar ósjálfstæði á sinn hátt. Þegar öllu er á botninn hvolft eru FLs í eðli sínu heiðarleikatakmarkanir sem tekið er tillit til þegar gagnagrunnur er hannaður (í samhengi við þetta verkefni eru FLs stundum kallaðir ofurlyklar).
Við skulum íhuga umsókn þeirra um fjögur venjuleg eyðublöð á myndinni hér að neðan. Mundu að venjulegt form Boyce-Codd er strangara en þriðja form, en minna strangt en fjórða. Við erum ekki að íhuga hið síðarnefnda í bili, þar sem mótun þess krefst skilnings á fjölgildum háðum, sem eru ekki áhugaverðar fyrir okkur í þessari grein.
Annað svæði þar sem ósjálfstæðir hafa fundið beitingu sína er að draga úr vídd eiginleika rýmisins í verkefnum eins og að byggja upp barnalegan Bayes flokkara, greina mikilvæga eiginleika og endurskipuleggja aðhvarfslíkan. Í upprunalegu greinunum er þetta verkefni kallað ákvörðun um óþarfa og eiginleika mikilvægi [5, 6] og það er leyst með virkri notkun gagnagrunnshugtaka. Með tilkomu slíkra verka má segja að í dag sé eftirspurn eftir lausnum sem gera okkur kleift að sameina gagnagrunn, greiningu og útfærslu á ofangreindum hagræðingarvandamálum í eitt verkfæri [7, 8, 9].
Það eru til mörg reiknirit (bæði nútímaleg og ekki svo nútímaleg) til að leita að alríkislögum í gagnasafni. Slíkum reikniritum má skipta í þrjá hópa:
- Reiknirit sem nota yfirferð algebrugrindanna (Griðlaralgrímar)
- Reiknirit byggð á leit að samþykktum gildum (munur- og samþykkja reiknirit)
- Reiknirit byggt á parslegum samanburði (Dependency induction algorithms)
Stutt lýsing á hverri tegund reiknirit er sýnd í töflunni hér að neðan:
Þú getur lesið meira um þessa flokkun [4]. Hér að neðan eru dæmi um reiknirit fyrir hverja tegund:
Eins og er birtast ný reiknirit sem sameina nokkrar aðferðir til að finna hagnýtar ósjálfstæði. Dæmi um slík reiknirit eru Pyro [2] og HyFD [3]. Gert er ráð fyrir greiningu á starfi þeirra í eftirfarandi greinum í þessari ritröð. Í þessari grein munum við aðeins skoða grunnhugtökin og lemma sem eru nauðsynleg til að skilja tæknigreiningaraðferðir.
Við skulum byrja á einföldu - munur- og sammála-mengi, notað í annarri gerð reikniritanna. Mismunamengi er mengi af túllum sem hafa ekki sömu gildi, en sammála-mengi, þvert á móti, er túllum sem hafa sömu gildi. Það er rétt að taka fram að í þessu tilfelli erum við aðeins að huga að vinstri hlið ósjálfstæðisins.
Annað mikilvægt hugtak sem kom fram hér að ofan er algebrugrindin. Þar sem mörg nútíma reiknirit starfa eftir þessu hugtaki, þurfum við að hafa hugmynd um hvað það er.
Til þess að kynna hugtakið grind er nauðsynlegt að skilgreina hlutaröðað mengi (eða hlutaraðað mengi, skammstafað sem poset).
Skilgreining 2. Sagt er að mengi S sé að hluta til raðað eftir tvíundartengslunum ⩽ ef fyrir alla a, b, c ∈ S eru eftirfarandi eiginleikar uppfylltir:
- Reflexivity, það er a ⩽ a
- Andsamhverfa, það er að segja ef a ⩽ b og b ⩽ a, þá er a = b
- Transitivity, það er, fyrir a ⩽ b og b ⩽ c fylgir að a ⩽ c
Slík vensla kallast (laus) hlutröðunartengsl og mengið sjálft kallað hlutaröðuð mengi. Formlegt tákn: ⟨S, ⩽⟩.
Sem einfaldasta dæmið um hlutaraðað mengi getum við tekið mengi allra náttúrulegra talna N með venjulegu röðunartengslunum ⩽. Auðvelt er að sannreyna að öllum nauðsynlegum grunnsetningum sé fullnægt.
Merkingarríkara dæmi. Lítum á mengi allra hlutmengja {1, 2, 3}, raðað eftir inntökutengslunum ⊆. Reyndar uppfyllir þetta samband öll skilyrði fyrir hlutaröð, þannig að ⟨P ({1, 2, 3}), ⊆⟩ er að hluta til röð. Myndin hér að neðan sýnir uppbyggingu þessa mengis: ef hægt er að ná í einn þátt með örvum til annars þáttar, þá eru þeir í röð sambandi.
Okkur vantar tvær einfaldar skilgreiningar til viðbótar frá sviði stærðfræði - supremum og infimum.
Skilgreining 3. Látum ⟨S, ⩽⟩ vera hlutaraðað mengi, A ⊆ S. Efri mörk A er stakt u ∈ S þannig að ∀x ∈ S: x ⩽ u. Látum U vera mengi allra efri mörka S. Ef það er minnsti þáttur í U, þá er það kallað supremum og er táknað sup A.
Hugmyndin um nákvæm lægri mörk er kynnt á svipaðan hátt.
Skilgreining 4. Látum ⟨S, ⩽⟩ vera hlutaraðað mengi, A ⊆ S. Innifalið á A er frumefni l ∈ S þannig að ∀x ∈ S: l ⩽ x. Látum L vera mengi allra neðri marka S. Ef stærsti þátturinn er í L, þá er hann kallaður infimum og er táknaður inf A.
Líttu á sem dæmi hér að ofan hlutaröðuðu mengi ⟨P ({1, 2, 3}), ⊆⟩ og finndu æðsta og innifalið í því:
Nú getum við mótað skilgreiningu á algebrugrindum.
Skilgreining 5. Látum ⟨P,⩽⟩ vera hlutaröðuðu mengi þannig að hvert tveggja þátta hlutmengi hefur efri og neðri mörk. Þá er P kallað algebrugrind. Í þessu tilviki er sup{x, y} skrifað sem x ∨ y, og inf {x, y} sem x ∧ y.
Athugum að vinnudæmið okkar ⟨P ({1, 2, 3}), ⊆⟩ er grind. Reyndar, fyrir hvaða a, b ∈ P ({1, 2, 3}), a∨b = a∪b og a∧b = a∩b. Skoðaðu til dæmis mengin {1, 2} og {1, 3} og finndu infimum og supremum þeirra. Ef við skerum þau, fáum við mengið {1}, sem mun vera nafnið. Við fáum yfirburðinn með því að sameina þau - {1, 2, 3}.
Í reikniritum til að bera kennsl á líkamleg vandamál er leitarrýmið oft táknað í formi grindar, þar sem mengi eins staks (lesið fyrsta stig leitargrindarinnar, þar sem vinstri hlið ósjálfstæðanna samanstendur af einum eigindi) tákna hvern eiginleika af upprunalegu sambandi.
Í fyrsta lagi lítum við á ósjálfstæði formsins ∅ → Einn eiginleiki. Þetta skref gerir þér kleift að ákvarða hvaða eiginleikar eru aðallyklar (fyrir slíka eiginleika eru engir ákvarðanir og því er vinstri hliðin tóm). Ennfremur færast slík reiknirit upp eftir grindunum. Það er athyglisvert að ekki er hægt að fara yfir alla grindina, það er að segja ef æskileg hámarksstærð vinstri hliðar er send til inntaksins, þá mun reikniritið ekki fara lengra en stigi með þeirri stærð.
Myndin hér að neðan sýnir hvernig hægt er að nota algebrugrind í vandamálinu við að finna FZ. Hér hver brún (X, XY) táknar ósjálfstæði X → Y. Við höfum til dæmis staðist fyrsta þrepið og vitum að fíkninni er viðhaldið A → B (við munum sýna þetta sem græna tengingu milli hornpunktanna A и B). Þetta þýðir að lengra, þegar við förum upp eftir grindunum, gætum við ekki athugað ósjálfstæði A, C → B, því það verður ekki lengur lágmark. Á sama hátt myndum við ekki athuga það ef ósjálfstæði væri haldið C → B.
Að auki, að jafnaði, nota öll nútíma reiknirit til að leita að alríkislögum gagnauppbyggingu eins og skipting (í upprunalegu upprunanum - strípuð skipting [1]). Formleg skilgreining á skipting er sem hér segir:
Skilgreining 6. Látum X ⊆ R vera mengi eiginda fyrir vensl r. Þyrping er mengi af túllum í r sem hafa sama gildi fyrir X, það er c(t) = {i|ti[X] = t[X]}. Skipting er safn af klösum, að undanskildum klösum með lengd eininga:
Í einföldum orðum, skipting fyrir eigind X er safn af lista, þar sem hver listi inniheldur línunúmer með sömu gildum fyrir X. Í nútímabókmenntum er uppbyggingin sem táknar skipting kölluð stöðulistavísitala (PLI). Einingalengdarklasar eru útilokaðir vegna PLI-þjöppunar vegna þess að þeir eru klasar sem innihalda aðeins skráningarnúmer með einstakt gildi sem alltaf er auðvelt að bera kennsl á.
Við skulum líta á dæmi. Snúum okkur aftur að sömu töflu með sjúklingum og byggjum skilrúm fyrir dálkana Sjúklingur и Paul (Nýr dálkur hefur birst til vinstri, þar sem númer töflulínunnar eru merkt):
Þar að auki, samkvæmt skilgreiningunni, skiptingin fyrir dálkinn Sjúklingur verður í raun tómt þar sem stakir klasar eru útilokaðir frá skiptingunni.
Skipting er hægt að fá með nokkrum eiginleikum. Og það eru tvær leiðir til að gera þetta: með því að fara í gegnum töfluna, byggðu skipting með því að nota alla nauðsynlega eiginleika í einu, eða byggðu hana með því að nota skurðaðgerðir skiptinga með því að nota undirmengi eiginda. Leitaralgrím alríkislaga nota seinni valkostinn.
Í einföldum orðum, til að fá til dæmis skipting eftir dálkum ABC, þú getur tekið skipting fyrir AC и B (eða önnur mengi ósamstæðra hlutmengja) og skera þau hvert við annað. Aðgerð skurðpunkta tveggja skilrúma velur þyrpingar af stærstu lengd sem eru sameiginlegar fyrir báðar skiptingarnar.
Við skulum skoða dæmi:
Í fyrra tilvikinu fengum við tómt skipting. Ef þú lítur vel á töfluna, þá eru í raun engin eins gildi fyrir eiginleikana tvo. Ef við breytum töflunni lítillega (tilfellið til hægri) fáum við nú þegar gatnamót sem ekki eru tóm. Þar að auki innihalda línur 1 og 2 í raun sömu gildi fyrir eiginleikana Paul и Læknir.
Næst munum við þurfa slíkt hugtak eins og skiptingarstærð. Formlega:
Einfaldlega sagt, skiptingarstærðin er fjöldi klasa sem eru í skiptingunni (mundu að stakir klasar eru ekki með í skiptingunni!):
Nú getum við skilgreint eitt af lykillemmunum, sem fyrir gefnar skiptingar gerir okkur kleift að ákvarða hvort ósjálfstæði sé haldið eða ekki:
Lemma 1. Ósjálfstæði A, B → C gildir ef og aðeins ef
Samkvæmt lemma þarf að framkvæma fjögur skref til að ákvarða hvort ósjálfstæði haldist:
- Reiknaðu skiptinguna fyrir vinstri hlið ósjálfstæðisins
- Reiknaðu skiptinguna fyrir hægri hlið ósjálfstæðisins
- Reiknaðu afurð fyrsta og annars skrefs
- Berðu saman stærðir skiptinganna sem fengust í fyrsta og þriðja skrefi
Hér að neðan er dæmi um að athuga hvort ósjálfstæði haldist samkvæmt þessu lemma:
Í þessari grein skoðuðum við hugtök eins og virknifíkn, áætluð virknifíkn, skoðuðum hvar þau eru notuð, sem og hvaða reiknirit til að leita að líkamlegum aðgerðum eru til. Við skoðuðum einnig ítarlega helstu en mikilvægu hugtökin sem eru virkan notuð í nútíma reikniritum til að leita að alríkislögum.
Heimildir:
- Huhtala Y. o.fl. TANE: Skilvirkt reiknirit til að uppgötva hagnýtar og áætlaðar ósjálfstæði //Tölvudagbókin. – 1999. – T. 42. – Nei. 2. – bls 100-111.
- Kruse S., Naumann F. Skilvirk uppgötvun á áætluðum ósjálfstæði // Proceedings of the VLDB Endowment. – 2018. – T. 11. – Nei. 7. – bls 759-772.
- Papenbrock T., Naumann F. A blending approach to functional dependency discovery //Proceedings of the 2016 International Conference on Management of Data. – ACM, 2016. – bls. 821-833.
- Papenbrock T. o.fl. Functional dependency discovery: Tilraunamat á sjö reikniritum //Proceedings of the VLDB Endowment. – 2015. – T. 8. – Nei. 10. – bls 1082-1093.
- Kumar A. o.fl. Til að taka þátt eða ekki að taka þátt?: Hugsaðu þig tvisvar um að taka þátt áður en eiginleikar eru valdir //Proceedings of the 2016 International Conference on Management of Data. – ACM, 2016. – bls. 19-34.
- Abo Khamis M. o.fl. Nám í gagnagrunni með dreifðum tensorum //Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems. – ACM, 2018. – bls. 325-340.
- Hellerstein JM o.fl. MADlib greiningarsafnið: eða MAD færni, SQL //Proceedings of the VLDB Endowment. – 2012. – T. 5. – Nei. 12. – bls 1700-1711.
- Qin C., Rusu F. Hugmyndafræðilegar nálganir fyrir fínstillingu dreifðrar hallarfalls á jörðu niðri //Proceedings of the Fourth Workshop on Data analytics in the Cloud. – ACM, 2015. – Bls. 1.
- Meng X. o.fl. Mllib: Machine learning in apache spark //The Journal of Machine Learning Research. – 2016. – T. 17. – Nei. 1. – bls 1235-1241.
Greinarhöfundar: , rannsakandi við , и , rannsakandi við
Heimild: www.habr.com