Sissejuhatus funktsionaalsetesse sõltuvustesse

Selles artiklis arutame funktsionaalsete sõltuvuste olemust, rakendusvaldkondi ja olemasolevaid algoritme nende tuvastamiseks andmebaasides.

Käsitleme funktsionaalset sõltuvust suhteliste andmebaaside kontekstis. Üksikasjalikult öeldes salvestatakse sellistes andmebaasides teave tabelite kujul. Edasi kasutame ligikaudseid mõisteid, mis ei ole rangelt vastastikku asendatavad, nagu nimetame ise tabelit suhteliseks, veerge atribuuttideks (nende kogum on skeem) ning rida väärtuste kogumit teatud atribuutide alamhulgas - kordu.

Näiteks ülaltoodud tabelis, (Benson, M, M organ) on kordu atribuutide suhtes (Patsient, Soov, Arst).
Täpsemalt väljendatakse seda järgmisel kujul: [Patsient, Soov, Arst] = (Benson, M, M organ).
Nüüd saame tutvustada funktsionaalsete sõltuvuste (ФЗ) mõistet:

Määratlus 1. Suhe R rahuldab funktsionaalset sõltuvust X → Y (kus X, Y ⊆ R) siis ja ainult siis, kui iga kordu puhul , ∈ R kehtib: kui [X] = [X], siis [Y ] = [Y ]. Sellisel juhul öeldakse, et X (determinant või määratlev atribuutide hulk) määratleb funktsionaalselt Y (sõltuv atribuutide hulk).

Teisisõnu, FZ olemasolu X → Y tähendab, et kui meil on kaks tuple R ja need kattuvad atribuutidega X, siis nad kattuvad ka atribuutidega Y.
Nüüd, järjestikku. Vaatleme atribuutide Patsient ja Sugu mille jaoks tahame teada, kas nende vahel on sõltuvusi või mitte. Sellise atribuutide hulga jaoks võivad eksisteerida järgmised sõltuvused:

1. Patsient → Sugu
2. Sugu → Patsient

Ülaltoodud määratlemise kohaselt peab esimese sõltuvuse säilitamiseks iga unikaalne väärtus veerus Patsient olema seotud ainult ühe väärtusega veerus Sugu. Ja näidistabeli jaoks on see tõesti nii. Kuid vastupidi see ei toimi, st teine sõltuvus ei kehti ning atribuut Sugu ei ole determinant Patsiendi. Sarnaselt, kui võtta sõltuvus Doktor → Patsient, võib märgata, et see rikutakse, kuna väärtus Robin antud atribuudil on mitu erinevat väärtust — Ellis ja Graham.

Seega võimaldavad funktsionaalsed sõltuvused määratleda olemasolevad seosed tabeli atribuutide kogumite vahel. Edaspidi uurime kõige huvitavamaid seoseid, nimelt neid, X → Y, mis on:

• ei ole triviaalne, ehk parempoolne osa sõltuvusest ei ole vasakpoolse alamhulk (Y ̸⊆ X);
• minimaalsed, st ei ole sellist sõltuvust Z → Y, et Z ⊂ X.

Kuni praeguseni käsitletud sõltuvused olid ranged, st ei lubanud tabelis mingeid rikkumisi, kuid nende kõrval on ka selliseid, mis lubavad teatud järjendite väärtuste vahel mõningast ebakõla. Sellised sõltuvused jagunevad eraldi klassiks, neid nimetatakse ligikaudseteks ja nende rikkumist lubatakse teatud arvu järjendite põhjal. See arv reguleeritakse maksimaalse vea näitajaga emax. Näiteks veamäär = 0.01 võib tähendada, et sõltuvuse rikkumine võib esineda 1% olemasolevatest tupikutest arvestatavas atribuutide kogumis. Seega, 1000 kirje puhul võivad maksimaalselt 10 tupikut rikkuda seadust. Meie vaatleme natuke teistsugust mõõdikut, mis põhineb võrreldavate tupikute paarilistest väärtustest. Sõltuvuse jaoks X → Y suhtes r arvutatakse järgmiselt:

