Sissejuhatus funktsionaalsetesse sõltuvustesse

Selles artiklis arutame funktsionaalseid sõltuvusi andmebaasides — mis need on, kus neid kasutatakse ja millised algoritmid on nende leidmiseks olemas.

Me käsitleme funktsionaalseid sõltuvusi relatsiooniliste andmebaaside kontekstis. Üldiselt öeldes salvestatakse sellistes andmebaasides teave tabelite kujul. Edasi kasutame ligikaudseid mõisteid, mis ei ole range relatsiooniteooria kontekstis omavahel asendatavad: ise tabelit nimetame relatsiooniks, veerge — atribuutideks (nende kogumit — relatsiooni skeemiks) ja ridade väärtuste kogumit atribuutide alamhulgas — tupleks.

Näiteks ülaltoodud tabelis, (Benson, M, M organ) on tupleks atribuutide (Patsient, Sugu, Doktor).
Rohkem formaalselt on see järgmises vormis: [Patsient, Sugu, Doktor] = (Benson, M, M organ).
Nüüd võime sisse viia funktsionaalse sõltuvuse (FS) mõiste:

Määratlus 1. Relatsioon R rahuldab FS X → Y (kus X, Y ⊆ R) siis ja ainult siis, kui iga tuple R-is täidab: kui , [X] = [X], siis [Y ] = [Y ]. Sellisel juhul öeldakse, et X (determinant või määrav atribuutide kogum) määrab funktsionaalselt Y (sõltuvate atribuutide kogum). Teisisõnu, FS olemasolu

X → Y tähendab, et kui meil on kaks tupleksit ja need on samad attribuutide mõttes R , siis need peavad olema samad ka atribuutide järgi. XNüüd käsitleme järjestikku atribuute Y.
Patsient Sugu ja Sugu mille vahel soovime teada, kas nende vahel on sõltuvusi või mitte. Selle atribuuttüübi jaoks võivad eksisteerida järgmised sõltuvused:

1. Patsient → Sugu
2. Sugu → Patsient

Eelneva määratluse kohaselt peab esimese sõltuvuse säilimiseks igale unikaalsele veeru väärtusele vastama ainult üks veeru väärtus. Sugu Ja see on tõesti nii näidistabelis. Kuid vastupidises suunas see ei toimi, seega teine sõltuvus ei kehti ja atribuut Suguei ole determinant Sugu Patsient . Samamoodi, kui võtame sõltuvuseDoktor → Patsient , võib märkida, et see rikub, kuna väärtusRobin selle atribuudi järgi omab mitut erinevat väärtust — Ellis ja Graham Ellis ja Graham.

Seega funktsionaalne sõltuvus võimaldab määratleda olemasolevad seosed tabeli atribuutide kogumite vahel. Edaspidi käsitleme kõige huvitavamaid seoseid, täpsemalt selliseid tähendab, et kui meil on kaks tupleksit, mis on:

• mitte triviaalne, st sõltuvuse parem pool ei ole vasaku allhuvi (Y ̸⊆ X);
• minimaalne, st ei ole sellist sõltuvust Z → Y, et Z ⊂ X.

Kuni seni käsitletud sõltuvused on olnud ranged, st nad ei võimalda tabelis mingit rikkumist, kuid lisaks neile on ka selliseid, mis lubavad teatud tasemel ebakõla tupikute väärtuste vahel. Need sõltuvused jagatakse eraldi klassi, nimetatakse neid ligikaudseteks ning lubatakse rikkuda teatud arvu tupikutes. See number reguleeritakse maksimumvea näitaja emax abil. Näiteks veaprotsent = 0.01 võib tähendada, et sõltuvus võib rikutud olla 1% olemasolevatest tupikutest käsitletavas atribuutide kogumis. See tähendab, et 1000 kirje puhul võivad maksimaalselt 10 tupikut reeglit rikkuda. Me vaatame aga veidi teist mõõdikut, mis põhineb võrdlevate tupikute paarilise erisuse väärtustel. Sõltuvus tähendab, et kui meil on kaks tupleksit suhtes r loetakse nii:

Arvutame vea , võib märkida, et see rikub, kuna väärtus ületoodud näites. Meil on kaks tupikut, mille väärtused erinevad atribuudil Sugu, kuid langevad kokku Doktoris: [Doktor, Patsient] = (Robin, Ellis) ja [Doktor, Patsient] = (Robin, Graham). Järgides vea määratlemist, peame arvestama kõiki konflikte paaride, seega on neid kaks: (, ) ja selle pöörde (, ). Asetame valemisse ja saame.

