Tässä artikkelissa puhumme tietokantojen toiminnallisista riippuvuuksista - mitä ne ovat, missä niitä käytetään ja mitä algoritmeja on olemassa niiden löytämiseksi.
Tarkastelemme toiminnallisia riippuvuuksia relaatiotietokantojen yhteydessä. Hyvin karkeasti sanottuna tällaisiin tietokantoihin tiedot tallennetaan taulukoiden muodossa. Seuraavaksi käytämme likimääräisiä käsitteitä, jotka eivät ole keskenään vaihdettavissa tiukassa relaatioteoriassa: kutsumme itse taulukkoa suhteeksi, sarakkeita - attribuutteja (niiden joukko - relaatioskeema) ja riviarvojen joukkoa attribuuttien osajoukossa. - monikko.
Esimerkiksi yllä olevassa taulukossa (Benson, M, M urut) on joukko attribuutteja (Potilas, Paul, lääkäri).
Muodollisesti tämä on kirjoitettu seuraavasti: [Potilas, sukupuoli, lääkäri] = (Benson, M, M urut).
Nyt voimme ottaa käyttöön toiminnallisen riippuvuuden (FD) käsitteen:
Määritelmä 1. Relaatio R täyttää liittovaltion lain X → Y (jossa X, Y ⊆ R) jos ja vain jos jollekin monikolle , ∈ R pätee: jos [X] = [X] siis [Y] = [Y]. Tässä tapauksessa sanomme, että X (determinantti tai määrittävä attribuuttijoukko) määrittää toiminnallisesti Y:n (riippuvainen joukko).
Toisin sanoen liittovaltion lain olemassaolo X → Y tarkoittaa, että jos meillä on kaksi monikkoa R ja ne vastaavat ominaisuuksia X, niin ne vastaavat määritteitä Y.
Ja nyt järjestyksessä. Katsotaanpa attribuutteja potilas и Paavali jonka osalta haluamme selvittää, onko niiden välillä riippuvuuksia vai ei. Tällaisella attribuuttijoukolla voi olla seuraavia riippuvuuksia:
- Potilas → Sukupuoli
- Sukupuoli → Potilas
Kuten edellä on määritelty, jotta ensimmäinen riippuvuus säilyy, kukin yksilöllinen sarakearvo potilas vain yhden sarakkeen arvon on vastattava Paavali. Ja esimerkkitaulukossa näin on todellakin. Tämä ei kuitenkaan toimi päinvastaiseen suuntaan, eli toinen riippuvuus ei täyty, ja attribuutti Paavali ei ole määräävä tekijä Potilas. Samoin, jos otamme riippuvuuden Lääkäri → Potilas, näet, että sitä on rikottu, koska arvo punarinta tällä attribuutilla on useita eri merkityksiä - Ellis ja Graham.
Siten toiminnalliset riippuvuudet mahdollistavat olemassa olevien suhteiden määrittämisen taulukon attribuuttijoukkojen välillä. Tästä eteenpäin tarkastellaan mielenkiintoisimpia yhteyksiä tai pikemminkin sellaisia X → Ymitä he ovat:
- ei-triviaali, eli riippuvuuden oikea puoli ei ole vasemman osajoukko (Y ̸⊆ X);
- minimaalinen, eli sellaista riippuvuutta ei ole Z → YEttä Z ⊂ X.
Tähän asti harkitut riippuvuudet olivat tiukkoja, eli ne eivät sisältäneet taulukon rikkomuksia, mutta niiden lisäksi on myös sellaisia, jotka sallivat jonkin verran epäjohdonmukaisuutta monikkoarvojen välillä. Tällaiset riippuvuudet sijoitetaan erilliseen luokkaan, jota kutsutaan likimääräisiksi, ja niitä voidaan rikkoa tietyn määrän monikoita varten. Tätä määrää säätelee maksimivirheilmaisin emax. Esimerkiksi virheprosentti = 0.01 voi tarkoittaa, että riippuvuutta voi rikkoa 1 % tarkasteltavan attribuuttijoukon käytettävissä olevista monikoista. Eli 1000 tietueessa enintään 10 monikkoa voi rikkoa liittovaltion lakia. Tarkastelemme hieman erilaista mittaria, joka perustuu vertailtavien monikoiden pareittain eri arvoihin. Riippuvuuden vuoksi X → Y asenteesta r sitä pidetään näin:
Lasketaan virhe Lääkäri → Potilas yllä olevasta esimerkistä. Meillä on kaksi monikkoa, joiden arvot eroavat attribuutissa potilas, mutta samaan aikaan Lääkäri: [Lääkäri, potilas] = (Robin, Ellis) Ja [Lääkäri, potilas] = (Robin, Graham). Virheen määritelmän mukaisesti meidän on otettava huomioon kaikki ristiriitaiset parit, mikä tarkoittaa, että niitä on kaksi: (, ) ja sen inversio (, ). Korvataan se kaavaan ja saadaan:
Yritetään nyt vastata kysymykseen: "Miksi se kaikki on?" Itse asiassa liittovaltion lait ovat erilaisia. Ensimmäinen tyyppi ovat riippuvuudet, jotka järjestelmänvalvoja määrittää tietokannan suunnitteluvaiheessa. Niitä on yleensä vähän, ne ovat tiukkoja, ja pääsovellus on tietojen normalisointi ja relaatioskeemasuunnittelu.
Toinen tyyppi ovat riippuvuudet, jotka edustavat "piilotettua" dataa ja aiemmin tuntemattomia attribuuttien välisiä suhteita. Toisin sanoen tällaisia riippuvuuksia ei ajateltu suunnitteluhetkellä ja ne löytyvät olemassa olevasta tietojoukosta, jotta myöhemmin voidaan monien tunnistettujen liittovaltion lakien perusteella tehdä johtopäätöksiä tallennetusta tiedosta. Juuri näiden riippuvuuksien kanssa työskentelemme. Niitä käsittelee kokonainen tiedon louhinnan ala erilaisilla hakutekniikoilla ja niiden pohjalle rakennetuilla algoritmeilla. Selvitetään, kuinka missä tahansa tiedossa löydetyt toiminnalliset riippuvuudet (tarkat tai likimääräiset) voivat olla hyödyllisiä.
Nykyään yksi tärkeimmistä riippuvuuksien sovelluksista on tietojen puhdistaminen. Se sisältää prosessien kehittämisen "likaisen tiedon" tunnistamiseksi ja sen korjaamiseksi. Näkyviä esimerkkejä "likaisista tiedoista" ovat kaksoiskappaleet, tietovirheet tai kirjoitusvirheet, puuttuvat arvot, vanhentuneet tiedot, ylimääräiset välilyönnit ja vastaavat.
Esimerkki tietovirheestä:
Esimerkki tietojen kaksoiskappaleista:
Meillä on esimerkiksi taulukko ja joukko liittovaltion lakeja, jotka on suoritettava. Tietojen puhdistamiseen kuuluu tässä tapauksessa tietojen muuttaminen siten, että liittovaltion lait muuttuvat oikein. Tässä tapauksessa muutosten määrän tulisi olla minimaalinen (tällä menettelyllä on omat algoritminsa, joihin emme keskity tässä artikkelissa). Alla on esimerkki tällaisesta datamuunnoksesta. Vasemmalla on alkuperäinen suhde, jossa tarvittavat FL:t eivät ilmeisesti täyty (esimerkki yhden FL:n rikkomisesta on korostettu punaisella). Oikealla on päivitetty suhde, ja vihreät solut näyttävät muuttuneet arvot. Tämän toimenpiteen jälkeen tarvittavat riippuvuudet alkoivat säilyttää.
Toinen suosittu sovellus on tietokantasuunnittelu. Tässä kannattaa palauttaa mieleen normaalit muodot ja normalisointi. Normalisointi on prosessi, jossa suhde saatetaan mukaiseksi tiettyjen vaatimusten kanssa, joista jokainen määritellään normaalimuodolla omalla tavallaan. Emme kuvaile erilaisten normaalimuotojen vaatimuksia (tämä tehdään missä tahansa aloittelijan tietokantakurssin kirjassa), mutta huomioimme vain, että jokainen niistä käyttää toiminnallisten riippuvuuksien käsitettä omalla tavallaan. Loppujen lopuksi FL:t ovat luonnostaan eheysrajoituksia, jotka otetaan huomioon tietokantaa suunniteltaessa (tämän tehtävän yhteydessä FL:itä kutsutaan joskus superavaimiksi).
Tarkastellaanpa heidän hakemustaan alla olevan kuvan neljälle normaalille lomakkeelle. Muista, että Boyce-Coddin normaalimuoto on tiukempi kuin kolmas muoto, mutta vähemmän tiukka kuin neljäs. Emme harkitse jälkimmäistä toistaiseksi, koska sen muotoilu edellyttää moniarvoisten riippuvuuksien ymmärtämistä, jotka eivät ole kiinnostavia tässä artikkelissa.
Toinen alue, jolla riippuvuudet ovat löytäneet sovelluksensa, on piirreavaruuden ulottuvuuden vähentäminen tehtävissä, kuten naiivin Bayes-luokittajan rakentaminen, merkittävien ominaisuuksien tunnistaminen ja regressiomallin uudelleenparametrisointi. Alkuperäisissä artikkeleissa tätä tehtävää kutsutaan redundantin ja ominaisuuden relevanssin määrittämiseksi [5, 6] ja se ratkaistaan tietokantakäsitteiden aktiivisella käytöllä. Tällaisten teosten myötä voidaan sanoa, että nykyään on kysyntää ratkaisuille, joiden avulla voimme yhdistää tietokannan, analytiikan ja yllä olevien optimointiongelmien toteuttamisen yhdeksi työkaluksi [7, 8, 9].
Liittovaltion lakien etsimiseen tietojoukosta on olemassa monia algoritmeja (sekä moderneja että vähemmän moderneja). Tällaiset algoritmit voidaan jakaa kolmeen ryhmään:
- Algoritmit, joissa käytetään algebrallisten hilan läpikulkua (hilaläpikulkualgoritmit)
- Algoritmit, jotka perustuvat sovittujen arvojen etsimiseen (ero- ja sovitusalgoritmit)
- Parivertailuihin perustuvat algoritmit (riippuvuuden induktioalgoritmit)
Alla olevassa taulukossa on lyhyt kuvaus kustakin algoritmityypistä:
Voit lukea lisää tästä luokituksesta [4]. Alla on esimerkkejä kunkin tyypin algoritmeista:
Tällä hetkellä ilmestyy uusia algoritmeja, jotka yhdistävät useita lähestymistapoja toiminnallisten riippuvuuksien löytämiseen. Esimerkkejä tällaisista algoritmeista ovat Pyro [2] ja HyFD [3]. Heidän työnsä analyysiä odotetaan tämän sarjan seuraavissa artikkeleissa. Tässä artikkelissa tarkastellaan vain peruskäsitteitä ja lemmoja, jotka ovat tarpeen riippuvuuden havaitsemistekniikoiden ymmärtämiseksi.
Aloitetaan yksinkertaisella - ero- ja samaa-joukolla, jota käytetään toisen tyyppisissä algoritmeissa. Difference-set on joukko monikoita, joilla ei ole samoja arvoja, kun taas samaa-joukko on päinvastoin monikko, joilla on samat arvot. On syytä huomata, että tässä tapauksessa tarkastelemme vain riippuvuuden vasenta puolta.
Toinen tärkeä käsite, joka kohdattiin edellä, on algebrallinen hila. Koska monet nykyaikaiset algoritmit toimivat tällä konseptilla, meillä on oltava käsitys siitä, mikä se on.
Hilan käsitteen käyttöön ottamiseksi on tarpeen määritellä osittain järjestetty joukko (tai osittain järjestetty joukko, lyhennettynä poset).
Määritelmä 2. Joukon S sanotaan olevan osittain järjestetty binäärirelaatiolla ⩽, jos kaikille a, b, c ∈ S seuraavat ominaisuudet täyttyvät:
- Refleksiivisyys, eli a ⩽ a
- Antisymmetria, eli jos a ⩽ b ja b ⩽ a, niin a = b
- Transitiivisuudesta eli a ⩽ b:lle ja b ⩽ c:lle seuraa, että a ⩽ c
Tällaista relaatiota kutsutaan (löysäksi) osittaisen järjestyksen relaatioksi ja itse joukkoa kutsutaan osittain järjestetyksi joukoksi. Muodollinen merkintä: ⟨S, ⩽⟩.
Yksinkertaisina esimerkkinä osittain järjestetystä joukosta voidaan ottaa kaikkien luonnollisten lukujen N joukko tavanomaisella järjestyssuhteella ⩽. On helppo varmistaa, että kaikki tarvittavat aksioomit täyttyvät.
Järkevämpi esimerkki. Tarkastellaan kaikkien osajoukkojen joukkoa {1, 2, 3}, jotka on järjestetty inkluusiorelaation ⊆ mukaan. Tämä relaatio todellakin täyttää kaikki osittaisen järjestyksen ehdot, joten ⟨P ({1, 2, 3}), ⊆⟩ on osittain järjestetty joukko. Alla oleva kuva esittää tämän joukon rakenteen: jos yksi elementti voidaan saavuttaa nuolilla toiseen elementtiin, ne ovat järjestyssuhteessa.
Tarvitsemme vielä kaksi yksinkertaista määritelmää matematiikan alalta - supremum ja infimum.
Määritelmä 3. Olkoon ⟨S, ⩽⟩ osittain järjestetty joukko, A ⊆ S. A:n yläraja on alkio u ∈ S siten, että ∀x ∈ S: x ⩽ u. Olkoon U kaikkien S:n ylärajojen joukko. Jos U:ssa on pienin alkio, niin sitä kutsutaan supremumiksi ja merkitään sup A:lla.
Tarkan alarajan käsite esitellään samalla tavalla.
Määritelmä 4. Olkoon ⟨S, ⩽⟩ osittain järjestetty joukko, A ⊆ S. A:n infimumi on alkio l ∈ S siten, että ∀x ∈ S: l ⩽ x. Olkoon L kaikkien S:n alarajojen joukko. Jos L:ssä on suurin alkio, niin sitä kutsutaan infimumiksi ja merkitään inf A:lla.
Tarkastellaan esimerkkinä yllä olevaa osittain järjestettyä joukkoa ⟨P ({1, 2, 3}), ⊆⟩ ja etsi siitä supremum ja infimum:
Nyt voimme muotoilla algebrallisen hilan määritelmän.
Määritelmä 5. Olkoon ⟨P,⩽⟩ osittain järjestetty joukko siten, että jokaisella kaksialkioisella osajoukolla on ylä- ja alaraja. Silloin P:tä kutsutaan algebralliseksi hilaksi. Tässä tapauksessa sup{x, y} kirjoitetaan muodossa x ∨ y ja inf {x, y} muodossa x ∧ y.
Tarkistetaan, että työesimerkkimme ⟨P ({1, 2, 3}), ⊆⟩ on hila. Todellakin, millä tahansa a:lla b ∈ P ({1, 2, 3}), a∨b = a∪b ja a∧b = a∩b. Harkitse esimerkiksi joukkoja {1, 2} ja {1, 3} ja etsi niiden infimum ja supremum. Jos leikkaamme ne, saamme joukon {1}, joka on infimum. Supremumin saamme yhdistämällä ne - {1, 2, 3}.
Fyysisten ongelmien tunnistamisalgoritmeissa hakuavaruus esitetään usein hilan muodossa, jossa yhden elementin joukot (lue hakuhilan ensimmäinen taso, jossa riippuvuuksien vasen puoli koostuu yhdestä attribuutista) edustavat jokaista attribuuttia. alkuperäisestä suhteesta.
Ensin tarkastellaan muotoa ∅ → olevia riippuvuuksia Yksi attribuutti. Tämän vaiheen avulla voit määrittää, mitkä attribuutit ovat ensisijaisia avaimia (tällaisille attribuuteille ei ole determinantteja, ja siksi vasen puoli on tyhjä). Lisäksi tällaiset algoritmit liikkuvat ylöspäin hilaa pitkin. On syytä huomata, että koko hila ei voi kulkea läpi, eli jos vasemman puolen haluttu maksimikoko välitetään sisääntuloon, niin algoritmi ei mene pidemmälle kuin taso tällä koolla.
Alla oleva kuva näyttää kuinka algebrallista hilaa voidaan käyttää FZ:n löytämisongelmassa. Tässä jokainen reuna (X, XY) edustaa riippuvuutta X → Y. Olemme esimerkiksi läpäisseet ensimmäisen tason ja tiedämme, että riippuvuus säilyy A → B (Näytämme tämän vihreänä yhteytenä kärkien välillä A и B). Tämä tarkoittaa, että edelleen, kun siirrymme ylöspäin hilaa pitkin, emme välttämättä tarkista riippuvuutta A, C → B, koska se ei ole enää minimaalinen. Emme myöskään tarkastaisi sitä, jos riippuvuus olisi pidetty C → B.
Lisäksi yleensä kaikki nykyaikaiset algoritmit liittovaltion lakien etsimiseen käyttävät tietorakennetta, kuten osiota (alkuperäisessä lähteessä - riisuttu osio [1]). Osion muodollinen määritelmä on seuraava:
Määritelmä 6. Olkoon X ⊆ R attribuuttien joukko relaatiolle r. Klusteri on joukko r:n monikkoindeksejä, joilla on sama arvo X:lle, eli c(t) = {i|ti[X] = t[X]}. Osio on joukko klustereita, ei yksikköpituisia klustereita:
Yksinkertaisesti sanottuna osio attribuutille X on joukko luetteloita, joissa jokainen luettelo sisältää rivinumerot, joilla on samat arvot X. Nykyaikaisessa kirjallisuudessa osioita edustavaa rakennetta kutsutaan paikkaluetteloindeksiksi (PLI). Yksikköpituiset klusterit jätetään pois PLI-pakkaustarkoituksiin, koska ne ovat klustereita, jotka sisältävät vain tietuenumeron, jolla on yksilöllinen arvo, joka on aina helppo tunnistaa.
Katsotaanpa esimerkkiä. Palataan samaan taulukkoon potilaiden kanssa ja rakennetaan osioita sarakkeille potilas и Paavali (vasemmalle on ilmestynyt uusi sarake, johon on merkitty taulukon rivinumerot):
Lisäksi määritelmän mukaan sarakkeen osio potilas on itse asiassa tyhjä, koska yksittäiset klusterit suljetaan pois osiosta.
Osiot voidaan saada useilla määritteillä. Ja on olemassa kaksi tapaa tehdä tämä: käymällä taulukon läpi, rakentamalla osio käyttämällä kaikkia tarvittavia määritteitä kerralla tai rakentamalla se käyttämällä osioiden leikkaustoimintoa attribuuttien osajoukon avulla. Liittovaltion lain hakualgoritmit käyttävät toista vaihtoehtoa.
Yksinkertaisesti sanottuna, esimerkiksi saada osio sarakkeiden mukaan ABC, voit ottaa osioita varten AC и B (tai mikä tahansa muu erillisten osajoukkojen joukko) ja leikkaa ne keskenään. Kahden osion leikkausoperaatio valitsee suurimman pituiset klusterit, jotka ovat yhteisiä molemmille osioille.
Katsotaanpa esimerkkiä:
Ensimmäisessä tapauksessa saimme tyhjän osion. Jos katsot taulukkoa tarkasti, näillä kahdella attribuutilla ei todellakaan ole identtisiä arvoja. Jos muutamme hieman taulukkoa (oikealla oleva tapaus), saamme jo ei-tyhjän risteyksen. Lisäksi rivit 1 ja 2 sisältävät itse asiassa samat attribuuttien arvot Paavali и Lääkäri.
Seuraavaksi tarvitsemme sellaisen käsitteen kuin osion koko. Muodollisesti:
Yksinkertaisesti sanottuna osion koko on osioon sisältyvien klustereiden lukumäärä (muista, että yksittäiset klusterit eivät sisälly osioon!):
Nyt voimme määritellä yhden avainlemmoista, jonka avulla tietyille osiolle voidaan määrittää, onko riippuvuus säilytetty vai ei:
Lemma 1. Riippuvuus A, B → C pätee jos ja vain jos
Lemman mukaan riippuvuuden pätevyyden määrittämiseksi on suoritettava neljä vaihetta:
- Laske osio riippuvuuden vasemmalle puolelle
- Laske osio riippuvuuden oikealle puolelle
- Laske ensimmäisen ja toisen vaiheen tulo
- Vertaa ensimmäisessä ja kolmannessa vaiheessa saatujen väliseinien kokoja
Alla on esimerkki sen tarkistamisesta, pitääkö riippuvuus tämän lemman mukaan:
Tässä artikkelissa tarkastelimme käsitteitä, kuten toiminnallinen riippuvuus, likimääräinen toiminnallinen riippuvuus, tarkastelimme, missä niitä käytetään, sekä mitä algoritmeja fyysisten toimintojen etsimiseen on olemassa. Tutkimme myös yksityiskohtaisesti peruskäsitteitä, joita käytetään aktiivisesti nykyaikaisissa liittovaltion lakien etsimisalgoritmeissa.
Viitteet:
- Huhtala Y. et ai. TANE: Tehokas algoritmi toiminnallisten ja likimääräisten riippuvuuksien löytämiseen //Tietokoneen päiväkirja. – 1999. – T. 42. – Ei. 2. – s. 100-111.
- Kruse S., Naumann F. Tehokas likimääräisten riippuvuuksien löytäminen // Proceedings of the VLDB Endowment. – 2018. – T. 11. – Ei. 7. – s. 759-772.
- Papenbrock T., Naumann F. Hybridi lähestymistapa toiminnallisen riippuvuuden löytämiseen // Proceedings of the 2016 International Conference on Management of Data. – ACM, 2016. – s. 821-833.
- Papenbrock T. et ai. Funktionaalisen riippuvuuden etsintä: Seitsemän algoritmin kokeellinen arviointi //Proceedings of the VLDB Endowment. – 2015. – T. 8. – Ei. 10. – s. 1082-1093.
- Kumar A. et ai. Liitytkö vai ollako liittymättä?: Mietitkö liittymistä kahdesti ennen ominaisuuden valintaa //Proceedings of the 2016 International Conference on Data Management. – ACM, 2016. – s. 19-34.
- Abo Khamis M. et ai. Tietokannan sisäinen oppiminen harvoilla tensoreilla //Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems. – ACM, 2018. – s. 325-340.
- Hellerstein JM et ai. MADlib-analytiikkakirjasto: tai MAD-taidot, SQL //Proceedings of the VLDB Endowment. – 2012. – T. 5. – Ei. 12. – s. 1700-1711.
- Qin C., Rusu F. Spekulatiivisia approksimaatioita terascale-jaetun gradientin laskeutumisen optimointiin //Proceedings of the Fourth Workshop on Data analytics in the Cloud. – ACM, 2015. – s. 1.
- Meng X. et ai. Mllib: Koneoppiminen apache-sparkissa //The Journal of Machine Learning Research. – 2016. – T. 17. – Ei. 1. – s. 1235-1241.
Artikkelin kirjoittajat: , tutkija osoitteessa , и , tutkija osoitteessa
Lähde: will.com