Arvutame vea Doktor → Patsient ülaltoodud näite puhul. Meil on kaks tupikut, mille väärtused erinevad atribuudi Patsient, kuid kattuvad Doktor: [Doktor, Patsient] = (Robin, Ellis) ja [Doktor, Patsient] = (Robin, Graham). Järgides veamääratlust, peame arvestama kõiki konfliktseid paare, seega on neid kaks: (, ) ja nende inverseerimine (, ). Asendame valemisse ja saame:

Ja nüüd püüame vastata küsimusele: «Miks see kõik vajalik on?». Tegelikult on sõltuvusi erinevaid. Esimene tüüp — need on sõltuvused, mis määratakse administraatori poolt andmebaasi projekteerimise etapis. Neid on tavaliselt vähe, need on rangelt määratletud, ja nende peamine rakendus on andmete normaliseerimine ja suhte skeemi kujundamine.

Teine tüüp on sõltuvused, mis esindavad "peidetud" andmeid ja varasemaid teadmata seoseid atribuutide vahel. See tähendab, et selliste sõltuvuste üle ei mõeldud projekteerimise hetkel ning need avastatakse juba olemasolevates andmekogumites, et seejärel tuletada mitmete avastatud funktsionaalsete sõltuvuste põhjal järeldusi salvestatud teabe kohta. Just nende sõltuvustega me tegeleme. Nendega tegeleb terve andmekaevanduse valdkond, kasutades erinevaid otsingutehnikaid ja nende põhjal väljatöötatud algoritme. Vaatame nüüd, kuidas võivad leitud funktsionaalsed sõltuvused (täpsed või ligikaudsed) olla kasulikud mingites andmetes.

Praegu on sõltuvuste peamisteks rakendusvaldkondadeks andmete puhastamine. See hõlmab „mustade andmete” avastamise protsesside väljatöötamist, millele järgneb nende parandamine. Tüüpilised näited „mustadest andmetest” on dubleerimised, andmevead või trükivead, puuduolevad väärtused, aegunud andmed, liigsuured tühikud jne.

Andmevea näide:

Andmete dubleerimise näide:

Näiteks, meil on tabel ja komplekt nõudeid, mida tuleb täita. Andmete puhastamine tähendab antud juhul andmete muutmist nii, et nõuded oleksid täidetud. Seejuures peab muudatuste arv olema minimaalne (selle protseduuri jaoks on olemas oma algoritmid, millest me ei hakka käesolevas artiklis rääkima). Allpool on toodud näide sellisest andmete vormindamisest. Vasakul on algne suhe, milles ei täideta vajalikke nõudeid (punase värviga on esitatud ühe nõude rikkumise näide). Paremal on uuendatud suhe, kus rohelised lahtrid näitavad muudetud väärtusi. Pärast sellise protseduuri läbiviimist vajalikud sõltuvused on tagatud.

Teiseks populaarseks rakenduseks on andmebaasi disain. Siin on oluline meelde jätta normaalsed vormid ja normaliseerimine. Normaliseerimine on protsess, mille käigus suheldakse seostega vastavalt teatud nõudmiste kogumile, millest igaüht määratleb omaette normaalsed vormid. Me ei hakka nende erinevate normaalsete vormide nõudeid arutama (seda tehakse algajatele mõeldud andmebaasi õpikutes), vaid märgime vaid, et igaühel neist on oma viis funktsionaalsete sõltuvuste kontseptsiooni kasutamiseks. Lõppude lõpuks on funktsionaalsed sõltuvused oma olemuselt terviklikkuse piirangud, mida arvestatakse andmebaasi projekteerimisel (selle ülesande kontekstis nimetatakse funktsionaalseid sõltuvusi vahel supervõtmeteks).

Vaatleme nende rakendust nelja normaalse vormi puhul alloleval pildil. Kordame, et Boyce-Coddi normaalsed vormid on rangemad kui kolmas vorm, kuid samas vähem ranged kui neljas. Viimast me praegu ei arutle, kuna selle määratlemiseks on vajalik arusaamine mitme väärtuse sõltuvusest, mis ei ole selles artiklis meie jaoks huvitav.