Nüüd püüame vastata küsimusele: "Aga miks see kõik on?" Tegelikult on funktsionaalsed sõltuvused erinevad. Esimene tüüp — need on sõltuvused, mida määratleb administraator andmebaasi projekteerimise etapis. Need on tavaliselt vähe, nad on ranged, ja nende peamine rakendus on andmete normaliseerimine ja suhteskeemi disain.

Teine tüüp on sõltuvused, mis esindavad "peidetud" andmeid ja varem tundmatuid seoseid atribuutide vahel. Teisisõnu, selliste sõltuvuste üle ei mõeldud projekteerimise hetkel ning neid avastatakse juba olemasoleva andmekogumi põhjal, et seejärel teha tuvastatud funktsionaalsete sõltuvuste alusel järeldusi salvestatud teabe kohta. Just nende sõltuvustega me tegeleme. Neid uurib terve andmekaevanduse valdkond koos erinevate otsingutehnikatega ja nende alusel loodud algoritmidega. Uurime, kuidas võivad tuvastatud funktsionaalsed sõltuvused (olgu need täpsed või ligikaudsed) mingites andmetes kasulikud olla.

Täna on sõltuvuste peamised rakendusalad andmete puhastamine. See hõlmab protsesside väljatöötamist, mis tuvastavad "mustad andmed" nende hilisemaks parandamiseks. Iseloomulikud näited "mustadest andmetest" on duplikaadid, andmevead või trükivead, puuduvad väärtused, vananenud andmed, liigsed tühikud ja muud sarnased probleemid.

Andmevea näide:

Andmete duplikaatide näide:

Näiteks meil on tabel ja rida funktsionaalseid sõltuvusi, mida tuleks järgida. Andmete puhastamine eeldab, et muudetakse andmeid selliselt, et funktsionaalsed sõltuvused saavad õigeks. Samuti peab muudatuste arv olema minimaalne (selle protseduuri jaoks on olemas omad algoritmid, millele me käesolevas artiklis ei keskendu). Allpool on toodud näide sellisest andmete teisendamisest. Vasakul on algne suhe, kus on selgelt näha, et vajalikud funktsionaalsed sõltuvused ei kehti (punasega on välja toodud üks rikkumise näide). Paremal on esitatud uuendatud suhe, kus rohelised lahtrid näitavad muudetud väärtusi. Pärast sellist protseduuri on vajalikud sõltuvused saanud kehtima.

Teine populaarne rakendusala on andmebaasi disain. Siin on oluline meeles pidada normaalvorme ja normaliseerimist. Normaliseerimine on protsess, mille käigus muudetakse suhe vastavaks teatud nõuetele, millest igaüht määratletakse omamoodi normaalvormiga. Me ei hakka selgitama erinevate normaalvormide nõudeid (see on kajastatud igas algaja andmebaasi õpikusse), kuid märkime, et igaühel neist on omapärane kasutus funktsionaalsete sõltuvuste kontseptsioonis. Lõppude lõpuks on funktsionaalsed sõltuvused oma olemuselt terviklikkuse piirangud, mida arvestatakse andmebaasi projekteerimisel (käesoleva ülesande kontekstis nimetatakse funktsionaalseid sõltuvusi mõnikord supervõtmeteks).

Vaatame nende rakendust neljas normaalvormis alloleval pildil. Tuletame meelde, et Boyce-Coddi normaalvorm on rangem kui kolmas vorm, kuid samas vähem range kui neljas. Viimast me veel ei käsitle, kuna selle määratlemiseks on vajalik arusaamine mitme väärtuse sõltuvustest, mis ei ole selle artikli kontekstis huvitavad.

Teine valdkond, kus sõltuvused on oma rakenduse leidnud, on ruumi omaduste mõõtmete vähendamine sellistes ülesannetes nagu naiivse Bayesi klassifikaatori loomine, oluliste omaduste esiletoomine ja regressioonimudeli reparemeteering. Originaalartiklites nimetatakse seda ülesannet liigsete omaduste määratlemiseks (feature redundancy) ja asjakohaste omaduste määratlemiseks (feature relevancy) [5, 6], ning see lahendatakse aktiivse andmebaasi kontseptsioonide kasutamisega. Selliste uuringute ilmumisega võime öelda, et täna on nõudlus lahenduste järele, mis suudavad siduda andmebaasi, analüütika ja ülaltoodud optimeerimisprobleemide rakendamise üheks tööriistaks [7, 8, 9].

