Baze de date2-3

8/9/2019 Baze de date2-3

1/18

Baze de date Curs 2-3 1

Curs 2-3Prof. dr. ing. Dorin Carstoiu


2/18

Curs 2-3 2Baze de date

Cuprins1. Modelul datelor

2. Enttitati, atribute, relatii

3. Modelul entitate relatie (E-R)4.4. Memorarea datelor, fisiere, organizareMemorarea datelor, fisiere, organizare

5.5. Metode de cautare pentru acces la dateMetode de cautare pentru acces la date


3/18


1. Modele de date, scheme si instante1. Modele de date, scheme si instante

Definitie: Se defineste modelul datelor ca un set de concepte ce poatemodelul datelor ca un set de concepte ce poatefi utilizat in descrierea structurii datelorfi utilizat in descrierea structurii datelor. Prin structura bazei de datestructura bazei de datese intelege tipul datelor, legatura dintre ele, restrictiile ce trebuiescindeplinite de date.

O arhitectura de date asociata unei baze de date poate fireprezentata pe trei niveluri, avind ca scop separarea aplicatiilor

utilizatorului de baza de date fizica.Nivel

extern Grup 1 . Grup n

Nivel

conceptual Schema conceptuala

Nivel Schema internaintern

Mediul de stocare


4/18


Nivelul internNivelul intern constituit din schema interna ce descrie structura destocare fizica a datelor in baza de date

Nivelul conceptualNivelul conceptualsau schema conceptuala descrie structuraintregii baze de date pentru o comunitate de utilizatori. La nivelulconceptual se face o descriere completa a bazei de date, ascunzinddetaliile legate de stocarea fizica, concentrindu-se asupra descrierii

entitatilor, tipurilor de date, relatiilor dintre ele, precum si arestrictiilor asociate.

Nivelul externNivelul extern sau nivelul vizual (utilizator), include o colectie descheme externe ce descriu baza de date prin prisma diferitilorutilizatori. Fiecare grup utilizator descrie baza de date prin prismapropriilor interese. Exista tendinta la acest nivel ca grupuri deutilizatori sa ascunda detalii de care nu sint interesate. Si la acest

nivel se pot folosi modele de implementare sau modele de nivelinalt.


5/18


Modele conceptuale de nivel inalt (extern, conceptual)Modele conceptuale de nivel inalt (extern, conceptual)

Cerintele pentru constructia unei baze de date aferenta unei companii,numita COMPANIE.

Compania are un numar de angajati organizati pe departamente, siurmareste realizarea unor proiecte.

Compania este organizata in departamente, fiecare departament areun nume, un numar de cod, un numar de angajati (minim 6), putindavea mai multe sedii.

Un departament este implicat in mai multe proiecte, fiecare din eleare un nume, un numar de cod, si o singura locatie.

Se pastreaza pentru fiecare angajat numele, numarul de cod (socialsecurity number - ssn), adresa, salariul, sex, data de nastere. Oriceangajat este afiliat la un departament, insa poate lucra la mai multeproiecte ce nu sunt neaparat coordonate de acelasi departament.

Trebuie deci stocat si numarul de ore alocate saptaminal pentrufiecare proiect. De asemenea, fiecare angajat are un sef direct,numit si supervizor.

Lista persoanelor in intretinerea fiecarui angajat este importantaintrucit este utilizata la calculul impozitului, lista contine numele, sex,data nasterii.


6/18


2. Entitati, atribute, relatii

O entitate este un obiect real sau conceptual, cu oO entitate este un obiect real sau conceptual, cu oexistenta independenta. O entitate este un obiect cuexistenta independenta. O entitate este un obiect cuexistenta fizica, persoana particulara, automobil,existenta fizica, persoana particulara, automobil,companie, activitate, curs universitar, etc.companie, activitate, curs universitar, etc.

Orice entitate are o serie de proprietati numite si atributeatributece particularizeaza entitatea respectiva. De exemplu,

pentru o entitate angajat se pot enumera o serie deatribute cum sint nume, adresa, data nasterii, sex,salariu.

Ex:

e1={Nume=Vasile Ionescu, Adresa=Dreptatii - 211,

Sector 6, Virsta = 40, Telefon=6621311} e2={ Nume=U.P.B., Sediu=Splaiul Independentei - 313,

Rector=V. Constantinescu}


7/18


