Definirea modelului relational, Normalizarea relatiilor

Definirea modelului relational

Normalizarea relatiilor

Nivelul intern (fizic)

Proiectarea bazei de date

Modelul relational are la baza conceptul de relatie definit în teoria matematica a multimilor, ca fiind o submultime a produsului 24524l1115y cartezian al mai multor multimi:

R M₁ M₂ M_n. Relatia poate fi definita si în termenii logicii matematice. Fie m = (m₁, m₂, . , m_n) M₁ M₂ M_n si un predicat P(m₁, m₂, . , m_n), atunci: [M₁, M₂ , . , M_n] R = (m₁, m₂, . , m_n) / P (m₁, m₂, . , m_n) = adevarat

Familia de multimi pe care este definita relatia se numeste domeniu, iar daca M₁ = M₂ = . = M_n, relatia este omogena. Numarul n se numeste gradul relatiei (aritatea relatiei), un element al relatiei t = (m₁, m₂, . , m_n) este numit tuplu, iar numarul de tupluri indica cardinalul relatiei.

Relatiile se reprezinta într-o forma simpla prin tabele, supuse urmatoarelor restrictii:

q       în fiecare coloana toate valorile sunt de acelasi fel;

q       fiecare valoare este un numar sau un sir de caractere(nu trebuie sa fie grup sau ansamblu);

q       ordinea liniilor în tabel nu este predefinita si nu sunt admise duplicate;

q       coloanele sunt identificate prin nume distincte care reprezinta atributele relatiei.

Prelucrarea relatiilor se face prin algebra relationala

Operatorii relationali se pot grupa în operatori de baza, care pot genera toata clasa operatorilor relationali si operatori auxiliari. Operatorii relationali de baza se împart în operatori de asamblare si operatori unari.

Operatorii de asamblare sunt operatori binari, care primesc la intrare 2 relatii si genereaza la iesire o singura relatie. Acestia sunt: reuniunea, diferenta si produsul cartezian, care au aceeasi semnificatie ca si în teoria multimilor. Operatorii unari se aplica asupra unei relatii si genereaza o alta relatie. Din aceasta clasa fac parte proiectia si selectia.

Proiectia relatiei R de schema R (A₁, A₂, . , A_n) dupa atributele A_i1, A_i2, . , A_ip (i_i i_k si p < n) este relatia R' de schema R' (A_i1, A_i2, . , A_ip), ale carei tupluri se obtin prin eliminarea valorilor atributelor din R care nu apar în R' si prin suprimarea dublurilor.

R' = P A_i1, A_i2, . , A_ip (R)

Altfel spus, prin intermediul proiectiei, dintr-un tabel cu un anumit numar de coloane se obtine unul cu un numar mai mic de coloane.

Selectia relatiei R fata de criteriul Q este relatia R' cu aceiasi schema ca si R, ale carei tupluri satisfac criteriul (predicat).

Q = A_i1 q C₁ L A_i2 q C₂ L A_ip q_p C_p, unde q_i < > , C_i - constante

Altfel spus, prin operatorul de selectie, dintr-un tabel cu un anumit numar de coloane se obtine unul cu aceleasi coloane, dar cu un numar mai mic de rînduri.

Operatorii auxiliari pot fi dedusi din setul de operatori de baza si sunt: compunerea (Join), intersectia si împartirea (diviziunea). Compunerea conditionala (Join) a doua relatii R1 si R2 dupa calificatorul multi -atribut Q este relatia E ale carei tupluri sunt cele ale produsului cartezian R1 x R2 care satisfac calificatorul Q. Functie de calificatorul Q se disting mai multe tipuri de compuneri:

q       daca Q este de forma A_i = B_j , se numeste echicompunere;

q       daca Q este de forma A_i q B_j : unde q < > se numeste q compunere, si poate fi exprimata în functie de operatorii de baza.

q       daca Q este de forma A_i = A_j se numeste autocompunere.

Compunere naturala este o echicompunere pe R₁ si R₂ dupa toate atributele având acelasi nume în R₁ si R₂, urmata de o proiectie care permite conservarea unuia dintre aceste atribute, egale ca nume.

Privita prin prisma modelului relational, baza de date apare ca o colectie de relatii (tabele) normalizate, în care fiecare coloana reprezinta un atribut distinct iar fiecare rând un tuplu distinct. Tuplurile unei relatii se pot identifica în mod unic prin intermediul valorilor unuia sau mai multor atribute (eventual toate atributele), care joaca rol de cheie primara a relatiei respective. Se numeste domeniu primar, un domeniu pe care este definit un singur atribut drept cheie primara. Dându-se doua relatii R₁ si R₂ cu atributele A₁ si A₂ chei primare definite pe acelasi domeniu primar D, spunem ca A₁ este cheie externa, daca utilizând o parte din valorile ei sau toate, putem regasi tuplurile relatiei R₂. Altfel spus, un atribut al unei relatii este cheie externa, daca se regaseste pe post de cheie primara într-o alta relatie.

