Uvod u funkcionalne ovisnosti

U ovom ćemo članku govoriti o funkcionalnim ovisnostima u bazama podataka – što su, gdje se koriste i koji algoritmi postoje za njihovo pronalaženje.

Razmotrit ćemo funkcionalne ovisnosti u kontekstu relacijskih baza podataka. Vrlo grubo rečeno, u takvim bazama podataka informacije se pohranjuju u obliku tablica. Zatim koristimo približne koncepte koji nisu međusobno zamjenjivi u strogoj relacijskoj teoriji: samu tablicu ćemo nazvati relacijom, stupce - atributima (njihov skup - relacijskom shemom), a skup vrijednosti redaka na podskupu atributa - tuple.

Na primjer, u gornjoj tablici, (Benson, M, M orgulje) je skup atributa (pacijent, Paul, doktor).
Formalnije, ovo je napisano na sljedeći način: [Pacijent, spol, liječnik] = (Benson, M, M orgulje).
Sada možemo uvesti koncept funkcionalne ovisnosti (FD):

Definicija 1. Relacija R zadovoljava federalni zakon X → Y (gdje je X, Y ⊆ R) ako i samo ako za bilo koju torku , ∈ R vrijedi: ako [X] = [X], dakle [Y] = [Y]. U ovom slučaju kažemo da X (determinanta ili definirajući skup atributa) funkcionalno određuje Y (ovisni skup).

Drugim riječima, prisutnost federalnog zakona X → Y znači da ako imamo dvije torke R a podudaraju se u atributima X, tada će se podudarati u atributima Y.
A sad redom. Pogledajmo atribute pacijent и Пол za koje želimo saznati postoje li među njima ovisnosti ili ne. Za takav skup atributa mogu postojati sljedeće ovisnosti:

1. Pacijent → Spol
2. Spol → Pacijent

Kao što je gore definirano, kako bi prva ovisnost održala, svaka jedinstvena vrijednost stupca pacijent samo jedna vrijednost stupca mora odgovarati Пол. A za primjer tablice to je doista slučaj. Međutim, to ne funkcionira u suprotnom smjeru, tj. druga ovisnost nije zadovoljena, a atribut Пол nije odrednica za Pacijent. Slično, ako uzmemo ovisnost Liječnik → Pacijent, možete vidjeti da je prekršen, jer vrijednost crvendać ovaj atribut ima nekoliko različitih značenja - Ellis i Graham.

Stoga funkcionalne ovisnosti omogućuju određivanje postojećih odnosa između skupova atributa tablice. Odavde ćemo razmotriti najzanimljivije veze, odnosno takve X → Yono što jesu:

• netrivijalan, to jest desna strana ovisnosti nije podskup lijeve (Y ̸⊆ X);
• minimalna, odnosno nema te ovisnosti Z → YDa Z ⊂ X.

Ovisnosti razmatrane do ove točke bile su stroge, odnosno nisu predviđale nikakva kršenja na tablici, ali osim njih postoje i one koje dopuštaju neku nedosljednost između vrijednosti torki. Takve se ovisnosti smještaju u zasebnu klasu, koja se naziva približna, i dopušteno ju je prekršiti za određeni broj torki. Ovaj iznos je reguliran maksimalnim indikatorom pogreške emax. Na primjer, stopa pogreške = 0.01 može značiti da se ovisnost može narušiti za 1% dostupnih torki na razmatranom skupu atributa. Odnosno, za 1000 zapisa, najviše 10 tupleova može kršiti Savezni zakon. Razmotrit ćemo nešto drugačiju metriku, temeljenu na parovima različitih vrijednosti torki koje se uspoređuju. Za ovisnost X → Y na stav r smatra se ovako:

Izračunajmo pogrešku za Liječnik → Pacijent iz gornjeg primjera. Imamo dvije torke čije se vrijednosti razlikuju na atributu pacijent, ali se podudaraju na Liječnik: [Doktor, pacijent] = (Robin, Ellis) I [Doktor, pacijent] = (Robin, Graham). Slijedom definicije greške, moramo uzeti u obzir sve konfliktne parove, što znači da će ih biti dva: (, ) i njegov inverz (, ). Zamijenimo to u formulu i dobijemo:

