Curs RDBMS - baze de date

Curs RDBMS

Sectiunea 1:

Notiuni generale baze de date

In functie de destinatie (modul de utilizare) se definesc doua tipuri de baze de date:

OLTP (online transaction processing) - o baza de date "operationala", folosita atunci cand se doreste stocarea si managementul unor operatii curente, operatii ce au o frecventa de aparitie mare. In functie de operatiile critice, baza de date poate fi proiectata astfel incat acestea sa se efectueze cat mai repede (operatiile critice sunt INSERT/UPDATE/DELETE)

OLAP (online analytical processing) - o baza de date "analitica", folosita pentru a extrage informatii, rapoarte analitice, sintetice, statistici, etc. Cunoscuta ca si "sistem multidimensional". Fiecare informatie poate fi privita ca o dimensiune. Software-ul localizeaza intersectia mai multor dimensiuni si afiseaza rezultatul ( De exemplu: toate produsele vandute in Timisoara, care au un pret mai mare de 100$ intr-o anumita perioada de timp) (Operatia critica: SELECT)

Modele fizice de SGBD

Flat files + ISAM - O baza de date ce foloseste fisiere plate stocheaza datele intr-un singur fisier care are definite coloane si contine linii. Nu exista relatii definite intre mai multe fisiere pentru ca un fisier nu stie de existenta altuia. Accesul si actualizarea se fac destul de rapid deoarece au un sistem de indexare a informatiilor (ISAM - Indexed Sequential Access Method). Pentru o coloana anume, daca se doreste accesarea directa a unei informatii, se adauga un index in care sunt ordonate liniile conform cu valorile din acea coloana. Sistemul este eficient pentru a fi folosit atunci cand nu exista relatii foarte multe intre fisiere.

Ierahic - Acest model leaga inregistrarile intre ele intr-o structura arborescenta (de exemplu fiecare angajat are un singur sef) - deci relatia gestionata este de tipul parinte-copii .
Daca aceasta dependenta nu mai este verificata ( de exemplu un pacient are mai mult de un singur doctor) atunci modelul ierarhic devine model retea.

Retea - similar cu modelul Ierarhic cu diferenta ca un copil poate avea mai multi parinti.

Relational - In acest model datele sunt stocate in tabele si coloane. Tabelele pot fi relationate intre ele prin valori unice de relationare. In modelul relational accentul se pune pe accesarea si regasirea datelor si pe pastrarea integritatii acestora. Informatiile pot si extrase, referite, prin SQL (Structured Query Language) indiferent daca ele sunt stocate intr-o tabela sau in mai multe. Integritatea datelor se obtine prin definirea unor reguli si contrangeri.

Obiectual - modul de salvare a informatiilor este acela obiectual, asa cum apar obiectele definite intr-un limbaj de programare. Acest sistem de baze de date contine si mecanisme de persistare transparenta a informatiilor, de acces concurential, etc. Se foloseste atunci cand entitatile logice cu care se lucreaza sunt complexe si nu se pot stabili identificatori unici si relatii clare.

Sectiunea 2:

Modelul Relational (RDBMS)

Modelul logic de definire a bazei de date

Conceptele cu care se lucreaza sunt:

Entitate: O entitate reprezinta un obiect concret/discret. Putem sa asemanam entitatile cu substantivele dintr-o fraza.(de exemplu: un calculator, un angajat, o factura etc.)

Relatie: Aceasta reprezinta modul in care doua sau mai multe entitati se leaga (se relationeaza) una de cealalta. Ele pot fi asemanate (aproximativ) cu verbele dintr-o fraza. (de exemplu relatia apartine dintre un calculator si o companie, relatia supervizeaza dintre un angajat si un departament, etc.)

Exemplu (substantivele sunt entitati si verbele relatii): Un client face un contract de servicii cu un furnizor de servicii. Furnizorul trimite clientului facturi pentru serviciile efectuate.

Atribut: atat entitatile cat si relatiile pot avea atribute care reprezinta caracteristici ale acestora. (de exemplu: entitatea persoana poate avea atributul CNP; relatia apartine dintre calculator si companie poate avea atributul data achizitionarii)