Deoarece relatiile reflecta un anumit aspect din realitate, acestea se supun unor restrictii care sunt de doua tipuri:

q       restrictii de integritate care depind de semantica valorilor domeniilor si care cer ca relatiile sa se supuna urmatoarelor reguli:

integritatea entitatii, prin care valorile cheii primare trebuie sa fie diferite de zero; altfel cheia nu va mai fi identificator;

integritatea referirii, potrivit careia valorile unei chei externe trebuie sa refere tuplurile unei alte relatii sau sa fie nedefinite.

q       alte restrictii care se aplica asupra tuplurilor relatiei si nu asupra domeniilor, reflectând anumite corelatii de ordin valoric (egalitate, inegalitate).

E. F. Codd, a aratat ca într-o anumita forma relatiile poseda proprietati nedorite, pe care le-a numit anomalii de actualizare:

q       Anomalia de stergere consta în faptul ca anumite date care urmeaza sa fie sterse, fac parte din tupluri în care se gasesc si alte date care mai sunt necesare în continuare, ori stergerea facându-se la nivelul tuplului, acestea se pierd.

q       Anomalia de adaugare consta în faptul ca anumite date care urmeaza sa fie adaugate fac parte din tupluri incomplete (pentru care nu se cunosc toate datele), ceea ce face ca acestea sa nu poata fi adaugate.

q       Anomalia de modificare rezulta din faptul ca este dificil de modificat o valoare a unui atribut atunci când ea apare în mai multe tupluri ale relatiei.

Pentru a înlatura aceste anomalii, Codd a stabilit trei forme normale pentru relatii si a introdus procesul de normalizare care se bazeaza pe notiunea de dependenta functionala (FD) ca relatie între atributele unei entitati ce are un caracter invariant.