Pokušajmo sada odgovoriti na pitanje: "Zašto je sve to?" Zapravo, savezni zakoni su drugačiji. Prva vrsta su one ovisnosti koje određuje administrator u fazi projektiranja baze podataka. Obično ih je malo, strogi su, a glavna je primjena normalizacija podataka i dizajn relacijske sheme.

Drugi tip su ovisnosti, koje predstavljaju "skrivene" podatke i prethodno nepoznate odnose između atributa. To jest, o takvim ovisnostima se nije razmišljalo u vrijeme dizajna i one se pronalaze za postojeći skup podataka, tako da se kasnije, na temelju mnogih identificiranih federalnih zakona, mogu izvući bilo kakvi zaključci o pohranjenim informacijama. Upravo s tim ovisnostima radimo. Njima se bavi cijelo područje rudarenja podataka s različitim tehnikama pretraživanja i algoritmima izgrađenim na njihovoj osnovi. Shvatimo kako pronađene funkcionalne ovisnosti (točne ili približne) u bilo kojim podacima mogu biti korisne.

Danas je jedna od glavnih primjena ovisnosti čišćenje podataka. Uključuje razvoj procesa za prepoznavanje "prljavih podataka" i njihovo ispravljanje. Istaknuti primjeri "prljavih podataka" su duplikati, pogreške u podacima ili tipfeleri, vrijednosti koje nedostaju, zastarjeli podaci, dodatni razmaci i slično.

Primjer pogreške podataka:

Primjer duplikata u podacima:

Na primjer, imamo tablicu i skup federalnih zakona koji se moraju izvršiti. Čišćenje podataka u ovom slučaju uključuje promjenu podataka kako bi federalni zakoni postali točni. U ovom slučaju, broj izmjena bi trebao biti minimalan (ovaj postupak ima svoje algoritme, na koje se nećemo usredotočiti u ovom članku). Ispod je primjer takve transformacije podataka. Lijevo je izvorni odnos u kojem, očito, nisu ispunjeni potrebni FL (primjer kršenja jednog od FL označen je crvenom bojom). Desno je ažurirani odnos, sa zelenim ćelijama koje prikazuju promijenjene vrijednosti. Nakon ovog postupka počele su se održavati potrebne ovisnosti.

Druga popularna aplikacija je dizajn baze podataka. Ovdje se vrijedi prisjetiti normalnih oblika i normalizacije. Normalizacija je proces usklađivanja odnosa s određenim skupom zahtjeva, od kojih je svaki definiran normalnim oblikom na svoj način. Nećemo opisivati ​​zahtjeve raznih normalnih formi (to se radi u bilo kojoj knjizi o tečaju baza podataka za početnike), ali ćemo samo primijetiti da svaka od njih koristi koncept funkcionalnih ovisnosti na svoj način. Uostalom, FL-ovi su inherentna ograničenja integriteta koja se uzimaju u obzir prilikom dizajniranja baze podataka (u kontekstu ovog zadatka, FL-ovi se ponekad nazivaju superključevi).

Razmotrimo njihovu primjenu za četiri normalne forme na donjoj slici. Podsjetimo se da je Boyce-Coddov normalni oblik stroži od trećeg oblika, ali manje stroži od četvrtog. Potonji za sada ne razmatramo, budući da njegova formulacija zahtijeva razumijevanje viševrijednih ovisnosti, koje nam u ovom članku nisu zanimljive.

Drugo područje u kojem su ovisnosti pronašle svoju primjenu je smanjenje dimenzionalnosti prostora značajki u zadacima kao što je izgradnja jednostavnog Bayesovog klasifikatora, identificiranje značajnih značajki i reparametrizacija regresijskog modela. U izvornim se člancima ovaj zadatak naziva određivanje redundantnosti i značajke relevantnosti [5, 6], a rješava se aktivnom uporabom koncepata baze podataka. S pojavom ovakvih radova, možemo reći da danas postoji potražnja za rješenjima koja nam omogućuju kombiniranje baze podataka, analitike i implementacije gore navedenih optimizacijskih problema u jedan alat [7, 8, 9].