Cheie: O cheie a unei entitati este o combinatie de atribute care identifica in mod unic liniile (instantele entitatii), adica nu exista doua linii care sa fie diferite si sa aiba aceleasi valori ale atributelor care constituie cheia. Daca aceasta cheie este ireductibila, adica scotand un atribut din cheie, oricare ar fi acesta, nu se mai respecta regula de mai sus si noua combinatie de atribute nu mai e cheie, atunci cheia se numeste cheie candidata. (de ex: pentru o entitate Persoana: o cheie ar fi (NUME, PRENUME, CNP) iar cheia candidata este (CNP,NUME) (din experienta stim ca CNP-ul singur nu este unic).

Cheie primara: aceasta se alege arbitrar dintre cheile candidate, dar este de preferat sa aiba cat mai putine coloane.

Chei "artificiale" si chei "reale": cheile reale sunt cele care rezulta din modelul abtract si sunt constituite din atribute ale entitatilor sau relatiilor reprezentate, cele artificiale sunt folosite pentru o gestionare mai usoara a datelor si sunt adaugate atunci cand se face implementarea modelului.

Modelul fizic de definire a bazei de date: reprezinta implementarea fizica intr-un sistem SGBD a modelului logic. Conceptele logice se traduc in concepte fizice:

Entitate -> Tabela

Relatie -> Cheie straina sau Tabela

Atribut -> Coloana in Tabela

Instanta a entitatii -> Linie in Tabela

De mentionat ca nu trebuie neaparat sa exista o corespondenta exacta intre modelul logic si modelul fizic. In proiectarea modelului logic accentul se pune pe modelarea cat mai clara a businessului cerut iar in proiectarea modelului fizic se va tine seama si de considerente de performanta, optimizare acces, spatiu ocupat, arhitectura fizica a serverelor, etc.

Clasificarea relatiilor

Gradul unei relatii: reprezinta numarul de entitati pe care le conecteaza (in mod general gradul este n, iar cazuri particulare sunt relatiile ternare si binare). Exista teorii care spun ca cel mai bine e sa reduci toate relatiile la relatii binare.

Cardinalitate (relatii binare): reprezinta multiplicitatea in cadrul relatiei pentru fiecare entitate relationata.

Relatie 1 - 1: Atunci cand cel mult o instanta din entitatea A este asociata cu o singura instanta din entitatea B. (de exemplu intr-o companie fiecare angajat are asignat un calculator. Pentru fiecare angajat exista un singur calculator asociat si fiecare calculator este asociat cel mult unui angajat.) Relatia 1 - 1 poate aparea in mod natural ca o reprezentare a businessului (asociere unica intre doua entitati) sau ca metoda indirecta de modelare (optimizare acces, derivare entitati, etc.) . Posibile metode de implementare sunt:

o       O singura tabela - care sa contina atributele ambelor entitati. Avantaje: viteza de acces, spatiu mic ocupat; Dezavantaje: foarte greu de modificat in viitor daca se doreste schimbarea cardinalitatii

o       Doua tabele - fiecare sa contina cate o entitate. Cheia primara din tabela parinte este cheie primara si straina in tabela copil .

o       Doua tabele - fiecare sa contina cate o entitate. Cheia primara din tabela parinte este cheie straina in tabela copil . In plus trebuie pusa o restrictie in tabela copil astfel incat sa se asigure unicitatea cheii straine, asigurand relatia 1 - 1.

Relatie 1 - n: O instanta din entitatea A este asociata cu una sau mai multe instante din entitatea B. (De exemplu un profesor care preda un curs are mai multi elevi dar fiecare elev are un singur profesor). Posibile metode de implementare sunt:

o       O singura tabela - care sa contina atributele ambelor entitati. Dezavantaje: redundanta a datelor, anomalii de utilizare (Insert/Update/Delete)

o       Doua tabele - fiecare sa contina cate o entitate. Cheia primara din tabela parinte este cheie straina in tabela copil .

o       Trei tabele - doua tabele sa contina cele doua entitati si una sa contina cheile de legatura. In plus trebuie pusa o restrictie in tabela de legatura astfel incat sa se asigure unicitatea acelei chei care are multiplicitatea 1. Avantajul ar fi ca relatia se poate modifica foarte usor in viitor in m-n.

Cateva scenarii tipice de utilizare a relatiei 1 - n ar fi: tabela lookup, tabele master-detail, etc.

Relatie m - n: Fiecarei instante din entitatea A ii pot corespunde mai multe instante din entitatea B, si invers. Posibile metode de implementare:

o       O singura tabela: care sa contina atributele ambelor entitati si sa contina ca si valori toate combinatiile de instante dintre cele doua. Dezavantaj major : redundanta si anomalii de utilizare

o       Trei tabele: doua tabele sa contina cele doua entitati si a treia sa contina cheile de legatura.

Relatia aceasta poate fi o legatura pur si simplu (de exemplu relatia dintre pacienti si doctori intr-un spital) sau poate fi o relatie atributata (care sa existe ca si entitate in sine)( de exemplu . furnizoriServicii, clienti si contracte)

Alegerea tipului de relatie intre doua entitati trebuie facuta printr-o analiza atenta nu doar a situatiei existente ci si a posibilitatilor de extensie ulterioare; totodata trebuie sa se tina seama si de criteriile de performanta (altfel s-ar face toate relatiile ca fiind de tipul m-n si s-ar putea suporta orice modificari ulterioare ale cerintelor).

Sectiunea 3:

Optimizarea bazei de date

Indexarea tabelelor

Un index este o lista ordonata de linii dintr-o tabela folosita de DBMS pentru a accelera cautarea in tabela. Indexul este structurat ca un arbore de cautare care are ca si chei valoarea/valorile din coloanele specificate. Queriurile efectuate pe o tabela indexata se executa mult mai rapid si mai eficient decat cele efectuate pe o tabela neindexata. In loc ca atunci cand se cauta o valoare sa se scaneze toata tabela, DBMS-ul foloseste indexul si gaseste mult mai repede inregistrarea care are acea valoare. Unele din DBMS-uri folosesc in plus indecsii si pentru integritatea datelor prin aceea ca asigura unicitatea valorilor din acele coloane.

Partitionarea datelor

De multe ori cantitatea informatiilor stocate intr-o tabela ingreuneaza viteza de accesare a acestora. Atunci cand este posibil, datele se pot partitiona pentru a creste viteza de acces. Partitionarea se poate face in doua moduri:

partitionare orizontala: In acest tip de partitionare o tabela care contine multe inregistrari se sparge in mai multe tabele care au exact aceleasi coloane. Fiecare tabela nou creata va contine un subset de date din tabela initiala. Aceasta metoda este eficienta in cazul in care:

separarea in subseturi de date se face potrivit cu majoritatea interogarilor/accesarilor informatiilor, astfel incat sa nu fie nevoie prea des sa se grupeze in acelasi resultset (rezultatul unui query) a informatiilor din mai multe sub-tabele,

si in plus criteriul dupa care se face impartirea sa nu aiba o dinamica ridicata, ca sa nu fie nevoie sa se mute inregistrari dintr-o sub-tabela in alta.

De exemplu daca consideram ca avem tabela abonatilor telefonici care contine abonatii din toata tara, o putem sparge in cate o tabela pentru fiecare judet in care isi au domiciliul abonatii. Asta inseamna totusi ca statistic vorbind abonatii nu isi schimba prea des domiciliul si in plus nu ma intereseaza prea des sa obtin informatii grupate pe abonatii din mai multe judete.

partitionare verticala: Acest tip de partitionare se refera la tabelele care au foarte multe coloane. Aceste tabele vor fi relationate prin relatii 1 - 1, avand aceeasi cheie de identificare. Motivele pentru care se face aceasta partitionare ar fi:

Doar un subset din aceste coloane este accesat in mod curent, restul foarte rar.

In functie de cerinte se poate ca sa se doreasca drepturi diferite de acces pe anumite coloane, sau mai mult, doar anumite date se modifica iar celelalte sunt read-only.

In cazul folosirii sistemelor de dimensiuni mari sau foarte mari, partitionarea se poate face astfel incat subtabelele rezultate sa rezide chiar pe servere diferite pentru a distribui incarcarea acestora.

Normalizarea

Normalizarea este acel proces de modelare a unei baze de date, proces realizat in mai multi pasi, astfel incat in final datele sa fie consistente si sa nu fie redundante (informatii duplicate).

In general o baza de date denormalizata ridica mai multe probleme legate de consistenta si simplitatea operatiilor efectuate asupra datelor. Sa presupunem ca o tabela contine informatii legate de 2 entitati diferite: elevi si cursuri. Datorita acestui lucru pot apare urmatoarele probleme:

Redundanta: avem aceeasi informatie stocata de mai multe ori -> spatiu ocupat inutil

Anomalii de Insert: daca vrem sa adaugam un curs nou trebuie sa introducem si cel putin un elev

Anomalii de Update: acelasi elev care participa la doua cursuri poate avea informatii diferite pentru acelasi atribut ( de exemplu doua nume diferite - big mistake!!! )

Anomalii de Delete: daca stergem ultimul elev de la un curs stergem si informatiile legate de curs.

Cum putem gandi de fapt normalizarea: fiecare tabela trebuie sa contina informatii despre o singura "tema": entitate sau relatie, din modelul reprezentat. Este evident ca daca ea contine sa spunem informatii despre doua entitati apar anomaliile de IUD. Daca exista informatii despre o entitate si o relatie atunci atributele entitatii pot apare de mai multe ori, in functie de natura relatiei, si de asemenea nu pot stoca date de spre entitate fara a exista o relatie, ceea ce este de multe ori nenatural.

Asadar, daca avem grija sa nu avem intr-o tabela informatii legate de mai mult decat o entitate sau relatie, totul e ok.

Normalizarea unei baze de date se bazeaza pe principiul de compozitiei nedistructive, care spune in principiu ca o tabela care nu respecta formele normale trebuie fragmentata in mai multe tabele normalizate, cu conditia sa nu pierdem informatii (in special relatii intre entitati) si sa putem reconstitui prin join-uri forma initiala a tabelei.

In cadrul procesului de normalizare s-au definit un set de reguli acceptate de comun acord, reguli ce trebuie respectate astfel incat sa se poata spune despre o baza de date ca este normalizata. Aceste reguli au fost denumite Forme Normale. Exista cel putin 6 asemenea forme normale, ele fiind cumulative. Primele 3 dintre acestea au un impact important in performantele unei baze de date.

• Prima forma normala (1NF)

O tabela este in prima forma normala daca are o cheie primara (adica nu exista linii duplicate), nu exista grupuri repetitive si toate atributele sunt atomice si consitente(au acelasi tip).

Grupuri repetitive: combinatii de coloane care contin exact acelasi gen de informatii si se repeta. De exemplu avem o tabela de genul:

Atribute nonatomice: atribute care pot fi divizate fara a se pierde semnificatia lor. De exemplu un camp de adresa poate fi impartit in strada, numar, bloc, scara, ap. etc. O observatie importanta este ca atomicitatea unui camp poate tine de natura aplicatiei. Daca de exemplu nu vom avea nevoie niciodata sa obtinem separat numele strazii sau numarul apartamentului, atunci putem considera adresa un atribut atomic, altfel nu. O greseala ar fi sa exageram, fragmentand atributele atunci cand nu este nevoie.

Coloanele sunt consistente daca contin informatii de acelasi gen. Este o greseala de exemplu sa facem o coloana de tip caracter care contine informatii numerice pe care le procesam mai apoi prin conversie

• A doua forma normala (2NF)

O tabela este in a doua forma normala daca este in prima forma normala si toate atributele non-chei depind de intreaga cheie primara.

Asta inseamna ca intr-o tabela toate atributele trebuie sa apartina entitatii pe care o identifica cheia primara, adica nu trebuie sa amestecam atributele a doua entitati diferite. Daca anumite atribute depind de o parte a cheii primare atunci ele apartin unei alte entitati identificata de partea respectiva.. De exemplu avem o tabela cu detaliile unei facturi:

Cheia primara este NR_FACTURA, COD_PROD si identifica liniile unei facturi. NR_FACTURA este acea parte a cheii primare care identifica factura. Este o greseala sa punem in aceasta tabela COD_CLIENT, pentru ca este un atribut al facturii, nu al liniei din factura. Codul clientului va apare de mai multe ori si chiar putem gresi, punand doua coduri diferite la aceeasi factura. Acelasi lucru se poate spune despre coloana DENUMIRE_PRODUS care depinde doar de COD_PRODUS.

• A treia forma normala (3NF)

O tabela este in a treia forma normala daca este in a doua forma normala si toate toate atributele non-chei depind direct de cheia primara.

Ce inseamna acest lucru? Pe scurt. nu trebuie sa punem intr-o tabela "atribute ale atributelor".

Exemplu:

Cheia primara este COD_FIRMA, iar COD_LOC este un atribut al firmei, localitatea in care se afla. Desi numele localitatii depinde de codul firmei, el este un atribut al localitatii, si nu al firmei. Prima problema care apare este ca nu putem adauga o localitate noua in baza de date daca nu adaugam si o firma.

De obicei daca o baza de date respecta primele trei forme normale este suficient de normalizata astfel incat sa se poata lucra cu ea. Pe langa primele trei forme, mai exista si altele (Forma normala Boyce-Codd, A patra forma normala, A cincea forma normala, Forma normala Domain-Key ).

Sa luam un exemplu de baza de date nenormalizata si sa o aducem in 3NF.

Normalizarea este foarte buna daca gandim ca baza de date trebuie sa fie consistenta si sa ocupe cat mai putin spatiu. Din pacate lucrul acesta costa. Dezavantajul folosirii unei baze de date normalizata excesiv este acela ca performanta scade destul de mult si totodata creste si complexitatea folosirii acestei baze de date. Daca pentru o baza de date nenormalizata era suficient sa fac un SELECT pe tabela sa obtin toate datele, dupa normalizare trebuie sa fac o multime de join-uri pentru a obtine acelasi rezultat. Tinand seama de faptul ca adesea utilizatorii vor sa vizualizeze datele consolidate si foarte rar ii intereseaza doar o bucatica din informatii, atunci ne putem imagina ca desi pentru programatori normalizarea este frumoasa si buna, utilizatorii sunt aceia care platesc pretul . si asta nu e bine.

Pentru a face un compromis intre o baza de date bine structurata si un acces rapid si facil la date, asupra bazei de date trebuie sa i aplice un proces de denormalizare controlata.

Sectiunea 4:

Denormalizarea

Denormalizarea este procesul invers normalizarii in sensul ca anumite redundante sunt introduse intentionat in designul bazei de date pentru a usura accesarea datelor.

Procesul este urmatorul: Se porneste de la o baza de date nenormalizata, se normalizeaza conform cu regulile bine-cunoscute (formele normale) si apoi se studiaza care sunt queriurile care sunt greoaie si ca scriere si ca timp de executie. Se studiaza tabelele si relatiile care sunt referite de acele queriuri si se renunta la anumite reguli de normalizare punctual in acele locuri (de obicei prin dublarea unor informatii).

Dupa cum am mentionat atunci cand spuneam de avantajele normalizarii, o baza de date normalizata nu are redundanta si nici inconsistente. Aceasta inseamna ca exceptiile de la regulile normalizarii vor trebui sa fie contracarate prin alte masuri (de aceea spuneam ca denormalizarea trebuie sa fie controlata). (de exemplu pentru a ne asigura ca o valoare care apare de mai multe ori este modificata in toate locurile atunci cand se modifica intr-unul, introducem un trigger care sa se ocupe de asta).

Cateva scenarii tipice in care se foloseste denormalizarea:

1. Istoricul preturilor (tarifelor) intr-un nomenclator (vezi diagramele in Visio):

Presupunem ca avem un nomenclator de produse, in care se stocheaza urmatoarele informatii:

• CodProdus
• DenumireProdus
• Pret

Daca vrem sa pastram si istoricul preturilor, ar trebui sa introducem si Data Intrarii in Vigoare a pretului respectiv. Daca tinem seama de principiile normalizarii, vom face o noua tabela Preturi, in care vom avea urmatoarele informatii:

• IdProdus (cheie straina)
• Pret
• DataIntrareInVigoare

In acest moment putem spune ca avem o baza de date normalizata care sa gestioneze Produsele si Preturile acestora, cu istoricul lor.

Totusi gandindu-ne la modul de constructie al queriurilor, constatam ca pentru a afla pretul unui produs la o anumita data, operatia este destul de complexa si de neperformanta, din cauza ca nu pot determina dintr-o singura inregistrare din istoric daca ea respecta criteriul de selectie.

Pentru a imbunatati aceasta introducem inca un camp in tabela de preturi, si anume DataExpirare. Teoretic aceasta informatie este redundanta, pentru ca se poate deduce din Data intrarii in vigoare a urmatoarei valori a pretului produsului, dar interogara se simplifica, devenind o simpla conjunctie de doua conditii (DATA > DataIntrareInVigoare ) && (DATA < DataExpirare)

Problema care apare insa este aceea ca aceasta redundanta ne obliga sa folosim mecanisme suplimentare de validare a valorilor introduse. Trebuie ca in momentul introducerii unui nou pret, sau in momentul modificarii unui pret existent, sau in momentul stergerii unui pret sa verificam ca intervalele datelor sa fie disjuncte dar sa nu existe perioade calendaristice neacoperite.

Pe langa aceasta denormalizare, se mai poate aplica una in anumite conditii. Daca se constata ca desi se pastreaza istoricul preturilor, in majoritatea cazurilor ne intereseaza doar ultima valoare introdusa (adica pretul curent) atunci aceasta valoare se poate stoca chiar in tabela de produse, ea inlocuindu-se de fiecare data cand se introduce o noua valoare in tabela de preturi. Avantajul ar fi acela al vitezei crescute ce acces la pretul curent (pentru ca nu mai trebuie facut nici un join). Dezavantajele ar fi acelea ca trebuie scris cod separat care sa se ocupe de sincronizarea acestei valori redundante, si in plus codul care aduce ultima valoare ar fi diferit de cel care aduce celelalte valori.

In concluzie, in functie de cerintele specifice ale aplicatiei si de operatiile critice asupra bazei de data, se pot aplica diverse denormalizari care sa mareasca performanta.

2. Calcule de totaluri partiale intr-o structura arborescenta

Sa presupunem ca avem o aplicatie care gestioneaza fisele de fabricatie a diverse masini industriale. Mai multe piese formeaza un subansamblu, care intra in componenta unei parti a masinii, iar partile formeaza masina. Sa presupunem ca pretul final al masinii este suma preturilor componentelor. Asta poate sa nu fie impresionant, dar ganditi-va ca exista masinarii care sunt formate din mii de piese, cu multi pasi de asamblare (ceea ce implica multe nivele in arborele care descrie componenta masinii ). Daca aplicatia trebuie sa afiseze alaturi de alte informatii si preturile diverselor subansamble sau produse finite poate sa fie cam incomod ca se calculeze de fiecare data suma preturilor.

O denormalizare care ar aduce o imbunatatire asupra performantei ar fi sa stocam pentru fiecare produs, parte sau subansamblu pretul sau, obtinut prin sumarea preturilor componentelor sale de pe nivelul imediat inferior. Daca modul de constructie a unei masini nu se schimba prea des ( asa cum se intampla de obicei ), dar se fac multe interogari legate de pret atunci costul mentinerii consistentelor este mic in comparatie cu costul recalcularii la fiecare interogare.