Hipergrafuri

Introducere

O schema ”bună” a bazei de date trebuie să posede mai multe calități.Printre aceste calități putem menționa, în primul rând, formele normale, proprietate jocțiunii fără piederi și conservarea dependențelor.

Însă, asupra schemei bazei de date mai pot fi definite niște constrângeri sintactice cum ar fi, spre exemplu, aciclicitatea. Se cunosc diferite tipuri de aciclicitate. Similar unei ierarhii de forme normale ale schemelor, fiecare formă fiind mai restrictivă decât predecesoarea, există și o ierarhie de tipuri de aciclicități. Dupa cum se știe, proiectantul bazei de date trebuie să țină cont că, dacă schema relațională nu se găsește în forma normală corespunzătoare, atunci pot apărea diverse probleme de actualizare a bazei de date. De asemenea, de competența proiectantului ține și selectează gradului de aciclitate în care dorește ca schema să fie proiectată.

Schemele aciclice se bucură de o serie de proprietăți. Cu cât gradul de aciclicitate este mai înalt, cu atât mai ”bună” este schema. Mai mult decât atât, unii algoritmi, ce au o complexitate exponențială asupra schemelor ciclice, asupra schemelor aciclice, sunt polinomiale.

Schemele aciclice ale bazelor de date pot fi caracterizate în diferite moduri. În primul rând, definiția de aciclicitate poate fi formulată prin forme echivalente. Toate aceste forme se bazează pe reprezentarea schemelor bazelor de date cu ajutorul hipergrafurilor.

Unele definiții de aciclități se aduc, utilizând componentele hipergrafurilor în timp ce altele sunt bazate pr grafuri oridinare construite din hipergrafuri.

Multe din propietațile schemelor aciclice pot fi concepute în calitate de caracteristici, în sens că schema are o proprietate particulară, dacă și numai dacă schema este aciclică. O parte din propietăți sunt strâns legate de procesarea interpretărilor la baza de date.

Scheme hipergrafuri

Întrucât schema bazei de date este o mulțime de scheme relaționale, e foarte comod de a asocia schemei bazei de date hipergraf.

Vom aduce noțiunea de hipergraf. Hipergraful este analogic grafului ordinar neorientat, cu excepția că o muchie a lui nu unește numai două noduri, ci o mulțime arbitrară de noduri.

Fig.1.1 Schema bazei de date Bd={FURNIZOR CONTRACT DATĂ, FURNIZOR ARTICOL PREȚ, FURNIZOR ARTICOL CONTRACT}

Definiție: Hipergaful H este o pereche (N, E), unde N este o mulțime finită de noduri și E o mulțime de muchii (sau hipermuchii), care sunt submulțimi nevide ale mulțimii de noduri N.

Mai departe vom identifica un hipergraf numai prin menționarea muchiilor sale și implicit vom presupune că mulțimea de noduri este exact multimea nodurilor ce apartin tuturor muchiilor.

Fig.1.2 Hipergraful schemei bazei de date din fig.1.1

Schemei bazei de date îi vom pune în corespondență un hipergraf în felul următor. Mulțimea de atribute U ce formeză mulțimea universală este mulțimea de noduri, iar fiecare scehmă relațională din schema bazei de date reprezintă o muchie ce include nodurile notate cu atributele din schema relațională. Hipergraful din fig.1.2. corespunde schemi din fig 1.1.

Considerăm doua scheme ale bazelor de date fin fig 1.3. si fig.1.4, fiecare conținând trei scheme relationale. Unica diferență dintre aceste scheme este că a doua schemă a bazei de date are atribultul D în ultima schemă relațională, în timp ce prima schemă a bazei de date conține atributul E. Cu toate că acestă diferență la prima vedere pare neesențială, în realitate, schema din figura 1.3 este aciclică, iar cea din figura 1.4 este ciclică. Mai departe vom vedea că prima schemă posedă o serie de priorități dezirabile, dar a doua nu. Pentru o vizualizare a faptului că a doua schemă este ciclică considerăm hipergrafurile corespunzătoare din figura 1.5.

Fig.1.3. Schema Db1={ABC,CBD,AE}

Fig.1.4. Schema Db2={ABC,CBD,AD}

Nu vom aduce aici definiția aciclicității, vom spune doar ca primul hipergarf este aciclic, iar al doilea este ciclic. Adică vom spune ca schema Db1 este aciclică si Db2 este cilică.

Fig.1.5.Hipergarfurile schemelor Db1 și Db2

În acest capitol, nu vom examina toate propietățile pe care le posedă o schemă aciclică a bazelor de date. Acete propietăți au fost studiate de mulți cercetori în diferite context. Cel mai remarcabil fapt este însă că toate aceste propietăți sunt echivalente (în sens că ele sunt echivalente aciclicității).

Algoritmul Graham

Există un simplu algoritm de determinare a aciclicității schemei de date. Din considerente pedagogie, expunerea formală a aciclicitățtii o lăsăm pentru secțiunea următoare.

Algoritmul Graham de determinare a acilicității constă în reducerea pas cu pas a hipergrafului, conform a două reguli până nici una din reguli nu mai poate fi aplicată asupra hipergrafului, reprezentând schema bazei de date.

Dacă în urma aplicării regulilor obținem un hipergraf vid, atunci schema bazei de date este aciclică, în caz contrar este ciclică.

Fig.1.6.Hipergraful schemei Db={ABC,EDC,AEF,ACE}

Fie hipergarful H=(N, E). Regulile de reducere sunt următoarele.

EM (eliminare muchie). Muchia Ei se elimină din E, dacă există o muchie Ej, i≠j, încât Ei Ej.

EN (elinimare nod). Dacă nodul ni aparține numai unei singure muchii, el este eliminat din N, deci și din muchia din care face parte.

Exemplu 1.6. Considerăm hipergraful din fig.1.6. și să verficăm, aplicând algoritmul de mai sus, daca el este aciclic sau nu.

Pentru comoditate, vom repereenta fiecare muchie a hipergafului prin nodurile sale ampalsate pe o linie, nodurile comune ale muchiilor fiind puse unul sub altul.

Deci algoritmul cu considerarea hipergrafului:

Se aplică regulile EM și EN, până nu mai pot fi făcute modificări asupra hipergrafului.

Aplicăm regula EN pentru a înlătura nodurile izolate (ce aparțin unei singure muchii). În exemplul nostru, se înlătură nodurile B, D și F, fiind izolate. Au rămas:

Cu ajutorul regulii EM, eliminăm muchiile nodurile cărora se găsesc în alte muchii. Așadar, prima muchie AC se conține în ultima ACE și, înlăturând-o pe prima, obținem:

Similar, din aceeași cauză, înlăturăm prima, CE, și a doua, AE, muchii. Atunci obținem un hipergraf format dintr-o singură muchie:

Apelând din nou le regula EN, sunt eliminate nodurile A,C și E.

Am obținut o mulțime vidă. Deci schema bazei de date reprezentată de hipergraful din fig.1.6 este aciclică.

Teorema 1.6. Un hipergraf (sau o schemă) este aciclică, dacă aplicând algoritmul Graham obținem o mulțime vidă.

În legătură că demonstrările unor teoreme sunt destul de complexe și necesită cunoștințe suplimentare ce depășesc cardul acestei lucrări, demonstrările nu vor fi aduse. Teoremele vor fi pur si simplu numai formulate.

Fig.1.7.Hipergraful schemei Db={ABC, CDE, AEF}