Funktsionaalsete sõltuvuste leidmiseks andmestikus on palju algoritme (nii kaasaegseid kui ka vanemaid). Need algoritmid võib jagada kolme rühma:

• Alglib, mis kasutavad algebra parameetrite läbimist (Lattice traversal algorithms)
• Alglib, mis põhinevad kooskõlastatud väärtuste leidmisel (Difference- and agree-set algorithms)
• Alglib, mis põhinevad paarilisetel võrdlustel (Dependency induction algorithms)

Iga algoritmi tüübi lühike kirjeldus on toodud allolevas tabelis:


Lisage rohkem teavet selle klassifikatsiooni kohta [4]. Allpool on toodud näited algoritmidest igat tüüpi jaoks:

Praegu ilmuvad uusi algoritme, mis ühendavad endas mitu lähenemist funktsionaalsete sõltuvuste leidmiseks. Selliste algoritmide näideteks on Pyro [2] ja HyFD [3]. Nende töö analüüsi plaanitakse käesoleva artikli järgmistes osades. Käesolevas artiklis käsitleme vaid peamisi mõisted ja lemmasid, mis on vajalikud sõltuvuste tuvastamise tehnikate mõistmiseks.

Alustame lihtsast - difference- ja agree-set, mida kasutatakse teise tüübi algoritmides. Difference-set on tulude kogum, mille väärtused ei kattu, samas kui agree-set on vastupidi - tulude kogum, mille väärtused kattuvad. Tuleb märkida, et antud juhul käsitleme ainult sõltuvuse vasakut osa.

Samuti on oluline mõiste, mis esineb ülal, algebraline mastaap. Kuna paljud kaasaegsed algoritmid töötavad selle mõistega, peame saama ettekujutuse, mis see on.

Kuna defineerime mastaapi, on vajalik osaliselt järjestatud hulga (või partially ordered set, lühendatult - poset) määratlemine.

Määratlemine 2. Öeldakse, et hulk S on osaliselt järjestatud binaarse suhtega ⩽, kui iga a, b, c ∈ S korral kehtivad omadused:

1. Refleksiivsus, st a ⩽ a
2. Antisümmeetrilisus, st kui a ⩽ b ja b ⩽ a, siis a = b
3. Transitiivsus, st kui a ⩽ b ja b ⩽ c, siis a ⩽ c

Sellist suhet nimetatakse (mittearvulise) osalise järjekorra suhtes ja ise hulk on osaliselt järjestatud hulk. Formaalsed tähised: ⟨S, ⩽⟩.

Lihtsaima näitena osaliselt järjestatud hulka võib võtta kõik naturaalarvud N koos tavapärase järjekorra suhtega ⩽. Pole raske kontrollida, et kõik vajalikud aksioomid kehtivad.

Rikkalikum näide. Kaaluge hulka kõigist alamhulga {1, 2, 3}, mis on järjestatud sisaldava suhtega ⊆. Tõepoolest, see suhe rahuldab kõiki osalise järjekorra tingimusi, seega ⟨P ({1, 2, 3}), ⊆⟩ - osaliselt järjestatud hulk. Allolevas joonises on kujutatud selle hulga struktuuri: kui ühel elemendil on nooled teise elemendini, siis on nad järjekorras.

Me vajame veel kahte lihtsat definitsiooni matemaatika valdkonnast — suprema (supremum) ja infima (infimum).

Määratlemine 3. Olgu ⟨S, ⩽⟩ — osaliselt järjekorda seatud hulk, A ⊆ S. A ülemine piir on selline element u ∈ S, et ∀x ∈ S: x ⩽ u. Olgu U — kõikide ülemiste piiride hulk S-is. Kui U-s on minimaalne element, siis nimetatakse seda supremaks ja tähistatakse kui sup A.

Sarnasel viisil määratletakse täpsuse madalam piir.

Määratlemine 4. Olgu ⟨S, ⩽⟩ — osaliselt järjekorda seatud hulk, A ⊆ S. A madalam piir on selline element l ∈ S, et ∀x ∈ S: l ⩽ x. Olgu L — kõikide madalamate piiride hulk S-is. Kui L-s on maksimaalne element, siis nimetatakse seda infimuks ja tähistatakse kui inf A.