Fie date doua atribute D si E si notam domeniul valorilor lui D cu DOM (D) si domeniul valorilor lui E cu DOM (E) si o functie f: DOM (D) DOM (E). Spunem ca f este o dependenta functionala, daca pentru (") d DOM (D) distinct îi corespunde o singura valoare e DOM (E). Atributul D se numeste "determinantul" dependentei, iar dependenta se simbolizeaza D E. Dependenta functionala poate fi generalizata pe mai multe atribute: f: A₁, A₂, ., A_n B₁, B₂, ., B_m unde A₁, A₂, ., A_n se numeste "partea stânga" iar B₁, B₂, ., B_m se numeste "partea dreapta" a FD-ului.

O dependenta functionala f: DOM (D) DOM (E) este elementara (completa), daca nu exista o alta dependenta f': DOM (D') DOM (E), unde DOM (D') DOM (D) sau, altfel spus, daca "partea stânga" nu mai poate fi descompusa astfel încât rezultatul obtinut sa fie tot o dependenta functionala. Daca f: D₁, D₂,., D_m, D_{m + 1}, . , D_n E si g: D₁, D₂,., D_m E sunt doua FD-uri, unde m < n, atunci atributele D_{m + 1}, . , D_n se numesc atribute superflue pentru f, deoarece atributele D₁, D₂,., D_m sunt suficiente pentru a-l determina functional pe E. În aceasta situatie spunem ca E este dependent partial de D₁, D₂,., D_n.

Fie R [A₁, A₂,., A_n] o relatie si K o submultime a multimii de atribute (K . Spunem ca submultimea K este cheie primara pentru relatia R daca sunt îndeplinite urmatoarele conditii:

q       ") A_i K, A_i este dependent functional pe K;

q       ") K' K, A_i nu este dependent functional pe K'.

Armstrong a introdus un set de axiome si reguli de inferenta, care permit prelucrarea dependentelor functionale. Notând cu M multimea atributelor relatiei R, axiomele lui Armstrong sunt:

A1. Reflexivitatea: daca A B M A B;

A2. Cresterea: daca A B si X M AX BX;

A3. Tranzitivitatea: daca A B si B C A C.

Din cele trei axiome rezulta urmatoarele reguli de inferenta:

R1. Reuniunea: daca A B si A C A BC;

R2. Pseudotranzitivitatea: daca A B si XB C AX C;

R3. Descompunerea: daca A BC A B si A C.

O relatie este în forma normala 1 (1NF), daca si numai daca toate atributele ei contin numai valori atomice (fig. 1.a.).

Cheia primara a relatiei R este compusa din P# si B#, iar atributele U, X, C, L si T nu sunt complet dependente functional de aceasta. De asemenea perechile de atribute (L, C) si (L, T) sunt mutual dependente. Aceasta relatie poseda anomaliile de actualizare prezentate mai înainte, de exemplu:

q       nu putem adauga un tuplu pentru care nu cunoastem beneficiarul (B#) si localitatea (L), deoarece conform regulii de integritate a entitatii nici o componenta a cheii primare (P#, B#) nu poate fi nula;

q       daca produsul P5 nu mai poate fi fabricat temporar, deci trebuie sters tuplul (P5, buc, 30, 10, B₂, Aiud, 500, 968), înseamna ca se pierd si informatiile despre beneficiarul B₂, care mai sunt necesare în continuare;

q       daca dupa o perioada de timp intervine o schimbare a preturilor produselor, modificarea acestora se face greu datorita faptului ca acelasi pret intervine în mai multe tupluri (redundanta mare).

Pentru a înlatura anomaliile de actualizare, utilizând operatorul de proiectie, descompunem relatia R în trei relatii R1, R2 si R3 (fig. 1.b.) care sunt în forma normala 2 (2NF) si care conserva datele din relatia R.

O relatie este în forma normala 2 (2NF) daca si numai daca este în 1NF si orice atribut noncheie este complet dependent functional de cheia primara.

Analizând diagrama dependentelor functionale asociata relatiei R3 din fig. 1. b, observam existenta dependentelor tranzitive B# L, L C si B# L, L T care genereaza si ele anomalii de actualizare, cum sunt:

q       daca stergem tuplul referitor la beneficiarul B1 (B1, Brasov, 400, 921) se pierd si datele referitoare la localitatea, codul postal si prefixul telefonic, care mai sunt necesare;

q       modificarea codului postal (C) se face greu, datorita faptului ca aceiasi valoare apare în mai multe tupluri (redundanta mare);

q       nu putem adauga o noua localitate daca nu exista cel putin un beneficiar din localitatea respectiva.

Pentru a înlatura aceste anomalii, descompunem relatia R3 în doua relatii R₃₁ si R₃₂ (fig. 1.c.) care sunt în forma normala 3NF.

O relatie este în forma normala 3 ( 3NF ) daca si numai daca este în 2NF si fiecare atribut noncheie nu este dependent tranzitiv pe cheia primara. Relatiile R₁, R₂, R₃₁ , R₃₂ sunt în forma normala 3.

Considerând relatia A definita pe atributele: localitate (L), strada (S) si codul postal (C); cheia relatiei poate fi LS sau SC, iar multimea dependentelor functionale este: F = . Conform definitiei, relatia A este în 3NF si are doua chei candidate LS si SC. Analizând mai atent aceasta relatie, se observa ca nu putem adauga o localitate noua cu codul postal asociat daca nu specificam o adresa din localitatea respectiva, iar stergerea unei strazi implica si stergerea localitatii si a codului postal. Deci relatia A prezinta anomalii la operatiile de adaugare si stergere, ceea ce denota ca forma normala trei nu mânuieste satisfacator relatiile cu doi sau mai multi chei candidate.

Pentru a înlatura aceste anomalii, a fost introdusa forma normala Boyce - Codd (BCNF), (mai tare decât 3NF), potrivit careia o relatie A cu multimea dependentelor functionale F este în BCNF daca pentru orice dependenta (X Y) F cu Y X, X include o cheie, a relatiei A. Conform acestei definitii relatia A (L, S, C) cu F = nu este în BCNF din cauza dependentei C L, unde C nu este cheie pentru A.

Avantajele modelului relational

Facând o analiza a modelelor nerelationale comparativ cu modelul relational rezulta urmatoarele avantaje în favoarea celui din urma:

q       modelul relational este un model simplu care permite utilizatorului sa vada baza de date ca o colectie de tabele (relatii) - o reprezentare mentala larg accesibila atât informaticienilor cât si neinformaticienilor;

q       asigura independenta fizica si logica a programelor de prelucrare fata de structura datelor, eliminând din schema conceptuala si schemele externe toate detaliile privind structura de memorare si strategiile de acces;

q       operatia de normalizare introdusa de modelul relational asigura gasirea structurii optime a datelor prin înlaturarea anomaliilor de actualizare si diminuare a redundantei

q       Prin introducerea notiunilor de dependenta functionala, dependenta multivaloare si dependenta jonctiune modelul relational depaseste stadiul limitat al reprezentarii datelor în calculator, avansând spre formalizarea elementelor de semantica ce guverneaza domeniul informatiilor;

q       este un model omogen, deoarece reprezinta legaturile si asocierile dintre relatii tot prin relatii, spre deosebire de modelele ierarhic si retea care utilizeaza în acelasi scop conexiunea si respectiv setul.

q       suplete în comunicare cu utilizatorul neinformatician prin intermediul unor limbaje neprocedurale de nivel înalt.

Nivelul intern (modelul fizic) este cel ce corespunde structurii în care sunt stocate datele în interiorul masinii. Sunt specificate tabelele (fisierele) care le contin (nume, organizare, localizare etc.), componentele fiecarui fisier (lungime, câmpuri, plasare a acestora în cadrul fisierului), caile de acces la componentele tabelelor (indecsi, relatii, legaturi între tabele).

De exemplu, o factura poate fi accesata direct datorita unui index realizat pe numarul acesteia, iar cantitatile facturate pot fi cunoscute creând o legatura între tabelele "Factura_livrare" si "Produse_facturate", prin intermediul asocierii "Se_factureaza".

Se vor avea în vedere cerintele privind asigurarea protectiei datelor, atât din punct de vedere al continutului câmpurilor din tabele (verificarea si validarea valorilor câmpurilor la introducere, evitarea stergerii, din greseala sau din rea vointa, a datelor importante, cu secvente de program special concepute), cât si în ceea ce priveste accesul utilizatorilor la baza de date (stabilirea drepturilor de acces trebuie sa se faca tinând cont de rolul, functia si sarcinile fiecarui utilizator).

Proiectarea unei baze de date presupune realizarea modelelor conceptual, logic si fizic, prin trecerea de la MCD la MLD, apoi de la MLD la MFD.

MLD se obtine aplicând regulile de trecere de la MCD la MLD care vor fi prezentate în continuare.

1) O entitate devine o relatie, cu un nume distinct. Identificatorul entitatii devine cheie primara a relatiei. Atributele entitatii vor defini structura relatiei.

2) O RIF - restrictie de integritate functionala (asociere ierarhica) devine o legatura între relatii. Concret, relatia provenind din entitatea pentru care cardinalitatile sunt 1,1 "absoarbe" identificatorul celeilalte entitati, care se transforma în cheie externa (secundara). Daca se întâmpla ca asocierea sa aiba proprietate specifica, atributul respectiv este transferat si devine câmp al relatiei care provine din entitatea cu cardinalitate maxima 1. (Reamintim: pentru ca un câmp sa îndeplineasca rol de cheie externa, el trebuie sa fie cheie primara într-o alta relatie.)

3) O RIM - restrictie de integritate multipla (asociere non-ierarhica) devine o relatie, a carei cheie primara este constituita prin concatenarea identificatorilor entitatilor participante la asociere. Totodata, atributele proprii ale asocierii devin câmpuri în relatia nou determinata.