Exemplu 1.6 Pentru hipergarful din fig.1.7, algoritmul Graham nu produce o mulțime vidă. Deci schema reprezentată de el este ciclică.

Într-adevăr, algoritmul începe, considerând următorul hipergraf:

După înlăturarea nodurilor izolate B, D și F obținem:

Aici aplicarea regulilor EM și EN nu mai e posibilă și, prin urmare, hipergraful considerat este ciclic. Deci ciclică este și schema bazei de date asociată acestui hipergarf.

Acest exemplu este instructiv, din punct de vedere, că el ne demonstrează că nu orice subhipergraf al unui hipergraf aciclic este aciclic. Hipergraful din fig.1.7 este un subhipergraf al hipergrafului din fig.1.6.

Prin subhipergraf al unui hipergraf vom înțelege o submulțime de muchii și noduri al hipergrafului. Acest fenomen contraintuitiv nu are loc pentru grafurile ordinare, adică nu e posibil ca un subgraf al unui graf ordinar aciclic sa fie ciclic.

În secțiunile următoare, vor fi considerate ale ipuri de aciclicitate pentru hipergrafuri, în care fenomenul de mai sus nu are loc.

Consistențe

Vom examina o proprietate a bazei de date ce este echivalentă aciclicității.

Fie schema Db={R1,……, R m} a bazei de date db= {r1,….. , r m}. În secțiunile precedente spunem că verficarea, dacă o schemă a bazei de date posedă propietatea jocțiunii fără pierderi, este o problemă laborioasă.

Definiția 1.2. Vom spune că baza de date db={r1,….. , r m} } este consistență, dacă posedă propietatea jocțiunii fără piederi și consistență câte două, dacă orice pereche ri, rj de relații din db posedă propietatea jocțiunii fără pierderi.

Fig.1.8. Baza de date db={ r1 ( ABC), r2 (BCD), r3 (AD)}

Exemplu 1.3. Baza de date din fig.1.8. este joncționabilă fără pierderi fiiindcă relațiile r1, r2, r3 sunt proiecțiile relației universale din fig.1.9. E ușor de verificat că și orice două relații din db={ r1, r2, r3 } sunt joncționabile fără pierderi.

Fig.1.9. Relația universală r(ABCD)

Exemplul 1.4. Să observăm că baza de date din fig.1.10 nu este joncționabilă fără pierderi.

Într-adevăr tuplurile < a0 , b0 , c0 > și < b0 , c0 , d0 > din r1 și r2 sunt joncționabile, formând tuplul < a0 , b0 , c0 , d0 > . Dar, proiectând tuplul < a0 , b0 , c0 , d0 > pe mulțimea de atribute AD, nu poate fi obținut nici un tuplu din relția r3 . Orice două relații din fig.1.10 sunt joncționabile fără pierderi, dar baza de date în întregime nu este joncționabila fără piederi.

Acesta are loc, fiindcă schema bazei de date Db= {ABC, BCD, AD} este ciclică.

Fig.1.10. Baza de date r= { r1, r2, r3 }

Teorema 1.2. Dacă schema este aciclică, atunci baza de date este consistentă dacă și numai dacă e consistentă câte două.

Teorema 1.3. Dacă schema este ciclică, atunci există o bază de date consistentă câte două, dar care nu e consistentă.

Deci, verificarea dacă o bază de date este jonctionabilă fără piederi, în cazul cand schema ei este aciclică, constituie o procedură simplă. Se verifică dacă relațiile ei sunt joncționabile doua câte două. Această procedură are complexitate polinomială, spre deosebire de cazul cand schema este ciclică.

Program semijoncțiune de reducere completă

Să examinăm o problemă legată de altă proprietate echivalentă noțiunii de aciclitate. Fie că avem o bază de date distribuită, geografic plasată în mai multe orașe, câte o relație în fiecare oraș.

Fig.1.11. Relația r1 în orașul O1

Fig.1.12. Relația r2 în orașul O2

De exemplu, fie relația din fig.1.11 se găsește în orașul O1 , iar cea din fig.1.12 în orașul O2.

Presupunem că fiecare din relațiile r1 și r2 conțin multe tupluri (sunt prezentate doar câteva). Pentru a obține răspuns la o interpretare ce antrenează atribute din ambele relații, se poate întâmpla că transmiterea datelor între orașe constă mult mai scump, decât prelucrarea datelor în fiecare punct aparte. Deci, vom încerca să soluționăm problema de minimizare a volumului de date, transferate de la un punct la altul.

Transmiterea relațiilor intr-un punct, apoi efectuarea operațiilor necesare pentru extragerea răspunsului la întrebare, apoi returnarea răspunsului poate fi foarte ineficientă. La joncțiunea relațiilor pot participa doar o parte de tupluri, celelalte fiind nerelevante interpretării date. În cazul relațiilor noastre la joncțiune participă doar tuplul t1 din r1 și tuplurile t1 și t2 din r2, rezultatul fiind reprezentat în fig.1.13.

Fig.1.13. Joncținea relațiilor r1 și r2

Pentru soluționarea acestei probleme se propune așa numita strategie a semijoncțiunii. Vom descrie lucrul acestei strategii pentru exemplul noastru.