Postoji mnogo algoritama (i modernih i manje modernih) za traženje federalnih zakona u skupu podataka. Takvi se algoritmi mogu podijeliti u tri skupine:

• Algoritmi koji koriste obilazak algebarskih rešetki (algoritmi za obilazak rešetke)
• Algoritmi koji se temelje na traženju dogovorenih vrijednosti (algoritmi razlike i slaganja)
• Algoritmi temeljeni na parnim usporedbama (algoritmi indukcije ovisnosti)

Kratak opis svake vrste algoritma prikazan je u tablici ispod:


Više o ovoj klasifikaciji možete pročitati [4]. Ispod su primjeri algoritama za svaku vrstu:

Trenutno se pojavljuju novi algoritmi koji kombiniraju nekoliko pristupa pronalaženju funkcionalnih ovisnosti. Primjeri takvih algoritama su Pyro [2] i HyFD [3]. Analiza njihova rada očekuje se u sljedećim člancima ove serije. U ovom ćemo članku ispitati samo osnovne pojmove i leme koji su potrebni za razumijevanje tehnika otkrivanja ovisnosti.

Počnimo s jednim jednostavnim - skupom razlike i slaganja, koji se koristi u drugoj vrsti algoritama. Skup razlika je skup torki koje nemaju iste vrijednosti, dok su skup slaganja, naprotiv, torke koje imaju iste vrijednosti. Vrijedno je napomenuti da u ovom slučaju razmatramo samo lijevu stranu ovisnosti.

Još jedan važan koncept koji je gore spomenut je algebarska mreža. Budući da mnogi moderni algoritmi rade na ovom konceptu, moramo imati predodžbu o tome što je to.

Da bi se uveo pojam rešetke, potrebno je definirati djelomično uređen skup (ili djelomično uređen skup, skraćeno poset).

Definicija 2. Za skup S se kaže da je djelomično uređen binarnom relacijom ⩽ ako su za sve a, b, c ∈ S zadovoljena sljedeća svojstva:

1. Refleksivnost, odnosno a ⩽ a
2. Antisimetrija, odnosno ako je a ⩽ b i b ⩽ a, tada je a = b
3. Tranzitivnost, odnosno za a ⩽ b i b ⩽ c slijedi da je a ⩽ c

Takva se relacija naziva (labava) relacija djelomičnog reda, a sam skup naziva se djelomično uređen skup. Formalni zapis: ⟨S, ⩽⟩.

Kao najjednostavniji primjer djelomično uređenog skupa možemo uzeti skup svih prirodnih brojeva N s uobičajenom relacijom reda ⩽. Lako je provjeriti da su svi potrebni aksiomi zadovoljeni.

Smisleniji primjer. Promotrimo skup svih podskupova {1, 2, 3}, poredanih relacijom uključivanja ⊆. Doista, ova relacija zadovoljava sve uvjete djelomičnog reda, pa je ⟨P ({1, 2, 3}), ⊆⟩ djelomično uređen skup. Donja slika prikazuje strukturu ovog skupa: ako se jedan element može doseći strelicama do drugog elementa, tada su u odnosu poredak.

Trebat će nam još dvije jednostavne definicije iz područja matematike - supremum i infimum.

Definicija 3. Neka je ⟨S, ⩽⟩ djelomično uređen skup, A ⊆ S. Gornja granica A je element u ∈ S takav da je ∀x ∈ S: x ⩽ u. Neka je U skup svih gornjih granica od S. Ako postoji najmanji element u U, tada se on naziva supremum i označava sup A.

Pojam točne donje granice uvodi se na sličan način.

Definicija 4. Neka je ⟨S, ⩽⟩ djelomično uređen skup, A ⊆ S. Infimum od A je element l ∈ S takav da je ∀x ∈ S: l ⩽ x. Neka je L skup svih donjih granica od S. Ako postoji najveći element u L, tada se on naziva infimum i označava se kao inf A.

