Uvod u funkcionalne zavisnosti

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

Funkcionalne zavisnosti ćemo razmotriti u kontekstu relacionih baza podataka. Ugrubo govoreći, u takvim bazama podataka informacije se pohranjuju u obliku tabela. Zatim koristimo približne koncepte koji nisu zamjenjivi u strogoj teoriji relacija: sama tablica će se zvati relacija, stupci će se zvati atributi (njihov skup je shema relacije), a skup vrijednosti reda na podskupu atributa će se zvati tuple.

Na primjer, u gornjoj tabeli, (Benson, M, Morgan) je tuple po atributima (pacijent, Paul, doktor).
Formalnije, ovo se piše ovako: [Pacijent, Paul, doktor] = (Benson, M, Morgan).
Sada možemo uvesti koncept funkcionalne zavisnosti (FC):

Definicija 1. Relacija R zadovoljava FD X → Y (gdje je X, Y ⊆ R) ako i samo ako za bilo koje torke , ∈ R je zadovoljeno: ako [x]= [X], onda [Y] = [Y]. U takvom slučaju se kaže da X (determinanta ili definirajući skup atributa) funkcionalno određuje Y (zavisni skup).

Drugim riječima, prisustvo saveznog zakona X→Y znači da ako imamo dvije tuple u R i poklapaju se u atributima X, tada će se također podudarati po atributima Y.
A sada redom. Uzmite u obzir atribute Pacijent и Seks za koje želimo da znamo da li postoje zavisnosti između njih ili ne. Za takav skup atributa mogu postojati sljedeće zavisnosti:

1. Pacijent → Pol
2. Pol → Pacijent

Prema gornjoj definiciji, da bi se zadržala prva zavisnost, svaka jedinstvena vrijednost stupca Pacijent samo jedna vrijednost stupca mora odgovarati Seks. A za tabelu primjera, ovo je istina. Međutim, to ne radi u suprotnom smjeru, odnosno nije ispunjena druga ovisnost, a atribut Seks nije odrednica za Pacijent. Slično, ako uzmemo zavisnost Doktor → Pacijent, možete vidjeti da je prekršena, jer vrijednost crvendać na ovom atributu ima nekoliko različitih vrijednosti − Ellis i Graham.

Dakle, funkcionalne zavisnosti vam omogućavaju da odredite postojeće odnose između skupova atributa tabele. Odavde pa nadalje razmatrat ćemo najzanimljivije veze, tačnije takve X→Yšta su:

• netrivijalan, to jest, desna strana zavisnosti nije podskup lijeve (Y ⊆ X);
• minimalna, odnosno ne postoji takva zavisnost Z → Y, to Z ⊂ X.

Zavisnosti koje su do sada razmatrane bile su stroge, odnosno nisu predviđale nikakva kršenja na tabeli, ali pored njih postoje i one koje dopuštaju neku nedoslednost između vrednosti torki. Takve zavisnosti se izdvajaju u posebnu klasu, nazvanu približne, i dozvoljeno im je da budu narušene na određenom broju torki. Ovaj broj se prilagođava indikatorom maksimalne greške emax. Na primjer, stopa greške = 0.01 može značiti da zavisnost može biti narušena za 1% dostupnih tuple-a na razmatranom skupu atributa. To jest, za 1000 zapisa, maksimalno 10 tuple-ova može prekršiti savezni zakon. Razmotrit ćemo malo drugačiju metriku zasnovanu na parovima različitih vrijednosti upoređenih točaka. Za ovisnost X→Y u odnosu r računa se ovako:

Izračunajmo grešku za Doktor → Pacijent iz gornjeg primjera. Imamo dva tuple-a čije se vrijednosti razlikuju po atributu Pacijent, ali se poklapaju sa doktore: [Doktor, pacijent] = (Robin, Elis) i [Doktor, pacijent] = (Robin, Graham). Nakon definicije greške, moramo uzeti u obzir sve konfliktne parove, što znači da će ih biti dva :(, ) i njegov inverzni (, ). Zamijenite u formuli i dobijete:

A sada pokušajmo odgovoriti na pitanje: "Zašto je to sve?". U stvari, FZ su drugačiji. Prvi tip su one zavisnosti koje definiše administrator u fazi dizajna baze podataka. Obično ih je malo, oni su strogi, a glavna primjena je normalizacija podataka i dizajn šeme odnosa.