Modelul logic al datelor se poate prezenta astfel:

a) scriind numele relatiei, urmat de atributele sale între paranteze; cheia primara se subliniaza cu linie continua, iar cheia externa - cu linie punctata sau se marcheaza cu semnul diez - #.

Se considera cazul unei întreprinderi de distributie a materialelor pentru utilaje care doreste informatizarea subdomeniului facturare.

q       Clientela este compusa din aproximativ 1000 de clienti, împartiti în urmatoarele categorii: întreprinderi de productie; firme de comert (revânzare); firme de service de profil.

q       În catalogul întreprinderii exista circa 5000 de piese si alte materiale. Preturile acestora ramân valabile 6 luni. Catalogul este actualizat o data pe semestru.

q       Preturile aplicabile sunt cele de la data comenzii.

q       Produsele se împart în doua categorii: utilaje mici si accesorii pentru automobile.

q       Întreprinderea este structurata în 3 agentii. Fiecare agentie îsi gestioneaza stocurile si primeste comenzi de la clientii proprii.

q       Facturarile sunt centralizate la sediu.

q       Contabilitatea este deja informatizata. Problema consta, reamintim, în a informatiza facturarile.

q       Planul de informatizare al întreprinderii are prevazuta instalarea de terminale în fiecare agentie. Ele vor fi racordate cu cele de la sediul firmei în cauza.

q       Conducerea întreprinderii doreste facilitarea obtinerii de statistici comparative lunare (pe ultimele 12 luni) si anuale (pe ultimii 2 ani) a cifrei de afaceri, pe agentii, pe clienti (cu recapitulare pe categorii de clienti), pe produse (cu recapitulare pe categorii de produse). Totodata, urmareste diminuarea costurilor de facturare prin trimiterea clientilor firmei a unei singure facturi pentru toate livrarile dintr-o luna. În momentul solicitarii lucrarii de informatizare, pentru fiecare bon de livrare este emisa o factura. De asemenea, un bon de comanda poate genera mai multe livrari, daca întreprinderea a epuizat stocul pentru un produs comandat.

