În acest articol vom vorbi despre dependențele funcționale din baze de date - ce sunt acestea, unde sunt folosite și ce algoritmi există pentru a le găsi.
Vom lua în considerare dependențele funcționale în contextul bazelor de date relaționale. Pentru a spune foarte aproximativ, în astfel de baze de date informațiile sunt stocate sub formă de tabele. În continuare, folosim concepte aproximative care nu sunt interschimbabile în teoria relațională strictă: vom numi tabelul însuși o relație, coloanele - atribute (setul lor - o schemă de relație) și setul de valori ale rândurilor pe un subset de atribute - un tuplu.
De exemplu, în tabelul de mai sus, (Benson, M, M organ) este un tuplu de atribute (Pacient, Paul, Doctor).
Mai formal, aceasta este scrisă după cum urmează: [Pacient, Sex, Doctor] = (Benson, M, M organ).
Acum putem introduce conceptul de dependență funcțională (FD):
Definiția 1. Relația R satisface legea federală X → Y (unde X, Y ⊆ R) dacă și numai dacă pentru orice tuplu , ∈ R ține: dacă [X] = [X], atunci [Y] = [Y]. În acest caz, spunem că X (determinantul sau setul definitoriu de atribute) determină funcțional Y (mulțimea dependentă).
Cu alte cuvinte, prezența unei legi federale X → Y înseamnă că dacă avem două tupluri înăuntru R și se potrivesc în atribute X, atunci ele vor coincide în atribute Y.
Și acum, în ordine. Să ne uităm la atribute Rabdator и Paul pentru care vrem să aflăm dacă între ele există sau nu dependențe. Pentru un astfel de set de atribute, pot exista următoarele dependențe:
- Pacient → Sex
- Sex → Pacient
După cum s-a definit mai sus, pentru ca prima dependență să fie păstrată, fiecare valoare de coloană unică Rabdator o singură valoare de coloană trebuie să se potrivească Paul. Și pentru tabelul exemplu, acesta este într-adevăr cazul. Cu toate acestea, acest lucru nu funcționează în direcția opusă, adică a doua dependență nu este satisfăcută, iar atributul Paul nu este un determinant pentru Rabdator. În mod similar, dacă luăm dependența Doctor → Pacient, puteți vedea că este încălcat, deoarece valoarea prihor acest atribut are mai multe semnificații diferite - Ellis și Graham.
Astfel, dependențele funcționale fac posibilă determinarea relațiilor existente între seturile de atribute de tabel. De aici încolo vom lua în considerare cele mai interesante conexiuni, sau mai bine zis așa X → Yce sunt ei:
- non-trivial, adică partea dreaptă a dependenței nu este un subset al stângi (Y ̸⊆ X);
- minimă, adică nu există o astfel de dependență Z → YCă Z ⊂ X.
Dependențe considerate până în acest moment au fost stricte, adică nu au prevăzut nicio încălcare pe tabel, dar pe lângă acestea, există și cele care permit o anumită inconsecvență între valorile tuplurilor. Astfel de dependențe sunt plasate într-o clasă separată, numită aproximativă și pot fi încălcate pentru un anumit număr de tupluri. Această sumă este reglementată de indicatorul de eroare maximă emax. De exemplu, rata de eroare = 0.01 poate însemna că dependența poate fi încălcată de 1% din tuplurile disponibile pe setul de atribute considerat. Adică, pentru 1000 de înregistrări, maximum 10 tupluri pot încălca Legea Federală. Vom lua în considerare o metrică ușor diferită, bazată pe valori diferite pe perechi ale tuplurilor comparate. Pentru dependență X → Y pe atitudine r este considerat astfel:
Să calculăm eroarea pentru Doctor → Pacient din exemplul de mai sus. Avem două tupluri ale căror valori diferă în funcție de atribut Rabdator, dar coincid pe Doctor: [Doctor, pacient] = (Robin, Ellis) Și [Doctor, pacient] = (Robin, Graham). După definirea unei erori, trebuie să luăm în considerare toate perechile conflictuale, ceea ce înseamnă că vor fi două dintre ele: (, ) și inversarea acesteia (, ). Să o înlocuim în formulă și să obținem:
Acum să încercăm să răspundem la întrebarea: „De ce este totul pentru?” De fapt, legile federale sunt diferite. Primul tip este acele dependențe care sunt determinate de administrator în etapa de proiectare a bazei de date. Ele sunt de obicei puține la număr, stricte, iar aplicația principală este normalizarea datelor și proiectarea schemelor relaționale.
Al doilea tip este dependențele, care reprezintă date „ascunse” și relații necunoscute anterior între atribute. Adică, astfel de dependențe nu au fost gândite la momentul proiectării și se găsesc pentru setul de date existent, astfel încât ulterior, pe baza numeroaselor legi federale identificate, să se poată trage orice concluzii despre informațiile stocate. Tocmai aceste dependențe sunt cu care lucrăm. Acestea sunt tratate de un întreg domeniu de data mining cu diverse tehnici de căutare și algoritmi construiți pe baza lor. Să ne dăm seama cum pot fi utile dependențele funcționale găsite (exacte sau aproximative) în orice date.
Astăzi, una dintre principalele aplicații ale dependențelor este curățarea datelor. Aceasta implică dezvoltarea proceselor de identificare a „datelor murdare” și apoi corectarea acestora. Exemple proeminente de „date murdare” sunt duplicatele, erorile de date sau greșelile de scriere, valorile lipsă, datele învechite, spațiile suplimentare și altele asemenea.
Exemplu de eroare de date:
Exemplu de duplicate în date:
De exemplu, avem un tabel și un set de legi federale care trebuie executate. Curățarea datelor în acest caz implică modificarea datelor astfel încât legile federale să devină corecte. În acest caz, numărul de modificări ar trebui să fie minim (această procedură are proprii algoritmi, pe care nu ne vom concentra în acest articol). Mai jos este un exemplu de astfel de transformare a datelor. În stânga este relația originală, în care, evident, nu sunt îndeplinite FL-urile necesare (un exemplu de încălcare a unuia dintre FL-uri este evidențiat cu roșu). În dreapta este relația actualizată, cu celulele verzi afișând valorile modificate. După această procedură, au început să fie menținute dependențele necesare.
O altă aplicație populară este proiectarea bazelor de date. Aici merită să amintim formele normale și normalizarea. Normalizarea este procesul de aducere a unei relații în conformitate cu un anumit set de cerințe, fiecare dintre acestea fiind definită de forma normală în felul său. Nu vom descrie cerințele diferitelor forme normale (acest lucru se face în orice carte despre un curs de bază de date pentru începători), dar vom observa doar că fiecare dintre ele utilizează conceptul de dependențe funcționale în felul său. La urma urmei, FL-urile sunt în mod inerent constrângeri de integritate care sunt luate în considerare la proiectarea unei baze de date (în contextul acestei sarcini, FL-urile sunt uneori numite superchei).
Să luăm în considerare aplicarea lor pentru cele patru forme normale din imaginea de mai jos. Amintiți-vă că forma normală Boyce-Codd este mai strictă decât a treia formă, dar mai puțin strictă decât a patra. Nu o luăm în considerare deocamdată, deoarece formularea sa necesită o înțelegere a dependențelor cu mai multe valori, care nu sunt interesante pentru noi în acest articol.
Un alt domeniu în care dependențele și-au găsit aplicația este reducerea dimensionalității spațiului de caracteristici în sarcini precum construirea unui clasificator Bayes naiv, identificarea caracteristicilor semnificative și reparametrizarea unui model de regresie. În articolele originale, această sarcină se numește determinarea relevanței redundante și a caracteristicilor [5, 6] și este rezolvată cu utilizarea activă a conceptelor bazei de date. Odată cu apariția unor astfel de lucrări, putem spune că astăzi există o cerere pentru soluții care ne permit să combinăm baza de date, analiza și implementarea problemelor de optimizare de mai sus într-un singur instrument [7, 8, 9].
Există mulți algoritmi (atât moderni, cât și mai puțin moderni) pentru căutarea legilor federale într-un set de date. Astfel de algoritmi pot fi împărțiți în trei grupuri:
- Algoritmi care utilizează traversarea rețelelor algebrice (algoritmi de traversare a rețelelor)
- Algoritmi bazați pe căutarea valorilor convenite (algoritmi de setare de diferență și de acord)
- Algoritmi bazați pe comparații pe perechi (algoritmi de inducție a dependenței)
O scurtă descriere a fiecărui tip de algoritm este prezentată în tabelul de mai jos:
Puteți citi mai multe despre această clasificare [4]. Mai jos sunt exemple de algoritmi pentru fiecare tip:
În prezent, apar noi algoritmi care combină mai multe abordări pentru găsirea dependențelor funcționale. Exemple de astfel de algoritmi sunt Pyro [2] și HyFD [3]. O analiză a muncii lor este așteptată în următoarele articole din această serie. În acest articol vom examina doar conceptele de bază și lema care sunt necesare pentru a înțelege tehnicile de detectare a dependenței.
Să începem cu unul simplu - set de diferențe și de acord, folosit în al doilea tip de algoritmi. Setul de diferențe este un set de tupluri care nu au aceleași valori, în timp ce setul de acord, dimpotrivă, este tupluri care au aceleași valori. Este de remarcat faptul că în acest caz luăm în considerare doar partea stângă a dependenței.
Un alt concept important care a fost întâlnit mai sus este rețeaua algebrică. Deoarece mulți algoritmi moderni operează pe acest concept, trebuie să avem o idee despre ce este acesta.
Pentru a introduce conceptul de rețea, este necesar să se definească o mulțime parțial ordonată (sau o mulțime parțial ordonată, prescurtată ca poset).
Definiția 2. Se spune că o mulțime S este parțial ordonată după relația binară ⩽ dacă pentru toate a, b, c ∈ S sunt îndeplinite următoarele proprietăți:
- Reflexivitate, adică a ⩽ a
- Antisimetrie, adică dacă a ⩽ b și b ⩽ a, atunci a = b
- Tranzitivitatea, adică pentru a ⩽ b și b ⩽ c rezultă că a ⩽ c
O astfel de relație se numește relație de ordine parțială (laxă), iar mulțimea în sine este numită mulțime parțial ordonată. Notație formală: ⟨S, ⩽⟩.
Ca exemplu cel mai simplu de mulțime parțial ordonată, putem lua mulțimea tuturor numerelor naturale N cu relația obișnuită de ordine ⩽. Este ușor de verificat dacă toate axiomele necesare sunt îndeplinite.
Un exemplu mai semnificativ. Se consideră mulțimea tuturor submulților {1, 2, 3}, ordonate după relația de includere ⊆. Într-adevăr, această relație satisface toate condițiile de ordine parțială, deci ⟨P ({1, 2, 3}), ⊆⟩ este o mulțime parțial ordonată. Figura de mai jos arată structura acestui set: dacă la un element se poate ajunge cu săgeți la un alt element, atunci ele sunt într-o relație de ordine.
Vom avea nevoie de încă două definiții simple din domeniul matematicii - supremum și infimum.
Definiția 3. Fie ⟨S, ⩽⟩ o mulțime parțial ordonată, A ⊆ S. Limita superioară a lui A este un element u ∈ S astfel încât ∀x ∈ S: x ⩽ u. Fie U mulțimea tuturor limitelor superioare ale lui S. Dacă există un element cel mai mic în U, atunci se numește supremum și se notează sup A.
Conceptul de limită inferioară exactă este introdus în mod similar.
Definiția 4. Fie ⟨S, ⩽⟩ o mulțime parțial ordonată, A ⊆ S. Infimumul lui A este un element l ∈ S astfel încât ∀x ∈ S: l ⩽ x. Fie L mulțimea tuturor limitelor inferioare ale lui S. Dacă există un element cel mai mare în L, atunci se numește infim și se notează ca inf A.
Luați în considerare ca exemplu mulțimea parțial ordonată de mai sus ⟨P ({1, 2, 3}), ⊆⟩ și găsiți supremul și infimumul în ea:
Acum putem formula definiția unei rețele algebrice.
Definiția 5. Fie ⟨P,⩽⟩ o mulțime parțial ordonată astfel încât fiecare submulțime de două elemente să aibă o limită superioară și inferioară. Atunci P se numește rețea algebrică. În acest caz, sup{x, y} se scrie ca x ∨ y, iar inf {x, y} ca x ∧ y.
Să verificăm dacă exemplul nostru de lucru ⟨P ({1, 2, 3}), ⊆⟩ este o rețea. Într-adevăr, pentru orice a, b ∈ P ({1, 2, 3}), a∨b = a∪b și a∧b = a∩b. De exemplu, luați în considerare mulțimile {1, 2} și {1, 3} și găsiți infimul și supremul lor. Dacă le intersectăm, vom obține mulțimea {1}, care va fi infimul. Obținem supremul combinându-le - {1, 2, 3}.
În algoritmii de identificare a problemelor fizice, spațiul de căutare este adesea reprezentat sub forma unei rețele, unde seturi de un element (a se citi primul nivel al rețelei de căutare, unde partea stângă a dependențelor este formată dintr-un atribut) reprezintă fiecare atribut. a relaţiei iniţiale.
În primul rând, luăm în considerare dependențele de forma ∅ → Un singur atribut. Acest pas vă permite să determinați care atribute sunt chei primare (pentru astfel de atribute nu există determinanți și, prin urmare, partea stângă este goală). Mai mult, astfel de algoritmi se deplasează în sus de-a lungul rețelei. Este de remarcat faptul că nu poate fi traversată întreaga zăbrele, adică dacă dimensiunea maximă dorită a părții stângi este transmisă la intrare, atunci algoritmul nu va depăși un nivel cu acea dimensiune.
Figura de mai jos arată cum o rețea algebrică poate fi utilizată în problema găsirii unui FZ. Aici fiecare margine (X, XY) reprezintă o dependență X → Y. De exemplu, am trecut de primul nivel și știm că dependența se menține A → B (vom afișa aceasta ca o conexiune verde între vârfuri A и B). Aceasta înseamnă că în continuare, atunci când ne deplasăm în sus de-a lungul rețelei, este posibil să nu verificăm dependența A, C → B, pentru că nu va mai fi minim. În mod similar, nu am verifica dacă dependența a fost păstrată C → B.
În plus, de regulă, toți algoritmii moderni pentru căutarea legilor federale folosesc o structură de date, cum ar fi o partiție (în sursa originală - partiția stripped [1]). Definiția formală a unei partiții este următoarea:
Definiția 6. Fie X ⊆ R un set de atribute pentru relația r. Un cluster este un set de indici de tupluri din r care au aceeași valoare pentru X, adică c(t) = {i|ti[X] = t[X]}. O partiție este un set de clustere, excluzând clusterele cu lungimea unității:
Cu cuvinte simple, o partiție pentru un atribut X este un set de liste, în care fiecare listă conține numere de rând cu aceleași valori pentru X. În literatura modernă, structura care reprezintă partițiile se numește indice de listă de poziții (PLI). Clusterele de lungime unitară sunt excluse în scopul compresiei PLI, deoarece sunt clustere care conțin doar un număr de înregistrare cu o valoare unică care va fi întotdeauna ușor de identificat.
Să ne uităm la un exemplu. Să revenim la același tabel cu pacienții și să construim partiții pentru coloane Rabdator и Paul (în stânga a apărut o nouă coloană, în care sunt marcate numerele rândurilor tabelului):
În plus, conform definiției, partiția pentru coloană Rabdator va fi de fapt gol, deoarece clusterele individuale sunt excluse din partiție.
Partițiile pot fi obținute prin mai multe atribute. Și există două moduri de a face acest lucru: parcurgând tabelul, construiți o partiție folosind toate atributele necesare simultan sau construiți-o folosind operația de intersecție a partițiilor folosind un subset de atribute. Algoritmii de căutare a legislației federale folosesc a doua opțiune.
Cu cuvinte simple, pentru, de exemplu, a obține o partiție pe coloane ABC, puteți lua partiții pentru AC и B (sau orice alt set de submulțimi disjunse) și le intersectează între ele. Operația de intersecție a două partiții selectează grupuri de cea mai mare lungime care sunt comune ambelor partiții.
Să ne uităm la un exemplu:
În primul caz, am primit o partiție goală. Dacă te uiți cu atenție la tabel, atunci, într-adevăr, nu există valori identice pentru cele două atribute. Dacă modificăm puțin tabelul (caza din dreapta), vom obține deja o intersecție negoală. Mai mult, liniile 1 și 2 conțin de fapt aceleași valori pentru atribute Paul и Doctor.
În continuare, vom avea nevoie de un astfel de concept precum dimensiunea partiției. Oficial:
Mai simplu spus, dimensiunea partiției este numărul de clustere incluse în partiție (rețineți că clusterele individuale nu sunt incluse în partiție!):
Acum putem defini una dintre lemele cheie, care pentru partițiile date ne permite să stabilim dacă o dependență este sau nu deținută:
Lema 1. Dependența A, B → C este valabilă dacă și numai dacă
Conform lemei, pentru a determina dacă o dependență este valabilă, trebuie parcurși patru pași:
- Calculați partiția pentru partea stângă a dependenței
- Calculați partiția pentru partea dreaptă a dependenței
- Calculați produsul primului și al doilea pas
- Comparați dimensiunile partițiilor obținute în primul și al treilea pas
Mai jos este un exemplu de verificare dacă dependența este valabilă în conformitate cu această lemă:
În acest articol, am examinat concepte precum dependența funcțională, dependența funcțională aproximativă, am analizat unde sunt utilizate, precum și ce algoritmi pentru căutarea funcțiilor fizice există. De asemenea, am examinat în detaliu conceptele de bază, dar importante, care sunt utilizate în mod activ în algoritmii moderni pentru căutarea legilor federale.
Referinte:
- Huhtala Y. și colab. TANE: Un algoritm eficient pentru descoperirea dependențelor funcționale și aproximative //Jurnalul computerului. – 1999. – T. 42. – Nr. 2. – p. 100-111.
- Kruse S., Naumann F. Descoperirea eficientă a dependențelor aproximative // Proceedings of the VLDB Endowment. – 2018. – T. 11. – Nr. 7. – p. 759-772.
- Papenbrock T., Naumann F. O abordare hibridă a descoperirii dependenței funcționale //Proceedings of the 2016 International Conference on Management of Data. – ACM, 2016. – p. 821-833.
- Papenbrock T. şi colab. Descoperirea dependenței funcționale: o evaluare experimentală a șapte algoritmi //Proceedings of the VLDB Endowment. – 2015. – T. 8. – Nr. 10. – p. 1082-1093.
- Kumar A. şi colab. Să vă alăturați sau să nu vă alăturați?: Vă gândiți de două ori la alăturari înainte de selecția caracteristicilor //Proceedings of the 2016 International Conference on Management of Data. – ACM, 2016. – p. 19-34.
- Abo Khamis M. și colab. Învățare în baza de date cu tensori rari //Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems. – ACM, 2018. – p. 325-340.
- Hellerstein J. M. şi colab. Biblioteca de analiză MADlib: sau abilitățile MAD, SQL //Proceedings of the VLDB Endowment. – 2012. – T. 5. – Nr. 12. – p. 1700-1711.
- Qin C., Rusu F. Speculative aproximations for terascale distributed gradient descent optimization //Proceedings of the Fourth Workshop on Data analytics in the Cloud. – ACM, 2015. – P. 1.
- Meng X. și colab. Mllib: Învățarea automată în apache spark //The Journal of Machine Learning Research. – 2016. – T. 17. – Nr. 1. – p. 1235-1241.
Autorii articolului: , cercetător la , и , cercetător la
Sursa: www.habr.com