Vaatleme näiteks eespool toodud osaliselt järjekorda seatud hulka ⟨P ({1, 2, 3}), ⊆⟩ ja leiame selles suprema ja infima:

Nüüd on võimalik sõnastada algebralise südamiku definitsioon.

Määratlemine 5. Olgu ⟨P, ⩽⟩ — osaliselt järjekorda seatud hulk, kus igal kahel elemendil on täpsed ülemised ja alumised piirid. Siis nimetatakse P algebralise südamikuks. Samuti kirjutatakse sup{x, y} kui x ∨ y ja inf {x, y} — kui x ∧ y.

Kontrollime, et meie töönäide ⟨P ({1, 2, 3}), ⊆⟩ on südamik. Tõepoolest, igale a, b ∈ P ({1, 2, 3}) kehtib, et a∨b = a∪b ja a∧b = a∩b. Näiteks vaatleme hulkasid {1, 2} ja {1, 3} ning leiame nende infima ja suprema. Kui me need ristame, saame hulga {1}, mis on infimum. Supremumi saame nende ühinemisel — {1, 2, 3}.

Algoritmides, mis avastavad FZ-d, esitatakse otsinguruum sageli südamiku kujul, kus ühe elemendi kogud (loe: südamiku otsingu esimene tase, kus sõltuvuste vasak pool koosneb ühest atribuudist) on igaüks algse suhte atribuut.
Alguses käsitletakse sõltuvusi, mis on vormis ∅ → Üksik atribuut. See samm aitab määrata, millised atribuudid on põhivõtmed (selliste atribuutide puhul ei ole determinantide olemasolu ja seetõttu on vasak pool tühi). Järgnevalt liiguvad sellised algoritmid südamikus ülespoole. Siiski tuleb märkida, et südamikku ei pea kogu aeg läbima, see tähendab, et kui sisestada soovitud maksimaalne vasaku poole suurus, ei liigu algoritm edasi tasemest, millel on selline suurus.

Allpool on näidatud, kuidas saab algebralist ruumi kasutada FZ otsingu ülesande lahendamiseks. Siin esindab iga serv (X, XY) sõltuvust tähendab, et kui meil on kaks tupleksit. Näiteks oleme läbinud esimese taseme ja teame, et sõltuvus on olemas A → B (kujundame selle rohelise seosega tippude vahel A ja B). Seega, kui liigume ruumis ülespoole, ei pea me kontrollima sõltuvust A, C → B, kuna see ei ole enam minimaalne. Samamoodi ei kontrolliks me seda, kui sõltuvus oleks C → B.

. Lisaks kasutavad enamik kaasaegseid FZ otsingu algoritme tavaliselt andmestruktuuri, nagu partitsioon (originaalis - stripped partition [1]). Partitsiooni formaalne määratlemine on järgmine:

Määratlemine 6. Olgu X ⊆ R - atribuute kogum suhtes r. Klaster on r-tuple'ide indeksite kogum, millel on X jaoks sama väärtus, st c(t) = {i|ti[X] = t[X]}. Partitsioon on klastrite kogum, mis välistab ühe pikkusega klastrid:

Lihtsustatult öeldes esindab partitsioon atribuuti X nimetuste kogumit, kus iga nimekiri sisaldab ridade numbreid, millel on sama väärtus X. Kaasaegses kirjanduses struktuuri, mis esindab partitsioone, nimetatakse position list index (PLI). Ühe pikkusega klastrid jäetakse PLI kokkusurumise eesmärgil välja, kuna need on klastrid, mis sisaldavad ainult ühte kirje numbrit, millel on ainulaadne väärtus, mida on alati lihtne määrata.

Vaatame näidet. Naaseme taas patsiendi tabeli juurde ja loome partitsioonid veergudele Sugu ja Sugu (vasakul on ilmunud uus veerg, kus on märgitud tabeli ridade numbrid):

Sellega seoses, määratlemise kohaselt on partitsioon veerule Sugu tõepoolest tühi, kuna ühekordsed klastrid jäetakse partitsioonist välja.

Partitsioone saab luua mitme atribuudi järgi. Selleks on kaks teed: kõndida tabeli kaudu ja luua partitsioon kohe kõikide vajalike atribuutide järgi, või luua see osade partitsioonide ristumise operatsiooni abil. FZ otsingu algoritmid kasutavad teist varianti.

