Dependență multivalorică

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 2 iunie 2019; verificările necesită 2 modificări .

Dependența multivalorică (de asemenea MZZ ) este o generalizare a conceptului de dependență funcțională , utilizată pe scară largă în teoria bazelor de date . În conceptul de forme normale , este introdus pentru a defini formal a patra formă normală

Definiții

Să existe o relație cu schema , precum și două subseturi arbitrare de atribute . Lasă . $r$ $R$ $A,B\subseteq R$ $C{\overset {\mathop {=} }{\,}}R\backslash (A\cup B)$

În acest caz, depinde de , dacă și numai dacă setul de valori ale atributelor corespunzătoare perechii de relații date depinde și nu de . $B$ $A$ $B$ $[a:A;c:C]$ $r$ $A$ $c$

Exprimată simbolic prin scriere

A\twoheadrightarrow B

Oficial

{\begin{aliniat}&r\left(R\right),\A,B\subseteq R,\C=R\backslash (A\cup B)\\&\left(A\twoheadrightarrow B\right )\Leftrightarrow \forall {{t}_{1}},{{t}_{2}}\in r\ \exists {{t}_{3}},{{t}_{4}}\ în r\ :\ \left\{{\begin{aligned}&{{t}_{1}}\left(A\right)={{t}_{2}}\left(A\right)= {{t}_{3}}\left(A\right)={{t}_{4}}\left(A\right)\\&{{t}_{3}}\left(B\ dreapta)={{t}_{1}}\stânga(B\dreapta)\\&{{t}_{3}}\left(C\right)={{t}_{2}}\stânga (C\right)\\&{{t}_{4}}\left(B\right)={{t}_{2}}\left(B\right)\\&{{t}_{ 4}}\left(C\right)={{t}_{1}}\left(C\right)\\\end{aliniat}}\right.\\\end{aliniat}}

O dependență cu mai multe valori este numită trivială dacă cel puțin una dintre următoarele condiții este adevărată: $A\twoheadrightarrow B$

Setul este un superset ; $A$ $B$ $B\subseteq A$
Unire și formează întregul antet al relației. $A$ $B$ $A\cup B=R$

Exemplu

Să presupunem că avem o relație care include o listă de discipline academice, literatura recomandată și numele lectorilor care predau cursurile corespunzătoare:

Discipline academice

Disciplina	Carte	Lector
MatAn	Kudryavtsev	Ivanov A.
MatAn	Fikhtengolts	Petrov B.
MatAn	Kudryavtsev	Petrov B.
MatAn	Fikhtengolts	Ivanov A.
MatAn	Kudryavtsev	Smirnov V.
MatAn	Fikhtengolts	Smirnov V.
VM	Kudryavtsev	Ivanov A.
VM	Kudryavtsev	Petrov B.

Întrucât lectorii care citesc subiectul și cărțile recomandate pe subiect nu depind unul de celălalt, această relație conține o dependență multivalorică. Această atitudine are o serie de anomalii. Una dintre ele este că dacă vrem să recomandăm o carte nouă într-un curs MatAn, va trebui să adăugăm atâtea intrări noi câte lectori sunt în MatAn și invers.

Formal, există două MZZ-uri: {Disciplina} {Carte}|{Lector} . $\twoheadrightarrow$

În primul rând, este redundant. Și în al doilea rând, pentru o astfel de relație, este necesar să se dezvolte un mecanism suplimentar de control al integrității. Soluția optimă a problemei ar fi să descompunem relația în două cu titlurile {Disciplina, Carte} și {Disciplina, Lector} . O astfel de descompunere ar fi în 4NF . Admisibilitatea descompunerii este stabilită de teorema lui Fagin (vezi mai jos).

Teoreme

Perechi conectate

Fagin a arătat că dependențele cu mai multe valori formează perechi conectate (în notație de definiție):

\left(A\twoheadrightarrow B\right)\Leftrightarrow \left(A\twoheadrightarrow C\right)

Prin urmare, ele sunt adesea reprezentate împreună în notație simbolică:

A\twoheadrightarrow B|C

Dependențe funcționale

Orice dependență funcțională este multivalorică. Cu alte cuvinte, o dependență funcțională este o dependență cu mai multe valori în care setul de valori dependente corespunzătoare unei valori date a determinantului are întotdeauna puterea unitară .

{\ displaystyle \ stânga ( A \ la B \ dreapta) \ Săgeată la dreapta \ stânga ( A \ twoheadrightarrow B \ dreapta)}

Reguli de ieșire

În 1977, Bury, Fagin și Howard au descoperit că regulile de inferență ale lui Armstrong pot fi generalizate și extinse atât la dependențe funcționale, cât și la dependențe multivalorice.

Să presupunem că avem o relație și un set de atribute . Pentru a scurta înregistrarea, vom scrie în schimb simplu . $r\stanga(R\dreapta)$ $A,B,C,D\subseteq R$ $X\cup Y$ $X Y$

Grupa 1: reguli de bază.

Plus $\left (A\cup B\cup C=R\right)\wedge \left(B\cap C\subseteq A\right)\Rightarrow \left(\left(A\twoheadrightarrow B\right)\Leftrightarrow \left(A\twoheadrightarrow C\right)\right)$
Tranzitivitatea $\left(A\twoheadrightarrow B\right)\wedge \left(B\twoheadrightarrow C\right)\Rightarrow \left(A\twoheadrightarrow C\backslash B\right)$
reflexivitate $\left(B\subseteq A\right)\Rightarrow \left(A\twoheadrightarrow B\right)$
Creştere $\left(A\twoheadrightarrow B\right)\wedge \left(C\subseteq D\right)\Rightarrow \left(AD\twoheadrightarrow BC\right)$

Grupa 2: Sunt derivate mai multe reguli suplimentare pentru a simplifica sarcina de a deduce dependențe cu mai multe valori.

Pseudotransitivitate $\left(A\twoheadrightarrow B\right)\wedge \left(BC\twoheadrightarrow D\right)\Rightarrow \left(AC\twoheadrightarrow D\backslash BC\right)$
O asociere $\left(A\twoheadrightarrow B\right)\wedge \left(A\twoheadrightarrow C\right)\Rightarrow \left(A\twoheadrightarrow BC\right)$
Descompunere $\left(A\twoheadrightarrow BC\right)\Rightarrow \left(A\twoheadrightarrow B\cap C\right)\wedge \left(A\twoheadrightarrow B\backslash C\right)\wedge \left(A\ twoheadrightarrow C\backslash B\right)$

Grupa 3: Se stabilește o legătură între dependențele funcționale și cu mai multe valori.

Replicare (copie) ${\ displaystyle \ stânga ( A \ la B \ dreapta) \ Săgeată la dreapta \ stânga ( A \ twoheadrightarrow B \ dreapta)}$
fuziune $\left(A\twoheadrightarrow B\right)\wedge\left(C\la D\right)\wedge \left(D\subseteq B\right)\wedge \left(B\cap C=\varnothing \ dreapta)\Săgeată la dreapta \stanga(A\la D\dreapta)$

Grupa 4: pentru dependențe funcționale, derivate din regulile de mai sus.

$\left(A\twoheadrightarrow B\right)\wedge \left(AB\to C\right)\Rightarrow \left (A\la C\backslash B\right)$

Regulile de inferență ale lui Armstrong, împreună cu regulile grupurilor 1 și 3 prezentate aici, formează o formă completă (folosindu-le, se pot deriva toate celelalte dependențe multi-valori implicate de setul lor dat) și de încredere („dependențe multi-valori suplimentare” nu pot fi dedusă; dependența multivalorică derivată este valabilă oriunde este un set de dependențe multivalorice din care a fost derivată) un set de reguli pentru deducerea dependențelor cu mai multe valori.

Aplicație

Descompunerea relației

Teorema lui Fagin

Să fie dat raportul . O relație va fi egală cu uniunea proiecțiilor sale dacă și numai dacă relația satisface o dependență multivalorică netrivială . $r\stanga(A,B,C\dreapta)$ $r$ $r\stânga[A,B\dreapta]$ $r\stânga[A,C\dreapta]$ $r$ $A\twoheadrightarrow B|C$

\left(r\left(A,B,C\right)=r\left[A,B\right]\{\text{JOIN})\r\left[A,C\right]\right )\Leftrightarrow \left(A\twoheadrightarrow B|C\right)

Această teoremă este o versiune mai strictă a teoremei lui Heath .

Vezi și

Literatură

K. J. Data. Introduction to Database Systems = Introduction to Database Systems. - Ed. a 8-a. - M . : „Williams” , 2006. - S. 1328. - ISBN 0-321-19784-4 .