Drugi tip su zavisnosti koje predstavljaju "skrivene" podatke i prethodno nepoznate odnose između atributa. Odnosno, takve zavisnosti nisu razmišljane u trenutku projektovanja i one se već nalaze za postojeći skup podataka, tako da se kasnije, na osnovu skupa identifikovanih FD, mogu izvući bilo kakvi zaključci o pohranjenim informacijama. Sa takvim zavisnostima mi radimo. Bave se čitavim poljem rudarenja podataka sa različitim tehnikama pretraživanja i algoritmima izgrađenim na njihovoj osnovi. Hajde da shvatimo kako pronađene funkcionalne zavisnosti (tačne ili približne) u bilo kojim podacima mogu biti korisne.

Danas se među glavnim područjima primjene ovisnosti izdvaja čišćenje podataka. To uključuje razvoj procesa za identifikaciju "prljavih podataka" i njihovo ispravljanje. Svijetli predstavnici "prljavih podataka" su duplikati, greške u podacima ili tipkarske greške, nedostajuće vrijednosti, zastarjeli podaci, dodatni razmaci i slično.

Primjer greške u podacima:

Primjer duplikata u podacima:

Na primjer, imamo tabelu i set saveznih zakona koji se moraju ispuniti. Čišćenje podataka u ovom slučaju uključuje promjenu podataka na način da federalni zakoni postanu istiniti. U isto vrijeme, broj izmjena trebao bi biti minimalan (postoje algoritmi za ovu proceduru, na koje se nećemo fokusirati u ovom članku). Ispod je primjer takve transformacije podataka. Na lijevoj strani je početna relacija, u kojoj, očigledno, nisu ispunjeni potrebni FL (primjer kršenja jednog od FL-a je označen crvenom bojom). Desno je ažurirani odnos, sa zelenim ćelijama koje prikazuju promijenjene vrijednosti. Nakon provođenja takvog postupka počele su se održavati potrebne ovisnosti.

Još jedno popularno područje primjene je dizajn baze podataka. Ovdje je vrijedno podsjetiti na normalne oblike i normalizaciju. Normalizacija je proces usklađivanja odnosa sa nekim skupom zahteva, od kojih je svaki definisan normalnim oblikom na svoj način. Nećemo opisivati ​​zahtjeve raznih normalnih oblika (to se radi u bilo kojoj knjizi na kursu baze podataka za početnike), ali samo napominjemo da svaki od njih koristi koncept funkcionalnih ovisnosti na svoj način. Na kraju krajeva, FD-ovi su inherentno ograničenja integriteta koja se uzimaju u obzir prilikom dizajniranja baze podataka (u kontekstu ovog zadatka, FD-ovi se ponekad nazivaju superključevima).

Razmotrite njihovu primjenu za četiri normalna oblika na slici ispod. Podsjetimo da je Boyce-Codd normalni oblik rigorozniji od trećeg oblika, ali manje strog od četvrtog. Potonje još ne razmatramo, jer njegova formulacija zahtijeva razumijevanje viševrijednih ovisnosti, koje nas u ovom članku ne zanimaju.

Još jedno područje u kojem su zavisnosti pronašle svoj put je smanjenje dimenzije prostora karakteristika u takvim problemima kao što je izgradnja naivnog Bayesovog klasifikatora, izdvajanje značajnih karakteristika i reparametriziranje regresijskog modela. U originalnim člancima ovaj problem se naziva određivanje redundantnih karakteristika (feature redundancy) i relevantnih (feature relevance) [5, 6], a rješava se aktivnom upotrebom koncepata baze podataka. Pojavom ovakvih radova, možemo reći da danas postoji potražnja za rješenjima koja omogućavaju kombinovanje baze podataka, analitike i implementacije navedenih optimizacijskih problema u jedan alat [7, 8, 9].

Postoji mnogo algoritama (i modernih i ne baš modernih) za traženje FD u skupu podataka. Takvi algoritmi se mogu podijeliti u tri grupe:

• Algoritmi prelaska mreže
• Algoritmi zasnovani na potrazi za konzistentnim vrijednostima (algoritmi skupa razlika i slaganja)
• Algoritmi zasnovani na parovima poređenja (algoritmi indukcije zavisnosti)

Kratak opis svake vrste algoritma je predstavljen u tabeli ispod:


Više detalja o ovoj klasifikaciji može se naći u [4]. Ispod su primjeri algoritama za svaki tip:

Trenutno se pojavljuju novi algoritmi koji kombinuju nekoliko pristupa istovremenom pronalaženju funkcionalnih zavisnosti. Primjeri takvih algoritama su Pyro [2] i HyFD [3]. Analiza njihovog rada očekuje se u narednim člancima ove serije. U ovom članku ćemo analizirati samo osnovne koncepte i lemu koji su neophodni za razumijevanje tehnika za identifikaciju ovisnosti.

