BDD_Prezentare

8/3/2019 BDD_Prezentare

1/445

Capitolul 1. Modelul relaionalModelul relaional ca i orice alt model de date

utilizat n proiectarea logic a bazelor de dateelibereaz utilizatorul de cunoaterea detaliilordespre structura fizici metodele de acces la date.

El are dou avantaje suplimentare:

- e simplu, structurile de date snt omogene nform de relaii tabelare. `- este riguros din punct de vedere matematicgraie faptului c se sprijin pe teoria matematic arelaiilorilogic de ordinul unu.- Modelul relaional a fost propus de E. Codd n1970.


2/445

Orice model de date, trebuie s se bazeze pe treicomponente: structuri de date, restricii de integritate

i operatorii de manipulare a datelor.Structurile de date. Structurile sunt definite deun limbaj de definire a datelor (data definitionlanguage). Datele n modelul relaional sunt

structurate n relaii bidimensionale. Elementeleprincipale ale structurii relaionale sunt relaiile,tuplurile, atributele, domeniile.

Restriciile de integritate. Prin integritatea

datelor se subnelege c datele rmn stabile, nsigurani corecte. Integritatea n modelul relaionaleste meninut de restricii interne.


3/445

-Manipularea datelor.Relaiile pot fi manipulateutiliznd un limbaj de manipulare a datelor (data

manipulation language). n modelul relaional, limbajulfolosete operatorii relaionali bazai pe conceptulalgebrei relaionale.

1.1. Structura relaional a datelor

Unul din avantajele modelului relaional rezid nomogenitatea lui. Toate datele sunt structurate ntabele, fiecare linie ale crorare acelai format. Linia

ntr-un tabel reprezint un obiect (sau o relaie dintreobiecte) din lumeanconjurtoare.


4/445

1.1.1. Atribute i domenii

n modelul relaional fiecare coloan a unei linii dintr-untabel corespunde noiunii de cmp din fiiere. Cmpuleste cea mai mic unitate accesibil de date. Fiecarecmp poate conine un anumit tip de date (integer, real,

character, string etc.), pentru care se specific numrulnecesar de octei de memorie.Definiia 1.1. Fie U o mulime nevid de elementeA1,A2,...,An, numite atribute. Mulimea U ={A1,A2,...,An} se numete universul unei baze de daterelaionale sau mulimeuniversal.


5/445

Definiia 1.2.Domeniul unui atribut Ai din U, 1 i n,

notat cu dom(Ai), este o mulimefinit de valori de acelaitip care le poate primi atributul Ai.

Domeniul este simplu, dac elementele sale sunt atomice

(adic nu pot fi descompuse din punctul de vedere alSGBD-ului). Atributul ce are un domeniu de valori simpluse numeteatribut atomic. Domeniul unei submulimi R auniversului U , se noteaz dom(R), este uniunea tuturordomeniilor atributelor din R, adic dom(R) =AiRdom(Ai), unde dom() =, dac R=.


6/445

n modelul relaional fiecare tabel reprezint orelaie.

Atributele sunt nite identificatori pentru adifereniai marca coloanele tabelului.

Toate atributele ce apar ntr-un tabel trebuie sfie distincte is fie incluse n universul U.

Atributele au un caracter global n baza de date:dac un nume denot dou coloane n tabele

distincte n aceeai baza de date, atunci elreprezintacelai atribut.


7/445

Relaiatabelar cu i linii ij coloane are i*j elemente.Fiecare element este o valoare dintr-un domeniu simplu.

Cu toate c atributele n universul U trebuie s fie distincte,domeniile acestor atribute nu trebuie neaprat s fiedisjuncte.

De exemplu, managerul n acelai timp poate fi funcionar.Deci domeniile atributelor MANAGER iFUNCIONAR nu sunt disjuncte, adic MANAGER iFUNCIONARsunt definite pe acelai domeniu (cu toate

c atributele respective pot avea i valori distincte).


8/445

Convenie. Mai departe vom utiliza urmtoarelenotaii. Universul U={A1,A2,...,An} i oricesubmulime a lui, R=(Ai1,.-.,Aik}, vor fi reprezentateca string-uri, adic

U=A1...An,R = Ai1Aik.

Vom folosi AiU, n loc de {AiU} pentru "Ai esteo submulime a mulimii U".Reuniunea YZ a dou mulimi Y i Z va fireprezentat de simbolul YZ, unde operaiabinar

uniunea, "", este omis.Mulimile Y i Z pot fi i mulimi vide, fiindcZ=Z, Y=Y i =.


9/445

Cu litere majuscule de la nceputul alfabetuluilatin vom nota atributele singulare, iar cu cele de

la sfritul alfabetului latin - mulimi de atribute.1.1.2.Tupluri

n sistemele cu fiiere o mulime de cmpuri ce e

conceput ca o unitate de salvare i cutare senumetenregistrare. nregistrarea are un formatspecific i depinde de tipurile de date ale

cmpurilor. O linie dintr-o relaie tabelarcorespunde nregistrrii din fiiere i n teoriarelaional se numetetuplu.


10/445

Definiia 1.3. Fie R o submulime a universului

U, RU, unde R i fie dom(R) domeniulmulimii R. Tuplu se numete o funcie,t:Rdom(R), din R n dom(R), adic

t = {(Ai1,a1),...,(Aik,ak)}, Unde orice Aij, 1, j k, este un atribut n R i

un argument al lui t, iar orice aj, 1 < j < k, este o

valoare n dom(Aij).


11/445

Defniiia 1.4. Fie X=Bi...Bmo submulime

proprie a mulimii R, XR, unde X. X-valoarea tuplului t, notat cu t[X], este

t[X] = {(Bj, bj)|bj=t(Bj)=t(Aip),

1 j m, p{1,...,k}}. Dac X=Aij, j{1,..,k}, atunci Aij-valoarea

tuplului t se mai numete Aij-component a

tuplului t.


12/445

Ultima definiie ne spune, c t(Aij)=t[Aij]=ajpentru ajdom(Aj). Deci nu vom difereniasimbolurile t(Aij) i t[Aij] pentru un atributsingular Aij din U.Pentru comoditate tuplul t i X-valoarea

tuplului t vor fi notatet=

i

t[X]=,respectiv.


13/445

ns, dac coloanele tabelului ce corespund

mulimilorR i X sunt marcate cu atribute dinR i X, iar ordinea atributelor ce marcheazcorespund ordinii atributelor n R i X, atunci

notaiile tuplului t i X-valorii tuplului t pot fisimplificate respectiv

t =

i t[X]=.


14/445

Deci putem reprezenta printr-un string nunumai o mulime de atribute, dar i o mulimede valori. Dar permutarea atributelor ntr-untabel va trebui reflectat n tupluri,

permutndu-le componentele. Cu toate cstring-urile ce reprezint tuplurile iniial ifinal vor fi diferite, vom considera c aceste

tupluri sunt identice.


15/445

n tuplul t= distingem dou

componente - string-ul de atribute Ai1...Aik,care este invariant n timp i string-ul de valoria1...ak, care este foarte dinamic. Partea

invariant a tuplului vom numi-o schematuplului (uneori se noteaz sch(t)). ndat ceam definit schema tuplului, expresia "tuplulasupra R" devine clar i este echivalent

expresiei "tuplul t cu schema R".


16/445

Pentru comoditate notaional, un tuplu cu

numele t i schema R se va nota uneorit(R)=t(Ail)t(Ai2)...t(Aik).

Deci putem concepe tuplul t(R) ca un tuplu

variabil asupra R i fiecare component t(Aij),l < j < k, ca un domeniu variabil.Dac tuplult(R) are o formconstant,adic string-ul lui de

valori este i aceste valori sunt ndom(R), el se numete tuplu constant asupraR.


17/445

1.1.3. Relaii i scheme Definiia 1.5. Fie R o submulime a

universului U. Relaia r asupra R este omulimefinit de tupluri cu schema R.Aritatea

relaiei r este egal cu cardinalitatea mulimiiR. Cardinalitatea relaiei r este numrul detupluri n ea.


18/445

Definiia 1.6. Fie RU i relaia r asupra R.Mulimea de atribute R se numete schemarelaiei r (notat cu sch(r)=R).

Definiia 1.7.Baza de date relaional este omulimefinit de relaii,

db = {r1,,rm},

unde r, este o relaie cu schemaRi, 1 i m.


19/445

Definiia 1.8. Fie baza de date db = {r1,...,rm}.

Schema bazei de date este mulimea schemelorrelaiilor ce formeaz baza de date, Db ={R1,...,Rm}, unde Ri = sch(ri)


20/445

Deci schema unei relaii este o expresie a

proprietilor comune i invariante aletuplurilor ce compun relaia. Schema uneirelaii mai este cunoscut sub denumirea deintensia unei relaii. Relaia se mai numeteextensie.

Extensia reprezint mulimea tuplurilor carecompun la un moment dat relaia,mulime care

este variabil n timp.


21/445

Din definiiile de mai sus putem conchideurmtoarele:

(1) ntr-o relaie nu exist coloane cu numeduplicate, fiindc atributele Aij, 1 j k, suntelemente ale mulimii R.

(2) Relaia r, nu are tupluri identice, fiindc r,

este o mulime de tupluri. (3) Ordinea tuplurilor n r, este

nesemnificativ,fiindc r, este o mulime.

(4) Ordinea coloanelor e nesemnificativ. (5) Valorile atributelor n r, sunt atomice

fiindc domeniile sunt simple.


22/445

Relaiile care se stocheaz fizic i formeazbaza de date se numesc relaii de baza.

Exist i relaii virtuale, cunoscute i subnumele de relaii derivate sau viziuni.

Relaia este definit implicit prin mulimea

tuplurilor componente a altor relaii. Relaiile de baza sunt proiectate de

administratorul bazei de date, n timp ce

viziunile sunt definite de utilizatorii bazei dedate.


23/445

Numele relaiei, de obicei, se scrie cuminuscule, de exemplu, relaiar.

Exemplul 1.1. Baza de date "Universitatea"const din patru relaii:studeni,

discipline,

corp_dldactlc ,

arj

(vezi fig 1.1)


24/445

studeni NUME NOTA

_MED

FACULTATEA DECAN

Vasilache 7,8 CIM Popovici

discipline FACULTATE DISCIPLINA

corp didac DISCIPLINA PROFESOR

arja DISCIPLINA TIP ORE

Fig.l.l. Baza de date Universitatea


25/445

Datele n fiecare relaie sunt atomice i sunt luate dindomeniile (simple) atributelor corespunztoare.

Atributul FACULTATE n relaiile studeni idiscipline reprezintacelai atribut.

Atributul DISCIPIN figureaz n trei relaiidiscipline, corp_didaciarj

Cele opt atribute prezente n relaiile descriseconstituie universul U=NUME NOT_MEDFACULTATE DECAN DISCIPLINA PROFESOR

TIP ORE. Aadar, atributele oricrei relaii formeaz o

submulime a mulimii universale U.


26/445

Domeniul atributului NUME const dineventualele nume de familie, dar conine i

valori active, adic numele studenilor ce ifac studiile la facultate.

Domeniul atributului NOT_MED conine

numere pozitive cu valoarea maxim 10. Celelalte domenii se definesc similar.

Nu e exclus faptul c un decan s fie student la

o alt facultate n cazul acesta domeniile activeale atributelor NUME i DECAN nu vor fidisjuncte.


27/445

Tuplurile relaiei studeni sunt definite pemulimea de atribute R= NUME NOTA_MEDFACULTATE DECAN.

Ele sunt concepute ca tupluri constante-valoriale tuplului variabil t(R) =t(NUME)t(NOTA_MED) t(FACULTATE) t(DECAN).

De exemplu, tuplul constant arat c Vasilache estestudent La facultatea Cibernetic a crei decaneste Popovici i are nota medie 7.8.


28/445

Considerm X=NUME DECAN. Tuplul variabil v

fi t[X]=t(NUME) t(DECAN). Tuplul constantdefinit pe schema X este derivat din tuplul


29/445

Baza de date "Universitatea" const din patru relaii.

db={studeni, discipline, corp_didactic,arj}.

Schema bazei de date este mulimea schemelor celorpatru relaii Db= {NUMENOT_MED FACULTATEDECAN, FACULTATE DISCIPLIN, DISCIPLINPROFESOR, DISCIPLIN TIP ORE}.

Relaiilestudeni, discipline, corp_didactic, arj auaritatea 4, 2, 2 i 3 respectiv. Ele formeaz relaiile debaza.

Relaia definit pe atributele X= NUME DECAN e orelaie virtual.


30/445

1.2. Restricii de integritate

1.2.1. Tipuri de restricii Restriciile de integritate definesc cerinele pe caretrebuie s le satisfac datele din baza de date pentru aputea fi considerate corecte, coerente n raport cu

lumea real pe care o reflect. Restriciile sunt principalul mod de integrare a

semanticii datelor n cadrul modelului relaional.

Mecanismele de definire i verificare ale acestorrestricii reprezint instrumentele principale decontrol al semanticii datelor, n modelul relaional.


31/445

Restriciile sunt studiate mai ales sub aspectulputerii lor de modelare i al posibilitii deverificare a respectrii lor.

Restriciile de integritate pot fi divizate n liniimari n dou grupuri:

restricii de comportament

i dependene ntre date.


32/445

Restriciile de comportament specificcaracteristicile independente ale unui atribut

(sau domeniu). Ele exprim semanticaelementelor domeniilor. De exemplu, toate valorile atributului

NOT_MED trebuie s fie mai mare dectzero, dar nu poate depi zece.

Sau nici o persoan de vrsta 25 ani nu poateavea o vechime n munc de 30 ani.

Deci, conform acestei restricii, valorileatributului trebuie s se ncadreze ntreanumite limite.


33/445

Al doilea tip de restricii specific legtura

dintre atribute (sau domenii). Aici putemidentifica aa-numita dependen desubmulime. Considerm, de exemplu, relaia

personaldefinit pe mulimea de atribute{ANGAJAT SALARIU DEPARTAMENTMANAGER}. n relaiapersonal, un managereste n acelai timp un angajat, dar nu orice

angajat este manager. Deci avem c dom(MANAGER)

dom(ANGAJAT).


34/445

Dac presupunem c angajatul are un singursalariu, se subordoneaz unui singur managerdirect, lucreaz ntr-un singur departament,atunci ANGAJAT-valorile determin n modunic toate tuplurile n relaiapersonal.

Aceast restricie este numit dependenfuncional. Dependenele funcionale vor fistudiate detaliat n capitolul 3. Alte tipuri de

dependene cum ar fi cele multivaloare idejonciune vor fi studiate n capitolul 4.


35/445

1.2.2. Chei ntruct relaiareprezint o mulime de tupluri,

iar o mulime nu poate conine elementeleduplicate, relaia nu poate prezenta tupluriidentice.

Deci tuplurile sunt unice i trebuie s existeposibilitatea identificrii lor n cadrul uneirelaii.

Identificarea unui tuplu fr a consulta toate

componentele tuplului a dus la apariianoiuniide cheie.


36/445

Definiia 1.9. Fie U mulimeauniversal de atribute, RU i

R. Mulimea K de atribute, unde KR, se

numete cheie pentru schema R (sau pentru

relaia r cu schema R), dac ea posedurmtoareleproprieti: (1) pentru orice dou tupluri t1i t2 din r avem

t1[K]t2|K]; (2) nici o submulime K' proprie a lui K nu

posed proprietatea (1)


37/445

Definiia 1.10.Mulimea de atribute ce posedproprietatea (l) se numete supercheie. Deci cheia

este o supercheie minimal. Orice cheie e i supercheie.

Afirmaia invers nu e corect.

Este evident c o mulime vid nu poate servi dreptcheie a unei relaii ce conine mai mult de un tupluorice relaie are celpuin o cheie.

La limit cheia este constituit fie dintr-un singuratribut, fie din totalitatea atributelor din schemarelaiei respective.


38/445

ntr-o relaie pot exista mai multe chei. Sespune n acest caz crelaiaposed mai multechei candidate.

n aceastsituaie administratorul bazei de datev stabili una din cheile candidate sserveascn mod efectiv la identificarea unic atuplurilor. Ea v primi numele de cheieprimar.

Primare se vor numi i domeniile atributelor ceformeaz o cheieprimar.


39/445

Definiia 1.11. Cheia primar a unei relaii se

numete cheie simpl, dac este constituit dintr-unsingur atribut, iar atunci cnd este format din maimulte atribute este denumitcheie compus.

Remarc. Nu toate atributele unei chei compuse pot

fi definite pe domenii primare. Definiia 1.12. O cheie extern reprezint un atribut

(grup de atribute) dintr-o schema Ri definit (definite)pe acelai (aceleai) domeniu (domenii) ca i cheia

primar a altei scheme Rj.


40/445

Relaia ri se numeterelaie care refer, iar rjpoart numele de relaie referent.

Unele atribute pot avea aa numitele valorinedefinite sau necunoscute notate cu "null.

Ins sunt bine cunoscute restriciile formulate

prin urmtoarele reguli numite reguli deactualizare (inserare, modificare i eliminare) arelaiilor.


41/445

(1) Restricia entitii: cheia primar a uneirelaii de baza nu poate conine valori "null.

(2) Restricia referirii:dac atributul A al uneichei a relaiei r, este definit pe un domeniuprimar, atunci trebuie s existe o relaie de

baza r, cu o cheie primar B nct orice A-valoare din r, sapar n calitate de B-valoaren r.


42/445


43/445

Considerm relaiile discipline (FACULTATEDISCIPLIN) i corp_dldac(DSCIPLIN

PROFESOR) Fiindc la orice facultate se predcel puin o disciplini orice profesor pred celpuin o disciplin,i similar, orice disciplin se

predmcar la o facultate i se pred cel puinde un profesor, cheile primare ale acestor relaiisunt compuse i constau din toate atributelecorespunztoarefiecreirelaii.


44/445

n relaiaarj(DISCIPLIN TIP ORE), orice

disciplin poate fi de trei tipuri (prelegeri,practic, laborator) i poate avea diferite ore depredare, unele discipline pot avea acelai tip iacelainumrde ore. Epuin probabil ca cheia

relaieiarjs fie simpl. Putem presupune ccheia ei este compus.


45/445

n acest exemplu, domeniul dom(NUME) esteprimar. Cheile compuse ale relaiilor

discipline, corp_didac, arj nu sunt definitepe acest domeniu primar.

Conform regulii (1) atributele celor patru chei

nu pot avea valori "null" Dat fiind faptul cnici o cheie din cele trei compuse nu suntdefinite pe domeniul primar dom(NUME),

exemplul dat nu ne demonstreaz regula (2).


46/445

Exemplul 1.3. Considerm relaiilestudeniifaculti din fig. 1.2.

studeni NUME FACULTATE AN

n1 f1 a1

n2 f1 a2n f a

faculti FACULTATE DECAN

f1 d1f2 d2

flg.1.2.


47/445


48/445

Extensiile relaiilor se schimb pe parcursultimpului.

S-ar preac pentru fiecare instan a relaieipot fi determinate cheile i supercheile. Darschemele relaiilor, adic intensiile, trebuie sfie invariante.

Cheile trebuie s rmn chei pentru oriceeventuale extensii.

Prin urmare determinarea cheii unei relaii

necesit cunoaterea semanticii relaieirespective, nu numai celei din momentul ncare se stabilete cheia.


49/445

Convenie. Dac relaia posed o singur

cheie sau dorim s evideniem numai cheiaprimar mai departe vom sublinia atributele ceformeaz aceast cheie. De exemplu, relaia rcu schema ABCD i cheia AC se scrie r(A,BC,D). n cazul c relaiaposed mai multechei, atunci le vom scrie explicit: relaiar(ABCD) are dou chei candidate k1=ac,

K2=B.


50/445


51/445


52/445

Instruciuni pentru controlCREATE ASSERTIONDROP ASSERTIONGRANTREVOKE

ALTER SESSION


53/445

Tipuri de date.Toate datele, care sunt stocate n baza de date suntcaracterizate prin tip i lungime. Aceast caracterizare estedefinit ca tipul de date al obiectului.Tabelele sunt dispozitive de stocare ntr-o baz de date

relaional. Coloanele tabelului definesc caracteristiciledatelor i n acelai timp atribuie un nume datelor dincoloana respectiv.Coloanele, precum i variabilele, i constantele suntcaracterizate din tipul i lungimea datelor. Aceste proprietifac ca serverul s trateze n mod difereniat tipurile de datediferite.


54/445

Tipuri de date SQLcharacter [ varying ] (n) integer date

bit [ varying ] (n) smallint time

numeric (p,q) float (p) timestamp

decimal (p,q) interval

Tipurile interne de date ale programului Oracle sunt:Char; varchar2; varchar;

number; date; raw;

long raw; rowid; long; mlslabel


55/445

RESTRICII DE INTEGRITATEn baza de date relaional Oracle, exist

urmtoarele tipuri de restricii de integritate adatelor:Null; Unique; Primary key;

Referential; Check.

Restricia de integritate pentru un tabel estestabilit atunci cnd tabelul este creat saumodificat. Pentru a stabili o restricie de integritate,putei include clauza constraint n comenzilecreate table sau alter table. Exemplul urmtorilustreaz sintaxa general a clauzei constraint:CONSTRAINT nume_restricie

tip_restricie


56/445

Restricia de integritate nulln mod prestabilit, toate coloanele unui tabelaccept valori nule adic, este permisabsena uneivalori n coloan. Prin stabilirea restriciei notnuil, impunei coloanei specificate s posede o

valoare pentru fiecare linie a tabelului.Pentru a afiarestriciilenull dintr-un tabel, folosiicomanda describe dup care urmeaz numeletabelului.


57/445

Restricia de integritate uniqueRestricie de integritate unique impune ca toate valorile dintr-o

coloan s fie distincte, nu pot exista valori duplicate n coloanarespectiv. Oracle v permite s plasai aceast restricie pe mai multecoloane, definind astfel o aa numit restricie de unicitate compus. Orestricie de unicitate compus cere ca o combinaie a coloanei cu cheieunic s nu se repete. Instruciunea urmtoare creeaz o restricie deunicitate asupra coloanei marca_ang a tabelului ANG:

create table ang(marca ang number(7)constraint s_ang_marca_ang_uk unique,

nume varchar2(20)constraint s_ang_nume_nn not null,prenume varchar2 (20),nr_dept varchar2(5));


58/445

Restricia de integritateprimary key

Restricia de integritate primary key desemneazo coloan sau o combinaie de coloane drept cheieprincipal a tabelului. Cheia principal identific n modunivoc fiecare linie a tabelului. De asemenea, aceastrestricie creeaz n mod implicit restriciile not nulli unique pe coloana respectiv. Dei Oracle nuimpune existena unei chei principale pentru fiecaretabel, este bine s v obinuii s o creai. De asemenea,este recomandabil s desemnai drept cheie principal ocoloana sau o combinaie de coloane ale cror valori nuse modific niciodat.


59/445

Instruciunea urmtoare creeaz o restricie primary keypentru cmpul marca_ang al tabelului ANG:

create table ang(marca_ang number(7)constraint s_ang_marca_ang_pk primarykey,nume varchar2(20)constraint s ang nume nn not null,prenume varchar2 (2'0'),

nr_dept varchar2(5));

Pentru a crea restricii asupra tabelelor putei folosi o a


60/445

Pentru a crea restricii asupra tabelelor, putei folosi o adoua sintax, cunoscut sub numele de sintaxarestricie_tabel. Cu aceast sintax, restriciile sunt

plasate la baza instruciunii create table. Exemplulurmtor creeaz acelai tabel ca n exemplul anterior,folosind sintaxa restricie_tabel:

create table ang

(marca_ang number(7),nume varchar2(20),

prenume varchar2(20),

nr_dept varchar2(5),

constraint s_ang marca_ang_pk primarykey (marca ang));


61/445


62/445

Restricia de integritate prin referinRestriciile de integritate prin referin sunt folosite pentru a

impune regulile care dicteaz relaiile dintre coloanele diverselortabele, ntre tabele se creeaz o relaie printe-fiu. Tabelul printeconine cheia referit iar tabelul fiu conine cheia extern.

Exemplul urmtor creeaz aceast restricie de integritate

prin referin asupra tabelului de adrese:alter table adreseadd constraint fk cod statforeign key (cod _stat)references cod_stat(cod_stat);


63/445


64/445

Restricia de integritate checkRestricia de integritate check definete n mod explicito condiie care trebuie s fie adevrat. Fiecare linie atabelului trebuie s respecte condiia. Condiia poate fievaluat i la valoarea Unknown pentru a permite

prezena valorii null. Dac se ncearc executarea uneiinstruciuni care ar duce la nerespectarea condiiei,instruciunea este derulat napoi.


65/445


66/445

O definiie n SQL a bazei de date Student i Curs.create table Student (

IDSt char(4),numSt varchar2(4),

anSt number(1) ,

IDGrup char(3),

constraint pk_etud primary key (IDSt));

Table created.


67/445

create table Curs(

IDC char(4),numC varchar2(2),

punctC number(2),

IDGrup char(3),

constraint pk_Curs primary key (IDC)

);


68/445

create table StudCurs (

IDC char(4),IDSt char(4),

Nrpunct number(2),

notaStC number(2) null,

constraint fk_Stud foreign key(IDSt) references

Student (IDSt),constraint fk_Curs foreign key(IDC) references

Curs (IDC),

constraint pk_StudCurs primary key (IDC,IDSt))

;


69/445

linstrucia describe. Exemplu :

describe Student;Name Null? Type

----------- -------- ------------

IDST NOT NULL CHAR(4)

NUMST VARCHAR2(3)ANST NUMBER(1)

IDGRUP CHAR(3)


70/445

1.3. Operaii de actualizare

Regulile de actualizare a bazei de date facparte din cele trei componente ale modeluluirelaional de date. Vom examina cele trei

operaii de actualizare a datelor: Inserareadatelor, tergerea datelor i modificareadatelor.


71/445


72/445

Rezultatul operaiei poate s eueze dinurmtoarele cauze:

(1) tuplul de inserie e definit pe o mulime deatribute ce nu corespunde schemei relaiei;

(2) valorile componentelor tuplului nu sunt

luate din domeniile corespunztoare; (3) n relaie deja se gsete un tuplu cu

asemenea componente cheie.

n toate aceste cazuri operaia Add pstreazrelaia r intact.


73/445

Operaia de tergere a datelor se utilizeaz

pentru eliminarea coninutuluirelaiilor. Pentrurelaia r de mai sus, operaia de tergere sereprezint:

Del (r; ). n cazul cnd numele de atribute sunt sortate,poate fi utilizaturmtoareanotaiescurt:

Del (r;).


74/445


75/445


76/445


77/445

Instruciile SQL : insert, update, et delete.insert into Student values ('0001','St01',1,'002');

insert into Student values ('0002','St02',2,'001');

insert into Student values ('0003','St03','1,'001');insert into Student values ('0004','St04','3,'001');insert into Student values ('0005','St05','4,'001');

insert into Student values ('0006','St06','2,'001');

insert into Student values ('0007','St07',1,'002');insert into Student values ('0008','St08',3,'002');

insert into Student values ('0009','St09',3,'003');insert into Student values ('0010','St10',3,'002');

insert into Student values ('0011','St11',3,'003');


78/445


79/445

insert into StudCurs values (5001','0001',20, null);







insert into StudCurs values (5003','0003',50, null);insert into StudCurs values (5004','0003',60, null);




insert into StudCurs values (5003','0006',50, null);insert into StudCurs values (5004','0007',60, null);


Selectarea datelor din tabeleSintaxa general a instruciunii select este urmtoarea


80/445

Sintaxa general a instruciunii select este urmtoarea:select nume_coloana(e) from tabel (sau vedere sau instantaneu)

select * from Student;

IDST NOME ANET IDG

---- ---- ---------- ---

0001 St01 1 002

0002 St02 2 001

0003 St03 1 001

0004 St04 3 0010005 St05 4 001

0006 St06 2 001

0007 St07 1 002

0008 St08 3 002

0009 St09 3 003

0010 St10 3 0020011 St11 3 003

11 rows selected.


81/445

select * from Cours;

IDC NO POINTC IDG---- -- ---------- ---

5001 c1 10 001

5002 c2 30 002

5003 c3 20 003

5004 c4 30 001

5005 c5 20 003


82/445

select * from StudCurs

IDC IDST NRPOINT NOTEETC

---- ---- ---------- ----------5001 0001 20

5002 0001 30

5003 0001 50

5004 0001 60

5005 0001 70

5001 0002 205002 0002 30

5003 0003 50

5004 0003 60

5005 0005 70

5001 0003 20

5002 0005 305003 0006 50

5004 0007 60

5005 0008 70


83/445


84/445

Eliminarea datelorPentru a elimina date dintr-un tabel sau din tabelele debaz ale unei vederi, folosii comanda SQL delete.

Instruciunea urmtoare elimin toate liniile din tabelulCALIFICARE_1:

delete from calificare_l;Uneori doriiseliminai numai anumite linii ale unui tabel.Pentru a face acest lucru, folosii comanda delete cuclauza where. De exemplu, instruciuneaurmtoareelimin

numai acele linii ale cror cantiti vndute sunt mai micidect 100:delete from comenzi

where cant_vanzari < 100;


85/445


86/445


87/445


88/445

2.1. Operaiile traditionale

2.1.1. Scheme relaionale compatibile Operaiile binare asupra relaiilor: uniunea,

intersecia i diferena, necesit ca

operanzii (relaiile) s fie definii pescheme compatibile. Compatibilitatea schemelor se definete n

felul urmtor.

Definiia 2 1 Vom spune c dou relaii r(R)


89/445

Definiia 2.1.Vom spune c dou relaii r(R)i s(S) sunt compatibile (sau au scheme

compatibile), dac ntre R i S exist ocoresponden biunivoc f:

pentru orice atribut A din R, exist un atribut

B n S nct dom(A)=dom(B), B=f(A) iA=f(B), unde f este funcia invers funciei f.

Remarc.Dou relaii cu aceeai schem sunt

compatibile.

Exemplu 2.1. Schemele relaiilorvnzrii articolenuibil S h l l iil i i


90/445

sunt compatibile. Schemele relaiilor vnzri ifurnizorisunt compatibile.

vnzri FIRMA ARTICO

f1 a1

f1 a2

f2 a1

f3 a1

articole ARTICOL CULOAR

E

A1 c1

a1 c2

a1 c3a3 c2

a2 c1

urnizori ARTICOL FURNIZOR

a1 f1a1 f3

a2 f1

a3 f3


91/445

Ultimele relaii sunt definite pe atribute ceprimesc valori din aceleai domenii.Valorile active sunt totui diferite, fiindc

un furnizor poate s nu fie firm iviceversa.

2 1 2 Uniunea


92/445

2.1.2. Uniunea

Uniunea a dou relaii presupune c schemele

lor sunt compatibile. Definiia 2.2. Uniuneaa dou relaii

compatibile r(R) i s(S), notat cu r s, e o

relaie definit pe schema R sau S i const dintuplurile ce aparin relaiilor r sau s, adic

rs = {t|trts}.

Exemplul 2.2. Fie relaiile r(A B C) i s(A BC) din fig.2.4. Relaia din fig.2.5 este

q = r s.


93/445

r A B C

a1 b1 c1

a1 b2 c3a2 b1 c2

s A B C

a1 b1 c1

a1 b1 c2a1 b2 c3

a3 b2 c3

Fig. 2.4. Relaiile r(A B C) i s(A B C)

q A B C

a1 b1 c1

a1 b1 c2

a1 b2 c3a2 b1 c2

a3 b2 c3

Fig.2.5. Relaia q = r s

Operaia uniunea are dou proprieti. Ea e


94/445

Operaia uniunea are douproprieti. Ea ecomutativ, adic r s = s r. Ea este iasociativ, adic (r s) q = r(s q)pentru relaiile mutual compatibile r, s i q.

Prin urmare, n expresiile ce conin o cascadde operaii uniunea, parantezele pot fi omise

fr a provoca ambiguiti. Deci, dac avem krelaii compatibile r1,r2,...,rk, uniunea acestorrelaii poate fi notat cu (r1, r2,..., rk).

Operaia uniunea are dou cazuri speciale.Pentru orice relaie r(R) au loc:r = r i rs = s, dac r s.

2 1 3 Intersecia


95/445

2.1.3. Intersecia

Similar uniunii, intersecia a dou relaii cere

ca operanzii s fie relaii cu schemecompatibile.

Definiia 2.3. Intersecia a dou relaii

compatibile r(R) i s(S), notat cu r s, este orelaiedefinit pe schema R sau S iconst dintuplurile ce aparin concomitent relaiilorr i s,

adic rs ={t|tr&ts}.

Exemplul 2.3. Fie relaiile r(A B C) i s(A B C)


96/445

din fig. 2.4. Relaia q = r s este prezentat nfig. 2.6.

q A B C

a1 b1 c1a1 b2 c3

fig.2.6.

2 1 4 Diferena


97/445

2.1.4.Diferena

Operaiadiferena presupune c operanzii sunt

relaii cu scheme compatibile.

Definiia 2.4. Diferena a dou relaiicompatibile r(R) i s(S), notat cu r \ s, este o

relaiedefinit pe mulimea de atribute R sau Si are n calitate de tupluri, toate tuplurile dinrelaia r ce nu sunt n s, adic

r\s ={t|tr & ts}.

Exemplul 2.4. Fie relaiile r(A B C) i s(A B C)


98/445

Exemplul 2.4. Fie relaiile r(A B C) i s(A B C)din fig.2.4. Relaiile q1 = r \ s, i q2= s \ r sunt

prezentate n fig.2.7.

q1 A B Ca2 b1 c2

q2 A B Ca1 b1 c2a3 b2 c3

Fi .2.7.


99/445

Din exemplul de mai sus observm cdiferena nu se bucur de proprietateacomutativ,adic

r \s s\ r.

Totodat, nu e nici asociativ,adic

(r \ s) \q r\ (s \ q),

fiindc

(r \ s) \ q = r \ (s q)pentru orice relaii mutual compatibile r, s, i q.


100/445

Diferena a dou relaii are patru cazuri

speciale. Un caz este\r=,

altul e

r \ = rpentru orice relaie r(R).

Celelalte cazuri le vom examina n urmtoareledouseciuni.


101/445

Exemplul 2.5. Fie relaia r(A B C) din fig.2,4


102/445

gi fie

dom(A) = {a1,a2,a3},dom(B) = {b1,b2},

dom(C) = {c1,c2,c3}.

Atunci tup(A B C) i r sunt cele din fig. 2.8.


103/445

tup A B C

a1 b1 c1

a1 b1 c2

a1 b1 c3a1 b2 c1

a1 b2 c2

a1 b2 c3

a2 b1 c1

a2 b1 c2

a2 b1 c3a2 b2 c1

a2 b2 c2

a2 b2 c3

a3 b1 c1

a3 b1 c2

a3 b1 c3a3 b2 c1

a3 b2 c2

a3 b2 c3

r A B C

a1 b1 c2

a1 b1 c3

a1 b2 c1a1 b2 c2

a2 b1 c1

a2 b1 c3

a2 b2 c1

a2 b2 c2

a2 b2 c3a3 b1 c1

a3 b1 c2

a3 b1 c3

a3 b2 c1

a3 b2 c2

a3 b2 c3

Fig.2.8.

Este clar c dac pentru un atribut A din R


104/445

Este clar c, dac pentru un atribut A din Rdomeniul dom(A) este infinit, atunci i r v fi

infinit i deci nu v fi o relaie conformdefiniiei noastre.

Pentru lichidarea acestui dezavantaj se

introduce noiunea de complement activ.


105/445


106/445

Exemplul 2.6. Fie relaia r(A B C) din fig.2.4.

Atunciadom(A) = {a1,a2},

adom(B) = {b1,b2},

adom(C) = {c1,c2,c3}.

Relaiile atup(A B C) i ~r sunt prezentate nfig.2.9.

atup A B C


107/445

atup A B C

a1 b1 c1

a1 b1 c2

a1 b1 c3

a1 b2 c1

a1 b2 c2

a1 b2 c3

a2 b1 c1a2 b1 c2

a2 b1 c3

a2 b2 c1

a2 b2 c2a2 b2 c3

~r A B C

a1 b1 c2

a1 b1 c3a1 b2 c1

a1 b2 c2

a2 b1 c1

a2

b1

c3

a2 b2 c1

a2 b2 c2

a2 b2 c3

Fig.2.9.

2.1.7. Produsul cartezian


108/445

Definiia 2.7. Produsul cartezian a dourelaii

r(A1...An) i s(B1...Bm), notat cu rs, este omulime de tupluri (i nu ntotdeauna o relaie)definite pe mulimea de atribute A1...AnB1...Bm.

Tuplurile reprezint toate posibilele asociaiide tupluri din r i s: dac trr i tss, atunciconcatenaia tr ts este un tuplu n r s,


109/445


110/445

Produsul cartezian q = rs arat ca n


111/445

fig 2 11

q A B C D E

a1 b1 c1d1e1

a1 b1 c1 d1e2a1 b2 c3d1e1

a1 b2 c3d1e2a2b1 c2d1e1

a2 b1 c2d1e2Fig 2 11

Produsul cartezian a dou relaii nevide nuntotdeauna produce o relaie Rezultatul e o


112/445

ntotdeauna produce o relaie. Rezultatul e orelaie,dac ambii operanzi sunt relaii cu scheme

nevide i disjuncte (vezi exemplul 2.7). Dac, ns, relaiile operanzi au scheme vide sau

nondisjuncte, atunci produsul cartezian nu este o

relaie. Aceastproblem poate fi soluionat cu ajutorul

operaiei atribuirea, care de fapt produce

schimbarea numelor atributelor.

Produsul cartezian nu este o operaie


113/445

comutativ n schimb sebucur de proprietatea

asociativ. Prin urmare, dac avem o cascad de produsecarteziene

r1( r2(...rk)), ea poate fi reprezentat n form de prefix

(r1,r2,..., rk)

Schemele relaiilorri, 1 i k, trebuie s fiedisjuncte dou cte dou. n caz contrarrezultatul nu v fi o relaie.

2.1.8. Atribuirea


114/445

2.1.8. Atribuirea

Fie r(R) i s(S) dou relaii cu scheme

compatibile i R S. Pentru a aplica asupra lor operaiile binare

tradiionale se face reatribuirea relaiilor pentru

a redenumi diferena de atribute R\ S sau S \R.

Atribuirea se utilizeaz i pentru pstrarea

rezultatelor intermediare.

Definiia 2.8. Fie r o relaie cu schema A1...An


115/445

Definiia2.8. Fie r o relaie cu schema A1...Ani {B1..,Bn,} o mulime de atribute

compatibile, adic dom(Bi) = dom(Ai), 1 i n.

O nou relaie s(B1.,.Bn) compatibil cu r se

poate defini prin atribuirea: s(B1...Bn) = r(A1...An).

Extensia relaiei s este extensia relaiei r: ts

atunci i numai atunci, cnd trr, unde ts[Bi]= tr[Ai], 1in

Exemplul 2.9. Fie relaia r(A B C) din fig.2.12. Atunci,


116/445

s(A D C): = r(A B C)

r A B Ca1 b1 c1

a1 b2 c3a2 b1 c2

s A D Ca1 b1 c1

a1 b2 c3a2 b1 c2

Fig 2.12

n urmtorul exemplu, operaia atribuirea se


117/445

folosete pentru pstrarea rezultatelor

intermediare. Exemplul2.10. Fie relaiile r(A B C) i s(A BC) din fig. 2.l3.

Atunci q : = (r s) \ (r s). Relaia q s-a construit aplicnd

consecutivitatea de operaii:

q1: = r s, q2: = r s, q= q1 \ q2.


118/445

2.2. Operaiile relaionale native


119/445

2.2.1. Proiecia

Proiecia e o operaie unar.

Definiia 2.9. Fie r o relaie cu schema R i X R.Proiecia relaiei r asupra mulimii de atribute X,

notat cu x(r), e o relaie cu schema X ce const dinX-valorile tuturor tuplurilor din r:

x(r)={t(Xl|tr}.

Tupluri distincte din r pot deveni identice, cnd seproiecteaz pe o mulime de atribute. Tuplurileduplicate n relaia rezultat se elimina.

Exemplul 2.11. Fie relaia r(A B C) din fig.2.14.

A i ( )


120/445

Atunci s = A,C(r).

r A B C

a 10 l

a 20 l

b 30 l

b 40 2

s A C

a l

b lb 2

Fig.2.14

Existdou cazuri speciale:

(1) X R At i ( )


121/445

(1) X = R. Atunci X(r) = r.

(2) r=. Atunci X(r) = . Dac mulimea de atribute X = , atunciproiecia (r) este indefinit, fiindc schemaunei relaii nu poate fi o mulimevid. Schemaunei relaii,produs de operaiaproiecia, arecelpuin un atribut.

Pentru cazul cnd RX operaia proiecia


122/445

Pentru cazul cnd RX, operaia proieciaiari este indefinit. Mulimea asupra creia

se face proiecia nu poate fi mai larg dectschema relaieiiniiale.

Fie relaia r(R) i Y X R.

Atunci y(x(r)) = y(r).

Dac X = Y, atunci

x( (y(r)) = x(r) =y(r).

2 2 2 Selecia


123/445

2.2.2. Selecia

Selecia este o operaie unar. PentruSelectarea unor tupluri dintr-o relaie enecesar specificarea condiiilor de selectare.n rezultat se obine o relaie ce e o submulime

de tupluri a relaieiiniiale.

Fie c condiia de selecie se noteaz prinf l l l l i ii l F d fi it


124/445

formula calculului propoziional, F, definitrecursiv:

(1) AB i Aa sunt formule, unde A i Bsunt atribute compatibile i adom(A), iar{=,, , }. Aceste formule suntatomice.

(2) Dac G i H sunt formule, atunciconjuncia G&H, disjunctia GH, negaiile ~Gi ~H sunt formule.

(3) Nimic altceva nu e formula.

Definiia 2 10 Formula F e aplicabil relaiei


125/445

Definiia 2.10. Formula F e aplicabilrelaieir(R), dac orice constant c din F este ndom(R), i orice atribut A din F este n R.

O relaie r satisface F (sau F e valid n r),dac F e aplicabilrelaieiri orice tuplu tr

satisface formula F n sensul c formula Gobinut prin substituirea oricrui atribut A dinF cu A-valoarea tuplului t are valoarea adevr.

D fi ii 2 11 S l i l i i (R) f


126/445

Definiia 2.11.Selecia relaiei r (R) conformformulei F, unde F e aplicabil relaiei r(R), eo submulime a relaiei r(R), notat cu F(r),ce const din toate tuplurile tr ce satisfac F,adic

F(r)={t|tr&F(t)}.

Exemplul 2.12. Fie r(A B C D) din fig. 2.l5. Atuncis=((a b) & (D>5))(r)


127/445

s=((a - b) & (D>5))(r)

r A B C D

a a l 7

b b 5 5

b b 12 3

b b 23 10

s A B C D

a a l 7

b b 23 10

Fig.2.l5.

E i t d i i l l l i i


128/445

Existdou cazuri speciale ale seleciei.

(1) Dac F e o formul ce nu e compus nicidintr-o formul atomic, adic e o formulnul, atunci F(r) = r. n acest caz asupratuplurilor tr nu se impune nici o restriciepentru selecie.

(2) Dac r(R) = , atunci F(r) = pentruorice formul F, fiindc F e valid n oricerelaievid.

Este evident c


129/445

Este evident c

G(F(r)) = G&F(r). ntruct conjuncia este comutativ,adic

G&F(r) = F&G (r),

atunci i compozitia a dou selecii estecomutativ.

Deci

G(F(r)) = F(G(r)).

Operaia selecia este distributiv n raport cu


130/445

Operaia selecia este distributiv n raport cuoperaiile binare tradiionale pe mulimi. Fie r

i s dou relaii compatibile i {,,\},atunci

F(r s) = F(r) F(s).

T b i i t l i t


131/445

Trebuie menionat c selecia nu comuteaz cu

operaia complement. ns selecia comuteazcu proiecia, dac sunt respectate unelecondiii. Fie r o relaie cu schema R, XR, ifie F o formul ce e satisfcut de tuplurilet[X]. Atunci

XF(r) = FX(r).

2.2.3. -jonciunea


132/445

Definiia 2.12. Fie r(R) i s(S) dou relaii,RS=, AR, BS i fie un elementdin mulimea {=, ,, }. Presupunemc atributele A i B sunt compatibile, adicdom(A) = dom(B).

-jonciunea relaiilor r(R) i s(S), notatcu r|X|ABs , este o mulime de tupluriconcatenate de forma trts, unde

trr, tss

i tr(A) ts(B),


133/445

Exemplul 2.13. Fie relaiile r(A B C) i s(D E) dinfig2 l6 unde dom(C) = dom(D) n fg 2 l7 relaia


134/445

fig2.l6, unde dom(C) = dom(D). n fg. 2.l7 relaiar|X|C>DS esteprezent.

r A B C

a1 b1 4

a1 b2 2a2 b1 6

s D E

3 e1

4 e1l e2

q A B C D E

a1 b1 4 1 e2

a1 b1 4 3 e1a1 b2 2 1 e2

a2 b1 6 3 e1

a2

b1

6 4 e1

a2 b1 6 1 e2Fig. 2.l6

Fig. 2.l7


135/445

Operaia -jonciunea poate fi exprimat prinoperaiile produsul cartezian i selecia.Rezultatul unei -jonciuni este acelai cu

rezultatul unei selecii operate asupra unuiprodus cartezian, adic

r|X|ABs = AB(rs).


136/445

2.2.4. Jonciunea (Jonciunea natural)


137/445

Definiia2.13. Fie dou relaii r(R) i s(S)

Jonciunearelaiilor r i s (notatia uzual r|X|s)este o relaie cu schema RS Tuplul t aparinerelaiei rezultat, dac exist tuplurile tri ts n r

i s, respectiv, i satisfact[R]=tri t[S]=ts,

adic

r |X| s = {t | t[R] = tr& t[S] = ts & trr & tss}


138/445

Exemplul2.14. n fig 2 18 sunt afiate relaiiler(A B C), s(B C D) i q(A B C D),

d |X|


139/445

unde q = r|X|s

r A B Ca1 b1 c1

a1 b2 c1

a2 b1 c2

s B C Db1 c1 d1

b1 c1 d2

b1 c2 d3

b2 c2 d4

q A B C Da1 b1 c1 d1

a1 b1 c1 d2

a2 b1 c2 d3

Fig 2 18

Dac R i S sunt disjuncte, RS=, atunci jonciunea relaiilor ri s este identic cu produsul cartezian al lor, adicr|X|s=rs

Dac R S=i |RS| = k, atunci jonciunea poate firedat prm operanle proiecia, selecia i produsul


140/445

p p p pcartezian

r|X|s = RS(F (rs)),undeF = (r.A1=s.A1)&(r.A2=s.A2)& &(r.Ak=s.Ak)

pentru AiRS, lik.

Dac R=S, atunci r|X|s = rs. Operaia jonciunea nu este comutativ, n schimb, ea

se bucur de proprietatea asociativ. Prin urmare, ocascad de jonciuni (r1|X|(r2 |X|(... rk)) poate fi

prefixat, adic |X|(r1,r2,...,rk Din exemplul 2.14 se vede c nu toate tuplurile

relaiilor r i s particip la jonciune.


141/445

Exemplul 2.15. Fie relaiile S1(AB), S2(B C), S3(AC) i q(A B C) din fig 2 19,


142/445

) q( ) g ,

unde

q=s1|X|s2|X|s3.Tuplurile


143/445

r(R), r1(R) i s(S).

Atunci are loc urmtoarea egalitate(r1r)|X|s=(r|X|s)(r1|X|s).S cercetm acum legtura dintre proiecie i jonciune.Fie dou relaii

r(R) i s(S).otm q=r|X|s(din definiia operaiei jonciunea, schema relaiei q esteRS).

Proiectm relaia q asupra mulimii de atribute R:r

1

=R(q).n ce corelaie se afl r1 i r?

Rspuns r1r.

Exemplul 2.16. Fie relaiile r(A B) i s(B


144/445

p ( ) (C). Notm q=r|X|s i r1 = AB(q). n urma

operaiilor, observm c tuplurile relaiei r1

constituie o submulime proprie a relaiei r(vezi fig. 2.20.).

r A B

a1 b1a1 b1

s B Cb1c1

q A B C

a1 b1 c1

r A B

a1 b1

Fig. 2.20

Exemplul 2.17. n acest exemplu r1 = r. Sunt daterelaiile r(R) i s(S) cu extensiile ca n fig. 2.21,

q r|X|s i r1 = (q)


145/445

q = r|X|s i r = AB(q).

Este evident, c semnul dintre relaiile r1 i r este "=",dac pentru orice tuplu tr din r exist un tuplu ts n s cesatisfac egalitatea tr[RS] = ts[RS]. Cu alte cuvinte,dac RS(r) = RS(s).

r A B

a1 b1

a2 b2

s B C

b1 c1

b2 c2

q A B C

a1 b1 c1

a2 b2 c2

r A Ba1 b1

a2 b2

Fig. 2.21

S considerm acum legtura dintre proiecie


146/445

S considerm acum legtura dintre proiecie

i jonciune, schimbnd ordinea de aplicare aacestor operaii. Fie relaia q este definit pemulimea de atribute RS. Notm

r = R(q) i s = S(q).Fie q1 = r|X|s. Care e relaia dintre q1 i q?Rspuns: qq1.

Exemplul 2.18. Relaia q din fig. 2.22 se

d f i d i l i il d


147/445

descompune far pierderi pe mulimile de

atribute AB i BC, fiindc q = q

1

, under = AB(q), s = BC(q), q1 = r|X|s.

r A B

a1 b1

a2 b2

s B C

b1 c1

b2 c1

q A B C

a1 b1 c1a2 b2 c2

Fig. 2.22

q A B C

a1 b1 c1

a1 b2 c1

Acuma s continum procesul de


148/445

pdescompunere a relaiei q1.Fie

r1 = R(q

1),

i

s1= S(q1).Construim jonciunea q11= r1|X|s1.Care este corelaia dintre q1 i q11?

Rspuns: q1

= q11

.

2.2.5. Divizarea


149/445

Definiia 2.15. Fie r(R) i s(S) dou relaii i SR.

otm Q = R\ S. Divizarea relaiei r la relaia s, notatcu rs, este o relaie definit pe mulimea de atribute Q:rs = {t| pentru tss(S)trr(R) ce satisface tr[Q]=t itr[S]=ts}.

Remarc. Operaia divizareaea poate fi conceputdrept operaie invers produsului cartezian. Fie q= rs.Atunci qs produce o relaie cu schema R i relaia q vconine numrul maximal de tupluri ce ar satisfaceexpresia qsr.

Teorema 2.1. Fie dou relaii q(Q) i s(S). Dac r=qs, atunci q=rs


150/445

rs.Exemplul 2.19. Fie relaia r(A B C) din fig.2.23. n fig.2.24 sunt

prezentate relaiile s i q, unde q= rs. S se observe c qsr i cq conine un numr maximal de tupluri ce posed aceastproprietate.

s C

c1

r A B C

a1 b1 c1a2 b1 c1

a1 b2 c1

a1 b2 c2

a2 b1 c2

a1

b2

c3

a1 b2 c4

a1 b1 c5

Fig. 2.23

q A B

a1 b1

a2 b1

a1 b2

Fig. 2.24

Teorema 2.2. Operaia divizarea poate fi


151/445

p pexprimat n termenii produsului cartezian,

diferenei i proieciei:rs=Q(r)\Q((Q(r)s)\r).

S subliniem c operaia divizarea nu este nicicomutativ, nici asociativ.Din definiia diviziunii i remarc urmeaz c,dac relaia r[R] este o submulime proprie deupluri a relaiei s(S), atunci rs este o relaieid.

Dac S= atunci rs este indefniit, fiindcindefinit este s().

2 2 6 Semijonciunea


152/445

2.2.6. Semijonciunea

Semijonctiunea e o operaie binar. Eaconst n construirea unei relaii din cele doui e format numai din tuplurile unei singurerelaii ce particip la jonciune.

Definiia 2.16. Fie dou relaii r(R) i s(S).Semijonciunea relaiei r i s, notat cu r|Xs,

este o mulime de tupluri determinat deexpresia r|Xs = R(r|X|s).

Exemplul 2 20 Fie relaiile r(A B) s(B C) i


153/445

Exemplul 2.20. Fie relaiile r(A B), s(B C) i

q(A B) din fig.2.25. Relaia q = r|Xs.

s B C

b1 c1

r A B

a1 b1

a1 b2a2 b1

Fig. 2.25

q A B

a1 b1

a2 b2

IMPLEMENTAREA OPERATORILOR ALGEBREIRELATIONALE N SQL


154/445

1. Restricia

A where Bselect * from StudCurs

WHERE NRPOINT > 59;

IDC IDST NRPOINT NOTEETC

---- ---- ---------- ----------5004 0001 60

5005 0001 70

5004 0003 60

5005 0005 70

5004 0007 605005 0008 70

6 rows selected.

2. Proiecia A[X,Y,...,Z]

SELECT DISTINCT IDST


155/445

FROM StudCurs;

IDST----

0001

0002

00030005

0006

0007

0008

7 rows selected.


156/445

4. Jonciunea A times B where C


157/445

select Cours.IDC, Student.IDST, null

from Student, Cours, dual

whereStudent.anEt=1

;

IDC IDST N

---- ---- -

5001 0001

5002 0001

5003 0001

5004 0001

5005 0001

IDC IDST N

---- ---- -

5001 0003

5002 0003

5003 0003

5004 0003

5005 0003

IDC IDST N

---- ---- -

5001 0007

5002 0007

5003 0007

5004 0007

5005 0007

5. Divizarea A(X,Y) devid by B(Y)

SELECT IDST FROM StudCurs


158/445

GROUP BY IDST

HAVING COUNT(*) = (SELECT COUNT(*) FROM Cours) ;

StudCursIDC IDST NRPOINT NOTE

---- ---- ---------- ------

-

5001 0001 20

5002 0001 30

5003 0001 50

5004 0001 60

5005 0001 70

5001 0002 20

5002 0002 30

5003 0003 50

5004 0003 60

5005 0005 70

5001 0003 205002 0005 30

5003 0006 50

5004 0007 605005 0008 70

CoursIDC NO POINTC IDG

---- -- ------- ---

5001 c1 10 001

5002 c2 30 002

5003 c3 20 003

5004 c4 30 0015005 c5 20 003

IDST

----

0001

:

Urmtoarele trei interogri cer ca tabelele s aibaceleai tipuri. Din acest motiv, vom construi doutabele virtuale numite vederi Student2 Student1


159/445

tabele virtuale numite vederi Student2 Student1din tabelul Student:

create view Student1 ASselect IDST, nomSt, anSt, IDGrup

FROM Student

WHERE anSt


160/445

select IDST, nomSt, anSt, IDGroup

FROM Student

WHERE anSt >= 3;

SELECT * FROM Student2;

Student2

IDST NOME ANST IDG---- ---- ---------- ---

0004 St04 3 001

0005 St05 4 001

0008 St08 3 002

0009 St09 3 003

0010 St10 3 0020011 St11 3 003

6. Uniune : A UnionB


161/445

SELECT *

FROMStudent1

UNIONSELECT *

FROMStudent2;

IDST NOME ANST IDG

---- ---- ---------- ---

0001 St01 1 0020002 St02 2 001

0003 St03 1 001

0004 St04 3 001

0005 St05 4 001

0006 St06 2 001

0007 St07 1 002

0008 St08 3 002

0009 St09 3 003

0010 St10 3 002

0011 St11 3 00311 rows selected.

7. Diferena A Minus B


162/445

SELECT *

FROM Student1MINUS

SELECT *

FROM Student2;

IDET NOME ANET IDG---- ---- ---------- ---

0001 St01 1 002

0002 St02 2 001

0003 St03 1 001

0006 St06 2 001

0007 St07 1 002

8. Intersecia: A intersect B


163/445

SELECT *

FROM Student1INTERSECT

SELECT *

FROM Student2;

IDET NOME ANET IDG---- ---- ---------- ---

0004 St04 3 001

0008 St08 3 002

0009 St09 3 003

0010 St10 3 002

0011 St11 3 003

Capitolul 3


164/445

Capitolul 3

DEPENDENE FUNCIONALEProiectarea logic a bazei de date presupunediminuarea redundanei i asigurareasecuritii datelor. Acest scop se poate atinge,

dac se cunosc restriciile ce pot fi aplicateasupra datelor. Dependenele sunt restriciiimpuse datelor n baza de date. Mulimea dedependene este partea esenial a schemeiunei relaii, deci i a schemei bazei de date.

3.1. Noiuni generaleS considerm relaia orar din fig 3 1


165/445

S considerm relaia orardin fig. 3.1.orar PROFESOR DISCIPLINA ZI ORA GRUPA SALA

Petrescu Baze de date Luni 8:00 0941 402Petrescu Baze de date Mierc. 14:30 0941 216

Petrescu Baze de date Mierc. 16:00 0941 216

Vasilache Progr.logic Luni 9:30 0941 404

Fig. 3.l. Relaia orarAceast relaie arat, care profesor pred disciplina dat,crei grupe, n ce zi a sptmnii, la ce or i n ce sal.Atributele ce formeaz schema acestei relaii nu pot primi

orice valori. Atributele se afl ntr-o interdependen.

n particular, se impun atributelor urmtoarele restricii:(1) di i li d i d di d


166/445

(1) o disciplina este predat unei grupe de studiu de un

singur profesor;(2) profesorul, n ziua dat, la ora dat se gsete ntr-o

singur sal;(3) n ziua dat, la ora dat, n sal dat se pred o

singur disciplina.Aceste restricii, ce reflect o interdependen ntreatribute, sunt exemple de dependene funcionale.

Dependena funcional este o generalizare a noiunii decheie.

Restriciile de mai sus pot fi formulate:(1) DISCIPLINA GRUPA d i f i l


167/445

(1) DISCIPLINA GRUPA determin funcional

PROFESOR sau, ce e echivalent PROFESOR e determinatfuncional de DISCIPLINA GRUPA;

(2) PROFESOR ZI ORA determin funcional SAL;(3) ZI ORA SAL determin funcional DISCIPLINA;

i notate respectiv:(1) DISCIPLINA GRUPA PROFESOR;(2) PROFESOR ZI ORA SALA;(3) ZI ORA SALA DISCIPLINA.

Unica posibilitate de a determin


168/445

dependenele funcionale const ntr-o analizcu luare-aminte a semanticii atributelor. nacest sens dependenele sunt de fapt aseriunidespre lumea real. Ele nu pot fi demonstrate.

Dar ele pot i trebuie s fie susinute deSGBD-uri. Majoritatea sistemelor susinnumai dependenele funcionale determinatede cheile relaiei. Dar sunt i sisteme ce susindependene funcionale arbitrare.

T b i i d l d d l


169/445

Trebuie menionat c declararea dependenelor

funcionale ntr-o baza de date este o decizie pe careo ia numai proiectantul bazei de date. Odatdeclarate SGBD-ul v susine aceste restricii. nafar de aceasta, dup cum se v vedea n celelalteseciuni, graie dependenelor, exist o structur maieficient de pstrare a datelor. Dependenelefuncionale vor servi la proiectarea schemelor

bazelor de date cu anumite proprieti dezirabile.

Definiia 3 1 Fi l i h R i


170/445

Definiia 3.1. Fie relaia r cu schema R i

X,YR. Vom spune c dependena funcionalXY este valid n relaia r (sau relaia rsatisface dependena funcional XY), dac,

pentru orice dou tupluri din r, fie t1 i t2 dincondiia c tuplurile au X-valori identice,urmeaz c au i Y-valori identice, adict1[X]=t2[X]t1[Y]=t2[Y].

D X Y lid (R) X


171/445

Dac X Y e valid n r(R), vom spune c X

determin funcional Y sau, c Y e determinatuncionalde X n aceast definiie (i mai departe)

simbolul "" noteaz "implic".Deci dependenta funcional XY reprezint o

restricie de integritate aplicat tuplurilor relaieir(R), n sensul c oricare dou tupluri din r care

prezint o aceeai valoare pentru X trebuie sprezinte o aceeai valoare pentru Y.


172/445

Definiia 3.l poate fi interpretat i n felul urmtor:relaia r(R) satisface dependenta funcional XY, dacrelaia Y(X=x(r)) conine nu mai mult de un tuplupentru orice valoare x a atributului X.

Partea stng a dependenei poart numele dedeterminant, iar partea dreapt a dependenei poartnumele de determinat Astfel n cadrul dependeneiXY, X este determinantul, iar Y determinatul.

Exemplul 3.1. Considerm relaiile din fig.3.2 n elesunt valide urmtoarele dependente functionale n


173/445

sunt valide urmtoarele dependente functionale n

relaia r1 AB, n relaia r2 AB, BA, n relaiar3 AB.

r1 A B

a1 b1a2 b2

a3 b1

a4 b1

a5 b2

a6 b2

Fig. 3. 2. Relaiile r1, r2 i r3

r2 A B

a1 b1a2 b4

a1 b1

a3 b2

a1 b4

a4 b3

r3 A B

a1 b1a2 b4

a1 b1

a3 b2

a2 b4

a4 b4

xemplul 3.1. Considerm relaiile din fig.3.2 n ele suntalide urmtoarele dependente functionale:n relaia r : AB


174/445

- n relaia r1: AB,

- n relaia r2: AB, BA,- n relaia r3: AB.

r1 A B

a1 b1a2 b2

a3 b1

a4 b1

a5 b2

a6 b2

Fig. 3. 2. Relaiile r1, r2 i r3

r2 A B

a1 b1a2 b4

a1 b1

a3 b2

a1 b4

a4 b3

r3 A B

a1 b1a2 b4

a1 b1

a3 b2

a2 b4

a4 b4

Pentru a verifica dac o dependenta e valid ntr-o relaiedat, se utilizeaz urmtorul algoritm.Algoritmul SATISF (r XY)


175/445

Algoritmul SATISF (r, XY)

Intrare: Relaia r(R), dependenta funcional XY, undeX,YR.Ieire: Adevr, dac relaia r satisface dependentafuncional XY,fals - n caz contrar.

(1) Se sorteaz tuplurile relaiei r n aa fel, ca tuplurile cuX-valori egale s fie grupate mpreun.(2) Se verifica dac mulimea de tupluri cu X-valori egaleare i Y-valori egale, atunci la ieire obinem adevr, n cazcontrarfals.

Menionm c nu ne intereseaz dependenele


176/445

funcionale ntmpltoare, dar numai acele cedecurg din semantica atributelor. De exemplu,

n relaia orar e valid i dependentafuncional

PROFESORDISCIPLIN

Dar ea nu reprezint o restricie ce reflectlumea real, fiindc n realitate un profesor

poate i, de regul, pred mai multe discipline.

umai dependenele nentmpltoare, asigur integritateasemantic a bazei de date De exemplu, dac un utilizatord t i l i t l


177/445

dorete s insereze n relaia orarun tuplu

dd(orar,


178/445

ntr-o relaie r(R) n orice moment sunt valide o

mulime de dependente funcionale, s zicem F. Adic Feste o mulime de dependente satisfcut de relaia r(R).Aici apare aceeai problem ca i n cazul cheilor. Oextensie a relaiei satisface mulimea F de dependente

funcionale, n timp ce alt extensie nu satisface. Pe noi neintereseaz numai dependenele ce sunt satisfcute deorice extensie a relaiei r(R). Dar pentru aceast suntnecesare cunotine asupra semanticii relaiei r(R).

om considera c mulimea F de dependente


179/445

funcionale este definit pe mulimea R de

atribute ce formeaz schema relaiei r i oriceextensie a relaiei r satisface mulimea F.Evident c mulimea de dependente valide n(R) este finit, fiindc finit este schema R.

Prin urmare, s-ar putea verifica dac r satisfacedependenele din F, aplicnd algoritmulSATISF. ns astfel de soluie este foartelabonoas. Exist o alt cale. Dac sunt

cunoscute nite dependente, din ele pot fideduse altele.


180/445

Definiia 3.2. Fie relaia r cu schema R, F - omulime de dependente funcionale i f odependenta asupra R.

otm cu SAT(F) mulimea tuturor relaiilorasupra R ce satisface orice dependenta din F.

Vom spune c F logic implic f, sau f esteconsecm logic a F. Scriem F|=f, dac oricerelaie r(R) ce satisface dependenele din Fsatisface i f, adic

r(R) SAT(F) r(R) SAT(F{f})


181/445

O regul de inferen stabilete c, dac o

relaie satisface anumite dependene, ea

trebuie s satisfac i alte dependene. Vom

considera ase reguli de inferen a

dependenelor funcionale.

Fie relaia r definit pe mulimea de atribute R

i

fie W,X,Y,ZR.

DF1. Regul reflexivitii. Dac YX atunci


182/445

DF1. Regul reflexivitii. Dac YX, atunci

XY.Definiia 3.3.0 dependen XY este trivialdac YX.

Regul DF1 genereaz numai dependenetriviale i ea nu depinde de F, ntructXR, atunci X i RX suntdependene triviale.Deoarece XX, XX e dependen trivial.Dintre aceste dependene prima, X, nu arenici o aplicare practic.


183/445

DF2. Regul incrementrii. Dac XY iZW, atunci XWYZ.S observm c regul DF2 are mai multecazuri speciale.

Dac Z= i XY, atunci XWY pentruorice submulime W din R.Dac W=Z i XY, atunci XWYW.Dac X=W, Z=X i XY, atunci XXXY,adic XXY.

Exemplul 3.2. Considerm relaia din figura3.3. Relaia r(ABCD) satisface dependenfuncional AB. Confom regulii DF2 n


184/445

aceast relaie sunt valide i dependenele:

ABB, ACB, ADB, ABCB,

ABDB, ACD.B, ABCDB, ACBC,AD^BD, ABCBC, ABDBD, ACDBC,ACDBD, ACDBCD, ABCDBC,ABCDBD, ABCDBCD.

r A B C D

a1 b1 c1d1

a2 b2 c1 d1

a1b1 c1d2

a3 b3 c2d3

Fig3.3

DF3. Regul aditivitii. Dac XY iXZ atunci XYZ


185/445

XZ, atunci XYZ.

Exemplul. 3.3. Relaia r(ABCD)reprezentat n fig.3.3 satisface dependenelefuncionale AB i AC. Conform reguliiDF3, relaia r trebuie s satisfac i dependen

ABC.DF4. Regul proiectivitii. Dac XYZ,atunci XY.

Exemplul 3.4. Relaia din fig.3.3 satisfacedependen funcional ABC. Conformregulii DF4, ea satisface i dependenele ABi AC.

DF5. Regul tranzitivitii. Dac XY iYZ atunci XZ


186/445

YZ, atunci XZ.

Exemplul 3.5. Relaia r(ABCD),reprezentat n fig.3.4, satisface dependenelefuncionale AB i BC. Conform reguliitranzitivitii, relaia r satisface i dependenfiinctional AC.

r A B C D

a1 b1 c2d1

a2 b2 c1 d2

a3b1 c2d1

a4 b1 c2d3

Fig.3.4


187/445

DF6. Regul pseudotranzitivitii. DacXY i YWZ, atunci XWZ.S observm c proiectivitatea (DF4) este,ntr-un sens, regul invers regulii aditivittii

(DF3). Regul DF3 se utilizeaz pentru a unidou dependene cu determinante egale n una,n timp ce regul DF4 - pentru descompunereaunei dependene.

3.3. Axiomele Armstrong


188/445

3.3. Axiomele Armstrong

Definiia 3.4. Fie F o mulime de dependeneasupra R i fie f o dependen funcionalasupra R. Derivaie a dependenei f din F,notat cu F|-f, este o consecutivitate finit de

dependene funcionale f1,f2,.,.,fkunde:(1) orice dependen f1 poate fi dedusa din (osubmulime a mulimii) F{f1,f2,...,fi-l},aplicnd regulile de inferen DF1-DF6;(2) f este ultimul element, fk, nconsecutivitate.

C di i (l) i fi f l


189/445

Remarc. Condiia (l) mai poate fi formulatn felul urmtor. Orice dependen f esteelement al mulimii F sau se deduce dinconsecutivitatea {f1, f2,..., fi-1}, aplicndregulile de inferen DFl-DF6.

Dac F|-f, vom spune c F deriv f sau c f ederivabil din F. Dac G este mulime dedependene funcionale, atunci prin F|-G sesubnelege c orice dependen funcional

din G e derivabil din F.


190/445

E clar c, dac n condiia (1) a definiiei 3.4mulimea de dependene funcionale F e vid,adic |-f, atunci f e dependen trivial,fiindc singura regula de inferen

corespunztoare poate fi doar DF1.Cu ajutorul regulilor de inferen putemdeduce noi dependene funcionale din celedate.


191/445

Exemplul 3.4. Fie r o relaie cu schema R iX,Y,ZR. Presupunem c n r(R) sunt validedependenele XYZ i XY. Atunci,conform regulii DF6, relaia r satisface i

dependen XXZ care se reduce La XZ.Pentru a combate o afirmaie desprevaliditatea unei dependene funcionale, esuficient de a aduce un exemplu de relaie cenu satisface afirmaia dat.

Exemplul 3.5. S combatem afirmaia cd d XY ZW i li d d


192/445

dependen XYZW implic dependenXZ.Relaia r(ABCD) din fig.3.6 satisfacedependen funcional ABCD, dar nusatisface dependen AC.

r A B C D

a1 b1 c1d1

a1 b2 c2d1

Fig.3.6


193/445

Unele reguli de inferen pot fi deduse dinaltele.Armstrong a artat c regulile DFl, DF2 iDF5 formeaz o mulime de reguliindependente, iar regulile DF3, DF4 i DF6pot fi deduse din DF l, DF2 i DF5.Mulimea {DFl, DF2, DF5} de reguli deinferen este cunoscut sub denumirea deaxiome Armstrong.

Teorema 3 1 Regulile DF3 DF4 i DF6 se


194/445

Teorema 3.1. Regulile DF3, DF4 i DF6 sededuc din regulile DFl, DF2, DF5.Definiia 3.5. Fie F o mulime de dependenefuncionale asupra schemei R i X,YR.nchiderea mulimii F, notat cu F+ se

definete recursiv:(1) FF+;(2) Dac F1F i F1|-XY, atunci XYF+;(3) Nimic altceva nu e n F+.


195/445

Deci,F

+=F{XY| F1|-XY pentru F1F i X,

YR}.Cu alte cuvinte, nchiderea unei mulimi de

dependene funcionale, F+ reprezintmulimea tuturor dependenelor funcionalecare se pot deriv din mulimea F, aplicndaxiomele Armstrong.

Este clar c F+

=(F+

)+

.

Exemplul 3.6. Fie relaia r(ABC) iF={ABC, CB}.Atunci


196/445

Atunci

F+= {AA, ABA, ACA, ABCA,BB, ABB, BCB, ABCB, CC,ACC, BCC, ABCC, ABAB,ABCAB, ACAC, ABCAC, BCBC,

ABCBC, ABCABC, ABC, ABAC,ABBC, AQABC, CB, CBC, ACB,ACAB}.n F+ primele nousprezece dependene sunt

triviale i se deriv din mulimea

dedependene, aplicnd DF1, adic |-{XY|YXABC}.

Alte dependene XY se deriv din ZY,


197/445

unde ZX, aplicnd regula incrementrii(DF2), adic {ZY} |-(XY|ZXR, YR,YX}. n F+ avem ase dependene deduse,aplicnd regula DF2 asupra F.

Deci:ABC|-{ABAC, ABBC, ABABC} i{CB)|-{CBC, ACB, ACAB}.Regula tranzitivitii nu genereaz dependenenetriviale. n afar de aceasta, F+ conine cele

dou dependene din F. n total F+ const dindouzeci i apte dependene.

Din exemplul de mai sus, se observa cnumrul de dependene ce alctuiesc F+ este


198/445

numrul de dependene ce alctuiesc F este

destul de mare n raport cu F.Dac F=, atunci F+ const numai dindependene triviale. Fiindc orice relaie r(R)satisface orice dependen trivial asupra R.

Dependenele triviale, bineneles, nu seconsider restricii asupra relaiei. ntruct Rare 2

[R] submulimi, numrul de dependenetriviale ntr-o relaie este exponenial. Nu vom

consider de asemenea dependenele de formaX, fiindc ele nu au aplicare practic.


199/445

3.4. Completitudinea regulilor de inferenDefiniia 3.6. Fie R1 o mulime de reguli de inferenasupra mulimii de dependene F. Mulimea R1 de regulieste nchis, dac F|-f, utiliznd regulile din R1, implic

F|=f. Mulimea de reguli de inferen R1 este complet,dac F|=f implic F|-f, utiliznd regulile din R1.


200/445

C mulimea de reguli DFl-DF6 este nchis,adic ele au loc n orice relaie, s-a demonstrat

pentru fiecare regul n parte n seciunea 3.2.

Pentru a arta c mulimea de reguli estecomplet, mai nti introducem noiunea denchidere a unei mulimi de atribute.


201/445

Definiia 3.7. Fie F o mulime dedependene asupra R i XR. nchidereamulimii de atribute X n raport cu mulimeade dependene F, notat cu X+ se defineteastfel:

(1) XX+ (X e o submulime a nchiderii);

(2) Dac ZX+ i ZYF, atunci YX+(3) Nici un alt atribut nu face parte din X

+.

Adic X+X{Y|ZX+ i ZYF}.

Condiiedefiniia

Comparare atribute,dependene

(AB)+


202/445

3.6.

p

(l)(2)(2)(2)

AB(AB)+ABAB i ABDEFDABDE i DCFCEABCDE i CE.GF

ABABDEABCDEABCDEG

Fig.3.7.

Exemplul 3.7. Fie R=ABCDEG i F={DC,ABDE, CEG}. S se arate c (AB)+ = ABCDEG. n

fg. 3.7 este reprezentat procesul de construire a (AB)+

.

Teorema 3.2. Mulimea de reguli de mferen DFl-DF6 este complet. Deci, dac F| =XY, atunci F|-XY


203/445

XY.

Lund n consideraie c s-a demonstrat (ncompartimentul 3.2.) c mulimea de reguli estenchis, adic F|-XY implic F|=XY putem spunec mulimea de reguli de inferen DF1-DF6 este

nchis i complet, adic F =XY, dac i numai dacF|-XY. Prin urmare, putem utiliza " |= " i " |-"deopotriv.Dat fiind faptul c regulile DFl-DF6 se deduc din

axiomele Armstrong, vom spune c i axiomeleArmstrong sunt nchise i complete.

3.5. Modele de derivriNoiunea de consecutivitate de derivare


204/445

introdus n seciunea 3.3 are o serie dedezavantaje. De regul, pentru o dependenpot exista o serie de derivri din mulimea dedependene date F. Aceste derivri, fiind nesen echivalente, difer prin ordinea i tipulregulilor aplicate pentru derivarea

dependenelor din consecutivitate. n plus,consecutivitile de derivare pot coninedependene derivate redundante. Mai jos vom

examina modele de derivri ce ntr-o msursau alta sunt lipsite de aceste dezavantaje.


205/445

3.5.1. RAP-consecutiviti de derivareAxiomele Armstrong sunt o submulimecomplet de reguli de inferen a mulimiiDF1-DF6. Exista, ns, mulimi complete de

reguli de inferen ce nu sunt submulimi alemulimii DF1-DF6. Considerm o astfel demulime de reguli de inferen denumit B-axiome.

Pentru relaia r(R), submulimile W, X, Y i Zale mulimii R i CR avem:


206/445

ale mulimii R i CR avem:B1. Regul reflexivitii. Dac YX, atunciXY.B2. Regul acumulrii. Dac XYZ iZCW, atunci XYZC.

B3. Regul proiectivitii. Dac XYZ,atunci XY.Teorema 3.3. Mulimea de reguli B1-B3 esteo mulime nchis.

Teorema 3.4. Mulimea de reguli B1-B3 estecomplet.

Definiia 3.8. Consecutivitatea de dependenefuncionale se numete RAP-consecutivitate dederivare (dup primele litere ale denumirilor


207/445

B-axiomelor: Reflexivitate, Acumulare,Proiectivitate) a unei dependene XY dinmulimea de dependene F, dac:(l) prima dependen n consecutivitate eXX;(2) ultima dependen n consecutivitate eXY (obinut, aplicnd regula B3);(3) orice dependen din consecutivitate (nafar de prima i ultima) sau este o dependendin F, sau are forma XZ i e obinut,aplicnd regula B2 asupra dependenelorprecedente.

Exemplul 3.8. Fie F=(ABE, G- J, BEI,EG, GIH}. Consecutivitatea de mai joseste RAP-consecutivitate de derivare a


208/445

este RAP consecutivitate de derivare a

dependenei ABGH din F.f1 :=ABAB (B1),f2 :=ABE (dat),f3 :=ABABE (B2: f1, f2),

f4 :=BEI (dat),f5 :=ABABEI (B2: f3, f4),f6 :=EG (dat),f7 := ABABEIG (B2:f5, f6),

f8 :=GIH (dat),f9 :=ABABEIGH (B2: f7, f8),f10:=ABGH (B3: f9).

3.5.2. DDA-grafuri de derivareDDA-graful (Derivation Directed Acyclic-

graph) este o interpretare grafic a RAP-

consecutivitii de derivare.


209/445

Fig 3.9

Definiia 3.9. Fie F o mulime de dependenefuncionale asupra schemei R. DDA-graasupra F este un graf orientat far cicluri ce se


210/445

asupra F este un graf orientat far cicluri ce se

definete recursiv:R1. O mulime de noduri notate cu atribute dinR este DDA-graf.R2. Dac H este DDA-graf i B1,.,.,Bn sunt

noduri n H i dependen funcionalB1,...BnCZ este n F, atunci H

1, obinut dinH prin adugarea nodului C (dac astfel de nodnu exist) i muchiilor (B1C) ... (BnC) orientate

spre C, este DDA-graf.R3. DDA-graf este numai graful obinut prinaplicarea regulilor R1 i R2.

Definiia 3.10. Nodul B al unui DDA-gra

H se numete iniial, dac n el nu intr nici omuchie (Nodunle iniiale se adaug n H prin


211/445

muchie (Nodunle iniiale se adaug n H prinregula R1)

Definiia 3.11. Fie H un DDA-graf asupra F

Graful H se numete DDA-graf de derivare adependenei XY din F, dac:

(1) X este mulimea de noduri iniiale n H,(2) orice atribut din Y este un nod n H.

Definiia 3.12. Mulimea de dependene dinF, utilizate de regula R1 pentru construirea

DDA-grafului H de derivare a unei dependeneXY din F se numete mulime utilizabil,notat cu U(H).

Exemplul 3.9. n fig. 3.9 sunt prezentate


212/445

etapele de construire a DDA-grafului dederivare a dependenei ABCG din mulimeade dependene funcionale

F={ABCD, AI, CE, DEGI}.Nodurile iniiale sunt A i B. Mulimea

utilizabil U(H)={ABCD, CE, DEGI}Graful H obinut este DDA-graful de derivarea dependenei ABCG din F, fiindcmulimea de atribute AB formeaz nodurile

iniiale din H, iar CG sunt noduri n H.

3.5.3. Derivaia maximalModelele de derivare descrise mai sus


213/445

poart mai mult un caracter teoretic. Ele nusunt lipsite de neajunsul c pentru odependen dat exist mai multeconsecutiviti de derivare Aici vom consideraun model, numit derivare maximal, liber deacest dezavantaj. Acest model este foarte

aproape de noiunea de nchidere a uneimulimi de atribute n raport cu o mulime dedependene funcionale Ei va fi utilizat ndemonstrarea diverselor rezultate privindacopennle de dependene funcionale.

Definiia 3.13. Fie F o mulime dedependene funcionale asupra schemei R i feXR. Derivaia maximal a mulimii de


214/445

atribute X n raport cu mulimea dedependene funcionale F este oconsecutivitate de mulimi de atribute

,

unde(1) X0=X,

(2) Xi=Xi-1Z, li n, unde Z = iWj pentruorice dependen VjWjF ce satisface

VjXi-1 i Wj X i-1.(3) n F nu exist nici o dependen VjWjpentru care V Xn i WiXn.

nainte de a arta c derivaia maximal esteun instrument puternic de modelare a derivrii


215/445

dependenelor funcionale, considerm douproprieti ale ei.Lema 3.1. Dac XY i consecutivitile

, sunt derivaiimaximale ale mulimilor X i Y,corespunztor, n raport cu F, atunci pentruorice Xi exist o mulime Yj nct XiYj i ji.

Lema 3.2. Dac estedenvaia maximal a mulimii X n raport cu

mulimea de dependene funcionale F, atunciXXiF

+, 0in.

n baza acestor dou proprieti se poatedemonstra.


216/445

Teorema 3.5. Fie derivaiamaximal a mulimii X n raport cu mulimeade dependene funcionale F Atunci XYF+dac i numai dac YXn.

Definiia 3.14. Fie XY

F

+

i denvaia maximal a mulimii X nraport cu F. Fie Xi este primul element din

consecutivitate ce conine mulimea Y.Subconsecutivitatea se numetederivaia dependenei funcionale XY nraport cu F.

Din teorema 3 5 i definiia 3.14 urmeaz:Consecina 3.1. XYF+ atunci i numai

atunci cnd exist derivaia dependenei XY


217/445

p

n raport cu F.Consecina 3.2. Dac XYF+ i

dependen VWF e utilizat n construireadenvaiei dependenei XY n raport cu F,

atunci XVF+.Trebuie menionat, c derivaia maximal

este un model de derivare liber dedezavantajele menionate la nceputul acestei

seciuni. Existena a unei singure derivaiipentru o dependen dat v fi util nexpunerea de mai departe a materiei.

3.5.4. Algoritmi


218/445

Pentru a deternuna dac F|=XY, esuficient de verificat dac XYF+. ns, F+este excesiv de mare n raport cu F. Edezirabil o metod de verificare, dac XYaparine F+, fr a deduce toate dependenelefuncionale din F. Un astfel de algontm eprezentat mai jos. Nucleul algontmului constdin procedura de construire a nchideriimulimii de atribute X n raport cu F. Dup ce

se gsete X+ se verific dac YX+.


219/445

Este evident c ultimul element, Xn, dinderivaia maximal nu este altceva dect X+ iarteorema 3.5 ne sugereaz c XY urmeaz

logic din F, dac YX+

. Deci, derivaiamaximal servete drept model teoretic pentruurmtorul algontm de deternunare a lui X+.


220/445

Algoritmul CLOSURE caut n F odependen funcional pentru caredeterminantul reprezint o submulime a luiXi, iar determinatul nu-este inclus n Xi. Dacse gsete o astfel de dependen funcional,atunci se adaug la Xi atributele, careconstituie determinatul dependenei. Dac nuse gsete, atunci nchiderea cutat, X+ estereprezentat de mulimea de atribute Xi.

Algoritmul CLOSURE (F, X, X+)Intrare: F- o mulime de dependenefuncionale asupra schemei R; X - o mulimede atribute, XR.


221/445

Ieire: X+ - nchiderea mulimii X n raport cuF.begini:=0; Xi:=X;

repeati:=i+l;Xi:= X i-1;For all VW in F

if VXi then Xi:= X iW;until Xi:= X i-1;retum (X+:=X,);end.

Exemplul 3.10. Fie F={BCD, ADE,BA}, X=B. S se calculeze X+.Iniial X0=B.n ciclul repeat:


222/445

pX1=B.n ciclul for:X1= BCD (aplicnd BCD),X1= ABCD (aplicnd BA).

X2=ABCD.n ciclul for:X2=ABCDE (aplicnd ADE)X3=ABCDE.

Dup ciclul forX3=X2.Rezultat: X+:=ABCDE.Deci nchiderea lui B n raport cu F este(B)+=ABCDE.


223/445

Algoritmul CLOSURE realmente

construiete derivaia maximal a mulimii deatribute X n raport cu F. Apelnd laCLOSURE e uor de construit algoritmul deverificare a apartenenei unei dependenefuncionale la F+. Aceast verificare e realizatn algoritmul MEMBERSHIP.

Algoritmul MEMBERSHIP(F, XY)Intrare: F- o mulime de dependene funcionale;


224/445

XY - o dependen funcional.Ieire: adevr, dac F | =XY, fals - n caz contrar.begin

CLOSURE (F, X, X+);

if YX+ then retum (adevr) else retum (fals);end.Corectitudinea algoritmilor CLOSURE iMEMBERSHIP rezult imediat din teorema 3.5.


225/445

3.6. Acoperirin aceast seciune se consider diverse

moduri de reprezentare a mulimilor de

dependene, cum ar fi mulimilenonredundante, reduse, canonice, minimale ioptimale.

3.6.1. Mulimi echivalente de dependenefuncionale

Definiia 3.15. Dou mulimi de dependenefuncionale F i G se numesc echivalente, notat cu


226/445

FG, dac F+=G+. Vom mai spune n acest caz c Facoper G (sau G acoper F).

Dac FG, adic F+=G+, atunci orice dependenXY ce urmeaz logic din F unneaz i din G. Deci

pentru a verifica dac F i G sunt echivalente se iaorice dependen XY din F i se verific dacG|=XY. Dac o oarecare dependen XY nuaparine lui G+ atunci F+G+. Apoi analogic se verific

dac orice dependen VW din G se deduce din F.Dac toate dependenele se deduc, mulimile F i Gsunt echivalente.


227/445

Exemplul 3.11. Mulimile F={ABC,ACD, ADB, CB} i G={ADC,ABD, CB} sunt echivalente, ns F nu

este echivalent mulimii G1

={ABC,ACD, ADB, ACB} (a se verifica ncalitate de exerciiu).


228/445

3.6.2. Acoperiri nonredundanteDefiniia 3.16. Mulimea de dependenefuncionale F este nonredundant, dac nuexist o submulime proprie F1a mulimii F iF

1F. Dac o astfel de submulime exist,atunci F se numete redundant. Mulimea Feste acoperire nonredundant a mulimii G,dac F este acoperire pentru G i F estenonredundant.


229/445

Exemplul 3.12. Fie G={ABC, BC}.Mulimea F={AB, AC, BC} esteacoperire a mulimii G, dar nu e acoperirenonredundant, fiindc F1={AB, BC} eacoperire pentru G, ns F1F.S considerm o alt interpretare a noiunii demulime nonredundant.

Definiia 3.17. Mulimea F de dependene


230/445

funcionale se numete nonredundant, dac n ea nuexist nici o dependen XY nct (F \ {XY})|=XY. n caz contrar, F se numete redundant.

Aceast definiie este pus n baza urmtoruluialgoritm de construire a acoperirii nonredundante. E de

menionat c rezultatul obinut n urma aplicriialgoritmului depinde de ordinea considerriidependenelor funcionale.

Algoritmul NONREDUN (F,G)

Intrare: F - o mulime de dependene


231/445

funcionale.Ieire: G - o acoperire nonredundant amulimii F.begin

G:=F;for all XY in Gif MEMBERSHIP (G \ {XY}, XY) thenG:=G\{XY};

retum (G);end.


232/445

Exemplul 3.13. Fie F = {AB, BA, BC,AC}. n rezultatul aplicrii algoritmului

ONREDUN obinem acoperirea nonredundant G= {AB, BA, AC}. Dac mulimea F e

prezentat n alt ordine {AB, AC, BA,BC} se obine rezultatul G = {AB, BA,BC}.


233/445

3.6.3. Acoperiri reduseDac F e o mulime nonredundant, atunci

nu poate fi eliminat din F nici o dependenfuncional fr a afecta echivalent mulimiiobinute cu cea anterioar. n schimb poate fimicorat dimensiunea mulimii F, eliminndunele atribute din dependenele funcionale.

Definiia 3.18. Fie F o mulime dedependene funcionale asupra schemei R iXYF. Atributul A este redundant n


234/445

dependen XY n raport cu F, dac:(1) AX, V=X \A i F\{XY}{VY}Fsau

(2) AY,W=Y\A i F\{XY}{XW}F.

Cu alte cuvinte, atributul A este redundantn dependen XY, dac el poate fi eliminatdin determinant sau determinat, fr a fischimbat nchiderea mulimii F. Procesul de

eliminare a atributelor redundante se numete,corespunztor, reducere n stnga i reduceren dreapta a dependenelor.


235/445

Exemplul 3.14. FieF = {ACB, AC, ABD}.

Atributul C este redundant n ACB,fiindc (AC)+ = A+ = ACBD. Adic AB este

n F+

. Deci dependen ACB poate finlocuit cu AB n mulimea de dependenefuncionale F. Atributul B este redundant n

partea dreapta a dependenei ABD.


236/445

Definiia 3.19. Fie F o mulime de dependenefuncionale asupra schemei R. Mulimea F senumete redus n s

Date post:	06-Apr-2018
Category:	Documents
Upload:	sergiu-alexandrov
View:	225 times
Download:	0 times

BDD_Prezentare

Documents