Veel üks valdkond, kus sõltuvused on leidnud oma rakenduse, on funktsioonide ruumide mõõtmete vähendamine, nagu näiteks naiivse Bayesi klassifikaatori ehitamine, oluliste tunnuste eristamine ja regressioonimudeli reparametreerimine. Originaalartiklites nimetatakse seda ülesanne liigsete tunnuste määratlemiseks (feature redundancy) ja asjakohaste tunnuste (feature relevancy) leidmiseks, ning selle lahendamine toimub aktiivsete andmebaasikonseptsioonide kasutamisega. Selliste tööde jaoks võime öelda, et täna on nõudlus lahenduste järele, mis võimaldavad kombineerida andmebaasi, analüüsi ja eelnevalt nimetatud optimeerimise probleeme ühte tööriista.

FZ otsimiseks andmekogus on palju algoritme (n nii kaasaegseid kui ka vähem moodsaid). Sellised algoritmid võib jagada kolme rühma:

• Algebraliste võrgustike läbimise algoritmid (Lattice traversal algorithms)
• Algoritmid, mis põhinevad kokkusobivate väärtuste leidmisel (Difference- and agree-set algorithms)
• Algoritmid, mis põhinevad paariliste võrdlemiste saavutamisel (Dependency induction algorithms)

Iga algoritmi tüübi lühikokkuvõte on esitatud allolevas tabelis:


Selle klassifikatsiooni kohta saab lugeda rohkem [4]. Allpool on toodud näited iga tüübi algoritmidest:

Praegu ilmuvad uued algoritmid, mis ühendavad mitmeid lähenemisviise funktsionaalsete sõltuvuste otsingus. Näiteks sellised algoritmid nagu Pyro [2] ja HyFD [3]. Nende töö analüüsitakse järgmistes käesoleva artikli seerias. Selle artikli raames käsitleme vaid põhikontseptsioone ja lemma, mis on vajalikud sõltuvuste tuvastamistaktikate mõistmiseks.

Alustame lihtsast — difference- ja agree-set, mida kasutatakse teise tüübi algoritmides. Difference-set koosneb tuplidest, mille väärtused ei kattu, samas kui agree-set sisaldab tupleid, mille väärtused kattuvad. Oluline on märkida, et selles kontekstis käsitleme ainult sõltuvuse vasakut poolt.

Samuti on oluline mõistet, mille juurde viidatud, algebraline ruum. Kuna paljud kaasaegsed algoritmid toimivad selle mõistega, peame olema teadlikud, mis see on.

Ette defineerida relva mõistet, on vajalik osaliselt järjestatud kogumi (inglise keeles partially ordered set, lühendatult — poset) määratlemine.

Määratlus 2. Öeldakse, et kogum S on osaliselt järjestatud binaarse suhtega ⩽, kui igasuguste a, b, c ∈ S kehtivad järgmised omadused:

1. Reflektiivsus, 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

Seda suhet nimetatakse (mitte range) osalise järjestuse suhtes ning kogumit ise — osaliselt järjestatud kogumiks. Formaalne tähistus: ⟨S, ⩽⟩.

Lihtsama näiteks osaliselt järjestatud kogumi kohta võib tuua kõigi naturaalarvude N kogumi, kus kehtib tavaline järjestussuhe ⩽. Pole raske kontrollida, et kõik vajalikud aksioomid on täidetud.

Rikkalikum näide. Vaatame kõiki alamhulkade kogumit {1, 2, 3}, mis on järjestatud sisaldusjärel ⊆. Tõepoolest, see suhe rahuldab kõiki osalise järjekorra tingimusi, seega ⟨P ({1, 2, 3}), ⊆⟩ on osaliselt järjekordne kogum. Alloleval joonisel on kujutatud selle kogumi struktuuri: kui ühest elemendist saab noolede kaudu teise elemendini jõuda, siis on nad järjekorras.

Me vajame veel kahte lihtsat määratlust matemaatika valdkonnast — supremumit (supremum) ja infimumit (infimum).

Määratlus 3. Olgu ⟨S, ⩽⟩ — osaliselt järjekordne kogum, A ⊆ S. A ülemine piir on selline element u ∈ S, et ∀x ∈ S: x ⩽ u. Olgu U — kõigi S ülemiste piiride kogum. Kui U-s on olemas väikseim element, siis nimetatakse seda supremumiks ja sümboliks on sup A.

Sarnasel viisil määratletakse täpse alumise piiri mõisted.

Määratlus 4. Olgu ⟨S, ⩽⟩ — osaliselt järjekordne kogum, A ⊆ S. A alumine piir on selline element l ∈ S, et ∀x ∈ S: l ⩽ x. Olgu L — kõigi S alumiste piiride kogum. Kui L-s on olemas suurim element, siis nimetatakse seda infimumiks ja sümboliks on inf A.

