Dependență funcțională (programare)

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

Dependența funcțională este o relație binară între seturi de atribute ale unei relații date și este, de fapt, o relație unu-la-mulți. Utilizarea sa se datorează faptului că vă permite să rezolvați formal și strict multe probleme.

Dependența funcțională este un concept care stă la baza multor probleme legate de bazele de date relaționale , inclusiv, în special, proiectarea acestora.

Definiții

Dependență funcțională

Fie ca o relație să fie dată cu o schemă (antet) și să fie câteva subseturi ale setului de atribute al relației . Un set depinde funcțional de dacă și numai dacă fiecare valoare a setului este asociată cu exact o valoare a setului . Desemnat . $r$ $R$ $A$ $B$ $r$ $B$ $A$ $A$ $B$ $A la B$

Cu alte cuvinte, dacă două tupluri au aceeași valoare în , atunci au aceeași valoare în . $A$ $B$

r\stanga(R\dreapta),\A\subseteq R,\B\subseteq R

\left(A\la B\right)\Leftrightarrow \left(\left(\forall {{t}_{1}}, {{t}_{2}}\in r:{{t} _{1}}\left(A\right)={{t}_{2}}\left(A\right)\right)\Rightarrow \left({{t}_{1}}\left(B) \right)={{t}_{2}}\stanga(B\dreapta)\dreapta)\dreapta)

În acest caz , determinantul este partea dependentă. $A$ $B$

O dependență funcțională se spune că este trivială dacă partea dependentă este o submulțime a determinantului.

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

Închiderea unui set de dependențe

Unele dependențe funcționale pot implica alte dependențe funcționale. De exemplu, dependența funcțională,

{\ displaystyle \ stânga (A \ la B \ dreapta) \ pană \ stânga (B \ la C \ dreapta) \ săgeată la dreapta \ stânga ( A \ la C \ dreapta)}

Mulțimea tuturor dependențelor funcționale care sunt implicate de un set dat de dependențe funcționale se numește închiderea mulțimii . ${{S}^{+}}$ $S$ $S$

Închiderea setului de atribute

Fie un set de atribute ale relației și setul de dependențe funcționale ale acestei relații. Închiderea setului de atribute în limite este un astfel de set de toate atributele relației încât dependența funcțională este un membru al închiderii . $Z$ $r$ $S$ ${{Z}^{+}}$ $Z$ $S$ ${{A}_{i)}$ $r$ $Z\la {{A}_{i)}$ ${{S}^{+}}$

r\stanga(R\dreapta),\S,\Z\subseteq R,\{{A}_{i}}\subseteq R,\ i={\overline {1,n}}

{{Z}^{+}}=\left\{{{A}_{i}}:\stânga(Z\la {{A}_{i}}\dreapta)\în {{S }^{+}}\dreapta\}

Seturi ireductibile de dependențe

Să fie și niște seturi de dependențe funcționale. ${{S}_{1}}$ ${{S}_{2))$

Dacă orice dependență funcțională de la intră și în , atunci acoperirea setului de dependențe funcționale este numită . ${{S}_{1}}$ ${{S}_{2}^{+}}$ ${{S}_{2))$ ${{S}_{1}}$
Dacă este o acoperire pentru , și este o acoperire pentru (adică ), atunci astfel de mulțimi sunt numite echivalente . ${{S}_{2))$ ${{S}_{1}}$ ${{S}_{1}}$ ${{S}_{2))$ ${\displaystyle S_{1}^{+}=S_{2}^{+))$
Se spune că un set de dependențe funcționale este ireductibil dacă și numai dacă sunt îndeplinite următoarele condiții: $S$
- În fiecare dependență funcțională, partea dependentă conține un singur element;
- Determinantul fiecărei dependențe funcționale este ireductibil (niciun atribut nu poate fi eliminat din determinant fără a schimba închiderea ); ${{S}^{+}}$
- Niciuna dintre dependențele funcționale de la nu poate fi eliminată fără a schimba închiderea . $S$ ${{S}^{+}}$
Pentru orice set de dependențe funcționale, există cel puțin un set echivalent care este ireductibil. O astfel de mulțime echivalentă se numește acoperire ireductibilă .

Evaluarea închiderii

Regulile de inferență ale lui Armstrong

În 1974, William Armstrong a propus un set de reguli pentru a deduce noi dependențe funcționale din date.

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$