Počnimo s jednostavnim - skupom razlika i slaganja, koji se koristi u drugoj vrsti algoritama. Difference-set je skup točaka koji se ne podudaraju u vrijednosti, a skup za slaganje, naprotiv, su torovi koji se podudaraju u vrijednosti. Treba napomenuti da u ovom slučaju razmatramo samo lijevu stranu zavisnosti.

Također važan koncept koji je gore naveden je algebarska rešetka. Budući da mnogi moderni algoritmi rade na ovom konceptu, moramo imati predstavu o tome šta je to.

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

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

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

Takva relacija se naziva relacija (nestrogog) parcijalnog reda, a sam skup se naziva djelomično uređen skup. Formalna notacija: ⟨S, ⩽⟩.

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

Smisaoniji primjer. Razmotrimo skup svih podskupova {1, 2, 3} poredanih relacijom uključivanja ⊆. Zaista, ova relacija zadovoljava sve uvjete parcijalnog poretka, tako da je ⟨P ({1, 2, 3}), ⊆⟩ djelomično uređen skup. Slika ispod prikazuje strukturu ovog skupa: ako je od jednog elementa moguće hodati duž strelica do drugog elementa, onda su oni u odnosu reda.

Potrebne su nam još dvije jednostavne definicije iz oblasti matematike - supremum (supremum) i infimum (infimum).

Definicija 3. Neka je ⟨S, ⩽⟩ skup, A ⊆ S. Gornja granica A je element u ∈ S takav da je ∀x ∈ S: x ⩽ u. Neka je U skup svih gornjih granica S. Ako U ima najmanji element, onda se naziva supremum i označava kao sup A.

Slično se uvodi i pojam tačne donje granice.

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

Kao primjer, razmotrite gornji djelomično uređen skup ⟨P ({1, 2, 3}), ⊆⟩ i pronađite supremum i infimum u njemu:

Sada možemo formulirati definiciju algebarske rešetke.

Definicija 5. Neka je ⟨P, ⩽⟩ skup takav da svaki podskup od dva elementa ima oštre gornje i donje granice. Tada se P naziva algebarska rešetka. U ovom slučaju, sup{x, y} se zapisuje kao x ∨ y, a inf {x, y} kao x ∧ y.

Provjerimo da je naš radni primjer ⟨P ({1, 2, 3}), ⊆⟩ rešetka. Zaista, 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 presiječemo, dobićemo skup {1}, koji će biti infimum. Supremum se dobija njihovim udruživanjem - {1, 2, 3}.

U algoritmima FD detekcije, prostor pretraživanja je često predstavljen u obliku rešetke, gdje skupovi jednog elementa (čitaj prvi nivo mreže pretraživanja, gdje se lijeva strana zavisnosti sastoji od jednog atributa) predstavljaju svaki atribut originalni odnos.
Na početku su zavisnosti oblika ∅ → pojedinačni atribut. Ovaj korak vam omogućava da odredite koji su atributi primarni ključevi (nema determinanti za takve atribute, pa je lijeva strana prazna). Nadalje, takvi algoritmi se pomiču naviše po rešetki. Istovremeno, vrijedi napomenuti da se ne može zaobići cijela rešetka, odnosno ako se željena maksimalna veličina lijeve strane prenese na ulaz, tada algoritam neće ići dalje od razine s ovom veličinom.

Slika ispod pokazuje kako možete koristiti algebarsku rešetku u problemu traženja FD. Ovdje svaka ivica (X,XY) predstavlja zavisnost X→Y. Na primjer, prošli smo prvi nivo i znamo da se zavisnost održava A→B (ovo ćemo prikazati sa zelenom vezom između vrhova A и B). Dakle, dalje, kada se krećemo gore po rešetki, ne možemo provjeriti ovisnost A, C → B, jer više neće biti minimalan. Slično, ne bismo ga provjeravali da je ovisnost zadržana C→B.

Osim toga, po pravilu, svi moderni algoritmi za traženje FD-ova koriste takvu strukturu podataka kao particiju (u izvornom izvoru - ogoljena particija [1]). Formalna definicija particije je sljedeća:

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

Jednostavno rečeno, particija za atribut X je skup lista, gdje svaka lista sadrži brojeve redova sa istim vrijednostima za X. U modernoj literaturi, struktura koja predstavlja particije naziva se indeks liste pozicija (PLI). Klasteri jedne dužine su isključeni za potrebe PLI kompresije jer su klasteri koji sadrže samo broj zapisa s jedinstvenom vrijednošću koju će uvijek biti lako postaviti.

