Selles artiklis räägime andmebaaside funktsionaalsetest sõltuvustest - mis need on, kus neid kasutatakse ja millised algoritmid on nende leidmiseks olemas.
Funktsionaalseid sõltuvusi käsitleme relatsiooniandmebaaside kontekstis. Väga jämedalt öeldes salvestatakse sellistes andmebaasides teave tabelite kujul. Järgmisena kasutame ligikaudseid mõisteid, mis pole ranges relatsiooniteoorias omavahel asendatavad: tabelit ennast nimetame relatsiooniks, veerge - atribuute (nende hulk - seosskeem) ja atribuutide alamhulga reaväärtuste kogumit. - korteež.
Näiteks ülaltoodud tabelis (Benson, M, M orel) on atribuutide hulk (Patsient, Paul, arst).
Ametlikumalt on see kirjutatud järgmiselt: [Patsient, sugu, arst] = (Benson, M, M orel).
Nüüd saame tutvustada funktsionaalse sõltuvuse (FD) mõistet:
1. definitsioon. Seos R vastab föderaalseadusele X → Y (kus X, Y ⊆ R) siis ja ainult siis, kui mis tahes korteeži puhul , ∈ R kehtib: kui [X] = [X] siis [Y] = [Y]. Sel juhul ütleme, et X (determinant ehk defineeriv atribuutide hulk) määrab funktsionaalselt Y (sõltuva hulga).
Teisisõnu, föderaalseaduse olemasolu X → Y tähendab, et kui meil on kaks korrust R ja need vastavad atribuutide poolest X, siis langevad need atribuutides kokku Y.
Ja nüüd järjekorras. Vaatame atribuute Patsient и Paul mille puhul tahame välja selgitada, kas nende vahel on sõltuvusi või mitte. Sellise atribuutide komplekti puhul võivad esineda järgmised sõltuvused:
- Patsient → Sugu
- Sugu → Patsient
Nagu eespool määratletud, et esimene sõltuvus kehtiks, iga kordumatu veeru väärtus Patsient ainult üks veeru väärtus peab ühtima Paul. Ja näitetabeli puhul on see tõepoolest nii. Kuid see ei tööta vastupidises suunas, see tähendab, et teine sõltuvus ei ole täidetud ja atribuut Paul ei ole määrav Patsient. Samamoodi, kui võtame sõltuvuse Arst → Patsient, näete, et seda on rikutud, kuna väärtus punarind sellel atribuudil on mitu erinevat tähendust - Ellis ja Graham.
Seega võimaldavad funktsionaalsed sõltuvused määrata olemasolevaid seoseid tabeliatribuutide komplektide vahel. Siit edasi käsitleme kõige huvitavamaid seoseid või pigem selliseid X → Ymis need on:
- mittetriviaalne, see tähendab, et sõltuvuse parem pool ei ole vasaku alamhulk (Y ̸⊆ X);
- minimaalne, see tähendab, et sellist sõltuvust pole Z → YEt Z ⊂ X.
Seni käsitletud sõltuvused olid ranged, see tähendab, et need ei näinud tabelis ette ühtegi rikkumist, kuid lisaks neile on ka neid, mis lubavad korteeži väärtuste vahel mõningast ebakõla. Sellised sõltuvused paigutatakse eraldi klassi, mida nimetatakse ligikaudseteks, ja neid on lubatud rikkuda teatud arvu korral. Seda summat reguleerib maksimaalse vea indikaator emax. Näiteks veamäär = 0.01 võib tähendada, et sõltuvust võib rikkuda 1% vaadeldava atribuutide komplekti saadaolevatest korteežidest. See tähendab, et 1000 kirje puhul võib föderaalseadust rikkuda maksimaalselt 10 korrust. Vaatleme veidi teistsugust mõõdikut, mis põhineb võrreldavate korteežide paarikaupa erinevatel väärtustel. Sõltuvuse eest X → Y suhtumise kohta r seda peetakse nii:
Arvutame vea Arst → Patsient ülaltoodud näitest. Meil on kaks korrust, mille atribuudi väärtused erinevad Patsient, kuid langevad kokku Arst: [Arst, patsient] = (Robin, Ellis) Ja [Arst, patsient] = (Robin, Graham). Vea definitsiooni järgi peame arvesse võtma kõiki vastuolulisi paare, mis tähendab, et neid on kaks: (, ) ja selle pöördväärtus (, ). Asendame selle valemiga ja saame:
Nüüd proovime vastata küsimusele: "Miks see kõik on?" Tegelikult on föderaalseadused erinevad. Esimene tüüp on need sõltuvused, mille administraator määrab andmebaasi kujundamise etapis. Neid on tavaliselt vähe, need on ranged ja peamine rakendus on andmete normaliseerimine ja relatsiooniskeemi kujundamine.
Teine tüüp on sõltuvused, mis esindavad "peidetud" andmeid ja varem tundmatuid seoseid atribuutide vahel. See tähendab, et projekteerimise ajal sellistele sõltuvustele ei mõelnud ja need leitakse olemasoleva andmekogumi jaoks, nii et hiljem saab paljude tuvastatud föderaalseaduste põhjal teha salvestatud teabe kohta mingeid järeldusi. Just nende sõltuvustega me töötame. Nendega tegeleb terve andmekaeve valdkond koos erinevate otsingutehnikate ja nende baasil üles ehitatud algoritmidega. Mõelgem välja, kuidas mis tahes andmetes leitud funktsionaalsed sõltuvused (täpsed või ligikaudsed) võivad olla kasulikud.
Tänapäeval on sõltuvuste üks peamisi rakendusi andmete puhastamine. See hõlmab protsesside väljatöötamist "määrdunud andmete" tuvastamiseks ja seejärel nende parandamiseks. "Mustade andmete" silmapaistvad näited on duplikaadid, andmevead või kirjavead, puuduvad väärtused, aegunud andmed, lisatühikud ja muu sarnane.
Andmevea näide:
Näide andmete duplikaatidest:
Näiteks on meil tabel ja föderaalseaduste kogum, mida tuleb täita. Andmete puhastamine hõlmab sel juhul andmete muutmist, et föderaalseadused muutuksid õigeks. Sel juhul peaks muudatuste arv olema minimaalne (sellel protseduuril on oma algoritmid, millele me selles artiklis ei keskendu). Allpool on näide sellisest andmete teisendamisest. Vasakul on algne suhe, milles ilmselgelt ei ole vajalikud FL-id täidetud (näide ühe FL-i rikkumisest on punasega esile tõstetud). Paremal on värskendatud suhe, rohelised lahtrid näitavad muudetud väärtusi. Pärast seda protseduuri hakati säilitama vajalikke sõltuvusi.
Teine populaarne rakendus on andmebaasi kujundamine. Siinkohal tasub meenutada normaalvorme ja normaliseerimist. Normaliseerimine on protsess, mille käigus viiakse seos vastavusse teatud nõuetega, millest igaüks on normaalvormiga omal moel defineeritud. Me ei kirjelda erinevate normaalvormide nõudeid (seda tehakse igas algajatele mõeldud andmebaasikursuse raamatus), kuid märgime ainult, et igaüks neist kasutab funktsionaalsete sõltuvuste mõistet omal moel. FL-id on ju oma olemuselt terviklikkuse piirangud, mida arvestatakse andmebaasi kujundamisel (selle ülesande kontekstis nimetatakse FL-e mõnikord ka supervõtmeteks).
Vaatleme nende taotlust neljale alloleval pildil olevale tavavormile. Tuletame meelde, et Boyce-Coddi tavavorm on rangem kui kolmas vorm, kuid vähem range kui neljas. Viimast me praegu ei kaalu, kuna selle sõnastamine eeldab mitmeväärtuslike sõltuvuste mõistmist, mis meid selles artiklis ei huvita.
Teine valdkond, kus sõltuvused on rakendust leidnud, on funktsiooniruumi mõõtmete vähendamine sellistes ülesannetes nagu naiivse Bayesi klassifikaatori loomine, oluliste tunnuste tuvastamine ja regressioonimudeli ümberparameetrite muutmine. Algsetes artiklites nimetatakse seda ülesannet liiasuse ja funktsiooni asjakohasuse määramiseks [5, 6] ning see lahendatakse andmebaasikontseptsioonide aktiivse kasutamisega. Selliste tööde tulekuga võib öelda, et tänapäeval on nõudlus lahenduste järele, mis võimaldavad ühendada andmebaasi, analüütika ja ülaltoodud optimeerimisülesannete realiseerimise üheks tööriistaks [7, 8, 9].
Andmekogust föderaalseaduste otsimiseks on palju algoritme (nii kaasaegseid kui ka mitte nii kaasaegseid). Sellised algoritmid võib jagada kolme rühma:
- Algebraliste võre läbimist kasutavad algoritmid (võre läbimise algoritmid)
- Algoritmid, mis põhinevad kokkulepitud väärtuste otsimisel (erinevus- ja kokkuleppealgoritmid)
- Paaripõhisel võrdlusel põhinevad algoritmid (sõltuvuse esilekutsumise algoritmid)
Igat tüüpi algoritmi lühikirjeldus on esitatud allolevas tabelis:
Selle klassifikatsiooni kohta saate rohkem lugeda [4]. Allpool on toodud iga tüübi algoritmide näited.
Praegu ilmuvad uued algoritmid, mis ühendavad mitmeid lähenemisviise funktsionaalsete sõltuvuste leidmiseks. Sellised algoritmid on näiteks Pyro [2] ja HyFD [3]. Nende töö analüüsi oodatakse selle sarja järgmistes artiklites. Selles artiklis käsitleme ainult põhimõisteid ja lemmat, mis on vajalikud sõltuvuse tuvastamise tehnikate mõistmiseks.
Alustame lihtsast – erinevus- ja nõustukomplektist, mida kasutatakse teist tüüpi algoritmides. Difference-set on korteežide kogum, millel ei ole samad väärtused, samas kui nõustumiskomplekt on vastupidi, samade väärtustega korteežid. Väärib märkimist, et antud juhul arvestame ainult sõltuvuse vasaku poolega.
Teine oluline ülaltoodud mõiste on algebraline võre. Kuna paljud kaasaegsed algoritmid töötavad selle kontseptsiooni alusel, peab meil olema ettekujutus, mis see on.
Võre mõiste tutvustamiseks on vaja defineerida osaliselt järjestatud hulk (või osaliselt järjestatud hulk, lühendatult poset).
2. definitsioon. Hulk S on osaliselt järjestatud kahendseose ⩽ järgi, kui kõigi a, b, c ∈ S korral on täidetud järgmised omadused:
- Refleksiivsus, see tähendab a ⩽ a
- Antisümmeetria, st kui a ⩽ b ja b ⩽ a, siis a = b
- Transitiivsus, st a ⩽ b ja b ⩽ c korral järeldub, et a ⩽ c
Sellist seost nimetatakse (lõdva) osalise järjestuse seoseks ja hulka ennast osaliselt järjestatud hulgaks. Formaalne märge: ⟨S, ⩽⟩.
Lihtsaima näitena osaliselt järjestatud hulgast võime võtta kõigi naturaalarvude hulga N tavalise järjestusseosega ⩽. Lihtne on kontrollida, kas kõik vajalikud aksioomid on täidetud.
Mõttekam näide. Vaatleme kõigi alamhulkade hulka {1, 2, 3}, mis on järjestatud kaasamise seose ⊆ järgi. Tõepoolest, see seos rahuldab kõik osalise järjestuse tingimused, seega ⟨P ({1, 2, 3}), ⊆⟩ on osaliselt järjestatud hulk. Alloleval joonisel on kujutatud selle komplekti ülesehitus: kui ühele elemendile pääseb nooltega teisele elemendile, siis on need järjestuses.
Vajame matemaatika valdkonnast veel kahte lihtsat määratlust - supremum ja infimum.
3. definitsioon. Olgu ⟨S, ⩽⟩ osaliselt järjestatud hulk A ⊆ S. A ülempiir on element u ∈ S nii, et ∀x ∈ S: x ⩽ u. Olgu U kõigi S ülemiste piiride hulk. Kui U-s on väikseim element, siis nimetatakse seda ülemsummaks ja tähistatakse sup A.
Sarnaselt tutvustatakse ka täpse alampiiri mõistet.
4. definitsioon. Olgu ⟨S, ⩽⟩ osaliselt järjestatud hulk, A ⊆ S. A infimum on element l ∈ S nii, et ∀x ∈ S: l ⩽ x. Olgu L kõigi S alumiste piiride hulk. Kui L-s on suurim element, siis nimetatakse seda infimumiks ja tähistatakse kui inf A.
Vaatleme näitena ülaltoodud osaliselt järjestatud hulka ⟨P ({1, 2, 3}), ⊆⟩ ja leidke sellest ülem- ja infimum:
Nüüd saame sõnastada algebralise võre definitsiooni.
5. definitsioon. Olgu ⟨P,⩽⟩ osaliselt järjestatud hulk, nii et igal kaheelemendilisel alamhulgal on ülemine ja alumine piir. Siis P nimetatakse algebraliseks võreks. Sel juhul kirjutatakse sup{x, y} kui x ∨ y ja inf {x, y} kui x ∧ y.
Kontrollime, kas meie töönäide ⟨P ({1, 2, 3}), ⊆⟩ on võre. Tõepoolest, iga a korral b ∈ P ({1, 2, 3}), a∨b = a∪b ja a∧b = a∩b. Näiteks kaaluge hulkasid {1, 2} ja {1, 3} ning leidke nende infimum ja ülemsumma. Kui me neid ristame, saame hulga {1}, mis on infimum. Supremumi saame nende kombineerimisel - {1, 2, 3}.
Füüsiliste probleemide tuvastamise algoritmides on otsinguruum sageli kujutatud võre kujul, kus ühe elemendi hulgad (loe otsinguvõre esimest taset, kus sõltuvuste vasak pool koosneb ühest atribuudist) esindavad iga atribuuti. algsest suhtest.
Esiteks vaatleme vormi ∅ → sõltuvusi Üksik atribuut. See samm võimaldab teil määrata, millised atribuudid on primaarvõtmed (selliste atribuutide jaoks pole determinante ja seetõttu on vasak pool tühi). Lisaks liiguvad sellised algoritmid mööda võre ülespoole. Väärib märkimist, et kogu võre ei saa läbida, see tähendab, et kui sisendisse edastatakse vasaku külje soovitud maksimaalne suurus, siis ei lähe algoritm selle suurusega tasemest kaugemale.
Alloleval joonisel on näha, kuidas saab algebralist võret kasutada FZ leidmise ülesandes. Siin iga serv (X, XY) tähistab sõltuvust X → Y. Näiteks oleme läbinud esimese taseme ja teame, et sõltuvus säilib A → B (kuvame selle tippude vahel rohelise ühendusena A и B). See tähendab, et edasi mööda võret üles liikudes ei pruugi me sõltuvust kontrollida A, C → B, sest see ei ole enam minimaalne. Samamoodi ei kontrolliks me seda, kui sõltuvust hoitakse C → B.
Lisaks kasutavad kõik kaasaegsed föderaalseaduste otsimise algoritmid reeglina andmestruktuuri, näiteks partitsiooni (algallikas - eemaldatud partitsioon [1]). Sektsiooni ametlik määratlus on järgmine:
6. definitsioon. Olgu X ⊆ R atribuutide hulk seose r jaoks. Klaster on indeksite komplekt r-s olevatest korteežidest, millel on X jaoks sama väärtus, st c(t) = {i|ti[X] = t[X]}. Partitsioon on klastrite kogum, välja arvatud ühiku pikkusega klastrid:
Lihtsamalt öeldes atribuudi partitsioon X on loendite komplekt, kus iga loend sisaldab samade väärtustega reanumbreid X. Kaasaegses kirjanduses nimetatakse partitsioone esindavat struktuuri positsiooniloendi indeksiks (PLI). Ühiku pikkusega klastrid on PLI tihendamise eesmärgil välistatud, kuna need on klastrid, mis sisaldavad ainult unikaalse väärtusega kirjenumbrit, mida on alati lihtne tuvastada.
Vaatame näidet. Naaseme patsientidega sama tabeli juurde ja ehitame veergudele vaheseinad Patsient и Paul (vasakul on ilmunud uus veerg, kuhu on märgitud tabeli ridade numbrid):
Lisaks on määratluse kohaselt veeru partitsioon Patsient on tegelikult tühi, kuna üksikud klastrid on partitsioonist välja jäetud.
Partitsioone saab hankida mitme atribuudi abil. Ja selleks on kaks võimalust: tabelit läbides koostage partitsioon, kasutades kõiki vajalikke atribuute korraga, või looge see partitsioonide ristumisoperatsiooni abil, kasutades atribuutide alamhulka. Föderaalseaduse otsingualgoritmid kasutavad teist võimalust.
Lihtsamalt öeldes, et saada näiteks partitsioon veergude kaupa ABC, võite võtta vaheseinu AC и B (või mis tahes muu disjunktsete alamhulkade komplekt) ja lõikuvad need üksteisega. Kahe partitsiooni ristumisoperatsioon valib suurima pikkusega klastrid, mis on ühised mõlemale partitsioonile.
Vaatame näidet:
Esimesel juhul saime tühja partitsiooni. Kui vaatate tabelit tähelepanelikult, siis tõepoolest pole kahe atribuudi jaoks identseid väärtusi. Kui me veidi tabelit modifitseerime (parempoolne juhtum), saame juba mittetühja ristmiku. Veelgi enam, read 1 ja 2 sisaldavad tegelikult atribuutide jaoks samu väärtusi Paul и arst.
Järgmisena vajame sellist kontseptsiooni nagu partitsiooni suurus. Formaalselt:
Lihtsamalt öeldes on partitsiooni suurus partitsioonis sisalduvate klastrite arv (pidage meeles, et üksikud klastrid ei sisaldu partitsioonis!):
Nüüd saame määratleda ühe võtmelemma, mis antud partitsioonide puhul võimaldab meil määrata, kas sõltuvust hoitakse või mitte:
Lemma 1. Sõltuvus A, B → C kehtib siis ja ainult siis
Lemma kohaselt tuleb sõltuvuse kehtivuse kindlakstegemiseks teha neli sammu:
- Arvutage sõltuvuse vasaku poole partitsioon
- Arvutage sõltuvuse parema poole partitsioon
- Arvutage esimese ja teise etapi korrutis
- Võrrelge esimeses ja kolmandas etapis saadud vaheseinte suurusi
Allpool on näide, kuidas kontrollida, kas sõltuvus kehtib selle lemma järgi:
Selles artiklis uurisime selliseid mõisteid nagu funktsionaalne sõltuvus, ligikaudne funktsionaalne sõltuvus, uurisime, kus neid kasutatakse ja millised on füüsikaliste funktsioonide otsimise algoritmid. Samuti uurisime üksikasjalikult põhilisi, kuid olulisi mõisteid, mida tänapäevastes föderaalseaduste otsimise algoritmides aktiivselt kasutatakse.
Viited:
- Huhtala Y. jt. TANE: tõhus algoritm funktsionaalsete ja ligikaudsete sõltuvuste avastamiseks //Arvutipäevik. – 1999. – T. 42. – Nr. 2. – lk 100-111.
- Kruse S., Naumann F. Ligikaudsete sõltuvuste tõhus avastamine // Proceedings of the VLDB Endowment. – 2018. – T. 11. – Nr. 7. – lk 759-772.
- Papenbrock T., Naumann F. Hübriidne lähenemine funktsionaalse sõltuvuse avastamisele // 2016. aasta rahvusvahelise andmehalduse konverentsi toimetised. – ACM, 2016. – lk 821-833.
- Papenbrock T. et al. Funktsionaalse sõltuvuse avastamine: seitsme algoritmi eksperimentaalne hindamine //Proceedings of the VLDB Endowment. – 2015. – T. 8. – Nr. 10. – lk 1082-1093.
- Kumar A. et al. Liituda või mitte liituda?: Enne funktsioonide valimist mõtlen liitumisele kaks korda //2016. aasta rahvusvahelise andmehalduskonverentsi toimetised. – ACM, 2016. – lk 19-34.
- Abo Khamis M. et al. Andmebaasisisene õpe hõredate tensorite abil //Andmebaasisüsteemide põhimõtete 37. ACM SIGMOD-SIGACT-SIGAI sümpoosioni toimetised. – ACM, 2018. – lk 325-340.
- Hellerstein JM et al. MADlibi analüütikateek: või MAD-oskused, SQL //Proceedings of the VLDB Endowment. – 2012. – T. 5. – Nr. 12. – lk 1700-1711.
- Qin C., Rusu F. Spekulatiivsed lähendused teraskaala hajutatud gradiendi laskumise optimeerimiseks // Proceedings of the Fourth Workshop on Data analytics in the Cloud. – ACM, 2015. – Lk 1.
- Meng X. et al. Mllib: masinõpe apache sädemes //The Journal of Machine Learning Research. – 2016. – T. 17. – Nr. 1. – lk 1235-1241.
Artikli autorid: , teadur aadressil , и , teadur aadressil
Allikas: www.habr.com