Vaatleme näiteks eespool mainitud osaliselt järjendatud hulka ⟨P ({1, 2, 3}), ⊆⟩ ja leidke sellest supreemia ja infimium.

Nüüd saab sõnastada algebrailise võrgustiku määratlemise.

Määratlemine 5. Olgu ⟨P, ⩽⟩ — osaliselt järjendatud hulk, nii et igal kahel elemendi alamhulgal on täpsed ülemised ja alumised piirid. Siis nimetatakse P algebrailiseks võrgustikuks. Samuti kirjutatakse sup{x, y} kui x ∨ y ja inf {x, y} kui x ∧ y.

Kontrollime, kas meie näidishulk ⟨P ({1, 2, 3}), ⊆⟩ on võrgustik. Tõepoolest, igasuguste a, b ∈ P ({1, 2, 3}) puhul kehtib a∨b = a∪b ja a∧b = a∩b. Näiteks vaatleme gruppe {1, 2} ja {1, 3} ja leiame nende infimiumi ja supreemia. Kui me need ristame, saame hulga {1}, mis on infimium. Supreemia saame aga nende liitmisega — {1, 2, 3}.

FZ avastamise algoritmides on otsinguruum sageli esitatud võrgustiku kujul, kus üheelementilised hulgad (loe: otsinguvõrgu esimene tase, kus sõltuvuste vasak pool koosneb ühest atribuudist) esindavad iga algse seose attribuuti.
Alguses käsitletakse sõltuvusi vormis ∅ → Üksik atribuut. See etapp võimaldab määrata, millised atribuudid on peamised võtmed (selliste atribuutide puhul ei ole determinantide olemasolu, seega vasak pool on tühi). Edasi liiguvad sellised algoritmid võrku ülespoole. Oluline on märkida, et võrku ei pea tingimata täielikult läbima, see tähendab, et kui edastate soovitud maksimaalse vasaku poole suuruse, siis algoritm ei liigu selle suuruse tasemest kaugemale.

Alloleval joonisel on näidatud, kuidas saab kasutada algebralist võrku FZ-i otsingu ülesandes. Iga serv (X, XY) esindab sõltuvust X → Y. Näiteks oleme läbinud esimese taseme ja teame, et sõltuvus hoitakse A → B (kujuta seda ette rohelise ühendusena tippude vahel A ja B). See tähendab, et kui liigume võrku ülespoole, siis me ei saa enam sõltuvust kontrollida A, C → B, kuna see ei ole enam minimaalne. Samamoodi ei kontrolliks me seda, kui sõltuvus oleks hoitud C → B.

Lisaks kasutavad kõik kaasaegsed FZ-otsingu algoritmid tavaliselt andmestruktuuri, mida nimetatakse partiitsiooniks (algallikas — stripped partition [1]). Partiitsiooni formaalne määratlus on järgmine:

Määratlemine 6. Olgu X ⊆ R — atribuutide kogum suhtes r. Klaster on kogum r-tuple indeksitest, mille X-i väärtused on ühesugused, st c(t) = {i|ti[X] = t[X]}. Partiitsioon on klastrite hulk, välja arvatud üksikpikkuste klastrid:

Lihtsalt öeldes, partiitsioon atribuudile X on loendite kogum, kus iga loend sisaldab ridade numbreid, mille väärtused on ühesugused X. Kaasaegses kirjanduses tähistatakse partiitsioone struktuuriga, mida nimetatakse position list index (PLI). Üksikpikkuste klastrid jäetakse PLI tihendamise eesmärgil välja, kuna need on klastrid, mis sisaldavad ainult ühte kirje numbrit unikaalse väärtusega, mille määramine on alati lihtne.

Vaatame näidet. Naaseme tagasi sama tabeli juurde, kus on patsiendid, ning koostame partiitsioone Patsient ja Sugu (vasakul on ilmnenud uus veerg, kus on tähistatud tabeli ridade numbrid):

Sellel juhul on veergu puudutav partitsioon vastavalt määratlemisele Patsient tegelikult tühi, kuna üksikud klastrid on partitsioonist välja jäetud.