Atribut compus. Unele atribute pot fi impartite in parti mai mici cusemnificatie independenta. Un astfel de atribut este un atributcompuscompus. Un exemplu este cel al atributului adresa, ce poate fisubdivizat in atributele componente Oras, Judet, Cod postal, Strada.

Atributele ce nu sint compuse se numesc atribute atomiceatomice.Valoarea atributelor compusee se formeaza prin concatenareavalorilor atributelor atomice.

Multe atribute au valoare unica pentru o entitate particulara si sintnumite atribute cu o singurasingura valoarevaloare. Spre exemplu virsta uneipersoane. Exista atribute ce pot lua mai multe valori dintr-un set finit,ca de exemplu gradele didactice intr-o universitate, culoarea unuiautomobil, etc. Acestea sint atribute cu maimai multemulte valorivalori.. AtributeleAtributelederivatederivate sint atributele ce se pot determina din relatiile ce exista intre

ele ca de exemplu, virsta unei persoane ce se poate determina dindata curenta si data de nastere.


8/18


O baza de date este constituita in mod uzual din grupe de entitatisimilare. Fiecare angajat este caracterizat de aceleasi atribute, darfiecare entitate angajat va avea un set propriu de valori ce ilcaracterizeaza. Entitatile ce sint caracterizate de aceleasi atribute senumesc entitatientitati tiptip. Pentru entitatea tip ANGAJAT avind atributeleNume, Virsta, Salariu, se dau mai jos ca exemplu doua entitatiparticulare.

e1(Popescu Vasile, 43, 3880)e2(Dumitriu Petre, 32, 3240)

Descrierea atributelor entitatii tip este numita schema entitatiischema entitatii

Uzual, o entitate tip contine un atribut ce are valori distincte pentrufiecare entitate individuala. Acest atribut este numit atrtibut cheieatrtibut cheie, iarvalorile sale pot fi utilizate pentru identificarea in mod unic a

entitatilor componente. O cheie poate fi formata si din mai multe atribute, avind proprietatea

ca prin combinarea valorilor acestora se obtine un set de valoridistinct.


9/18


Pentru a se distinge, atributele compuse vor fi reprezentate intreparanteze. Se poate face prima descriere a bazei de dateCOMPANIE

O entitate tip DEPARTAMENTavind atributele Nume, Numar,Locatie (Sediu), Manager, Data de la care are aceasta functie.

Entitatea tip PROIECTcu atributele Nume, Numar, Locatie,Departamentul ce coordoneaza proiectul, cu atribut cheie oricaredintre Nume sau Numar.

Entitatea tip ANGAJATcu atributele Nume, SSN, Sex, Data nasterii,

Adresa, Salariu, Departament si Supervizor. Atributele Nume siAdresa pot fi atribute compuse.

O entitate tip INTRETINUTcu atributele Angajat, Nume, Sex, Datade nastere, Tip relatie (referitor la relatia dintre angajat si persoanaaflata in intretinere).

In aceasta incercare de definire nu s-a tinut cont de faptul ca un

angajat poate sa lucreze la mai multe proiecte, nu apare in acestcaz indicat numarul de ore pe saptamina alocate unui anumitproiect. Poate fi avut in vedere in cadrul entitatii ANGAJAT prinatributul compus Lucreaza_la ce ar avea componentele(Proiect,Ore).O alta alternativa poate fi introducerea unui atributcompus cu mai multe valori la entitatea PROIECT, atribut ce arecomponentele (Angajat, Ore).


10/18


O relatie tiprelatie tip R intre n entitati tip E1,E2,...,En este o asociatie deentitati de acelasi tip.

O relatie instanta ri arata de fapt ca entitatile participante in ri sint inrelatii ce corespund lumii reale. De exemplu relatiaLUCREAZA_PENTRU intre entitatile tip ANGAJAT siDEPARTAMENT asociaza fiecare angajat cu departamentul pentrucare acesta lucreaza.

Se defineste rangul sau gradul unei relatiirangul sau gradul unei relatii tip ca numarul entitatilortip ca numarul entitatilor

tip participantetip participante. Daca relatia se stabileste intre elementele aceleiasi entitati se spune

ca s-a stabilit o relatie recursivarelatie recursiva. Ca exemplu, relatia SUPERVIZORse stabileste intre angajati si supervizor, relatie in care ambii sintmembrii aceleiasi entitati.