Lihtsustatult öeldes, et saada partitsioon veergude järgi ABC, saab võtta partitsioonid jaoks AC ja B (või mõni muu mitteühtivate alamkogumite kogum) ja nende omavaheline ristamine. Kaks partitsiooni ristumise operatsioon eraldab pikimad klastrid, mis on mõlema partitsiooni jaoks ühised.

Vaatame näidet:

Esimesel juhul saime tühja partitsiooni. Kui vaadata tabelit, siis tõesti, kahe atribuudiga ei ole sama väärtust. Kui me aga muudame tabelit veidi (parem juhul), saame mitte-tühja ristumise. Sellisel juhul sisaldavad read 1 ja 2 tõepoolest sama väärtust atribuutide järgi. Sugu ja Doktor.

Seejärel vajame mõistet, nagu partitsiooni suurus. Vormiliselt:

Lihtsamalt öeldes, partitsiooni suurus on klastrite arv, mis kuuluvad partitsiooni (meeles pidada, et üksikklastrid partitsiooni ei ära kuulu!):

Nüüd saame määratleda ühe võtme lemma, mis antud partitsioonide jaoks võimaldab tuvastada, kas sõltuvus kehtib või mitte:

Lemma 1. Sõltuvus A, B → C kehtib, kui ja ainult siis, kui

Lema kohaselt on sõltuvuse kehtivuse määramiseks vajalik järgmiste nelja sammu täitmine:

1. Arvutage sõltuvuse vasaku osa partitsioon
2. Arvutage sõltuvuse parema osa partitsioon
3. Arvutage esimese ja teise sammu korrutis
4. Võrrelge partitsioonide suurusi, mis saadi esimeses ja kolmandas etapis

Allpool on näide sellest, kuidas kontrollida, kas sõltuvus on selle lemma kohaselt kehtiv:

Selles artiklis oleme käsitlenud selliseid mõisteid nagu funktsionaalne sõltuvus, ligikaudne funktsionaalne sõltuvus, arutanud, kus neid kasutatakse, ja millised funktsionaalse sõltuvuse otsimise algoritmid eksisteerivad. Samuti oleme põhjalikult käsitlenud baasmõisteid, maar tabelites, intensiivselt kaasaegsetes funktsionaalse sõltuvuse otsimise algoritmides.

Viidatud kirjandus:

1. Huhtala Y. jt. TANE: Efektiivne algoritm funktsionaalsete ja ligikaudsete sõltuvuste avastamiseks // The computer journal. – 1999. – Vol. 42. – No. 2. – Lk. 100-111.
2. Kruse S., Naumann F. Efektiivne ligikaudsete sõltuvuste avastamine // Proceedings of the VLDB Endowment. – 2018. – Vol. 11. – No. 7. – Lk. 759-772.
3. Papenbrock T., Naumann F. Hübriidne lähenemine funktsionaalse sõltuvuse avastamisele // Proceedings of the 2016 International Conference on Management of Data. – ACM, 2016. – Lk. 821-833.
4. Papenbrock T. jt. Funktsionaalse sõltuvuse avastamine: seitse algoritmi katsetavad hindamist // Proceedings of the VLDB Endowment. – 2015. – Vol. 8. – No. 10. – Lk. 1082-1093.
5. Kumar A. jt. Kas ühendada või mitte ühendada?: Liitmise üle kaks korda mõtlemine enne omaduste valimist // Proceedings of the 2016 International Conference on Management of Data. – ACM, 2016. – Lk. 19-34.
6. Abo Khamis M. et al. Andmebaasis õppimine haruldaste tensorite abil // 37. ACM SIGMOD-SIGACT-SIGAI sümpoosion andmebaasisüsteemide põhimõtetest. – ACM, 2018. – lk. 325-340.
7. Hellerstein J. M. et al. MADlib analüütika teek: või MAD oskused, SQL // VLDB Endowmenti protseduurid. – 2012. – V. 5. – Nr. 12. – lk. 1700-1711.
8. Qin C., Rusu F. Spekulatiivsed lähendused teraskalejaotatud gradientide langetamise optimeerimisele // Neljanda töötuba andmeanalüütikas pilves. – ACM, 2015. – lk. 1.
9. Meng X. et al. Mllib: Masinõpe Apache Sparkis // Masinõppe uuringute ajakiri. – 2016. – V. 17. – Nr. 1. – lk. 1235-1241.

Artikli autorid: Anastasia Birillo, teadlane JetBrains Research, , CS keskuse üliõpilane ja Nikita Bobrov, teadlane JetBrains Research

Allikas: habr.com