Razmotrimo kao primjer gornji djelomično uređeni skup ⟨P ({1, 2, 3}), ⊆⟩ i pronađi supremum i infimum u njemu:

Sada možemo formulirati definiciju algebarske rešetke.

Definicija 5. Neka je ⟨P,⩽⟩ djelomično uređen skup tako da svaki podskup od dva elementa ima gornju i donju granicu. Tada se P naziva algebarska rešetka. U ovom slučaju, sup{x, y} se piše kao x ∨ y, a inf {x, y} kao x ∧ y.

Provjerimo da je naš radni primjer ⟨P ({1, 2, 3}), ⊆⟩ rešetka. Doista, za bilo koje a, b ∈ P ({1, 2, 3}), a∨b = a∪b, i a∧b = a∩b. Na primjer, razmotrite skupove {1, 2} i {1, 3} i pronađite njihov infimum i supremum. Ako ih presječemo, dobit ćemo skup {1} koji će biti infimum. Supremem dobivamo njihovim kombiniranjem - {1, 2, 3}.

U algoritmima za identificiranje fizičkih problema prostor pretraživanja često se predstavlja u obliku rešetke, gdje skupovi jednog elementa (čitaj prva razina rešetke pretraživanja, gdje se lijeva strana ovisnosti sastoji od jednog atributa) predstavljaju svaki atribut izvornog odnosa.
Prvo razmatramo ovisnosti oblika ∅ → Pojedinačni atribut. Ovaj korak vam omogućuje da odredite koji su atributi primarni ključevi (za takve atribute nema odrednica, pa je lijeva strana prazna). Nadalje, takvi se algoritmi kreću prema gore duž rešetke. Vrijedno je napomenuti da se ne može prijeći cijela rešetka, to jest, ako se željena maksimalna veličina lijeve strane proslijedi na ulaz, tada algoritam neće ići dalje od razine s tom veličinom.

Donja slika pokazuje kako se algebarska mreža može koristiti u problemu pronalaženja FZ. Ovdje svaki rub (X, XY) predstavlja ovisnost X → Y. Na primjer, prošli smo prvu razinu i znamo da se ovisnost održava A → B (to ćemo prikazati kao zelenu vezu između vrhova A и B). To znači da dalje, kada se pomičemo prema gore duž rešetke, možda nećemo provjeriti ovisnost A, C → B, jer više neće biti minimalan. Slično, ne bismo provjeravali da je ovisnost održana C → B.

Osim toga, u pravilu svi moderni algoritmi za traženje saveznih zakona koriste strukturu podataka kao što je particija (u izvornom izvoru - stripped partition [1]). Formalna definicija particije je sljedeća:

Definicija 6. Neka je X ⊆ R skup atributa za relaciju r. Klaster je skup indeksa torki u r koji imaju istu vrijednost za X, to jest, c(t) = {i|ti[X] = t[X]}. Particija je skup klastera, isključujući klastere jedinične duljine:

Jednostavnim riječima, particija za atribut X je skup popisa, gdje svaki popis sadrži brojeve redaka s istim vrijednostima za X. U modernoj literaturi struktura koja predstavlja particije naziva se indeks popisa pozicija (PLI). Klasteri jedinične duljine isključeni su za potrebe PLI kompresije jer su to klasteri koji sadrže samo broj zapisa s jedinstvenom vrijednošću koju će uvijek biti lako identificirati.

Pogledajmo primjer. Vratimo se istom stolu s pacijentima i izgradimo pregrade za stupove pacijent и Пол (lijevo se pojavio novi stupac u kojem su označeni brojevi redaka tablice):

Štoviše, prema definiciji, pregrada za stupac pacijent će zapravo biti prazan, jer su pojedinačni klasteri isključeni iz particije.

Particije se mogu dobiti po nekoliko atributa. A postoje dva načina da to učinite: prolaskom kroz tablicu, izgradite particiju koristeći sve potrebne atribute odjednom ili je izgradite koristeći operaciju presjeka particija koristeći podskup atributa. Algoritmi pretraživanja saveznih zakona koriste drugu opciju.