Reflexivitate : ${\ displaystyle \ stânga (B \ subseteq A \ dreapta) \ Săgeată la dreapta \ stânga ( A \ la B \ dreapta)}$
Reaprovizionare : $\stânga(A\la B\dreapta)\Săgeată la dreapta \la stânga(AC\la BC\dreapta)$
Tranzitivitate : ${\ displaystyle \ stânga (A \ la B \ dreapta) \ pană \ stânga (B \ la C \ dreapta) \ săgeată la dreapta \ stânga ( A \ la C \ dreapta)}$

Regulile de inferență ale lui Armstrong sunt complete (folosindu-le, se pot deriva toate celelalte dependențe funcționale implicate de setul dat) și fiabile („de prisos” dependențe funcționale nu pot fi deduse: dependența funcțională derivată este valabilă oriunde sunt dependențele funcționale originale (din care a fost derivate) sunt valabile).

În plus, mai multe reguli suplimentare sunt derivate pur și simplu din aceste reguli, care simplifică sarcina de a deriva dependențe funcționale.

Autodeterminare : $A\to A$
Descompunere : ${\ displaystyle \ stânga (A \ la BC \ dreapta) \ Săgeată la dreapta \ stânga (A \ la B \ dreapta) \ pană \ stânga ( A \ la C \ dreapta)}$
Consolidare : ${\ displaystyle \ stânga (A \ la B \ dreapta) \ pană \ stânga ( A \ la C \ dreapta) \ săgeată la dreapta \ stânga ( A \ la BC \ dreapta)}$
Compozitie : ${\ displaystyle \ stânga (A \ la B \ dreapta) \ pană \ stânga ( C \ la D \ dreapta) \ Săgeată la dreapta \ stânga ( AC \ la BD \ dreapta)}$
Teorema de unificare universală a lui Darwen : ${\ displaystyle \ stânga (A \ la B \ dreapta) \ pană \ stânga ( C \ la D \ dreapta) \ săgeată la dreapta \ stânga ( A \ cupă \ stânga ( CB \ dreapta) \ la BD \ dreapta)}$

Teoremă: O dependență funcțională este dedusă dintr-un set dat de dependențe funcționale conform regulilor de inferență ale lui Armstrong dacă și numai dacă . $A la B$ $S$ $B\subseteq {{A}^{+}}$

Închiderea setului de atribute

Dacă aplicăm regulile din secțiunea anterioară până când crearea de noi dependențe funcționale se oprește de la sine, atunci obținem o închidere pentru un anumit set de dependențe funcționale. În practică, rareori este necesar să se calculeze această închidere de la sine, de cele mai multe ori suntem mult mai interesați să știm dacă cutare sau cutare dependență funcțională va fi inclusă în închidere. Pentru a face acest lucru, este suficient să calculăm închiderea determinantului. Există un algoritm destul de simplu pentru asta.

Să fie un set de atribute care vor deveni în cele din urmă o închidere. $X$
Căutăm dependențe funcționale de forma , unde și . Adăugăm partea dependentă a fiecărei dependențe găsite la . ${{B}_{1}}{{B}_{2}}\ldots {{B}_{m}}\la C$ ${{B}_{1}}{{B}_{2}}\ldots {{B}_{m}}\subseteq X$ $C\nu \subset X$ $X$
Repetați pasul 2 până când este imposibil să adăugați atribute la set. $X$
Un set la care nu pot fi adăugate atribute va fi o închidere. $X$

Aplicație

Proiectare baze de date

Dependențe funcționale sunt constrângeri de integritate și definesc semantica datelor stocate în baza de date. Cu fiecare actualizare, SGBD -ul trebuie să verifice conformitatea acestora. Prin urmare, prezența unui număr mare de dependențe funcționale este nedorită, altfel încetinește activitatea. Pentru a simplifica sarcina, este necesar să reduceți setul de dependențe funcționale la minimum necesar.

Dacă este o acoperire ireductibilă a setului inițial de dependențe funcționale , atunci verificarea îndeplinirii dependențelor funcționale de la garantează automat îndeplinirea tuturor dependențelor funcționale de la . Astfel, sarcina de a găsi mulțimea minimă necesară se reduce la găsirea unei acoperiri ireductibile a mulțimii de dependențe funcționale, care va fi folosită în locul mulțimii inițiale. $eu$ $S$ $eu$ $S$

Vezi și

Model de date relaționale
Proiectarea bazei de date
forma normala
Dependența multivalorică este o generalizare a dependenței funcționale.

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 .