Partitsioone saab saada mitme atribuutide alusel. Selleks on kaks teed: läbides tabeli, moodustada partitsioon kohe kõikide vajalike atribuutide alusel, või luua see partitsioonide ühisosa operatsiooni kaudu alamhulga atribuutidest. FZ otsingu algoritmid kasutavad teist varianti.

Lihtsate sõnadega, et näiteks saada partitsioon veergude alusel ABC, saab võtta partitsioonid AC ja B (või mis tahes muu mitteühtivad alamhulk) ja ühisosa nendest luua. Kahe partitsiooni ühisosa operatsioon eraldab pikimaid klastreid, mis on ühised mõlemale partitsioonile.

Vaatame näidet:

Esimesel juhul saime tühja partitsiooni. Kui vaadata tabelisse, siis tõepoolest, sama väärtuste koondumine kahe atribuudiga puudub. Kui me aga muudame tabelit veidi (parem pool), siis saame jälle mittetühja ühisosa. Selle käigus sisaldavad read 1 ja 2 tõepoolest sama väärtust attribuutide alusel. Sugu ja Doktor.

Edasi liikudes peame tutvuma sellise mõiste nagu partitsiooni suurus. Formaalsetes tingimustes:

Lihtsamalt öeldes on partitsiooni suurus klastrite arv, mis kuulub partitsiooni (me peame meeles, et üksikute klastrite partitsioonides ei ole!):

Nüüd saame määratleda ühe võtmelüli, mis antud partitsioonide puhul võimaldab kindlaks teha, kas sõltuvus kehtib või mitte:

Lüli 1. Sõltuvus A, B → C kehtib, kui ja ainult kui

Vastavalt lülile on sõltuvuse kehtivuse määratlemiseks vajalik järgida nelja sammu:

1. Arvutada sõltuvuse vasakpoolsuse partitsioon
2. Arvutada sõltuvuse parempoolsuse partitsioon
3. Arvutada esimese ja teise sammu tulemus
4. Võrrelda esimese ja kolmanda sammu meetoditega saadud partitsioonide suurusi

Allpool on toodud näide, kuidas kontrollida, kas sõltuvus kehtib antud lüli põhjal:

Selles artiklis käsitlesime funktsionaalse sõltuvuse ja ligikaudse funktsionaalse sõltuvuse mõisted, uurisime, kus neid rakendatakse ning millised otsingualgoritmid funktsionaalsuse leidmiseks olemas on. Samuti käsitlesime üksikasjalikult põhimõisted, mis on aktiivselt kasutusel tänapäevastes funktsionaalsuse leidmise algoritmides.

Viidatud kirjandusele:

1. Huhtala Y. jt. TANE: Efektiivne algoritm funktsionaalsete ja ligikaudsete sõltuvuste avastamiseks // The computer journal. – 1999. – Vol. 42. – No. 2. – P. 100-111.
2. Kruse S., Naumann F. Efektiivne ligikaudsete sõltuvuste avastamine // Proceedings of the VLDB Endowment. – 2018. – Vol. 11. – No. 7. – P. 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. – P. 821-833.
4. Papenbrock T. jt. Funktsionaalse sõltuvuse avastamine: seitse algoritmi katsehindamine // Proceedings of the VLDB Endowment. – 2015. – Vol. 8. – No. 10. – P. 1082-1093.
5. Kumar A. jt. Liituda või mitte liituda?: Liitudes kaks korda mõtlema enne tunnusvalikut // Proceedings of the 2016 International Conference on Management of Data. – ACM, 2016. – P. 19-34.
6. Abo Khamis M. jt. Andmebaasis õppimine haruldaste tensoritega // Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems. – ACM, 2018. – P. 325-340.
7. Hellerstein J. M. jt. MADlibi analüütikateek: või MAD oskused, SQL // Proceedings of the VLDB Endowment. – 2012. – Vol. 5. – No. 12. – P. 1700-1711.
8. Qin C., Rusu F. Spekulatiivsed lähenemised teraskaalaliste jaotatud gradientide allahindamise optimeerimisele // Neljandate andmeanalüüsi töötoad pilves. – ACM, 2015. – Lk 1.
9. Meng X. jt. Mllib: Masinõpe Apache Sparkis // Masinõppe uurimisajakiri. – 2016. – Vol 17. – Nr 1. – Lk 1235-1241.

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

Allikas: habr.com