Jednostavnim riječima, da biste, na primjer, dobili particiju po stupcima abeceda, možete uzeti particije za AC и B (ili bilo koji drugi skup disjunktnih podskupova) i sijeku ih jedan s drugim. Operacijom presjeka dviju particija odabiru se klasteri najveće duljine koji su zajednički objema particijama.

Pogledajmo primjer:

U prvom slučaju dobili smo praznu particiju. Ako pažljivo pogledate tablicu, onda doista ne postoje identične vrijednosti za dva atributa. Ako malo modificiramo tablicu (slučaj desno), već ćemo dobiti neprazno sjecište. Štoviše, linije 1 i 2 zapravo sadrže iste vrijednosti za atribute Пол и Liječnik.

Zatim će nam trebati takav koncept kao veličina particije. Formalno:

Jednostavno rečeno, veličina particije je broj klastera uključenih u particiju (zapamtite da pojedinačni klasteri nisu uključeni u particiju!):

Sada možemo definirati jednu od ključnih lema, koja nam za dane particije omogućuje da odredimo da li se ovisnost održava ili ne:

Lema 1. Ovisnost A, B → C vrijedi ako i samo ako

Prema lemi, da bi se utvrdilo vrijedi li ovisnost, moraju se izvršiti četiri koraka:

1. Izračunajte particiju za lijevu stranu zavisnosti
2. Izračunajte particiju za desnu stranu zavisnosti
3. Izračunajte umnožak prvog i drugog koraka
4. Usporedite veličine pregrada dobivenih u prvom i trećem koraku

Ispod je primjer provjere vrijedi li ovisnost prema ovoj lemi:

U ovom smo članku ispitali pojmove kao što su funkcionalna ovisnost, približna funkcionalna ovisnost, pogledali gdje se koriste, kao i koji algoritmi za traženje fizičkih funkcija postoje. Također smo detaljno ispitali osnovne, ali važne koncepte koji se aktivno koriste u modernim algoritmima za traženje saveznih zakona.

Reference:

1. Huhtala Y. i sur. TANE: Učinkovit algoritam za otkrivanje funkcionalnih i približnih ovisnosti // Računalni časopis. – 1999. – T. 42. – Br. 2. – 100-111 str.
2. Kruse S., Naumann F. Učinkovito otkrivanje približnih ovisnosti // Proceedings of the VLDB Endowment. – 2018. – T. 11. – Br. 7. – 759-772 str.
3. Papenbrock T., Naumann F. Hibridni pristup otkrivanju funkcionalne ovisnosti //Proceedings of the 2016 International Conference on Management of Data. – ACM, 2016. – str. 821-833.
4. Papenbrock T. i sur. Otkriće funkcionalne ovisnosti: eksperimentalna procjena sedam algoritama // Proceedings of the VLDB Endowment. – 2015. – T. 8. – Br. 10. – 1082-1093 str.
5. Kumar A. i sur. Pridružiti se ili ne pridružiti se?: Dvaput razmisliti o spajanjima prije odabira značajki //Proceedings of the International Conference on Management of Data 2016. – ACM, 2016. – str. 19-34.
6. Abo Khamis M. i sur. Učenje u bazi podataka s rijetkim tenzorima //Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems. – ACM, 2018. – str. 325-340.
7. Hellerstein JM i sur. MADlib analitička biblioteka: ili MAD vještine, SQL //Proceedings of the VLDB Endowment. – 2012. – T. 5. – Br. 12. – 1700-1711 str.
8. Qin C., Rusu F. Spekulativne aproksimacije za optimizaciju spuštanja distribuiranog gradijenta u teraskali //Proceedings of the Fourth Workshop on Data analytics in Cloud. – ACM, 2015. – 1. str.
9. Meng X. i sur. Mllib: Strojno učenje u apache sparku // The Journal of Machine Learning Research. – 2016. – T. 17. – Br. 1. – 1235-1241 str.

Autori članka: Anastazija Birillo, istraživač na JetBrains istraživanje, Student CS centra и Nikita Bobrov, istraživač na JetBrains istraživanje

Izvor: www.habr.com