Restrictia de cardinalitateRestrictia de cardinalitate este marcata de numarul relatiilor instantala care o entitate poate sa participe. Se simbolizeaza prin (m:n)

Restrictia de participareRestrictia de participare specifica conditia de existenta a unei relatii.Pot exista restrictii de participare partiala sau totala.


11/18


12/18


4. MEMORAREA DATELOR, FISIERE, ORGANIZARE4. MEMORAREA DATELOR, FISIERE, ORGANIZARE

Mediul de stocare poate fi impartit in doua categorii:

stocarea primarastocarea primara priveste acel mediu asupra caruia se poate operadirect de catre unitatea centrala.

stocarea secundarastocarea secundara se efera la toate mediile externe de memorare,cum sunt discul magnetic, banda magnetica, disc optic,caracterizate de capacitate mare, cost redus, dar cu un timp de

acces mult mai mare decit memoria interna.Justificarea stocarii externe:

volumul prea mare pentru a fi stocate in memoria principala;

datele ramin dupa intreruperea sursei de alimentare, adica aucaracter permanent;

costul pe unitatea de informatie este mult mai mic;

asigura transportabilitatea intre mai multe masini


13/18


Informatia este stocata pe suprafata discului pe cercuri concentricecu diametre distincte numitepistepiste ((tracktrack)). La discurile compactate

pistele de aceeasi raza formeaza un cilindrucilindru. Fiecare pista este impartita in mai multe blocuriblocuri, ce apartin unui

sectorsector. Marimea unui bloc este cuprinsa uzual intre 512 si 4096octeti functie de sistemul de operare aferent. Separarea blocurilor seface prin spatii de lungime fixa numite gap interblocgap interbloc, ce contineinformatii speciale de control scrise in momentul initializarii discului.

Orice referire la informatiile stocate pe disc este o referire la un bloc.Adresa blocului este obtinuta prin combinarea numarului suprafetei,numarului pistei (intr-o suprafata) si numarului blocului (in cadrulunei piste).

Accesul la informatiile de pe disc se face prin citirea unui bloc siaducerea acestuia in memoria principala intr-un spatiu continuunumit bufferbuffer.

Cind mai multe blocuri se transfera in memoria interna, existentamai multor buffere face ca viteza de transfer sa creasca.


14/18


Inregistrari cu lungime fixa

Inregistrari cu lungime variabila

In general, un bloc contine mai multe inregistrari, dar pot existainregistrari ce incep intr-un bloc si se termina in alt bloc, functie de

dimensiunea tipica a inregistrarii.


15/18


Daca se noteaza numarul de octeti ai unui bloc cu B, si cu R

numarul de octeti ai unei inregistrari (valabil doar pentruinregistrarile de lungime fixa), numarul inregistrarilor ce pot fi stocateintr-un bloc va fi dat de realtia:

bfr = [B/R] in care,

bfr - reprezinta numarul de inregistrari pe bloc (blocking factor rate)numarul de inregistrari pe bloc (blocking factor rate)

[x] - reprezinta functia parte intreaga.

In general R nu divide pe B, deci, daca nu sint inregistrari ce trecdintr-un bloc in altul, in fiecare bloc folosit ramine un spatiu neocupatde B-(bfr*R) octeti.

Alocarea blocurilor

Alocarea contiguaAlocarea contigua sau consecutiva a blocurilor

Alocarea cu legaturiAlocarea cu legaturi este metoda caracterizata de existenta unorpointeri de inlantuire a blocurilor.

Alocarea indexataAlocarea indexata utilizeaza unul sau mai multe blocuri index cecontin pointeri la blocurile cu inregistrarile de date.


16/18


5. Metode de cautare

1. Cautare liniara (secventiala)

2. Cautare binara. Se considera un fisier secvential cu N inregistrari,ale carui chei sint in ordine crescatoare k1 < k2


17/18


Cautare binara uniforma

Cautare Shar (nod radacina [log2n)

Cautare Fibonacci

HASH

Pointer = functie_hash(camp_hash) si indica grupul in care segaseste inregistrarea.

Utilizata atat la stocare cat si la citire


18/18


Hash

Grup1Grup2

Grup3

Grup n

Overflow 1

Overflow k

Grupuri initiale (date de

valorile functiei hash)

Grupuri overflow

Baze de date2-3

Documents

Transcript of Baze de date2-3