Examinând toate acestea, se stabilesc dictionarul de date si regulile de gestiune de care urmeaza sa se tina cont în modelare. Printre acestea se numara:

Livrarile sunt facturate la tarifele în vigoare pe baza de comanda.

Catalogul este actualizat de ori pe an.

Un bon de livrare genereaza o singura factura dar o factura poate corespunde mai multor bonuri de livrare.

Exista posibilitatea facturarii dupa livrare.

Un client poate sa trimita una sau mai multe comenzi.

O comanda vine de la un singur client.

Un client lucreaza numai cu una dintre agentiile întreprinderii.

Un produs poate sa figureze sau nu pe un bon de comanda sau de livrare.

O comanda poate determina mai multe livrari.

Un bon de livrare priveste o singura comanda.

Fiecarui produs îi corespunde un singur procent de TVA.

O comanda priveste unul sau mai multe produse.

Un client apartine unei singure categorii.

Un produs apartine unei singure categorii de produse.

Se stocheaza separat cifrele de afaceri pe 12 luni si cele anuale pe ani, pe clienti si pe produse.

Facturarea se face o data pe luna pentru fiecare client care a trimis comenzi.

Situatiile statistice cerute de managementul întreprinderii se realizeaza lunar.

În fiecare an se întocmesc situatiile comparative pe ani.

Se obtine lunar jurnalul de vânzari, pentru asigurarea legaturii cu domeniul contabil.

Din dictionarul de date se elimina sinonimele si polisemiile (de exemplu, pentru a desemna cantitatile comandate si livrate nu se poate stabili acelasi nume de atribut, "cantitate", ci se vor utiliza doua atribute diferite: "CantComd" si, respectiv, "CantLiv").

S-a ajuns la modelul conceptual al datelor din fig. 2.15. Aplicând regulile de trecere enuntate, se obtine modelul logic al datelor:

Agentii (NrAg, NumeAg)

Categorii_client (CodCatCli, DenCatCli)

Clienti (CodCli, NumeCli, Strada, Oras, CodPostal, #CodCatCli, #NrAg)

Facturi (NrFactura, DataFactura)

Bon_livrare (NrBonLivrare, DataLivrare, #NrFactura, #NrComd)

Document_comanda (NrComd, DataComd, #CodCli)

Produse (CodProdus, DenProdus, CotaTVA, #CodCatProd)

Categorii_Produs (CodCatProd, DenCatProd)

Data_limita_catalog (DataLimita)

Preturi (CodProdus, DataLimita, PretVânz)

Comenzi (NrComd, CodProdus, CantComd)

Livrari (NrBonLiv, CodProdus, CantLiv)

Explicatii privind trecerea de la MCD la MLD:

Ca efect al aplicarii primei reguli de trecere MCD -> MLD, se definesc relatiile Agentii, Categorii_client, Clienti, Facturi, Bon_livrare, Document_comanda, Produse, Categorii_produs, Data_limita_catalog si cheile primare ale fiecareia.

Corespondenta "apartine_1" din modelul conceptual reflecta o restrictie de integritate functionala (asociere ierarhica). A doua regula conduce, în cadrul modelului logic, la aparitia cheii externe #CodCatCli în relatia Clienti. Analog se procedeaza pentru toate restrictiile de acest tip.

Asocierea non-ierarhica numita    "contine" (restrictie de integritate multipla) dintre entitatilele Livrare si Produs necesita utilizarea celei de-a treia reguli; se defineste astfel relatia Livrari, cu cheie primara formata din doua atribute-identificator ale entitatilor participante la relatie (NrBonLiv, CodProdus) si proprietatea specifica asocierii "contine" (CantLiv) care devine un atribut al relatiei. La fel se trateaza si celelalte corespondente de tip RIM.

Modelul conceptual poate fi completat cu datele privind evidenta anilor si a lunilor din fiecare an, relationate cu cele privind clientii si produsele comandate de acestia. Trecerea de la MLD la MFD se face utilizând facilitatile si instrumentele oferite de SGBD-ul ales.

Deoarece SGBD Access implementeaza în totalitate teoria modelului relational, trecerea de la MLD la MFD se face foarte simplu, dupa cum urmeaza:

q       relatiile se transpun în tabele;

q       legaturile dintre tabele sunt asigurate prin corespondentele între cheile primare si cele externe.

Figura 2