Pasul 1. Se taie proieția relației r2 din orașul O2 asupra atributelor AB (acestea sunt atributele comune pentru relațiile din orașul O1 și O2 și se transmite în orașul O1. Deci, se transimte un singur tuplu < a0 b0>.

Pasul 2. Se retează relația r1 din O1, eliminând din r1 acele tupluri ce nu se joncționează cu proiecția pe AB transmisă din orașul O2. (Să se observe că rezultatul obținut nu este altceva decât semijoncținea r1 și r2, adică r1←r2│Xr2.

Pasul 3. Din oarșul O1 relația obținută se transmite în oarșul O2, unde se produce joncțiunea ei cu relația r2.

Fie bd={ r1,…, rm} o bază de date distribuită și către această baza de date este adresată o interpelare. E de dorit ca din fiecare relație să fie înlăturate tuplurile ce nu participă la joncțiunea r1 │x│…│x│ rm.

Definiția 1.3. Vom numi reducere completă a relației ri mulțimea tuturor tuplurilor din ri ce participă la joncținea │x│(bd)= r1 │x│…│x│ rm. Orice consecutivitate de atribuiri ri←ri│Xsj se numește program semikoncțiune. Dacă pentru orice bază de date bd cu schema Bd și pentru orice relație ri , programul semijoncțiune pentru relația ri produce reducerea completă a ri , atunci acest program semijoncțiune se numește program semijoncțiune de reducere completă a schemei Bd.

Deci, dacă schema Bd posedă programul de reducere completă, atunci pot fi complet reduse relațiile r1,…, rm ,înainte de a fi transimse într-un punct comun de prelucrare și calculare a joncțiunii.

Însă într-un sistem distribuit concret, răspunsul la întrebare, dacă e eficientă sau nu utilizarea unui sau altui program de semijoncțiune, depinde de extensiile relațiilor aparte. Calculând r(R)│x│s(R) ăntr-un sistem distribuit, poate fi mai puțin costisitor de transmis toate relația în punctul unde este alcoată relația s, decât la început de transmis πR∩S(s) în punctul de locație a relaței r, aopi de transmis r│Xs în punctul s. Pentru o bază de date concretă utilizarea unui program de reducere completă poate fi convenabilă, iar pentru alta- poate să nu fie eficientă.

Exemplu 1.5. Fie Db={ABC, BCD, CD} schema bazei de date reprezentată în fig 1.14. Pentru schema Db există programe de reducere completă. Unul din ele poate fi:

r2←r2│Xr1;

r3←r3│Xr2;

r2←r2│Xr3;

r1←r1│Xr2;

Rezultatul acestui program e reprezentat în fig.1.14.

Fig.1.14.Baza de date Db={ r1, r2, r3}.

Exemplul 1.6.Considerăm schema Db={ABC, BCD, CE, DE}a bazei de date prezentate la fig.1.16.Pentru Db nu există un program de reducere completă

Fig.1.15. Reducerea completă db1= {r11, r21, r31 }a bazei de date db={ r1, r2, r3} din fig.1.14.

Fig.1.16.Baza de date Db={ r1, r2, r3, r4}

Teorema 1.4. Dacă schema bazei de date este aciclică, atunci există un program semijoncțiune ce reduce complet toate relațiile în baza de date.

Cu alte cuvinte, dacă schema este aciclică, atunci strategia semijoncținuii ete utilă. Însă, situația e completamente alta în cazul, daca schema este ciclică.

Teorema 1.5. Dacă schema bazei de date este ciclică, atunci nu întotdeauna există un program semijoncțiune ce reduce complet toate relațiile în baza de date.

Remarcă. Deci, din teorema 1.4 și 1.5, deducem ca schema bazei de date este aciclică, dacă și numai dacă există un program semijoncțiune de reducere completă a relațiilor în baza de date.

Expresii joncțiune monotone

Considerăm următorul scenariu. Utilizatorul a decis să joncționeze patru relații r1, r2, r3, și r4. Poate să se întâmple urmatoarele: E1 joncționează la început r1 și r2, r1│x│r2, și joncțiunea produce spre exemplu, o relație cu o mie de yupluri. Apoi el poate joncționa rezultatul cu r3 ,adică r1│x│r2│x│r3 , și obține o relație, să zicem, cu un milion tupluri. În final joncțiunea relațiilor r1, r2, r3, și r4 , r1│x│r2│x│r3│x│r4, produce zece tupluri. Prin urmare, chiar dacă rezultatul conține doar câteva tupluri, rezultatele intermediare pot fi excesiv de mari.

Trebuie menționat că și în cazul, când relațiile bazei de date sunt complet reductibile, o alegre nereușita a joncțiunilor poate genera dimensiuni foarte mari ale rezultatelor intermediare.

Exemplul 1.7. Considerăm calculrea joncțiunii relațiilor r1│x│r2│x│r3, ale bazei de date asupra schemei Db={ABC,BCD,CDE} din figura 1.17. Dacă începem cu calurarea r1│x│r3, atunci vom obține un rezultat intermediar cu 10 tupluri, în timp ce rezultatul dinal are 6 tupluri. Însă, dacă joncțiunea începe cu r1│x│r2, atunci relația din rezultatul intermediar va conține numai șase tupluri.

Fig.1.17 Baza de date cu schema Db={ABC,BCD,CDE}

Exemplul 1.8 Considerăm calculrea joncțiunii relațiilor , r1│x│r2│x│r3│x│r4, ale bazei de date asupra schemei Db={ABC, BCD, DE, CE}, reprezentată în gif 1.18. Joncțiunea oricăror perechi de relații produce un rezultat intermediar cu mai multe tupluri decât rezultatul final. Să menționam, însă, că această bază de date este compet reductibilă.

Pe noi ne interesează schemele bazelor de date, ale căror relații complet reductibile pot fi joncționate într-o așa consecutivitate de joncțiuni perechi încât numărul tupluri în rezultatele intermediare să nu depășească numărul de tupluri în rezulatul final. Mai mult decât atât, noi dorim să avem o astfel de consecutivitate, care ar avea această proprietate pentru toate bazele de date cu schema dată. În realitate noi vom cere satisfacerea unei condiții mai stricte: de fiecare dată când se calulează joncținea, relațiile ce participă în joncțiune trebuie să fie complet joncționabile.

Fig.1.18. Baza de date db={ r1, r2, r3, r4}

Definiția 1.4. Expresie joncțiune este o expresie formată din scheme relaționale, simbolul ”│x│”și paranteze, între care orice joncțiune este binară (participă numai două scheme).

Exemplul 1.9.Dacă R1,R2,R3 și R4 sunt scheme relaționale, atunci ((R2│x│R3 )│x│( R1│x│ R4 )) este o expresie joncțiune ce presupune joncuțiunea relațiilor cu schemele R2 și R3, joncțiunea relațiilor R1 și R4 , și apoi joncțiunea ambelor rezultate intermediare.

Fie Ө o expresie joncțiune asupra tuturor schemelor din Db și db o bază de date cu schema Db. Prin Ө(db) vom subînțelege relația ce rezultă prin substituirea oricărei scheme Ri din Ө cu ri , unde ri ϵ db și are schema Ri .De exemplu, dacă db={ r1, r2, r3, r4} și Ө este expresia joncțiune (R2│x│(R3│x│ R2 )),unde r2 și r3 au schemele respectiv R2 și R3, atunci Ө(db) este relația (r2│x│( r3│x│ r2 )),adică relația r2│x│r3.

O subexpresie a expresiei joncțiune se definește în mod obișnuit.

Definiția 1.5. Fie Ө o expresie joncțiune, conținând scheme relaționale din Db și fie db o bază de date cu schema Db. Vom spune că Ө este monotonă în raport cu db, dacă pentru orice subexpresie (Ө1│x│Ө2 ) din Ө relațiile Ө1(r) și Ө2(r) sunt consistente.

Intuitiv, Ө este monotonă în raport cu db, dacă nici un tuplu nu este pierdut, când se execută joncțiune binară din Ө (r).

Exemplul 1.10.Expresia ((R2│x│ R3 )│x│( R1│x│ R4 )) este monotonă în raport cu db={ r1, r2, r3, r4},unde ri are schema Ri, 1≤i≤4,dacă

(a) r2 și r3 sunt consistente;

(b) r1 și r4 sunt consistente;

(c) (r2│x│ r3 )│x│( r1│x│ r4 ) sunt consistente.

Definiția 1.6. Vom spune că expresia Ө este monotonă, dacă ea este monotonă în raport cu orice bază de date consistentă câte două relații cu scheme din Db. Dacă Ө include exact schemele din Db, atunci spunem că Db are expresie joncțiune monotonă.

Expresiile monotone asigură utilizarea eficientă a spațiului de memorie în timpul joncțiunilor, fiindcă nici o joncțiune intermediară nu are mai multe tupluri decât joncțiunea finală.

Teorema 1.6. O schemă a bazei de date este aciclică, dacă și numai dacă există o expresie joncțiune monotonă.

Scheme α- aciclice

Noțiunea de aciclicitate, utilizată până aici, nu e altceva decât noțiunea de α- aciclicitate.

Definiția 1.7. Fie H=(N, E) un hipergraf și n1 și n2 sunt două noduri din N. Vom numi cale din n1 în n2 (în hipergraful H) o consecutivitate de k≥1 muchii (E1,…,Ek), unde:

(i) n1Є E1 ;

(ii) n2Є Ek ;

(iii) Ei∩Ei+1 ≠Ø dacă 1≤i≤k.

Vom spune , de asemenea, că consecutivitatea (E1,…,Ek) este calea din E1 în Ek.

Definiția 1.8. Două noduri ale hipergrafului H sun conexe, dacă există o cale din unul în altul. O mulțime de noduri sau muchii sunt conexe, dacă orice două noduri sau muchii sunt conexe. Componenta de conexiune este mulțimea maximală de muchii conexe.

Exemplul 1.11.Considerăm hipergraful H din fig.1.19.Muchiile ABC,BCD,DE formează o cale din A în E și din ABC în DE, de aceea A și E, precum și ABC și DE sunt conexe. Mulțimile {ABC, BCD, DE } și {IJ, JKL, IKL} sunt componente de conexiune.

Fig.1.19 Un hipergraf cu două componente de conexiune

Noi vom examina hipergrafurile constituite dintr-o singură componentă de conexiune. Toate construcțiile și rezultatele ulterioare se generalizează și asupra hipergarfurilor cu mai multe componente.

Definiția 1.9. Fie hipergraful H=(N, E). Hipergraful redus (N, E1) se obține, eliminând din E toate muchiile ce se conțin în alte muchii. Hipergraful se numește redus, dacă el este egal cu reducerea lui, adică nu poate fi eliminată nici o muchie.

Definiția 1.10. Fie E1 o mulțime de muchii și fie N1 o mulțime de noduri ce apar în una sau mai multe muchii din E1. Vom spune că E1 este închisă, dacă pentru orice E1 din hipergarf există o muchie E2 în E1, încât E1∩ N1E2

Exemplul 1.12. Mulțimea de muchii {G,H,I} din fig. 1.20 este o mulțime închisă. Așadar, intersecția muchiei K cu G∪H∪I se conține în muchia H; similar, intersecția muchiei J cu G∪H∪I se conține în G. Însă, mulțimea {L,M} nu este închisă, datorită nodurilor x și y. Intersecția muchiei I cu L∪M nu se conține nici în L nici în M.

Fig .1.20

Să menționăm că orice mulțime de muchii într-un graf ordinar neorientat este închisă.

Definiția 1.11. Fie E1 o mulțime conexă, redusă de muchii și fie E1 și E2 în E1 .Fie Q=E11∩E2. Vom spune că Q este o mulțime de articulație pentru E1 ,dacă în rezultatul eliminării lui Q din orice muchie din E1 mulțimea { Ei \Q| Ei ϵ E1}\ {Ø} nu este conexă.

Definiția 1.12. Un hipergraf redus este α – aciclic, dacă orice mulțime închisă și conexă de cel puțin trei muchii are o mulțime de articulație. Un hipergraf se spune că este α – aciclic, dacă reducerea lui este α – aciclică.

Exemplul 1.13. E simplu de verificat că hipergraful din fig. 1.6 este α – aciclic. Muchiile lui sunt ABC, CDE, EFA și ACE. O mulțime de articulație pentru toată mulțimea de muchii este ABC∩ACE=AC , fiindcă în urma eliminării lui A și C din fiecare muchie obținem mulțimea de muchii B, DE, EF și E ce nu sunt conexe (B nu e conexă cu celelalte). Să menționăm că mulțimea de muchii { ABC, CDE, AFA} nu are nici o mulțime de articulație. Însă, ea nu este nici închisă, deci nu este nici o contradicție cu presupunerea noastră că hipergraful din fig.1.6 este α – aciclic.

Aici putem face o legătură dintre noțiunile de dependențe joncțiune și aciclicitate.

Definiția 1.13. Vom spune că dependența joncțiune |x|(R1, …, Rm) este α – aciclică, dacă α – aciclic este hipergraful format din mulțimea de muchii { R1, …, Rm }.

În calitate de concluzie, asupra celor spuse de la începutul acestui capitol, putem formula următoarea teoremă.

Teorema 1.7. Următoarele condiții asupra schemei bazei de date Db={ R1, …, Rm } sunt echivalente:

Schema Db este α – aciclică.

Algoritmul Graham produce o mulțime vidă de muchii.

Orice bază de date consistentă câte două asupra Db este consistentă.

Există un program semijoncțiune de reducere completă a bazei de date cu schema Db.

Schema Db are o expresie joncțiune monotonă.

Scheme β – aciclice

După cum se știe, un subhipergraf este o mulțime de muchii ale unui hipergraf. Similar, o subschemă a unei scheme a bazei de date este o submulțime de scheme relaționale din schema bazei de date. Am observat că subhipergraful unui hipergraf α- aciclic nu întodeauna este α- aciclic. Drept exemplu pot servi hipergrafurile din fig. 1.6. și fig. 1.7.

Ne interesează clasa de hipergrafuri ale căror subhipergrafuri sunt α-aciclice. Astfel de hipergrafuri se numesc β- aciclice. Importanța acestui tip de aciclicitate e greu subschemă a bazei de date. Deci și interpelările ce implică o parte din schemele relaționale vor fi procesate în mod eficient.

Definiția 1.14. Fie (E1, E2, …,Em, Em+1) o consecutivitate de muchii ale hipergrafului H=(N, E). Presupunem că muchiile E1, E2, …,Em sunt distincte și Em+1 =m≥3, dacă Ei∩Ej ≠Ø numai în cazul când j=i+1.

În fig.1.21, este reprezentat un ciclu simplu, ce constă din 6 muchii.

Fig.1.21. Un ciclu simplu

Definiția 1.15. Consecutivitatea de muchii (E1, E2, …,Em, Em+1) ale hipergrafului H=(N,E) se numește β-ciclu, dacă consecutivitatea (E11, …,Em1, Em+11) este ciclu simplu, unde Ei1 = Ei \ X, 1≤ i ≤ m șI X= E1∩E2∩ …∩Em.

Evident, orice ciclu simplu este un β- ciclu.

Definiția 1.16. Hipergraful H=(N,E) este β- aciclic, dacă el nu conține un β- ciclu , în caz contrar el este β- ciclic. Schema bazei de date Db={ R1, R2, …,Rm} este β- aciclică (β- ciclică), dacă hipergraful corespunzător este β- aciclic (β- ciclic).

Definiția 1.17.Consecutivitatea (E1,n1, E2,n2, …,Em,nm, Em+1) de muchii și noduri ale hipergrafului H=(N,E) se numește β- ciclu slab, dacă sunt satisfăcute condițiile:

(i) n1, n2, …, nm sunt noduri distincte ale lui H;

(ii) E1, E2, …,Em sunt muchii distincte ale lui H;

(iii) m≥3;

(iv) ni ϵEi∩ Ei+1, și niEj pentru orice j≠i, i+1,1≤i≤m.

Fig.1.22. β-ciclu este un β-ciclu slab.

Teorema 1.8. β-ciclu este un β-ciclu slab.

Demonstrație. Fie consecutivitatea (E1, E2, …,Em, Em+1) e un β-ciclu . Atunci E1, E2, …,Em , sunt distincte, Ei≠Ej ,m≥3 și pentru orice doua muchii vecine Ei și Ei+1, 1≤i≤m, există un nod ni în Ei ∩Ei+1 ,și niEj pentru orice j≠i, i+1.

Afirmația inversă nu este corectă.

Exemplul 1.14. În fig.1.22 consecutivitatea (E1,n1, E2,n2, …,E4,n4 , E1) este un β-ciclu slab, deoarece nodul yϵE1 ∩ E3∩ E4 și yE2.

Definiția 1.18. Consecutivitatea de muchii (E1, E2, …,Em, Em+1) ale hipergrafului H=(N,E) se numește Graham-ciclu, dacă sunt satisfăcute condițiile:

(i) E1, E2, …,Em sunt muchii distincte și E1=Em+1 ;

(ii) m≥3;

(iii)∆i= Ei∩ Ei+1≠Ø,1≤i≤m;

(iv) pentru orice 1≤i, j≤m, unde i≠j, mulțimile ∆i și ∆j sunt incomparabile, adică i j și j i.

Fig.1.23. Un Graham-ciclu

Teorema 1.9. β-ciclu slab este un Graham-ciclu.

Demonstrație. Fie (E1,n1, E2,n2, …,Em,nm, Em+1) un β-ciclu slab. Deoarece condițiile (i),(iv) din definiția β-ciclului slab, implică condițiile (iii), (iv) din definiția Graham-ciclului, iar condițiile (ii), (iii) din definiția 1.17 coincid cu condițiile (i) ,(ii) din definiția 1.18, atunci consecutivitatea (E1, E2, …,Em, Em+1) este Graham-ciclu.

Afirmația inversă nu este corectă.

Exemplul 1.15. În fig 1.23 consecutivitatea (E1, E2,E3, E4 ,E5 ,E1) este un Graham ciclu, dar nu este un β-ciclu slab. Unicele β-cicluri slabe sunt (E2,E3, E4 ,E2 ) și (E1,E4 ,E5 ,E1).

Definiția 1.19.Două muchii ale hipergrafului H=(N,E) se numesc vecine, dacă au noduri comune. Două muchii E2 și E3 sunt independente în raport cu muchia E1, dacă ele sunt vecine muchiei E1 și mulțimile E1∩E2 și E1∩E3 sunt incompatibile.

Menționăm că noțiunea de independență are sens numai atunci, când este vorba de două sau mai multe muchii vecine muchiei date. În particular, muchiile care nu au deloc sau au numai un singur vecine, nu au muchii vecine independente.

Definiția 1.20. Fie hipergraful H=(N,E) și FE. Mulțimea de muchii F se numește ciclu independent, dacă ea este conexă și fiecare muchie Ei ϵF are cel puțin două muchii vecine independente, Ej ,Ek ϵF.

O particularitate a ciclului independent constă în faptul că el e conceput ca o mulțime de muchii, și nu ca o consecutivitate de muchii.

Teorema 1.10. Mulțimea de muchii ce formează un ciclu Graham este un ciclu independent.

Demonstrație. Fie consecutivitatea (E1,E2, …,Em, Em+1) un ciclu Graham. Mulțimea de muchii {E1 ,…,Em} este conexă, deoarece ∆j= Ej∩ Ej+1≠Ø , 1≤j≤m. Fiecare muchie Ek, 2≤k≤m, are în calitate de muchii vecine independente pe Ek-1 și Ek+1 , fiindcă kk+1 și k+1k .Pentru muchia E1, muchiile vecine independente sunt E2 și Em.

Afirmația inversă nu este corectă.

Exemplul 1.16. În fig.1.24, mulțimea de muchii {E1 ,E2 , E3 , E4 , E5} este un ciclu independent, pe când Graham-cicluri în acest hipergraf sunt (E1 ,E2 , E3, E1 ) și (E3 , E4 , E5 , E3 ).

Fig.1.24. Un ciclu independent

Din teoremele 1.8, 1.9 și 1.10 și exemplele 1.14, 1.15, 1.16 urmează că corelația dintre noțiunile de β-ciclu, β-ciclu slab, Graham-ciclu și ciclu independent este cea din fig. 1.25.

Fig.1.25. Interpendența dintre cicluri

Următoarea teoremă poate fi pusă la baza algoritmului de testare a β-aciclicității. Trebuie menționat că cel mai eficient algoritm de determinare, dacă o schemă a bazei de date este β-aciclică, se bazează pe noțiunea de ciclu independent. Demostrarea teoremei 1.11 și descrierea algoritmului nu se aduce.

Teorema 1.11 Hipergraful H=(N,E) este β-ciclic, dacă și numai dacă el conține

(a)un β-ciclic, sau

(b)un β-ciclic slab, sau

(c)un Graham ciclu, sau

(d)un ciclu independent.

Scheme y-aciclice

O schemă a bazei de date este y-aciclică (y-ciclică), dacă hipergraful corespunzător este y-aciclic (y-ciclic).

Definiția 1.21. Consecutivitatea (E1,n1, E2,n2, …,Em,nm, Em+1) se numește y-ciclu în hipergraful H=(N,E), dacă

(i)n1 ,…, nm sunt noduri distincte în H;

(ii)E1 ,…, Em ,sunt muchii distincte în H și Em+1 = E1 ;

(iii)m>=3;

(iv)niϵ Ei ∩ Ei +1 ,1≤i≤m și niEj unde j≠1,i+1 pentru 1≤i≤m.

Să observăm că singura diferență dintre definiția y-ciclu slab este că ,condiția „1≤i≤m”,din definiția 1.17 (iv) este substituită de condiția „1≤i≤m” în definiția 1.21 (iv).Deseori e comod să ne referim la y-ciclu, luând în considerație numai consecutivitatea de muchii, făcând abstracție de noduri.

Definiția 1.22 Un hipergraf este y-ciclic, dacă conține cel puțin un y-ciclu.

Fig.1.26 Un hipergraf y-ciclic

Exemplul 1.17. În figura 1.26. nu este reprezentat un hipergraf y-ciclic, dar β-acilic. Într-adevăr, consecutivitatea (E, x, F, y, G, z, E) este un y-ciclu. Pe de altă parte, E∩F∩G=y și eliminând nodul y din fiecare muchie nu obținem un ciclu. Deci consecutivitatea (E, x, F, y, G, z, E) nu este un β-ciclu.

Cea mai elegantă caracteristică a unui hipergraf y-ciclic este formulată de următoarea definiție.

Definiția 1.23. Un hipergraf este y-ciclic, dacă conține un y-ciclu de lungimea 3, sau un ciclu simplu.

Exemplul 1.18. Un ciclu simplu și y-ciclu de lungime 3 sunt prezentate în fig.1.21 și 1.26 respectiv. Să menționăm, apelând la hipergraful din fig.1.26, că într-un y-ciclu de lungime 3 există cel puțin un nod în intersecția E∩F∩G, cel puțin un nod E,F,G nu pot fi. Deci, dacă există un y-ciclu de lungime 3, atunci sau are forma ca în fig.1.26 sau ca în fig.1.21, numai cu trei muchii.

Definiția 1.24. Un hipergraf este y-ciclic, dacă el conține o pereche E,F de muchii nondijuncte incomparabile și în hipergraful ce se obține din excluderea intersecției E∩F, din orice muchie restul muchiei E este conexă cu restul muchiei F.

Să arătăm că aceste trei definiții ale hipergrafului y-ciclice sunt echivalente.

Teorema 1.12. Definițiile 1.22,1.23 și 1.24 sunt echivalente. Demonstrație. Vom arăta că (1.22)(1.23)(1.24)(1.22), unde prin ”(i)(j)” subînțelegem că, dacă un hipergraf este y-ciclic conform definiției (i), atunci este y-ciclic conform definiției (j).

(1.22)(1.23).Fie H este y-ciclic, conform definiției 1.22 și să arătăm că H e y-ciclic și conform definiției 1.23.Fie că (E1,n1, E2,n2, …,Em,nm, Em+1) este un y-ciclic de lungime minimală.

Dacă m=3, atunci afirmația e demonstrată.

Presupunem că m≥4. Să arătam că ciclul de mai sus e un ciclu simplu, adică muchiile vecine se intersectează și muchiile nonvecine din consecutivitate nu se intersectează. Muchiile vecine se intersectează conform definiției y-ciclu. Să demonstrăm că muchiile ce nu sunt vecine nu se intersectează.

Să arătăm că E1 nu intersectează un nonvecin. Presupunem că se intersectează. Găsim un k(3≤k<m) cel mai mic posibil pentru care E1∩Ek≠Ø. Fie vϵE1∩Ek. Atunci (E1, n1, … Ek-1 , nk-1 , Ek ,v, E1 ) e un y-ciclu mai mic decât cel ipotetic. Aceasta e o contradicție.

Acum să arătăm că E2 nu intersectează un nonvecin. Pentru aceasta presupunem că vϵE2∩Ek unde 1≤k≤m. Avem două cazuri.

Cazul 1. vϵE3 .Cunoaștem că E1, deci E1 nu intersectează nonvecinul E3 .Găsim r cel mai mare posibil pentru care vϵEr. E ușor de observat că (E1, n1, E2, n2,v, Er,…, Em, nm, E1) este un y-ciclu mai mic decât cel ipotetic. Deci e contradicție.

Cazul 2. E3.Găsim r cel mai mic pentru care vϵEr .E ușor de văzut că (Er, v, E2 , n2 , E3, n3 ,…, Er ) este un y-ciclu mai scurt decât cel ipotetic. Contradicție.

Am arătat că nici E1 și nici E2 nu intersectează nonvecinii. Găsim j cel mai mic pentru Ej intersectează un nonvecin Ek : fie vϵEj∩Ek .Atunci 3≤j, și j+2≤k≤m. E ușor de văzut că (E1, n1, E2, n2,…, Ej ,v, Ek,…, Em+1) este un y-ciclu mai scurt decât cel ipotetic. Această contradicție implică (1.22)(1.23).

(1.23)(1.24).Fie H e y-ciclic conform definiției 1.23. Vom arăta că H e y-ciclic, conform definiției 1.24. Fiindcă H e y-ciclic conform definiției 1.23, H conține un ciclu de lungime 3 sau un ciclu simplu.

Presupunem că H conține un y – ciclu de lungime 3 și fie acest ciclu (E1, n1, E2, n2, E3,n3,E1). E ușor de verificat că H este y-ciclic, conform definiției 1.24, (unde E și F din fig.1.26 sunt E1 și E3 respectiv).

Acum presupunem că H conține un ciclu simplu. Presupunând că E și F sunt muchii nonvecine în ciclul simplu, vedem că H este y-ciclic, conform definiției 1.24.

(1.24)(1.21).Fie H e y-ciclic conform definiția (1.24). Vom arăta că H e y-ciclic conform definiției 1.21. Luăm E și F ca în definiția 1.24. și fie că Q=E∩F. Există o consecutivitate (E1,…, Em) de muchii ce satisface condițiile:

(i) E1=E,

(ii) Em=F,

(iii) (Ei ∩ Ei+1 )\Q ≠Ø, unde 1≤i≤m-1.

Presupunem că muchiile sunt selectate în așa fel că (i)-(iii) sunt satisfăcute pentru cel mai mic m. Dacă m=2, atunci conform (ii) E2=F. Atunci E1 ∩ E2 =Q, ce contrazice condiției (iii) pentru i=1. Prin urmare m≥3. Conform (iii), pentru orice 1≤i≤m-1 în (Ei ∩Ei+1 ) \Q se găsește câte un nod. Punem Ei+1 egal E(=E1) și nmE∩F (din presupunerea că E∩F≠Ø). Să arătăm că consecutivitatea (E1, n1, E2, n2,…, Em ,nm ,E1) este y-ciclu. Nodul n1 nu se găsește nici într-o muchie E3, …, Em-1, conform minimalității lui m (deci, dacă n1E1, unde 3≤i≤m-1, atunci consecutivitatea E1 , Ei , Ei+1 ,…, Em ,trebuie folosită în locul (E1 , E2 ,…, Em).Mai departe, n1…. Em=F. Deci n1E= E1 ;dar n1≠Ø=E∩F. Deci n1 se găsește în E1 și E2 , și nu în Ei , j≠1,2. Similar, n1 este în Ei și Ei+1 dar nu în alt Ei, pentru 1≤i≤m-1. În particular toate nodurile n1,…, nm-1 sunt distincte. În afară de aceasta nm este distinct de toate nodurile n1 ,…, nm-1 , fiindcă nmQ și ni….Q, pentru 1≤i≤m. Prin urmare, toate nodurile n1 ,…, nm sunt distincte. Din condiția că m e minimal urmează că toate muchiile E1,…,Em sunt distincte. Aceasta e suficient pentru a spune că (E1, n1, E2, n2,…, Em, nm, Em+1) este y-ciclu. Deci H e y-ciclic, conform definiției 1.22.

Propietăți ale schemelor y-aciclice

De noțiunea de y-aciclicitate sunt legate o serie de propietăți ale schemelor, proprietăți ce sunt echivalente acestei noțiuni. Vom examina doar trei proprietăți. Pentru simplitate, vom considera numai schemele bazelor de date hipergrafurile căror constau dintr-o singură componentă de conexiune.

(1)Orice expresie conexă de joncțiune asupra schemei bazei de date este monotonă. Fie o schemă conexă Db. Echivalența acestei proprietăți cu y-aciclicitate prezintă interes prin analogie cu teorema 1.6, care ne spune că schema bazei de date Db este α-aciclică, atunci și numai atunci când există o expresie joncțiune monotonă asupra Db. Deci echivalența se formează în felul următor. Schema bazei de date Db este y-aciclică, atunci și numai atunci, dacă orice expresie joncțiune asupra Db este monotonă (cuvântul „conexă” a fost omis, fiindcă numai o joncțiune monotonă poate fi conexă).Să observăm diferența dintre aceste două afirmații :în cazul α-aciclicității există o asemenea expresie joncțiune monotonă, pe când în cazul y-aciclicității orice expresie joncțiune este monotonă.Proprietatea de față garantează o mare libertate în luarea joncțiunilor. Așadar, fie db este o bază de date asupra unei scheme ce se supune propietății (1) și este considerată câte două. Presupunem că utilizatorul dorește să facă joncțiunea a unei submulțimi de relații din baza de date db. Conform proprietății (1) el poate joncționa relațiile oricum dorește fără a ”dăuna” și este singur că a acționat în mod eficient. Prin ”fără a dăuna” subînțelegem că nici o joncțiune nu va antrena relații cu scheme disjuncte, adică nu va calcula produsul cartezian. Prin ”mod eficient”, subînțelegem că nici o joncțiune intermediară nu va avea mai multe tupluri decât joncțiunea finală.

(2) Fie schema Db={R1,…,Rm}.Dependența joncțiune |X|( R1,…,Rm)presupune că orice submulțime conexă din Db posedă proprietatea joncțiunii fără pierderi. Adică orice dependență joncțiune inclusă |X|( S1,…,Sk), unde {R1,…,Rm}…..{S1,…,Sm},are proprietatea joncțiunii fără pierderi.

Să menționăm că această proprietate nu e caracteristică schemelor α-aciclice, fiindcă nu orice hipergraf α-aciclic este y-aciclic.

Exemplul 1.19. Hipergraful din fig.1.2 este α- aciclic este y-ciclic.

(3) În orice bază de date consistentă există o singură asociere între atributele unei mulțimi de atribute.

Fie db={ r1,…,rm } o bază consistentă cu schema DB={R1,…,Rm}. Prin asocierea atributelor din X,unde XR1 , …, Rm, subînțelegem o relație X(ri1|x|…|x|rik), unde {ri1,…,rik}db, XRi1,…,Rik și {Ri1, …, Rik} este conexă. Adică careva din relațiile bazei de date db sunt joncționate (unde nici o joncțiune nu formează produsul cartezian) și apoi rezultatul proiectat pe mulțimea de atribute X. Proprietatea (3) ne spune că relația rezultat este unică.

Fig.1.27

Exemplul 1.20. Fie schema bazei de date constă din trei scheme relaționale:serv_funcț cu atributele FUNCȚ (pentru ”funcționar”), DEPT (pentru ”departament”) și SAL (pentru ”salariu”); schema relațională info_dept cu atributele DEPT, ORAȘ și MGR (pentru ”manager”); și schema dom_funcț cu atributele FUNCȚ, STRADĂ, ORAȘ. În fig.1.27 este reprezentată baza de date cu un tuplu în fiecare relație.

În acest exemplu sunt două asocieri {FUNCȚ, ORAȘ} distincte. Una, care presupune un tuplu <Popescu, Craiova> ce ne arată orașul unde funcționarul își are serviciul și alta, cu tupul <Popescu, Calafat> ce ne indică locul de trai al funcționarului. Să menționăm că schema bazei de date este y-ciclică, chiar α- aciclică.

Să renumim atributul ORAȘ din schema info_drep cu OR_SERV și atributul ORAȘ din schema dom_funcț cu OR_DOM (vezi fig.1.28). Acum avem o singură asociere {FUNCȚ, OR_SERV}cu tuplul <Popescu, Craiova>, și o singură asociere {FUNCȚ, OR_DOM} cu un tuplu <Popescu, Calafat>.

Schema bazei de date din fig.1.28 este y-aciclică.

Dat fiind faptul că asocierea dintre atribute într-o schemă y-ciclică e unică se simplifică esențial forma interpelărilor. Cea mai simplă interpelare în limbajul SQL de găsire a tutror funcționarilor ce își au serviciul în orașul Craiova este

SELECT FUNCȚ

FROM serv_funcț, info_dept

WHERE serv_funcț. DEPT=info_dept.DEPT

AND info_dept.OR_SERV=”Craiova”

Dar, ținând cont de proprietatea (3), interpelarea poate fi formulată astfel:

SELECT FUNCȚ

WHERE OR_SERV=”Craiova”

Trebuie menționat că avantajele nu constau numai într-o sintaxă mai simplă a interpelărilor, dar și în posibilitatea SGBD-ului de a optimiza procesul de căutare a răspunsurilor cu o flexibilitate mai mare. Sistemul poate exploata faptul că oricare nu ar fi relațiile în joncțiune, joncțiunea va fi monotonă și deci eficientă.

Unele sisteme relaționale folosesc un fișier special care să determine ce relații trebuie să participe la joncțiune pentru a răspunde unei interpelări. Dacă schema bazei de date este y-aciclică, adică posedă proprietatea (3), nu e nevoie de un așa fișier.

Fig.1.28

Algoritm de testare a y-aciclicității

Următorul algoritm poate fi utilizat pentru verificarea dacă o schemă este sau nu aciclică. El este similar celui de testare a schemelor α-aciclice.

Algoritmul constă în aplicarea în orice ordine a regulilor (a) – (e) până nu mai poate fi aplicată nici o regulă.

(a)Nodul izolat (ce aparține unei singure muchii) se elimină din muchie.

(b) Muchia unitară (ce constă dintr-un singur nod) se elimină.

(c) Muchia vidă se elimină.

(d) Dacă două muchii conțin aceleași noduri, se elimină una din muchii.

(e) Dacă două noduri aparțin acelorași muchii, atunci un nod din cele două se elimină din toate muchiile ce le conțin.

Bineînțeles că aplicarea are un număr finit de pași. Dacă rezultatul final este o mulțime vidă de muchii, atunci hipergraful este y-aciclic.

Fig.1.2

Exemplul 1.20. Să aplicăm algoritmul asupra hipergrafului din fig.1.29. Pentru a simplifica lucrul algoritmului vom considera implicit utilizarea regulilor (d) și (c).

La începutul hipergrafului din fig.1.29 se prezintă:

B C D E F

A B C D

C

C D

E F

Nodul A e izolat și muchia {C} e unitară, deci conform regulilor (a) și (b) sunt eliminate. Au rămas muchiile:

B C D E F

B C D

C

C D

E F

Nodurile E și F aparțin împreună acelorași muchii (BCDEF și EF) și conform regulii (e) nodul F se elimină din ambele muchii. Similar, nodurile C și D aparțin acelorași muchii. Se elimină nodul D din cele trei muchii. Au rămas muchiile:

B C E

B C

C

E

Se elimină a treia și a patra muchie, fiindcă sunt unitare:

B C E

B C

Nodul E e izolat. După eliminarea nodului E au rămas muchiile:

B C

B C

Aceste două muchii sunt identice. Conform regulii (d) o muchie se elimină:

B C

Întrucât ambele noduri sunt izolate, ele sunt eliminate. În rezultat s-a obținut o mulțime vidă de muchii, deci hipergraful din fig.1.29 este y-aciclic. Deci și schema asociată lui este y-aciclică.

Scheme Berge-aciclice

Vom considera în această secțiune unul din cele mai puternice tipuri de aciclicitate ale schemelor bazei de date și anume Berge-aciclicitatea.

Definiția 1.25. Fie hipergraful H=(N,E). Consecutivitatea (E1, n1,E2,…,Em ,nm , Em+1) se numește Berge-ciclu, dacă sunt satisfăcute condițiile:

(i)n1,…, nm sunt noduri distincte în N;

(ii) E1,…, Em sunt distincte în E și E1=Em+1;

(iii) m>1;

(iv) ni , ni+1ϵE1, 0<i<m+1.

Definiția 1.26. Hipergraful H=(N,E) este Berge-ciclic, dacă conține cel puțin un Berge-ciclu, în caz contrar e Berge-aciclic.

Exemplul 1.21. Hipergraful din fig.1.30 este Berge-ciclic , dar y-aciclic. Un Berge-ciclu este consecutivitatea (ABC, B, BCD, C, ABC). Consecutivitatea dată nu e y-ciclu, fiindcă sunt implicate în ea numai două muchii.

Fig.1.30 Un hipergraf Berge-ciclic

Exemplul 1.21 ne sugerează următoarea teoremă.

Teoremă 1.13. Dacă o pereche de muchii ale unui hipergraf au două sau mai multe noduri comune, atunci hipergraful este Berge-ciclic.

Demonstrație. Afirmația rezultată imediat din definiția 1.25.

O procedură de testare, dacă o schemă este Berge-aciclică, constă în aplicarea următoarelor două reguli:

(a)Nodul izolat (ce aparține unei singure muchii) este eliminat din muchie;

(b) Muchia unitară (ce constă dintr-un singur nod) sau vidă se elimină.

Algoritmul sfârșește, dacă nu mai poate fi aplicată nici una din reguli. Dacă algoritmul produce o mulțime vidă de muchii, atunci hipergraful inițial este Berge-aciclic, în caz contrar e Berge – ciclic.

Scheme Ω – aciclice

În această secțiune, vom defini o subclasă a hipergrafuri, ω – aciclic și vom dovedi cu această clasă noțiunea de hipergraf aciclic utilizat de grafic teoreticienii, este echivalent cu această noțiune care este utilizat de către teoreticienii de baze de date.

În ultima secțiune, putem dovedi două noi caracterizări pentru hipergrafuri ω – aciclice. Vom demonstra mai întâi leme și exemple pentru a arăta că noțiunea de hipergrafuri aciclice utilizate în grafic teorie nu este echivalentă cu cea utilizată în una din teoriile bazelor de date.

Lema 3.1. Fie H=(X,Ɛ) un hipergraf. H este aciclic doar dacă |Ei∩Ej|≤1 pentru fiecare pereche de margini Ei , Ej Є Ɛ.

Dovada: Să presupunem că H este aciclic, și să își asume dimpotrivă, că există o pereche de margini Ei ≠Ej Ei , Ej Є Ɛ, astfel încât , |Ei∩Ej|>1.Asuma că {xi,xj}~Ei∩Ej ,astfel există xi, xj în Ei∩Ej . Considerăm secvența (xi , Ei , xj , Ej , xi). Prin urmare, acesta este un ciclu de lungime 2. Astfel H este ciclic. Acest lucru contrazice ipoteza. Dovada este finalizată.

Lema 3.2. Fie HR =(X,Ɛ) un hipergraf conectat la o schema a bazei de date R. În cazul în care Graham algoritmul de reducere nu reușească pe HR. Atunci rezultatul algoritmului reducere Graham pe HR (partea care rămâne din HR) are cel puțin trei hipergrafuri distincte și trei noduri distincte.

Dovada. Să presupunem contrariul, partea rămasă din HR are doar două margini ale Ei1≠Ei2 . Astfel, există xi1Є Ei1, xi2ЄEi2 ,și putem elimina xi1 din Rn .Acum Ei1~Ei2 și Ei1 poate fi îndepărtat prin Re . Partea care a rămas din HR are doar o margine și o putem elimina. Deci, HR este gol, ceea ce contrazice faptul că algoritmul de reducere Graham nu reușește pe HR .

Altfel, dacă partea rămasă din HR are doar două noduri, acesta poate să nu aibă trei hipergrafuri distincte. Lema este demonstrată.

Lema 3.3.Fie HR=(X,Ɛ) un hipergraf conectat la o schema a bazei de date R. Dacă HR este aciclic conform definiției 2.2, atunci este aciclic în conformitate cu definiția din teorii bazei de date relaționale.

Dovada. Să presupunem că HR este aciclic conform definiției 2.2 (G- definition), acum avem de demonstrat că reducerea Graham în HR, adică este aciclic în funcție de R-definition.

Să presupunem, dimpotrivă, că reducerea Graham nu reușește pe HR . In conformitate cu Lema 3.2, partea rămasă din HR are cel puțin trei hipergrafuri și trei noduri, și anume Ei1≠Ei2≠ Ei3 și xi1 ≠ xi2 ≠ xi3 (În cazul în care are mai mult de trei, dovada este similar). Fiecare nod xij ar trebui să fie în cel puțin două hipergrafuri, dacă nu este așa, acest nod poate fi eliminat prin RN regulă de reducere Graham. Putem construi o secvență în care (xi1, Ei1 , xi2 , Ei2 , xi3 , Ei2 , xi4) în care xi j , xij+1ЄEij (j=1,2,3). Astfel avem xi2 Є Ei1∩Ei2 și xi3 Є Ei2∩Ei3. Deoarece HR este aciclic (prin G -definition),apoi prin Lema 3.1 aplicat hipergrafului conectat HR există |Ei∩Ej|=1 pentru fiecare pereche de marginile Ɛ. Cu toate acestea, există doar xi2 în Ei1∩Ei2 și numai xi3 în Ei2∩Ei3, așa xi1 , xi4 ar trebui să fie în Ei1∩Ei3, se aplică din nou Lema 3.1, avem xi1= xi4. Vedem că îndeplinește secvența de mai sus condițiile din definiția 2.2, astfel că este un ciclu de lungime 3. Acest lucru contrazice ipoteza că HR este aciclic. Dovada este finalizată.

Exemplul 3.1. Considerăm hipergraful HRb (Fig. 2) pentru sistemul bazei de date Rb = {ABC, AF E,EDC, AEC}. Deoarece acest hipergraf are ciclul de lungime 3 (A, {AFE}, E, {EDC}, C, {CBA}, A), astfel, este ciclică conform definiției 2.2. Pe de altă parte, este ușor să verifice dacă reducere Graham în HR. Prin urmare, noțiunea de hipergrafuri aciclice utilizate de grafic teoreticieni nu este echivalent cu definițiile pentru noțiunea, utilizate în teoriile de baze de date.

Definiția 3.1. Fie H=(X,Ɛ) un hipergraf. H se numește ω – hipergraf dacă |Ei∩Ej|≤1 pentru fiecare pereche de margini distincte Ei,Ej Є Ɛ.

Dacă un ω – hipergraf H este aciclic (ciclic, respectiv) atunci H se numește ω – aciclic (ω – ciclic, respectiv) hipergraf.

O schema a bazei de date R este ω – aciclic (ω – ciclic, respectiv), în cazul în care hipergraful pentru R este ω – aciclic (ω – ciclic, respectiv).

Teorema următoare va arăta că, cu ω – hipergraf noțiunea de aciclic utilizat de grafic

teoreticienii este echivalentă cu cea utilizată de teoreticienii de baze de date.

Teoria 3.1. Fie H=(X,Ɛ) un ω – hipergraf , cele două condiții de mai jos sunt echivalente:

H este aciclic în conformitate cu G-definiția din teoria grafurilor;

H este aciclic în conformitate cu R-definiția în teoriile de baze de date.

Dovada. Va proceda prin următoarele etape:

=> (2) Demonstrația este imediată din Lema 3.3.

=> (3) Să presupunem că H este aciclică în conformitate cu R-definiția, astfel reducerea Graham în hipergraf H. Trebuie să demonstreze că H este, de asemenea, aciclice, conform G-definirea, adică H nu are un ciclu.

Luați în considerare un lanț arbitrară (x1, E1 , x2 , E2 ,…, xq , Eq , xq+1) de H, trebuie să arată doar că x1≠xq+1 . Să presupunem că x1= xq+1 . Acest lanț trebuie să satisface condițiile (1), (2), (3) din definiția 2.2, așa că avem:

xi Є Ei-1∩ Ei ,pentru i=2,3,…,q.

Traducere : xq+1 = x1 Є E1 ,

x1 = xq+1 Є Eq .

Prin urmare, vom obține: x1 Є E1∩ Eq . Este clar că fiecare xi (i = 1,2, …, q) aparține de cel puțin două margini, astfel, nici xi poate fi scos din acest lanț. Acest lucru contrazice ipoteza că reducerea Graham în hipergraf H. Teorema este demonstrată.

Bibiografie :

1. Vitalie Cotelea – Baze de date relaționale ( 2004 ),102-126

2. Nguyen Van Dinh – On the desirability of Ω–acyclic database schemes (2001) , 53-59

3.http://biblioteca.regielive.ro/cursuri/calculatoare/baze-de-date-aciclice-60240.html