Në këtë artikull do të flasim për varësitë funksionale në bazat e të dhënave - cilat janë ato, ku përdoren dhe cilat algoritme ekzistojnë për t'i gjetur ato.
Ne do të shqyrtojmë varësitë funksionale në kontekstin e bazave të të dhënave relacionale. Për ta thënë shumë përafërsisht, në baza të tilla të dhënash informacioni ruhet në formën e tabelave. Më pas, ne përdorim koncepte të përafërta që nuk janë të këmbyeshme në teorinë e rreptë relacionale: ne do ta quajmë vetë tabelën një relacion, kolonat - atribute (bashkësia e tyre - një skemë relacioni) dhe grupi i vlerave të rreshtit në një nëngrup atributesh. - një tufë.
Për shembull, në tabelën e mësipërme, (Benson, M, M organ) është një tufë atributesh (Pacient, Paul, Doktor).
Më formalisht, kjo shkruhet si më poshtë: [Pacienti, Gjinia, Doktori] = = (Benson, M, M organ).
Tani mund të prezantojmë konceptin e varësisë funksionale (FD):
Përkufizimi 1. Lidhja R plotëson ligjin federal X → Y (ku X, Y ⊆ R) nëse dhe vetëm nëse për ndonjë tuple , ∈ R vlen: nëse [X] = [X], atëherë [Y] = [Y]. Në këtë rast, themi se X (përcaktori, ose grupi përcaktues i atributeve) përcakton funksionalisht Y (bashkësinë e varur).
Me fjalë të tjera, prania e një ligji federal X → Y do të thotë se nëse kemi dy tupa në R dhe ato përputhen në atribute X, atëherë ato do të përkojnë në atribute Y.
Dhe tani, në rregull. Le të shohim atributet pacient и Пол për të cilat duam të zbulojmë nëse ka apo jo varësi ndërmjet tyre. Për një grup të tillë atributesh, varësitë e mëposhtme mund të ekzistojnë:
- Pacienti → Gjinia
- Gjinia → Pacient
Siç përkufizohet më sipër, në mënyrë që varësia e parë të mbajë, çdo vlerë unike të kolonës pacient vetëm një vlerë kolone duhet të përputhet Пол. Dhe për shembullin e tabelës ky është me të vërtetë rasti. Sidoqoftë, kjo nuk funksionon në drejtim të kundërt, domethënë, varësia e dytë nuk është e kënaqur, dhe atributi Пол nuk është përcaktues për Pacienti. Në mënyrë të ngjashme, nëse marrim varësinë Mjeku → Pacient, ju mund të shihni se është shkelur, pasi vlera Gushëkuq ky atribut ka disa kuptime të ndryshme - Ellis dhe Graham.
Kështu, varësitë funksionale bëjnë të mundur përcaktimin e marrëdhënieve ekzistuese midis grupeve të atributeve të tabelës. Që këtu e tutje do të shqyrtojmë lidhjet më interesante, ose më mirë të tilla X → Yçfarë janë ato:
- jo e parëndësishme, domethënë, ana e djathtë e varësisë nuk është një nëngrup i së majtës (Y ̸⊆ X);
- minimale, domethënë nuk ka një varësi të tillë Z → YQë Z ⊂ X.
Varësitë e konsideruara deri në këtë pikë ishin të rrepta, domethënë nuk parashikonin asnjë shkelje në tavolinë, por përveç tyre ka edhe nga ato që lejojnë disa mospërputhje midis vlerave të tupave. Varësi të tilla vendosen në një klasë të veçantë, të quajtur të përafërt, dhe lejohen të shkelen për një numër të caktuar tuplesh. Kjo shumë rregullohet nga treguesi maksimal i gabimit emax. Për shembull, shkalla e gabimit = 0.01 mund të nënkuptojë që varësia mund të shkelet me 1% të tupleve të disponueshëm në grupin e konsideruar të atributeve. Kjo do të thotë, për 1000 regjistrime, maksimumi 10 tuple mund të shkelin Ligjin Federal. Ne do të shqyrtojmë një metrikë paksa të ndryshme, bazuar në vlerat e ndryshme në çift të tupave që krahasohen. Për varësinë X → Y mbi qëndrimin r konsiderohet si kjo:
Le të llogarisim gabimin për Mjeku → Pacient nga shembulli i mësipërm. Kemi dy tuple, vlerat e të cilave ndryshojnë në atribut pacient, por përkojnë më Doktor: [Doktor, pacient] = (Robin, Ellis) Dhe [Doktor, pacient] = (Robin, Graham). Pas përcaktimit të një gabimi, ne duhet të marrim parasysh të gjitha çiftet konfliktuale, që do të thotë se do të jenë dy prej tyre: (, ) dhe anasjellta e saj (, ). Le ta zëvendësojmë atë në formulë dhe të marrim:
Tani le të përpiqemi t'i përgjigjemi pyetjes: "Pse është e gjitha për?" Në fakt, ligjet federale janë të ndryshme. Lloji i parë janë ato varësi që përcaktohen nga administratori në fazën e projektimit të bazës së të dhënave. Zakonisht janë të pakët në numër, të rreptë dhe aplikimi kryesor është normalizimi i të dhënave dhe dizajnimi i skemave relacionale.
Lloji i dytë janë varësitë, të cilat përfaqësojnë të dhëna "të fshehura" dhe marrëdhënie të panjohura më parë midis atributeve. Kjo do të thotë, varësi të tilla nuk u menduan në kohën e projektimit dhe ato gjenden për grupin ekzistues të të dhënave, në mënyrë që më vonë, bazuar në shumë ligje federale të identifikuara, të mund të nxirren çdo përfundim për informacionin e ruajtur. Janë pikërisht këto varësi me të cilat ne punojmë. Ato trajtohen nga një fushë e tërë e minierave të të dhënave me teknika të ndryshme kërkimi dhe algoritme të ndërtuara mbi bazën e tyre. Le të kuptojmë se si mund të jenë të dobishme varësitë funksionale të gjetura (të sakta ose të përafërta) në çdo të dhënë.
Sot, një nga aplikimet kryesore të varësive është pastrimi i të dhënave. Ai përfshin zhvillimin e proceseve për identifikimin e "të dhënave të pista" dhe më pas korrigjimin e tyre. Shembuj të spikatur të "të dhënave të pista" janë dublikatat, gabimet e të dhënave ose gabimet e shtypit, vlerat që mungojnë, të dhënat e vjetruara, hapësirat shtesë dhe të ngjashme.
Shembull i një gabimi të të dhënave:
Shembull i dublikatave në të dhëna:
Për shembull, ne kemi një tabelë dhe një grup ligjesh federale që duhet të ekzekutohen. Pastrimi i të dhënave në këtë rast përfshin ndryshimin e të dhënave në mënyrë që ligjet federale të bëhen të sakta. Në këtë rast, numri i modifikimeve duhet të jetë minimal (kjo procedurë ka algoritmet e veta, në të cilat nuk do të fokusohemi në këtë artikull). Më poshtë është një shembull i një transformimi të tillë të të dhënave. Në të majtë është marrëdhënia origjinale, në të cilën, padyshim, FL-të e nevojshme nuk plotësohen (një shembull i shkeljes së një prej FL-ve është theksuar me të kuqe). Në të djathtë është marrëdhënia e përditësuar, me qelizat jeshile që tregojnë vlerat e ndryshuara. Pas kësaj procedure filluan të ruheshin varësitë e nevojshme.
Një tjetër aplikacion i njohur është dizajni i bazës së të dhënave. Këtu ia vlen të kujtojmë format normale dhe normalizimin. Normalizimi është procesi i sjelljes së një marrëdhënieje në përputhje me një grup të caktuar kërkesash, secila prej të cilave përcaktohet nga forma normale në mënyrën e vet. Ne nuk do të përshkruajmë kërkesat e formave të ndryshme normale (kjo bëhet në çdo libër në një kurs bazë të dhënash për fillestarët), por do të vërejmë vetëm se secili prej tyre përdor konceptin e varësive funksionale në mënyrën e vet. Në fund të fundit, FL-të janë në thelb kufizime të integritetit që merren parasysh kur hartohet një bazë të dhënash (në kontekstin e kësaj detyre, FL-të quhen ndonjëherë superçelës).
Le të shqyrtojmë aplikimin e tyre për katër format normale në foton më poshtë. Kujtojmë se forma normale Boyce-Codd është më strikte se forma e tretë, por më pak e rreptë se e katërta. Këtë të fundit nuk po e konsiderojmë tani për tani, pasi formulimi i tij kërkon një kuptim të varësive me shumë vlera, të cilat nuk janë interesante për ne në këtë artikull.
Një fushë tjetër në të cilën varësitë kanë gjetur aplikimin e tyre është zvogëlimi i dimensionalitetit të hapësirës së veçorive në detyra të tilla si ndërtimi i një klasifikuesi naiv të Bayes, identifikimi i veçorive të rëndësishme dhe riparametizimi i një modeli regresioni. Në artikujt origjinal, kjo detyrë quhet përcaktimi i relevancës së tepërt dhe të veçorive [5, 6] dhe zgjidhet me përdorimin aktiv të koncepteve të bazës së të dhënave. Me ardhjen e veprave të tilla, mund të themi se sot ka një kërkesë për zgjidhje që na lejojnë të kombinojmë bazën e të dhënave, analitikën dhe zbatimin e problemeve të mësipërme të optimizimit në një mjet [7, 8, 9].
Ka shumë algoritme (të dyja moderne dhe jo aq moderne) për kërkimin e ligjeve federale në një grup të dhënash. Algoritme të tilla mund të ndahen në tre grupe:
- Algoritmet që përdorin kalimin e rrjetave algjebrike (Algoritmet e përshkimit të rrjetave)
- Algoritme të bazuara në kërkimin e vlerave të dakorduara (Algoritme të vendosura me dallime dhe marrëveshje)
- Algoritme të bazuara në krahasime në çift (Algoritmet e induksionit të varësisë)
Një përshkrim i shkurtër i secilit lloj algoritmi është paraqitur në tabelën e mëposhtme:
Ju mund të lexoni më shumë rreth këtij klasifikimi [4]. Më poshtë janë shembuj të algoritmeve për secilin lloj:
Aktualisht, po shfaqen algoritme të reja që kombinojnë disa qasje për gjetjen e varësive funksionale. Shembuj të algoritmeve të tilla janë Pyro [2] dhe HyFD [3]. Një analizë e punës së tyre pritet në artikujt vijues të kësaj serie. Në këtë artikull ne do të shqyrtojmë vetëm konceptet bazë dhe lemat që janë të nevojshme për të kuptuar teknikat e zbulimit të varësisë.
Le të fillojmë me një të thjeshtë - grup dallimi dhe dakordimi, i përdorur në llojin e dytë të algoritmeve. Bashkësia e diferencës është një grup tuplesh që nuk kanë të njëjtat vlera, ndërsa bashkësia e dakordësimit, përkundrazi, është grupe që kanë të njëjtat vlera. Vlen të theksohet se në këtë rast kemi parasysh vetëm anën e majtë të varësisë.
Një koncept tjetër i rëndësishëm që u ndesh më sipër është rrjeta algjebrike. Meqenëse shumë algoritme moderne veprojnë mbi këtë koncept, ne duhet të kemi një ide se çfarë është.
Për të prezantuar konceptin e një grilë, është e nevojshme të përkufizohet një grup pjesërisht i renditur (ose grup i renditur pjesërisht, i shkurtuar si poset).
Përkufizimi 2. Një grup S thuhet se është pjesërisht i renditur nga relacioni binare ⩽ nëse për të gjitha a, b, c ∈ S plotësohen vetitë e mëposhtme:
- Refleksiviteti, domethënë a ⩽ a
- Antisimetria, domethënë nëse a ⩽ b dhe b ⩽ a, atëherë a = b
- Transitiviteti, domethënë për a ⩽ b dhe b ⩽ c rezulton se a ⩽ c
Një relacion i tillë quhet relacion i rendit të pjesshëm (të lirshëm), dhe vetë bashkësia quhet bashkësi pjesërisht e renditur. Shënimi zyrtar: ⟨S, ⩽⟩.
Si shembulli më i thjeshtë i një bashkësie të renditur pjesërisht, mund të marrim bashkësinë e të gjithë numrave natyrorë N me relacionin e zakonshëm të rendit ⩽. Është e lehtë të verifikohet që të gjitha aksiomat e nevojshme janë përmbushur.
Një shembull më kuptimplotë. Merrni parasysh bashkësinë e të gjitha nënbashkësive {1, 2, 3}, të renditura nga relacioni i përfshirjes ⊆. Në të vërtetë, kjo lidhje plotëson të gjitha kushtet e rendit të pjesshëm, kështu që ⟨P ({1, 2, 3}), ⊆⟩ është një grup pjesërisht i renditur. Figura më poshtë tregon strukturën e këtij grupi: nëse një element mund të arrihet me shigjeta në një element tjetër, atëherë ata janë në një marrëdhënie rendi.
Do të na duhen edhe dy përkufizime të thjeshta nga fusha e matematikës - supremum dhe infimum.
Përkufizimi 3. Le të jetë ⟨S, ⩽⟩ një bashkësi e renditur pjesërisht, A ⊆ S. Kufiri i sipërm i A është një element u ∈ S i tillë që ∀x ∈ S: x ⩽ u. Le të jetë U bashkësia e të gjithë kufijve të sipërm të S. Nëse ka një element më të vogël në U, atëherë ai quhet supremum dhe shënohet sup A.
Koncepti i një kufiri të saktë të poshtëm prezantohet në mënyrë të ngjashme.
Përkufizimi 4. Le të jetë ⟨S, ⩽⟩ një bashkësi pjesërisht e renditur, A ⊆ S. Infimumi i A është një element l ∈ S i tillë që ∀x ∈ S: l ⩽ x. Le të jetë L bashkësia e të gjithë kufijve të poshtëm të S. Nëse ka një element më të madh në L, atëherë ai quhet infimum dhe shënohet si inf A.
Merrni si shembull grupin e renditur pjesërisht të mësipërm ⟨P ({1, 2, 3}), ⊆⟩ dhe gjeni supremum dhe infimum në të:
Tani mund të formulojmë përkufizimin e një rrjete algjebrike.
Përkufizimi 5. Le të jetë ⟨P,⩽⟩ një bashkësi e renditur pjesërisht e tillë që çdo nëngrup me dy elementë të ketë një kufi të sipërm dhe të poshtëm. Atëherë P quhet një rrjetë algjebrike. Në këtë rast, sup{x, y} shkruhet si x ∨ y, dhe inf {x, y} si x ∧ y.
Le të kontrollojmë që shembulli ynë i punës ⟨P ({1, 2, 3}), ⊆⟩ është një grilë. Në të vërtetë, për çdo a, b ∈ P ({1, 2, 3}), a∨b = a∪b dhe a∧b = a∩b. Për shembull, merrni parasysh grupet {1, 2} dhe {1, 3} dhe gjeni infimum dhe supremum të tyre. Nëse i kryqëzojmë, do të marrim grupin {1}, i cili do të jetë infimum. Ne marrim supremin duke i kombinuar - {1, 2, 3}.
Në algoritmet për identifikimin e problemeve fizike, hapësira e kërkimit shpesh paraqitet në formën e një grilë, ku grupet e një elementi (lexoni nivelin e parë të rrjetës së kërkimit, ku ana e majtë e varësive përbëhet nga një atribut) përfaqësojnë çdo atribut. të relacionit origjinal.
Së pari, ne konsiderojmë varësitë e formës ∅ → Atribut i vetëm. Ky hap ju lejon të përcaktoni se cilat atribute janë çelësat kryesorë (për atribute të tilla nuk ka përcaktues, dhe për këtë arsye ana e majtë është bosh). Më tej, algoritme të tilla lëvizin lart përgjatë grilës. Vlen të theksohet se jo e gjithë rrjeta mund të përshkohet, domethënë, nëse madhësia maksimale e dëshiruar e anës së majtë kalohet në hyrje, atëherë algoritmi nuk do të shkojë më tej se një nivel me atë madhësi.
Figura më poshtë tregon se si një rrjetë algjebrike mund të përdoret në problemin e gjetjes së një FZ. Këtu çdo skaj (X, XY) përfaqëson një varësi X → Y. Për shembull, ne kemi kaluar nivelin e parë dhe e dimë që varësia ruhet A → B (ne do ta shfaqim këtë si një lidhje jeshile midis kulmeve A и B). Kjo do të thotë që më tej, kur lëvizim lart përgjatë grilës, mund të mos kontrollojmë varësinë A, C → B, sepse nuk do të jetë më minimale. Në mënyrë të ngjashme, ne nuk do ta kontrollonim nëse varësia do të mbahej C → B.
Për më tepër, si rregull, të gjithë algoritmet moderne për kërkimin e ligjeve federale përdorin një strukturë të dhënash siç është një ndarje (në burimin origjinal - ndarje e zhveshur [1]). Përkufizimi zyrtar i një ndarjeje është si më poshtë:
Përkufizimi 6. Le të jetë X ⊆ R një bashkësi atributesh për relacionin r. Një grup është një grup indeksesh të tupave në r që kanë të njëjtën vlerë për X, domethënë c(t) = {i|ti[X] = t[X]}. Një ndarje është një grup grupimesh, duke përjashtuar grupimet me gjatësi njësi:
Me fjalë të thjeshta, një ndarje për një atribut X është një grup listash, ku çdo listë përmban numra rreshtash me të njëjtat vlera për X. Në literaturën moderne, struktura që përfaqëson ndarjet quhet indeksi i listës së pozicioneve (PLI). Grupet me gjatësi njësi përjashtohen për qëllime të kompresimit PLI sepse ato janë grupe që përmbajnë vetëm një numër rekord me një vlerë unike që do të jetë gjithmonë e lehtë për t'u identifikuar.
Le të shohim një shembull. Le të kthehemi në të njëjtën tabelë me pacientët dhe të ndërtojmë ndarje për kolonat pacient и Пол (një kolonë e re është shfaqur në të majtë, në të cilën janë shënuar numrat e rreshtave të tabelës):
Për më tepër, sipas përkufizimit, ndarja për kolonën pacient në fakt do të jetë bosh, pasi grupet e vetme janë të përjashtuara nga ndarja.
Ndarjet mund të merren nga disa atribute. Dhe ka dy mënyra për ta bërë këtë: duke kaluar nëpër tabelë, ndërtoni një ndarje duke përdorur të gjitha atributet e nevojshme menjëherë, ose ndërtoni atë duke përdorur funksionin e kryqëzimit të ndarjeve duke përdorur një nëngrup atributesh. Algoritmet e kërkimit të ligjit federal përdorin opsionin e dytë.
Me fjalë të thjeshta, për të marrë, për shembull, një ndarje sipas kolonave ABC, ju mund të merrni ndarje për AC и B (ose ndonjë grup tjetër nënbashkësish jo të përbashkëta) dhe ndërpritini ato me njëra-tjetrën. Operacioni i kryqëzimit të dy ndarjeve zgjedh grupe me gjatësinë më të madhe që janë të përbashkëta për të dy ndarjet.
Le të shohim një shembull:
Në rastin e parë, ne morëm një ndarje të zbrazët. Nëse shikoni nga afër tabelën, atëherë me të vërtetë, nuk ka vlera identike për dy atributet. Nëse modifikojmë pak tabelën (rasti në të djathtë), tashmë do të marrim një kryqëzim jo bosh. Për më tepër, rreshtat 1 dhe 2 përmbajnë në të vërtetë të njëjtat vlera për atributet Пол и Mjek.
Tjetra, do të na duhet një koncept i tillë si madhësia e ndarjes. Formalisht:
E thënë thjesht, madhësia e ndarjes është numri i grupimeve të përfshira në ndarje (mos harroni se grupimet e vetme nuk përfshihen në ndarje!):
Tani mund të përcaktojmë një nga lemat kryesore, e cila për ndarjet e dhëna na lejon të përcaktojmë nëse një varësi mbahet apo jo:
Lema 1. Varësia A, B → C vlen nëse dhe vetëm nëse
Sipas lemës, për të përcaktuar nëse ekziston një varësi, duhet të kryhen katër hapa:
- Llogaritni ndarjen për anën e majtë të varësisë
- Llogaritni ndarjen për anën e djathtë të varësisë
- Llogaritni produktin e hapit të parë dhe të dytë
- Krahasoni madhësitë e ndarjeve të marra në hapin e parë dhe të tretë
Më poshtë është një shembull për të kontrolluar nëse varësia qëndron sipas kësaj leme:
Në këtë artikull, ne shqyrtuam koncepte të tilla si varësia funksionale, varësia e përafërt funksionale, shikuam se ku përdoren ato, si dhe cilat algoritme për kërkimin e funksioneve fizike ekzistojnë. Ne shqyrtuam gjithashtu në detaje konceptet themelore, por të rëndësishme që përdoren në mënyrë aktive në algoritmet moderne për kërkimin e ligjeve federale.
Referencat:
- Huhtala Y. et al. TANE: Një algoritëm efikas për zbulimin e varësive funksionale dhe të përafërta //Ditari i kompjuterit. – 1999. – T. 42. – Nr. 2. – fq 100-111.
- Kruse S., Naumann F. Zbulimi efikas i varësive të përafërta // Proceedings of the VLDB Endowment. – 2018. – T. 11. – Nr. 7. – fq 759-772.
- Papenbrock T., Naumann F. Një qasje hibride për zbulimin e varësisë funksionale //Proceset e Konferencës Ndërkombëtare 2016 mbi Menaxhimin e të Dhënave. – ACM, 2016. – fq 821-833.
- Papenbrock T. et al. Zbulimi i varësisë funksionale: Një vlerësim eksperimental i shtatë algoritmeve //Proceedings of the VLDB Endowment. – 2015. – T. 8. – Nr. 10. – fq 1082-1093.
- Kumar A. et al. Të bashkohesh apo të mos bashkohesh?: Duke menduar dy herë për bashkimet përpara përzgjedhjes së funksioneve //Proceset e Konferencës Ndërkombëtare 2016 mbi Menaxhimin e të Dhënave. – ACM, 2016. – fq 19-34.
- Abo Khamis M. et al. Mësimi në bazën e të dhënave me tensorë të rrallë // Procedurat e Simpoziumit të 37-të ACM SIGMOD-SIGACT-SIGAI mbi Parimet e Sistemeve të Bazave të të Dhënave. – ACM, 2018. – fq 325-340.
- Hellerstein JM et al. Biblioteka e analitikës MADlib: ose aftësitë MAD, SQL //Proceedings of the VLDB Endowment. – 2012. – T. 5. – Nr. 12. – fq 1700-1711.
- Qin C., Rusu F. Përafrime spekulative për optimizimin e zbritjes së gradientit të shpërndarë në shkallë tera //Proceset e seminarit të katërt mbi analitikën e të dhënave në renë kompjuterike. – ACM, 2015. – F. 1.
- Meng X. et al. Mllib: Mësimi i makinerisë në shkëndijë apache //The Journal of Machine Learning Research. – 2016. – T. 17. – Nr. 1. – fq 1235-1241.
Autorët e artikullit: , studiues në , и , studiues në
Burimi: www.habr.com