Introducció a les dependències funcionals

En aquest article parlarem de les dependències funcionals a les bases de dades: què són, on s'utilitzen i quins algorismes existeixen per trobar-les.

Considerarem les dependències funcionals en el context de les bases de dades relacionals. Per dir-ho molt aproximadament, en aquestes bases de dades la informació s'emmagatzema en forma de taules. A continuació, utilitzem conceptes aproximats que no són intercanviables en la teoria relacional estricta: anomenarem la taula mateixa una relació, les columnes - atributs (el seu conjunt - un esquema de relació) i el conjunt de valors de fila en un subconjunt d'atributs. - una tupla.

Per exemple, a la taula anterior, (Benson, M, M organ) és una tupla d'atributs (Pacient, Paul, metge).
Més formalment, això s'escriu de la següent manera: [Pacient, gènere, metge] = (Orgue Benson, M, M).
Ara podem introduir el concepte de dependència funcional (FD):

Definició 1. La relació R compleix la llei federal X → Y (on X, Y ⊆ R) si i només si per a qualsevol tuple , ∈ R es compleix: si [X] = [X], doncs [Y] = [Y]. En aquest cas, diem que X (el determinant o conjunt d'atributs definidors) determina funcionalment Y (el conjunt dependent).

En altres paraules, la presència d'una llei federal X → Y vol dir que si hi tenim dues tuples R i coincideixen en atributs X, llavors coincidiran en atributs Y.
I ara, en ordre. Vegem els atributs Pacient и Sexe per la qual cosa volem esbrinar si hi ha dependències entre ells o no. Per a aquest conjunt d'atributs, poden existir les dependències següents:

1. Pacient → Gènere
2. Gènere → Pacient

Tal com s'ha definit anteriorment, per tal que la primera dependència es mantingui, cada valor de columna únic Pacient només ha de coincidir un valor de columna Sexe. I per a la taula d'exemple aquest és realment el cas. Tanmateix, això no funciona en la direcció oposada, és a dir, la segona dependència no es satisfà i l'atribut Sexe no és un determinant per Pacient. De la mateixa manera, si prenem la dependència Metge → Pacient, es pot veure que es viola, ja que el valor pit-roig aquest atribut té diversos significats diferents: Ellis i Graham.

Així, les dependències funcionals permeten determinar les relacions existents entre conjunts d'atributs de taula. A partir d'aquí ens plantejarem les connexions més interessants, o millor dit X → Yquè són:

• no trivial, és a dir, el costat dret de la dependència no és un subconjunt de l'esquerra (Y ̸⊆ X);
• mínima, és a dir, no hi ha aquesta dependència Z → YQue Z ⊂ X.

Les dependències considerades fins a aquest punt eren estrictes, és a dir, no preveien cap infracció sobre la taula, però a més d'elles, també n'hi ha que permeten certa inconsistència entre els valors de les tuples. Aquestes dependències es col·loquen en una classe separada, anomenada aproximada, i es permet que es violin durant un nombre determinat de tuples. Aquesta quantitat està regulada per l'indicador d'error màxim emax. Per exemple, la taxa d'error = 0.01 pot significar que la dependència pot ser violada per l'1% de les tuples disponibles en el conjunt d'atributs considerat. És a dir, per a 1000 registres, un màxim de 10 tuples poden infringir la Llei Federal. Considerarem una mètrica lleugerament diferent, basada en diferents valors per parelles de les tuples que es comparen. Per addicció X → Y sobre l'actitud r es considera així:

Calculem l'error de Metge → Pacient de l'exemple anterior. Tenim dues tuples els valors de les quals difereixen segons l'atribut Pacient, però coincideix Doctor: [Metge, pacient] = (Robin, Ellis) I [Metge, pacient] = (Robin, Graham). Seguint la definició d'error, hem de tenir en compte totes les parelles en conflicte, la qual cosa significa que n'hi haurà dos: (, ) i la seva inversió (, ). Substituïm-lo a la fórmula i obtenim:

Ara intentem respondre la pregunta: "Per què és tot per?" De fet, les lleis federals són diferents. El primer tipus són aquelles dependències que l'administrador determina en l'etapa de disseny de la base de dades. Solen ser pocs, estrictes i l'aplicació principal és la normalització de dades i el disseny d'esquemes relacionals.

El segon tipus són les dependències, que representen dades "ocultes" i relacions prèviament desconegudes entre atributs. És a dir, aquestes dependències no es van pensar en el moment del disseny i es troben per al conjunt de dades existent, de manera que posteriorment, a partir de les nombroses lleis federals identificades, es puguin extreure conclusions sobre la informació emmagatzemada. Són precisament aquestes dependències amb les que treballem. Són tractats per tot un camp de mineria de dades amb diverses tècniques de cerca i algorismes construïts sobre la seva base. Anem a esbrinar com poden ser útils les dependències funcionals trobades (exactes o aproximades) en qualsevol dada.

Avui dia, una de les principals aplicacions de les dependències és la neteja de dades. Implica desenvolupar processos per identificar les “dades brutes” i després corregir-les. Exemples destacats de "dades brutes" són duplicats, errors de dades o errors ortogràfics, valors que falten, dades obsoletes, espais addicionals i similars.

Exemple d'error de dades:

Exemple de duplicats a les dades:

Per exemple, tenim una taula i un conjunt de lleis federals que s'han d'executar. La neteja de dades en aquest cas implica canviar les dades perquè les lleis federals siguin correctes. En aquest cas, el nombre de modificacions hauria de ser mínim (aquest procediment té els seus propis algorismes, que no ens centrarem en aquest article). A continuació es mostra un exemple d'aquesta transformació de dades. A l'esquerra hi ha la relació original, en la qual, òbviament, no es compleixen els FL necessaris (un exemple d'incompliment d'un dels FL es destaca en vermell). A la dreta hi ha la relació actualitzada, amb les cel·les verdes que mostren els valors modificats. Després d'aquest tràmit, es van començar a mantenir les dependències necessàries.

Una altra aplicació popular és el disseny de bases de dades. Aquí val la pena recordar les formes normals i la normalització. La normalització és el procés de posar una relació en conformitat amb un determinat conjunt de requisits, cadascun dels quals està definit per la forma normal a la seva manera. No descriurem els requisits de diverses formes normals (això es fa en qualsevol llibre sobre un curs de bases de dades per a principiants), però només observarem que cadascuna d'elles utilitza el concepte de dependències funcionals a la seva manera. Després de tot, els FL són inherentment restriccions d'integritat que es tenen en compte a l'hora de dissenyar una base de dades (en el context d'aquesta tasca, les FL de vegades s'anomenen superclaus).

Considerem la seva aplicació per als quatre formularis normals de la imatge següent. Recordeu que la forma normal de Boyce-Codd és més estricta que la tercera, però menys que la quarta. De moment no estem considerant aquest últim, ja que la seva formulació requereix la comprensió de les dependències multivalorades, que no ens interessen en aquest article.

Una altra àrea en què les dependències han trobat la seva aplicació és reduir la dimensionalitat de l'espai de característiques en tasques com la construcció d'un classificador Bayes ingenu, la identificació de característiques significatives i la reparametriització d'un model de regressió. En els articles originals, aquesta tasca s'anomena determinació de la rellevància redundant i de les característiques [5, 6], i es resol amb l'ús actiu dels conceptes de bases de dades. Amb l'arribada d'aquests treballs, podem dir que avui hi ha una demanda de solucions que ens permetin combinar la base de dades, l'anàlisi i la implementació dels problemes d'optimització anteriors en una sola eina [7, 8, 9].

Hi ha molts algorismes (tant moderns com no tan moderns) per cercar lleis federals en un conjunt de dades. Aquests algorismes es poden dividir en tres grups:

• Algoritmes que utilitzen travessa de gelosies algebraiques (Algoritmes de travessa de gelosia)
• Algorismes basats en la cerca de valors acordats (Algoritmes de conjunt de diferències i d'acord)
• Algorismes basats en comparacions per parells (algorismes d'inducció de dependència)

A la taula següent es presenta una breu descripció de cada tipus d'algorisme:


Podeu llegir més informació sobre aquesta classificació [4]. A continuació es mostren exemples d'algorismes per a cada tipus:

Actualment, estan apareixent nous algorismes que combinen diversos enfocaments per trobar dependències funcionals. Exemples d'aquests algorismes són Pyro [2] i HyFD [3]. En els següents articles d'aquesta sèrie s'espera una anàlisi del seu treball. En aquest article només examinarem els conceptes bàsics i el lema necessaris per entendre les tècniques de detecció de dependències.

Comencem amb un de simple: el conjunt de diferència i d'acord, utilitzat en el segon tipus d'algorismes. El conjunt de diferències és un conjunt de tuples que no tenen els mateixos valors, mentre que el conjunt d'acord, al contrari, són tuples que tenen els mateixos valors. Val a dir que en aquest cas estem considerant només el costat esquerre de la dependència.

Un altre concepte important que es va trobar anteriorment és la xarxa algebraica. Com que molts algorismes moderns operen amb aquest concepte, hem de tenir una idea de què és.

Per introduir el concepte de gelosia, cal definir un conjunt parcialment ordenat (o conjunt parcialment ordenat, abreujat com a poset).

Definició 2. Es diu que un conjunt S està parcialment ordenat per la relació binària ⩽ si per a tot a, b, c ∈ S es compleixen les propietats següents:

1. Reflexivitat, és a dir, a ⩽ a
2. Antisimetria, és a dir, si a ⩽ b i b ⩽ a, aleshores a = b
3. La transitivitat, és a dir, per a a ⩽ b i b ⩽ c es dedueix que a ⩽ c

Aquesta relació s'anomena relació d'ordre parcial (solta), i el conjunt en si s'anomena conjunt parcialment ordenat. Notació formal: ⟨S, ⩽⟩.

Com a exemple més simple d'un conjunt parcialment ordenat, podem prendre el conjunt de tots els nombres naturals N amb la relació d'ordre habitual ⩽. És fàcil comprovar que es compleixen tots els axiomes necessaris.

Un exemple més significatiu. Considereu el conjunt de tots els subconjunts {1, 2, 3}, ordenats per la relació d'inclusió ⊆. De fet, aquesta relació satisfà totes les condicions d'ordre parcial, de manera que ⟨P ({1, 2, 3}), ⊆⟩ és un conjunt parcialment ordenat. La figura següent mostra l'estructura d'aquest conjunt: si es pot arribar a un element mitjançant fletxes a un altre element, llavors es troben en una relació d'ordre.

Necessitarem dues definicions més senzilles del camp de les matemàtiques: supremum i infimum.

Definició 3. Sigui ⟨S, ⩽⟩ un conjunt parcialment ordenat, A ⊆ S. La cota superior de A és un element u ∈ S tal que ∀x ∈ S: x ⩽ u. Sigui U el conjunt de tots els límits superiors de S. Si hi ha un element més petit en U, llavors s'anomena supremum i es denota sup A.

El concepte d'un límit inferior exacte s'introdueix de manera similar.

Definició 4. Sigui ⟨S, ⩽⟩ un conjunt parcialment ordenat, A ⊆ S. L'ínfim de A és un element l ∈ S tal que ∀x ∈ S: l ⩽ x. Sigui L el conjunt de tots els límits inferiors de S. Si hi ha un element més gran a L, llavors s'anomena ínfim i es denota com a inf A.

Considereu com a exemple el conjunt parcialment ordenat anteriorment ⟨P ({1, 2, 3}), ⊆⟩ i trobeu-hi el suprem i l'ínfim:

Ara podem formular la definició d'una xarxa algebraica.

Definició 5. Sigui ⟨P,⩽⟩ un conjunt parcialment ordenat de manera que cada subconjunt de dos elements tingui un límit superior i inferior. Aleshores P s'anomena xarxa algebraica. En aquest cas, sup{x, y} s'escriu com x ∨ y, i inf {x, y} com x ∧ y.

Comprovem que el nostre exemple de treball ⟨P ({1, 2, 3}), ⊆⟩ és una gelosia. De fet, per a qualsevol a, b ∈ P ({1, 2, 3}), a∨b = a∪b i a∧b = a∩b. Per exemple, considereu els conjunts {1, 2} i {1, 3} i trobeu el seu íntim i suprem. Si els talleem, obtindrem el conjunt {1}, que serà l'ínfim. Obtenim el supremum combinant-los - {1, 2, 3}.

En els algorismes per identificar problemes físics, l'espai de cerca es representa sovint en forma d'una gelosia, on conjunts d'un element (llegiu el primer nivell de la xarxa de cerca, on el costat esquerre de les dependències consta d'un atribut) representen cada atribut. de la relació original.
En primer lloc, considerem les dependències de la forma ∅ → Atribut únic. Aquest pas us permet determinar quins atributs són claus primàries (per a aquests atributs no hi ha determinants i, per tant, el costat esquerre està buit). A més, aquests algorismes es mouen cap amunt al llarg de la gelosia. Val la pena assenyalar que no es pot recórrer tota la gelosia, és a dir, si es passa a l'entrada la mida màxima desitjada del costat esquerre, l'algorisme no anirà més enllà d'un nivell amb aquesta mida.

La figura següent mostra com es pot utilitzar una xarxa algebraica en el problema de trobar una FZ. Aquí cada vora (X, XY) representa una dependència X → Y. Per exemple, hem superat el primer nivell i sabem que l'addicció es manté A → B (mostrarem això com una connexió verda entre els vèrtexs A и B). Això vol dir que, a més, quan ens movem cap amunt per la gelosia, és possible que no comprovem la dependència A, C → B, perquè ja no serà mínim. De la mateixa manera, no comprovaríem si es mantingués la dependència C → B.

A més, per regla general, tots els algorismes moderns per a la recerca de lleis federals utilitzen una estructura de dades com ara una partició (a la font original - partició despullada [1]). La definició formal d'una partició és la següent:

Definició 6. Sigui X ⊆ R un conjunt d'atributs per a la relació r. Un clúster és un conjunt d'índexs de tuples en r que tenen el mateix valor per a X, és a dir, c(t) = {i|ti[X] = t[X]}. Una partició és un conjunt de clústers, excloent els clústers de longitud d'unitat:

En paraules senzilles, una partició per a un atribut X és un conjunt de llistes, on cada llista conté números de línia amb els mateixos valors per X. A la literatura moderna, l'estructura que representa les particions s'anomena índex de llista de posicions (PLI). Els clústers de longitud d'unitat s'exclouen amb finalitats de compressió PLI perquè són clústers que només contenen un número de registre amb un valor únic que sempre serà fàcil d'identificar.

Vegem un exemple. Tornem a la mateixa taula amb pacients i construïm particions per a les columnes Pacient и Sexe (ha aparegut una nova columna a l'esquerra, en la qual es marquen els números de fila de la taula):

A més, segons la definició, la partició per a la columna Pacient en realitat estarà buit, ja que els clústers únics estan exclosos de la partició.

Les particions es poden obtenir mitjançant diversos atributs. I hi ha dues maneres de fer-ho: passant per la taula, construir una partició amb tots els atributs necessaris alhora, o construir-la mitjançant l'operació d'intersecció de particions utilitzant un subconjunt d'atributs. Els algorismes de cerca de lleis federals utilitzen la segona opció.

En paraules senzilles, per, per exemple, obtenir una partició per columnes abecedari, podeu agafar particions per AC и B (o qualsevol altre conjunt de subconjunts disjunts) i tallar-los entre si. L'operació d'intersecció de dues particions selecciona clústers de major longitud que són comuns a ambdues particions.

Vegem un exemple:

En el primer cas, vam rebre una partició buida. Si mireu detingudament la taula, de fet, no hi ha valors idèntics per als dos atributs. Si modifiquem lleugerament la taula (el cas de la dreta), ja obtindrem una intersecció no buida. A més, les línies 1 i 2 contenen realment els mateixos valors per als atributs Sexe и El metge.

A continuació, necessitarem un concepte com la mida de la partició. Formalment:

En poques paraules, la mida de la partició és el nombre de clústers inclosos a la partició (recordeu que els clústers únics no s'inclouen a la partició!):

Ara podem definir un dels lemes clau, que per a particions determinades ens permet determinar si es manté una dependència o no:

Lema 1. La dependència A, B → C es compleix si i només si

Segons el lema, per determinar si es compleix una dependència, s'han de realitzar quatre passos:

1. Calcula la partició del costat esquerre de la dependència
2. Calcula la partició del costat dret de la dependència
3. Calcula el producte del primer i del segon pas
4. Compareu les mides de les particions obtingudes en el primer i tercer pas

A continuació es mostra un exemple de comprovació de si la dependència es compleix segons aquest lema:

En aquest article, hem examinat conceptes com ara la dependència funcional, la dependència funcional aproximada, hem analitzat on s'utilitzen, així com quins algorismes per cercar funcions físiques existeixen. També vam examinar amb detall els conceptes bàsics però importants que s'utilitzen activament en algorismes moderns per a la recerca de lleis federals.

Referències:

1. Huhtala Y. et al. TANE: Un algorisme eficient per descobrir dependències funcionals i aproximades //The computer journal. – 1999. – T. 42. – Núm. 2. – pàgines 100-111.
2. Kruse S., Naumann F. Descobriment eficient de dependències aproximades // Proceedings of the VLDB Endowment. – 2018. – T. 11. – Núm. 7. – pàgines 759-772.
3. Papenbrock T., Naumann F. Un enfocament híbrid per al descobriment de dependències funcionals //Actes de la Conferència Internacional de Gestió de Dades de 2016. – ACM, 2016. – pàgs. 821-833.
4. Papenbrock T. et al. Descobriment de dependències funcionals: una avaluació experimental de set algorismes //Proceedings of the VLDB Endowment. – 2015. – T. 8. – Núm. 10. – pàgines 1082-1093.
5. Kumar A. et al. Unir-se o no unir-se?: Pensant dues vegades en les unions abans de seleccionar les funcions //Actes de la Conferència Internacional sobre Gestió de Dades de 2016. – ACM, 2016. – pàgs. 19-34.
6. Abo Khamis M. et al. Aprenentatge a la base de dades amb tensors dispersos //Actes del 37è Simposi ACM SIGMOD-SIGACT-SIGAI sobre principis de sistemes de bases de dades. – ACM, 2018. – pàgs. 325-340.
7. Hellerstein J. M. et al. La biblioteca d'anàlisi de MADlib: o habilitats MAD, els //Proceedings SQL de la dotació VLDB. – 2012. – T. 5. – Núm. 12. – pàgs 1700-1711.
8. Qin C., Rusu F. Aproximacions especulatives per a l'optimització de descens de gradient distribuït en terascales //Actes del quart taller sobre anàlisi de dades al núvol. – ACM, 2015. – P. 1.
9. Meng X. et al. Mllib: aprenentatge automàtic a apache spark //The Journal of Machine Learning Research. – 2016. – T. 17. – Núm. 1. – pàgines 1235-1241.

Autors de l'article: Anastasia Birillo, investigador de Investigació JetBrains, Estudiant del centre CS и Nikita Bobrov, investigador de Investigació JetBrains

Font: www.habr.com