Razmotrimo primjer. Vratimo se na istu tabelu sa pacijentima i napravimo particije za kolone Pacijent и Seks (na lijevoj strani se pojavila nova kolona u kojoj su označeni brojevi redova tabele):

U ovom slučaju, prema definiciji, particija za kolonu Pacijent će zapravo biti prazan, budući da su pojedinačni klasteri isključeni iz particije.

Particije se mogu dobiti pomoću nekoliko atributa. A za to postoje dva načina: hodajući kroz tabelu, napravite particiju odjednom po svim potrebnim atributima ili je napravite koristeći operaciju ukrštanja particija prema podskupu atributa. Algoritmi FD pretraživanja koriste drugu opciju.

Jednostavnim riječima, na primjer, da dobijete particiju po kolonama ABC, možete uzeti particije za AC и B (ili bilo koji drugi skup disjunktnih podskupova) i sijeku ih jedan s drugim. Operacija ukrštanja dvije particije odabire klastere najveće dužine koji su zajednički za obje particije.

Pogledajmo primjer:

U prvom slučaju, dobili smo praznu particiju. Ako pažljivo pogledate tabelu, onda zaista nema identičnih vrijednosti za dva atributa. Ako malo izmijenimo tabelu (slučaj desno), tada ćemo već dobiti nepraznu raskrsnicu. Istovremeno, redovi 1 i 2 zaista sadrže iste vrijednosti za atribute Seks и Doktor.

Zatim nam je potreban koncept kao što je 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 date particije, omogućava da odredimo da li se zavisnost drži ili ne:

Lema 1. Zavisnost A, B → C se održava ako i samo ako

Prema lemi, postoje četiri koraka za određivanje da li se zavisnost drži:

1. Izračunajte particiju za lijevu stranu zavisnosti
2. Izračunajte particiju za desnu stranu zavisnosti
3. Izračunajte proizvod prvog i drugog koraka
4. Uporedite veličine particija dobijene u prvom i trećem koraku

Ispod je primjer provjere da li ovisnost drži ova lema:

U ovom članku analizirali smo koncepte kao što su funkcionalna zavisnost, približna funkcionalna zavisnost, ispitali gde se koriste, kao i koji algoritmi za traženje FD postoje. Također smo detaljno analizirali osnovne, ali važne koncepte koji se aktivno koriste u modernim algoritmima za traženje FD-ova.

Linkovi na literaturu:

1. Huhtala Y. et al. TANE: Efikasan algoritam za otkrivanje funkcionalnih i približnih zavisnosti //The computer journal. - 1999. - T. 42. - Br. 2. - S. 100-111.
2. Kruse S., Naumann F. Učinkovito otkrivanje približnih ovisnosti // Proceedings of the VLDB Endowment. - 2018. - T. 11. - Br. 7. - S. 759-772.
3. Papenbrock T., Naumann F. Hibridni pristup otkrivanju funkcionalne ovisnosti // Proceedings of the 2016 International Conference on Management of Data. - ACM, 2016. - P. 821-833.
4. Papenbrock T. et al. Otkrivanje funkcionalne zavisnosti: Eksperimentalna evaluacija sedam algoritama //Proceedings of the VLDB Endowment. - 2015. - T. 8. - Br. 10. - S. 1082-1093.
5. Kumar A. et al. Pridružiti se ili ne pridružiti se?: Dvaput razmišljam o spajanjima prije odabira karakteristika //Proceedings of the 2016 International Conference on Management of Data. - ACM, 2016. - S. 19-34.
6. Abo Khamis M. et al. Učenje unutar baze podataka s rijetkim tenzorima //Zbornik radova 37. ACM SIGMOD-SIGACT-SIGAI simpozija o principima sistema baza podataka. - ACM, 2018. - P. 325-340.
7. Hellerstein JM et al. MADlib analitička biblioteka: ili MAD vještine, SQL //Proceedings of the VLDB Endowment. - 2012. - V. 5. - Br. 12. - S. 1700-1711.
8. Qin C., Rusu F. Spekulativne aproksimacije za optimizaciju teraskalnog distribuiranog gradijenta spuštanja // Proceedings of the Fourth Workshop on Data analytics in the Cloud. - ACM, 2015. - Str. 1.
9. Meng X. et al. Mllib: Strojno učenje u apache iskri //The Journal of Machine Learning Research. - 2016. - T. 17. - Br. 1. - S. 1235-1241.

Autori članaka: Anastasia Birillo, istraživač u JetBrains Research, CS student и Nikita Bobrov, istraživač u JetBrains Research

izvor: www.habr.com