Dependențe multivaloare, joncțiune

JONCŢIUNE

Modelul relaţional utilizează dependenţele pentru exprimarea constrângerilor pe care datele din baza de date trebuie să le satisfacă. Schema bazei de date relaţionale este definită de o varietate de constrângeri ce sunt impuse componentelor sale. Dependenţele funcţionale sunt un exemplu de astfel de constrângeri de integritate. Ele au fost studiate detaliat în capitolul 3.

O generalizare a dependenţelor funcţionale, numite dependenţe multivaloare, a fost descoperită de mai mulţi cercetători în domeniu. Cea mai importantă proprietate a dependenţei multivaloare constă în faptul că existenţa ei într-o relaţie este o condiţie necesară şi suficientă pentru ca relaţia să poată fi înlocuită fără pierderi de informaţii, independent de extensia curentă, cu două proiecţii ale sale. Această proprietate face ca dependenţa multivaloare să joace un rol important în teoria şi practica proiectării bazelor de date relaţionale.

O dată ce dependenţele multivaloare au devenit parte a teoriei relaţiilor, o cerinţă de bază ce trebuie să fie satisfăcută este cunoaşterea proprietăţilor lor şi, în particular, metodelor de manipulare. Întrucât dependenţele multivaloare sunt o generalizare a celor funcţionale, metodele aplicate asupra ultimelor pot servi drept ghid în susţinerea acestei cerinţe.

Este bine cunoscut că existenţa într-o relaţie a dependenţelor funcţionale implică că în ea există dependenţe funcţionale adiţionale. Aceasta e valabil şi pentru dependenţele multivaloare. Noţiunea de implicare este formalizată în conceptul de reguli de inferenţă. Sunt cunoscute mulţimi închise şi complete de reguli de inferenţă pentru dependenţele multivaloare.

Dependenţele joncţiune sunt o generalizare a dependenţelor multivaloare. E cunoscut faptul că o mulţime de dependenţe funcţionale plus o dependenţă joncţiune se consideră suficiente pentru exprimarea dependenţelor dintre atributele unei scheme a bazei de date.

Acest capitol cuprinde noţiuni generale despre dependenţele multivaloare, regulile de inferenţă, dependenţele multivaloare incluse, regulile de inferenţă ale dependenţelor joncţiune etc.

4.1. Dependenţe multivaloare

Definiţia 4.1. Fie relaţia r cu schema R şi X,YR. Notăm Z=R XY. Vom spune că relaţia r(R) satisface dependenţa multivaloare XY (sau XY e validă în r(R)), dacă pentru orice pereche de tupluri t1 şi t2 din r(R) ce satisfac t1[X]=t2[X] există în r(R) un tuplu t3 pentru care au loc egalităţile t3[X]=t1[X], t3[Y]=t1[Y] şi t3[Z]=t2[Z].

Remarcă. Din proprietatea de simetrie a acestei definiţii urmează că în r(R) mai există un tuplu t4 ce satisface egalităţile t4[X]=t1[X], t4[Y]=t2[Y] şi t4[Z]=t1[Z].

Teorema 4.1. O dependenţă multivaloare XY e validă în relaţia r(R) dacă şi numai dacă XZ e validă în r(R), unde Z = R XY.

Demonstraţie. Din remarca definiţiei 4.1 urmează că, dacă relaţia r(R) satisface dependenţa multivaloare XY, atunci de fiecare dată când t1[X]=t2[X] în r(R) există nu numai un tuplu t3 ce satisface t3[X]=t1[X], t3[Y]=t1[Y] şi t3[Z]=t2[Z], dar şi un tuplu t4 pentru care au loc egalităţile t4[X]=t1[X], t4[Y]=t2[Y] şi t4[Z]=t1[Z]. În consecinţă, tupluri distincte cu aceleaşi X-valori şi cu Y-valori (Z-valori) identice trebuie să aibă diferite Z-valori (Y-valori) pentru a menţine toate tuplurile distincte. Din această proprietate simetrică rezultă că relaţia r(R) satisface dependenţa multivaloare XY dacă şi numai dacă satisface dependenţa multivaloare XZ.

Exemplul 4.1. Relaţia r(ABCD) din fig.4.1 satisface dependenţa multivaloare BCA. În relaţia r(ABCD) e validă de asemenea dependenţa multivaloare BCD. Dacă, însă, din relaţia r(ABCD) este eliminat un tuplu, atunci dependenţele multivaloare BCA şi BCD devin invalide în r(ABCD).

r A B C D

a1 b1 c1 d1

a1 b1 c1 d2

a1 b1 c2 d1

a1 b1 c2 d2

a2 b1 c1 d1

a2 b1 c1 d2

a2 b1 c2 d1

a2 b1 c2 d2

Fig.4.1

În definiţia 4.1 nu s-au pus condiţii asupra mulţimilor X şi Y. Deci X  Y   în caz general. Determinatul Y poate fi redus. Să demonstrăm că varianta redusă, XY X, e echivalentă dependenţei XY.

Teorema 4.2. Dependenţa funcţională XY e validă în relaţia r(R), dacă şi numai dacă XY X e validă în r(R).

Demonstraţie. Necesitatea. Fie relaţia r(R) satisface dependenţa multivaloare XY. Notăm Y1 = Y X. Atunci Z= R XY = R XY1. Fie t1 şi t2 două tupluri cu X-valori egale, adică t1[X] = t2[X]. Fiindcă XY e validă în r(R), atunci în r trebuie să existe un tuplu t3 ce satisface t3[X]=t1[X], t3[Y]=t1[Y] şi t3[Z] = t2[Z]. Egalitatea t3[Y] = t1[Y] implică egalitatea t3[Y1] = t1[Y1]. Prin urmare, relaţia r satisface şi dependenţa multivaloare XY1.

Suficienţa. Fie r(R) satisface dependenţa multivaloare XY1, unde Y1 = Y X şi fie X1X. Să arătăm că dependenţa XY1X1 e validă în r(R). Întrucât r satisface XY1 şi dacă t1, t2r şi t1[X] = t2[X], atunci există un tuplu t3, pentru care t3[X] = t1[X], t3[Y1] = t1[Y1] şi t3[Z] = t2[Z]. Din X1 X şi t3[Y1] = t1[Y1] urmează t3[Y1X1] = t1[Y1X1]. Deci XY1X1.