Šiame straipsnyje kalbėsime apie funkcines priklausomybes duomenų bazėse – kokios jos yra, kur jos naudojamos ir kokie algoritmai egzistuoja joms rasti.
Apsvarstysime funkcines priklausomybes reliacinių duomenų bazių kontekste. Labai grubiai tariant, tokiose duomenų bazėse informacija saugoma lentelių pavidalu. Toliau naudojame apytiksles sąvokas, kurios griežtoje santykių teorijoje nėra keičiamos: pačią lentelę vadinsime ryšiu, stulpelius - atributais (jų rinkinys - santykių schema), o eilučių reikšmių rinkinį atributų poaibyje. - kortele.
Pavyzdžiui, aukščiau esančioje lentelėje (Bensonas, M, M vargonai) yra atributų rinkinys (Pacientas, Paulius, gydytojas).
Formaliau tai parašyta taip: [Pacientas, lytis, gydytojas🇧🇷 (Bensonas, M, M vargonai).
Dabar galime pristatyti funkcinės priklausomybės (FD) sąvoką:
1 apibrėžimas. Santykis R tenkina federalinį įstatymą X → Y (kur X, Y ⊆ R) tada ir tik tada, kai bet kuriai kortelei , ∈ R galioja: jei [X] = [X], tada [Y] = [Y]. Šiuo atveju sakome, kad X (determinantas arba apibrėžiantis atributų rinkinys) funkciškai nustato Y (priklausomąją aibę).
Kitaip tariant, federalinio įstatymo buvimas X → Y reiškia, kad jei turime dvi eilutes R ir jie atitinka atributus X, tada jie sutaps atributais Y.
O dabar tvarka. Pažiūrėkime į atributus Pacientas и Paulius dėl kurių norime išsiaiškinti, ar tarp jų yra priklausomybių, ar ne. Tokiam atributų rinkiniui gali būti šios priklausomybės:
- Pacientas → Lytis
- Lytis → Pacientas
Kaip apibrėžta pirmiau, kad būtų išlaikyta pirmoji priklausomybė, kiekviena unikali stulpelio reikšmė Pacientas turi atitikti tik viena stulpelio reikšmė Paulius. Ir pavyzdinėje lentelėje taip yra. Tačiau tai neveikia priešinga kryptimi, tai yra, antroji priklausomybė netenkinama, o požymis Paulius nėra lemiamas veiksnys Pacientas. Panašiai, jei imtume priklausomybę Gydytojas → Pacientas, matote, kad jis pažeistas, nes vertė liepsnelė šis požymis turi keletą skirtingų reikšmių - Elisas ir Greimas.
Taigi funkcinės priklausomybės leidžia nustatyti esamus ryšius tarp lentelės atributų rinkinių. Nuo šiol mes apsvarstysime įdomiausius ryšius, tiksliau tokius X → Ykas jie yra:
- ne trivialus, tai yra, dešinioji priklausomybės pusė nėra kairiosios poaibis (Y ̸⊆ X);
- minimali, tai yra, tokios priklausomybės nėra Z → YKad Z ⊂ X.
Iki šiol svarstytos priklausomybės buvo griežtos, tai yra, jos nenumatė jokių pažeidimų ant stalo, tačiau be jų yra ir tokių, kurie leidžia tam tikrą neatitikimą tarp kortelių verčių. Tokios priklausomybės yra įtrauktos į atskirą klasę, vadinamą apytiksliais, ir jas leidžiama pažeisti tam tikram kortelių skaičiui. Šią sumą reguliuoja maksimalaus klaidos indikatorius emax. Pavyzdžiui, klaidų lygis = 0.01 gali reikšti, kad priklausomybę gali pažeisti 1% turimų kortelių nuo nagrinėjamos atributų rinkinio. Tai reiškia, kad 1000 įrašų ne daugiau kaip 10 kortelių gali pažeisti federalinį įstatymą. Mes apsvarstysime šiek tiek kitokią metriką, pagrįstą poromis skirtingomis lyginamų kortelių reikšmėmis. Dėl priklausomybės X → Y apie požiūrį r tai laikoma taip:
Apskaičiuokime klaidą Gydytojas → Pacientas iš aukščiau pateikto pavyzdžio. Turime dvi eilutes, kurių atributo reikšmės skiriasi Pacientas, bet sutampa Daktaras: [Gydytojas, pacientas] = (Robinas, Elisas) Ir [Gydytojas, pacientas] = (Robinas, Greimas). Vadovaudamiesi klaidos apibrėžimu, turime atsižvelgti į visas prieštaraujančias poras, o tai reiškia, kad jų bus dvi: (, ) ir jo atvirkštinė (, ). Pakeiskime jį į formulę ir gaukime:
Dabar pabandykime atsakyti į klausimą: „Kodėl visa tai? Tiesą sakant, federaliniai įstatymai skiriasi. Pirmasis tipas yra tos priklausomybės, kurias nustato administratorius duomenų bazės projektavimo etape. Paprastai jų yra nedaug, jie yra griežti, o pagrindinis pritaikymas yra duomenų normalizavimas ir reliacinės schemos projektavimas.
Antrasis tipas yra priklausomybės, kurios atspindi „paslėptus“ duomenis ir anksčiau nežinomus ryšius tarp atributų. Tai yra, apie tokias priklausomybes nebuvo galvojama projektuojant ir jos yra randamos esamam duomenų rinkiniui, todėl vėliau, remiantis daugybe nustatytų federalinių įstatymų, būtų galima padaryti bet kokias išvadas apie saugomą informaciją. Būtent su šiomis priklausomybėmis dirbame. Su jais susiduria visa duomenų gavybos sritis, naudodama įvairius paieškos būdus ir jų pagrindu sukurtus algoritmus. Išsiaiškinkime, kuo gali būti naudingos rastos funkcinės priklausomybės (tikslios ar apytikslės) bet kuriuose duomenyse.
Šiandien vienas iš pagrindinių priklausomybių pritaikymo būdų yra duomenų valymas. Tai apima „nešvarių duomenų“ identifikavimo ir tada taisymo procesų kūrimą. Ryškūs „nešvarių duomenų“ pavyzdžiai yra dublikatai, duomenų klaidos arba rašybos klaidos, trūkstamos reikšmės, pasenę duomenys, papildomi tarpai ir panašiai.
Duomenų klaidos pavyzdys:
Duomenų dublikatų pavyzdys:
Pavyzdžiui, turime lentelę ir federalinių įstatymų rinkinį, kurie turi būti vykdomi. Duomenų valymas šiuo atveju apima duomenų pakeitimą, kad federaliniai įstatymai taptų teisingi. Tokiu atveju modifikacijų skaičius turėtų būti minimalus (ši procedūra turi savo algoritmus, į kuriuos šiame straipsnyje mes nekreipiame dėmesio). Žemiau pateikiamas tokio duomenų transformavimo pavyzdys. Kairėje yra pradinis santykis, kuriame, akivaizdu, netenkinami būtini FL (vieno iš FL pažeidimo pavyzdys paryškintas raudonai). Dešinėje yra atnaujintas santykis, o žaliuose langeliuose rodomos pakeistos reikšmės. Po šios procedūros pradėtos palaikyti reikiamos priklausomybės.
Kita populiari programa yra duomenų bazės dizainas. Čia verta prisiminti normalias formas ir normalizavimą. Normalizavimas – tai santykio suderinimo su tam tikru reikalavimų rinkiniu procesas, kurių kiekvienas savaip apibrėžiamas normalia forma. Įvairių normalių formų reikalavimų neaprašysime (tai daroma bet kurioje pradedantiesiems skirto duomenų bazės kurso knygoje), tačiau tik pažymėsime, kad kiekviena iš jų savaip naudoja funkcinių priklausomybių sąvoką. Juk FL iš esmės yra vientisumo apribojimai, į kuriuos atsižvelgiama kuriant duomenų bazę (šios užduoties kontekste FL kartais vadinami superraktais).
Panagrinėkime jų taikymą keturioms įprastoms formoms toliau pateiktame paveikslėlyje. Prisiminkite, kad Boyce-Codd normalioji forma yra griežtesnė nei trečioji forma, bet ne tokia griežta nei ketvirtoji. Pastarojo kol kas nesvarstome, nes jo formulavimui reikia suprasti daugiareikšmes priklausomybes, kurios mums šiame straipsnyje neįdomios.
Kita sritis, kurioje priklausomybės buvo pritaikytos, yra funkcijų erdvės matmenų mažinimas atliekant tokias užduotis kaip naivaus Bayes klasifikatoriaus kūrimas, reikšmingų savybių nustatymas ir regresijos modelio perparametravimas. Originaliuose straipsniuose ši užduotis vadinama perteklinio ir funkcijų aktualumo nustatymu [5, 6], o ji sprendžiama aktyviai naudojant duomenų bazių sąvokas. Atsiradus tokiems darbams, galima teigti, kad šiandien yra paklausa sprendimų, leidžiančių į vieną įrankį sujungti duomenų bazę, analizę ir minėtų optimizavimo problemų įgyvendinimą [7, 8, 9].
Federalinių įstatymų paieškai duomenų rinkinyje yra daug algoritmų (ir šiuolaikinių, ir ne tokių modernių), tokius algoritmus galima suskirstyti į tris grupes:
- Algoritmai, naudojantys algebrinių gardelių perėjimą (gardelės apėjimo algoritmai)
- Algoritmai, pagrįsti sutartų verčių paieška (skirtumo ir susitarimo nustatymo algoritmai)
- Algoritmai, pagrįsti poriniais palyginimais (priklausomybės indukcijos algoritmai)
Žemiau esančioje lentelėje pateikiamas trumpas kiekvieno algoritmo tipo aprašymas:
Daugiau apie šią klasifikaciją galite perskaityti [4]. Žemiau pateikiami kiekvieno tipo algoritmų pavyzdžiai:
Šiuo metu atsiranda naujų algoritmų, kurie sujungia kelis funkcinių priklausomybių paieškos metodus. Tokių algoritmų pavyzdžiai yra Pyro [2] ir HyFD [3]. Jų darbo analizės tikimasi tolesniuose šios serijos straipsniuose. Šiame straipsnyje mes išnagrinėsime tik pagrindines sąvokas ir lemą, kurios būtinos norint suprasti priklausomybės aptikimo būdus.
Pradėkime nuo paprasto – skirtumo ir susitarimo rinkinio, naudojamo antrojo tipo algoritmuose. Skirtumų rinkinys yra rinkinys kortelių, kurios neturi tų pačių reikšmių, o sutartinis rinkinys, priešingai, yra kortelių, turinčių tas pačias reikšmes. Verta pažymėti, kad šiuo atveju mes svarstome tik kairę priklausomybės pusę.
Kita svarbi sąvoka, su kuria buvo susidurta aukščiau, yra algebrinė gardelė. Kadangi daugelis šiuolaikinių algoritmų veikia pagal šią koncepciją, turime žinoti, kas tai yra.
Norint įvesti gardelės sąvoką, būtina apibrėžti iš dalies sutvarkytą aibę (arba iš dalies sutvarkytą aibę, sutrumpintai vadinama pozetė).
2 apibrėžimas. Sakoma, kad aibė S yra iš dalies sutvarkyta dvejetainiu ryšiu ⩽, jei tenkinamos visos a, b, c ∈ S šios savybės:
- Refleksyvumas, tai yra a ⩽ a
- Antisimetrija, tai yra, jei a ⩽ b ir b ⩽ a, tai a = b
- Tranzityvumas, tai yra a ⩽ b ir b ⩽ c, iš to išplaukia, kad a ⩽ c
Toks ryšys vadinamas (laisvuoju) dalinės tvarkos ryšiu, o pati aibė – iš dalies sutvarkyta aibe. Formalus žymėjimas: ⟨S, ⩽⟩.
Kaip paprasčiausią iš dalies sutvarkytos aibės pavyzdį galime paimti visų natūraliųjų skaičių aibę N su įprastiniu eilės ryšiu ⩽. Nesunku patikrinti, ar tenkinamos visos būtinos aksiomos.
Prasmingesnis pavyzdys. Apsvarstykite visų poaibių {1, 2, 3} aibę, išdėstytą pagal įtraukimo ryšį ⊆. Iš tiesų, šis ryšys tenkina visas dalinės tvarkos sąlygas, todėl ⟨P ({1, 2, 3}), ⊆⟩ yra iš dalies sutvarkyta aibė. Žemiau esančiame paveikslėlyje parodyta šio rinkinio struktūra: jei vieną elementą galima pasiekti rodyklėmis į kitą elementą, tada jie yra eilės santykiai.
Mums reikės dar dviejų paprastų apibrėžimų iš matematikos srities – supremum ir infimum.
3 apibrėžimas. Tegu ⟨S, ⩽⟩ yra iš dalies sutvarkyta aibė, A ⊆ S. Viršutinė A riba yra elementas u ∈ S, kad ∀x ∈ S: x ⩽ u. Tegu U yra visų viršutinių S ribų aibė. Jei U yra mažiausias elementas, jis vadinamas supremumu ir žymimas sup A.
Panašiai įvedama tikslios apatinės ribos sąvoka.
4 apibrėžimas. Tegu ⟨S, ⩽⟩ yra iš dalies sutvarkyta aibė, A ⊆ S. A infimumas yra toks elementas l ∈ S, kad ∀x ∈ S: l ⩽ x. Tegu L yra visų apatinių S ribų aibė. Jei L yra didžiausias elementas, tai jis vadinamas infimum ir žymimas kaip inf A.
Kaip pavyzdį apsvarstykite aukščiau pateiktą iš dalies sutvarkytą aibę ⟨P ({1, 2, 3}), ⊆⟩ ir suraskite joje aukščiausią ir infimumą:
Dabar galime suformuluoti algebrinės gardelės apibrėžimą.
5 apibrėžimas. Tegu ⟨P,⩽⟩ yra iš dalies sutvarkyta aibė, kad kiekvienas dviejų elementų poaibis turi viršutinę ir apatinę ribas. Tada P vadinamas algebrine gardele. Šiuo atveju sup{x, y} rašoma kaip x ∨ y, o inf {x, y} kaip x ∧ y.
Patikrinkime, ar mūsų darbo pavyzdys ⟨P ({1, 2, 3}), ⊆⟩ yra gardelė. Iš tiesų, bet kuriam a, b ∈ P ({1, 2, 3}), a∨b = a∪b ir a∧b = a∩b. Pavyzdžiui, apsvarstykite aibes {1, 2} ir {1, 3} ir suraskite jų infimum ir supremum. Jei juos susikirsime, gausime aibę {1}, kuri bus infimum. Supremumą gauname juos sujungę - {1, 2, 3}.
Fizinių problemų identifikavimo algoritmuose paieškos erdvė dažnai vaizduojama gardelės pavidalu, kur vieno elemento aibės (skaitykite pirmąjį paieškos gardelės lygmenį, kur kairėje priklausomybių pusėje yra vienas atributas) reiškia kiekvieną atributą. pradinio santykio.
Pirma, nagrinėjame formos ∅ → priklausomybes Vienas atributas. Šis veiksmas leidžia nustatyti, kurie atributai yra pirminiai raktai (tokiems atributams determinantų nėra, todėl kairioji pusė tuščia). Be to, tokie algoritmai juda aukštyn išilgai gardelės. Verta pažymėti, kad negalima pereiti visos gardelės, tai yra, jei į įvestį perduodamas norimas maksimalus kairiosios pusės dydis, tada algoritmas neviršys tokio dydžio lygio.
Žemiau esančiame paveikslėlyje parodyta, kaip algebrinė gardelė gali būti naudojama FZ suradimo uždavinyje. Čia kiekvienas kraštas (X, XY) reiškia priklausomybę X → Y. Pavyzdžiui, mes įveikėme pirmą lygį ir žinome, kad priklausomybė išlieka A → B (parodysime tai kaip žalią ryšį tarp viršūnių A и B). Tai reiškia, kad toliau, kai judame aukštyn palei gardelę, galime netikrinti priklausomybės A, C → B, nes jis jau nebus minimalus. Panašiai mes netikrintume, jei priklausomybė būtų laikoma C → B.
Be to, paprastai visi šiuolaikiniai federalinių įstatymų paieškos algoritmai naudoja duomenų struktūrą, tokią kaip skaidinys (pirminiame šaltinyje - pašalintas skaidinys [1]). Formalus skaidinio apibrėžimas yra toks:
6 apibrėžimas. Tegu X ⊆ R yra santykio r atributų rinkinys. Klasteris yra rinkinys indeksų, esančių r kortelių, turinčių tą pačią X reikšmę, ty c(t) = {i|ti[X] = t[X]}. Skirsnis yra grupių rinkinys, išskyrus vienetinio ilgio grupes:
Paprastais žodžiais tariant, atributo skaidinys X yra sąrašų rinkinys, kuriame kiekviename sąraše yra eilučių numeriai su tomis pačiomis reikšmėmis X. Šiuolaikinėje literatūroje pertvaras vaizduojanti struktūra vadinama pozicijų sąrašo indeksu (PLI). Vieneto ilgio klasteriai neįtraukiami PLI glaudinimo tikslais, nes tai yra klasteriai, kuriuose yra tik įrašo numeris su unikalia reikšme, kurią visada bus lengva atpažinti.
Pažiūrėkime į pavyzdį. Grįžkime prie tos pačios lentelės su pacientais ir statykime pertvaras kolonoms Pacientas и Paulius (kairėje atsirado naujas stulpelis, kuriame pažymėti lentelės eilučių numeriai):
Be to, pagal apibrėžimą, stulpelio skaidinys Pacientas iš tikrųjų bus tuščias, nes atskiri klasteriai neįtraukiami į skaidinį.
Pertvaros gali būti gaunamos naudojant kelis atributus. Ir yra du būdai tai padaryti: eidami per lentelę, sukurkite skaidinį naudodami visus būtinus atributus iš karto arba sukurkite jį naudodami skaidinių sankirtos operaciją, naudodami atributų poaibį. Federalinio įstatymo paieškos algoritmai naudoja antrąją parinktį.
Paprastais žodžiais tariant, pavyzdžiui, gauti skaidinį pagal stulpelius ABC, galite paimti pertvaras AC и B (ar bet kurį kitą nejungtų poaibių rinkinį) ir susikerta juos vienas su kitu. Dviejų pertvarų susikirtimo operacija parenka didžiausio ilgio grupes, kurios yra bendros abiem pertvaroms.
Pažiūrėkime į pavyzdį:
Pirmuoju atveju gavome tuščią skaidinį. Jei atidžiai pažvelgsite į lentelę, iš tikrųjų nėra identiškų dviejų atributų verčių. Jei šiek tiek pakeisime lentelę (dėklas dešinėje), jau gausime ne tuščią sankryžą. Be to, 1 ir 2 eilutėse iš tikrųjų yra tos pačios atributų reikšmės Paulius и gydytojas.
Toliau mums reikės tokios sąvokos kaip skaidinio dydis. Formaliai:
Paprasčiau tariant, skaidinio dydis yra į skaidinį įtrauktų grupių skaičius (atminkite, kad atskiri klasteriai nėra įtraukti į skaidinį!):
Dabar galime apibrėžti vieną iš pagrindinių lemmų, kuri tam tikroms skaidiniams leidžia nustatyti, ar priklausomybė yra, ar ne:
1 lema. Priklausomybė A, B → C galioja tada ir tik tada
Pagal lemą, norint nustatyti, ar priklausomybė galioja, reikia atlikti keturis veiksmus:
- Apskaičiuokite kairiosios priklausomybės pusės skaidinį
- Apskaičiuokite dešiniosios priklausomybės pusės skaidinį
- Apskaičiuokite pirmojo ir antrojo žingsnių sandaugą
- Palyginkite pirmame ir trečiame žingsnyje gautus pertvarų dydžius
Žemiau pateikiamas pavyzdys, kaip patikrinti, ar priklausomybė galioja pagal šią lemą:
Šiame straipsnyje mes išnagrinėjome tokias sąvokas kaip funkcinė priklausomybė, apytikslė funkcinė priklausomybė, apžvelgėme, kur jos naudojamos, taip pat kokie egzistuoja fizinių funkcijų paieškos algoritmai. Taip pat išsamiai išnagrinėjome pagrindines, bet svarbias sąvokas, kurios aktyviai naudojamos šiuolaikiniuose federalinių įstatymų paieškos algoritmuose.
Nuorodos:
- Huhtala Y. ir kt. TANE: efektyvus algoritmas funkcinėms ir apytikslėms priklausomybėms aptikti //Kompiuterio žurnalas. – 1999. – T. 42. – Nr. 2. – 100-111 p.
- Kruse S., Naumann F. Efektyvus apytikslių priklausomybių atradimas // Proceedings of the VLDB Endowment. – 2018. – T. 11. – Nr. 7. – 759-772 p.
- Papenbrock T., Naumann F. Hibridinis požiūris į funkcinės priklausomybės atradimą // 2016 m. tarptautinės duomenų valdymo konferencijos pranešimų medžiaga. – ACM, 2016. – 821-833 p.
- Papenbrock T. ir kt. Funkcinės priklausomybės atradimas: septynių algoritmų eksperimentinis įvertinimas //Proceedings of the VLDB Endowment. – 2015. – T. 8. – Nr. 10. – 1082-1093 p.
- Kumar A. ir kt. Prisijungti ar neprisijungti?: Du kartus pagalvokite apie prisijungimus prieš pasirenkant funkciją //2016 m. tarptautinės duomenų valdymo konferencijos pranešimų medžiaga. – ACM, 2016. – 19-34 p.
- Abo Khamis M. ir kt. Mokymasis duomenų bazėje su retais tensoriais // 37-ojo ACM SIGMOD-SIGACT-SIGAI simpoziumo duomenų bazių sistemų principai pranešimų medžiaga. – ACM, 2018. – 325-340 p.
- Hellerstein J. M. ir kt. MADlib analizės biblioteka: arba MAD įgūdžiai, SQL //Proceedings of the VLDB Endowment. – 2012. – T. 5. – Nr. 12. – 1700-1711 p.
- Qin C., Rusu F. Spekuliatyvūs aproksimacijos teraskalės paskirstyto gradiento nusileidimo optimizavimui // Ketvirtojo duomenų analizės debesyje seminaro darbai. – ACM, 2015. – P. 1.
- Meng X. ir kt. Mllib: mašininis mokymasis apache kibirkštyje //Mašinų mokymosi tyrimų žurnalas. – 2016. – T. 17. – Nr. 1. – 1235-1241 p.
Straipsnio autoriai: , tyrėjas adresu , и , tyrėjas adresu
Šaltinis: www.habr.com