Proiectarea Bazelor de Date Distribuite
1. INTRODUCERE
Sistemele bazelor de date distribuite (SBDD) sunt reuniunea a doua abordari asupra procesarii datelor care pot parea diametral opuse: tehnologiile sistemelor de baze de date si cele ale retelelor de calculatoare. Sistemele de baze de date au evoluat de la o procesare a datelor in care fiecare aplicatie isi defineste si mentine propriile date, la una in care datele sunt definite si administrate central. Aceasta noua orientare duce la independenta datelor, astfel aplicatiile devenind imune la schimbarile in organizarea fizica sau logica a datelor si viceversa. O motivatie majora in folosirea sistemelor de baze de date o constituie integrarea datelor si oferirea unui acces centralizat si controlat la aceste date. Pe de alta parte, tehnologia retelelor de calculatoare promoveaza un mod de lucru care este impotriva tuturor eforturilor de centralizare. Poate fi astfel greu de inteles cum aceste doua abordari contrastante pot fi sintetizate intr-o tehnologie care este mai puternica si mai promitatoare decat amandoua. Cheia intelegerii este realizarea faptului ca cel mai important obiectiv al tehnologiei bazelor de date nu este centralizarea, ci integrarea. Este important de stiut ca nici unul din acesti termeni nu il implica pe celalalt. Poate exista integrare fara centralizare, acesta fiind chiar scopul bazelor de date distribuite.
Procesarea distribuita a datelor
Procesare distribuita este unul dintre cei mai abuzati termeni in stiintele calculatoarelor in ultimii ani. A fost folosit pentru a referi sisteme diverse, cum ar fi sistemele multiprocesor, procesarea distribuita a datelor si retele de calculatoare. Procesare distribuita este un concept pentru care este greu sa se dea o definitie riguroasa, deci vom da o definitie în ceea ce priveste sistemele de baze de date distribuite. Un sistem de calcul distribuit consta dintr-un numar de elemente de procesare autonome (nu neaparat omogene) care sunt interconectate printr-o retea de calculatoare si coopereaza în executarea sarcinilor (task) lor. Prin “element de procesare” se intelege un calculator, ce poate executa programe proprii.
In acest context, se impune o intrebare: Ce se distribuie? Logica procesarii este unul din lucrurile care trebuie distribuite. Definitia unui sistem de calcul data mai sus presupune ca logica procesarii sau elementele de procesare sunt distribuite. O alta distribuire poate fi a functiilor. Diferitele functii ale unui sistem de calcul pot fi executate de parti diferite de hardware sau software. Alta distribuire poate fi cea conform datelor. Datele folosite de un numar de aplicatii pot fi distribuite la mai multe noduri de procesare. In sfarsit, si controlul poate fi distribuit. Controlul executiei diferitelor sarcini poate fi distribuit, in loc de a fi executat de un singur calculator. Din punctul de vedere al bazelor de date distribuite, toate aceste metode de distribuire sunt necesare si importante.
O alta intrebare care poate fi pusa este: De ce distribuim? Raspunsurile clasice la aceasta intrebare afirma ca procesarea distribuita corespunde mai bine structurii organizatorice a marilor intreprinderi de azi, si ca un astfel de sistem este mai sigur si mai avantajos. Dintr-o perspectiva globala totusi, se poate spune ca motivul principal pentru procesarea distribuita este rezolvarea problemelor mari si complicate cu care ne confruntam in zilele noastre, prin folosirea unor variatiuni a bine cunoscutei reguli divide et impera. Daca software-ul necesar procesarii distribuite poate fi creat, atunci este posibil sa rezolvam aceste probleme complicate prin simpla impartire a lor in parti mai mici, care pot fi rezolvate de diferite grupuri software, aflate pe calculatoare diferite, producand un sistem care ruleaza pe mai multe elemente de procesare, dar care poate efectua eficient o sarcina comuna.
1.2. Ce este un sistem de baze de date distribuite?
Putem defini o baza de date distribuita ca pe o colectie de baze de date corelate logic si distribuite pe o retea de calculatoare. Un sistem distribuit de gestionare a bazelor de date este definit ca un sistem software care permite gestionarea bazelor de date distribuite si face distribuirea transparenta pentru utilizatori. Sunt doi termeni importanti in aceasta definitie: corelate logic si distribuite intr-o retea de calculatoare.
Un sistem de baze de date distribuite (SBDD) nu este numai “o colectie de fisiere” care pot fi stocate individual la fiecare nod al unei retele de calculatoare. Pentru a forma un SBDD, fisierele trebuie sa fie corelate logic, sa existe o anumita structura intre ele si sa fie accesate prin intermediul unei interfete comune. Un SBDD nu este un sistem in care, in ciuda existentei unei retele, baza de date se afla pe un singur nod al retelei. In acest caz, problemele de gestionare a bazelor de date nu sunt diferite de cele din mediul centralizat. Baza de date este gestionata central de un calculator si toate cererile sunt trimise catre acel calculator. Deci existenta unei retele nu implica un mediu distribuit. Datele trebuie sa fie distribuite pe mai multe noduri ale unei retele.
Baza de date distribuita are caracter virtual. Componentele sale sunt stocate pe baze de date distincte, aflate pe noduri distincte ale unei retele. Fiecare nod este un sistem de baze de date, avand propriile baze de date, utilizatori proprii si SGBD local. Sistemul distribuit poate fi vazut ca o asociere intre SGBD-ul local si o componenta noua in fiecare nod. El furnizeaza functiile necesare pentru asociere.
Figura 1.1 Mediul SBDD
1.3. Avantajele si dezavantajele bazelor de date distribuite
Avantaje:
Autonomie locala. Utilizatorii unei baze de date ce se afla pe o anumita statie din retea au controlul local al datelor, datorita organizarii descentralizate. Datele locale se pastreaza local, unde apartin logic, în majoritatea cazurilor procesarea lor executandu-se în nodul în care sunt stocate,
Imbunatatirea performantei. Prin executia in paralel a mai multor sarcini, pe statii diferite, se pot reduce conflictele de acces la date si se poate imbunatati atat viteza de executie a operatiilor asupra bazelor de date cat si viteza accesului la informatiile stocate.
Îmbunatatirea sigurantei si disponibilitatii. Daca datele sunt replicate pe mai multe noduri, indisponibilitatea unuia dintre acestea sau o problema pe retea nu face ca datele sa nu poata fi accesate.
Economice. Daca bazele de date sunt dispersate geografic si aplicatiile ruleaza în locul în care sunt si datele, se îmbunatatesc costurile de comunicatie.
Expandabilitatea. Într-un mediu distribuit este mult mai usoara marirea dimensiunilor bazelor de date.
Partajabilitate. Organizatiile care au operatii distribuite geografic înmagazineaza în mod normal si datele în aceeasi maniera.
Dezavantaje:
Complexitatea. Problemele din cadrul SBDD sunt mai complexe decat cele centralizate, ele incluzand problemele distribuite, cat si cele nerezolvate înca în mediul centralizat. Problema complexitatii este a programatorului si nu a utilizatorului.
Costul. Sistemele distribuite necesita hardware si software aditional, ceea ce mareste costurile.
Distribuirea controlului. Acest punct, care este în acelasi timp si un avantaj, determina probleme de sincronizare si coordonare.
Securitate. Este bine cunoscuta dificultatea mentinerii controlului adecvat al securitatii in retea, deci si in bazele de date distribuite.
Adoptare dificila a tehnologiei. Multe firme au investit din greu în sistemele lor de baze de date, care nu sunt distribuite. În prezent nu exista instrumente sau tehnologii care sa ajute utilizatorii sa converteasca bazele de date centralizate în baze de date distribuite.
1.4. Transparenta in SGBDD
Transparenta în SGBDD se refera la separarea semanticii de nivel înalt a unui sistem de implementarea de la un nivel scazut. Cu alte cuvinte, un sistem transparent ascunde detaliile de implementare pentru utilizatori. Avantajele SGBD-urilor transparente sunt portabilitatea, reconfigurabilitatea, asigurarea unui mediu de dezvoltare pentru aplicatiile complexe.
Independenta datelor
Independenta datelor este o forma fundamentala a transparentei din SGBDD. Ea se refera la imunitatea aplicatiilor utilizatorului la schimbari în definirea si organizarea datelor, si viceversa.
Se pot pune în evidenta doua tipuri de independenta a datelor:
Independenta logica a datelor se refera la imunitatea aplicatiilor utilizatorului la schimbari în structura logica a bazei de date. Daca o aplicatie lucreaza cu un subset de atribute ale unei relatii, aceasta nu va fi afectata la adaugarea unui nou atribut la aceeasi relatie.
Independenta fizica a datelor se refera la ascunderea detaliilor structurii de inmagazinare pentru aplicatiile utilizator. Aplicatia nu trebuie sa fie modificata in momentul în care apar schimbari ale organizarii datelor.
Transparenta de retea
În mediile de gestiune a bazelor de date distribuite apare o resursa care trebuie sa fie gestionata: reteaua. De preferat, un utilizator va fi protejat de detaliile operationale ale retelei. Daca este posibil, existenta retelei trebuie ascunsa. Atunci nu va mai exista nici o diferenta (din punctul de vedere al utilizatorului) între aplicatiile care folosesc bazele de date centralizate si cele care folosesc baze de date distribuite. Acest tip de transparenta este numit transparenta de retea (network transparency).
Transparenta la replicare
Este necesar ca datele sa fie distribuite de o maniera replicativa între masinile de pe o retea. Deci aceleasi date se vor regasi pe mai multe masini. Acest lucru imbunatateste performantele sistemului intrucat cereri diferite si concurente ale utilizatorilor pot fi satisfacute mai usor. De exemplu datele care sunt des accesate de un utilizator pot fi stocate pe masina acestuia, cat si pe cea a altui utilizator, cu cerinte de acces similare. In cazul in care un nod de retea este indisponibil, datele pot fi accesate si la alte locatii. Ce date trebuie replicate si in cate copii depinde in mare masura de aplicatiile care le acceseaza. Replicarea datelor cauzeaza insa unele probleme in actualizarea datelor.
Faptul ca utilizatorul nu stie cate copii s-au facut si nu stie nimic despre existenta lor îl putem numi transparenta la replicare (replication transparency).
Transparenta la fragmentare
Se doreste ca fiecare obiect al bazei de date sa fie împartit în mici fragmente si fiecare fragment sa fie tratat ca un obiect separat al bazei de date. Acest lucru este determinat de ratiuni de performanta, disponibilitate si siguranta. De asemenea, fragmentarea poate reduce efectele negative ale replicarii.
Figura 1.2: Nivele de transparenta
Asigurarea transparentei
Se identifica trei nivele de asigurare a accesului transparent la date: nivelul de acces la date, nivelul sistemului de operare si cel al SGBD-ului.
Accesul transparent la date poate fi asigurat printr-un limbaj care sa transforme cererile utilizatorului in operatiile solicitate.
Unele sisteme de operare asigura un anumit nivel de transparenta utilizatorilor sistemului. De exemplu, driver-ele sistemului de operare trebuie sa se asigure ca fiecare periferic raspunde corespunzator cererilor. Utilizatorul tipic sau chiar programatorul unei aplicatii nu sunt nevoiti sa scrie driver-ul pentru a interactiona cu perifericele respective: aceste operatii sunt transparente utilizatorului.
Accesul transparent la date si transparenta sistemului de operare pot fi evident extinse si in mediile distribuite, unde accesul la resursele retelei este preluat de sistemele de operare distribuite.
Cel de-al treilea nivel in care transparenta poate fi asigurata este nivelul SGBD-urilor. Acesta se limiteaza la asigurarea operatiilor fundamentale ale anumitor sarcini care realizeaza trecerea de la nivelul sistemului de operare la cel al interfetei utilizator.
Aceste nivele de transparenta depind de diferitele componente ale mediului integrmentare
Se doreste ca fiecare obiect al bazei de date sa fie împartit în mici fragmente si fiecare fragment sa fie tratat ca un obiect separat al bazei de date. Acest lucru este determinat de ratiuni de performanta, disponibilitate si siguranta. De asemenea, fragmentarea poate reduce efectele negative ale replicarii.
Figura 1.2: Nivele de transparenta
Asigurarea transparentei
Se identifica trei nivele de asigurare a accesului transparent la date: nivelul de acces la date, nivelul sistemului de operare si cel al SGBD-ului.
Accesul transparent la date poate fi asigurat printr-un limbaj care sa transforme cererile utilizatorului in operatiile solicitate.
Unele sisteme de operare asigura un anumit nivel de transparenta utilizatorilor sistemului. De exemplu, driver-ele sistemului de operare trebuie sa se asigure ca fiecare periferic raspunde corespunzator cererilor. Utilizatorul tipic sau chiar programatorul unei aplicatii nu sunt nevoiti sa scrie driver-ul pentru a interactiona cu perifericele respective: aceste operatii sunt transparente utilizatorului.
Accesul transparent la date si transparenta sistemului de operare pot fi evident extinse si in mediile distribuite, unde accesul la resursele retelei este preluat de sistemele de operare distribuite.
Cel de-al treilea nivel in care transparenta poate fi asigurata este nivelul SGBD-urilor. Acesta se limiteaza la asigurarea operatiilor fundamentale ale anumitor sarcini care realizeaza trecerea de la nivelul sistemului de operare la cel al interfetei utilizator.
Aceste nivele de transparenta depind de diferitele componente ale mediului integrat. SGBD-ul este responsabil de independenta datelor si, de asemenea, de transparenta replicarii si fragmentarii datelor. Interfata utilizator poate suporta un nivel inalt de transparenta nu numai in ce priveste accesul la date prin limbaje de programare, dar si prin declararea unor structuri specifice care permit definirea obiectelor unei baze de date. Interfata utilizator presupune crearea unor interfete noi, care pot fi limbaje naturale, interfete grafice, chiar si sisteme de voce si asigura translatarea acestora in interfete locale corespunzatoare fiecarui nod eterogen al sistemului. Se poate adauga si un alt nivel al transparentei si anume transparenta limbajului, deci nivelul interfetelor grafice utilizator, al limbajului natural de acces la date.
2. ARHITECTURA SISTEMELOR DE GESTIUNE A BAZELOR DE DATE DISTRIBUITE
Arhitectura unui sistem defineste structura acestuia. Adica componentele sistemului sunt identificate, functia fiecarei componente este specificata si relatiile si interactiunile dintre aceste componente sunt definite. Aceasta platforma ramane adevarata pentru sistemele de calcul in general si sistemele software in particular.
2.1. Standardizarea SGBDD
Pentru standardizarea SGBDD o sa tinem cont de relatia stransa care exista între arhitectura unui sistem si modelul de referinta al acelui sistem, care este dezvoltat ca un precursor al oricarei activitati de standardizare. Modelul de referinta poate fi considerat un model arhitectural idealizat al acestui sistem. Acesta poate fi definit ca “un cadru de lucru conceptual al carui scop este sa împarta munca de standardizare în piese gestionabile, si sa arate la un nivel general cum aceste piese sunt legate între ele”.
Un model de referinta (si totodata arhitectura unui sistem) poate fi descris tinand cont de trei abordari diferite:
bazat pe componente. Un SGBD este compus din mai multe componente, fiecare furnizand anumite functionalitati.
bazat pe functionalitati. Diferite clase de utilizatori identifica o serie de functionalitati pe care sistemul le va furniza pentru fiecare astfel de clasa.
bazat pe date. Punct de vedere fundamental deoarece un SGBD foloseste date.
Toate aceste trei abordari sunt folosite pentru a realiza un model arhitectural. La sfarsitul anului 1972, Institutul National American de Standarde (ANSI), stabileste un Grup de Studiu pentru Sistemele de Gestiune a Bazelor de Date condus de un Comitet pentru Standardizarea Planificarilor si Cerintelor (SPARC). Acest grup avea rolul de a studia fezabilitatea realizarii unor standarde în acest domeniu. S-a realizat un raport interimar (1975) si un raport final (1977). Cadrul de lucru arhitectural propus în aceste rapoarte este cunoscut sub numele de “Arhitectura ANSI/SPARC”.
Tinand cont de abordarile discutate anterior (legate de standardizare), arhitectura ANSI/SPARC se bazeaza pe organizarea datelor. Foloseste trei vederi ale datelor (vezi Figura 3.4):
vederea externa: este ceea a utilizatorului
vederea interna: este cea a sistemului sau a masinii
vederea conceptuala: este cea a firmei (sau a domeniului modelat)
La cel mai de jos nivel al arhitecturii se afla vederea interna, care este legata de definirea fizica si organizarea datelor. Localizarea datelor pe diferite periferice de înmagazinare si mecanismele de acces folosite pentru cautarea si manipularea datelor sunt abordate la acest nivel.
La polul opus se afla vedera externa, care tine de felul in care utilizatorii vad baza de date. Un punct de vedere al unui utilizator reprezinta portiunea unei baze de date care va fi accesata de catre respectivul utilizator precum si relatiile care exista între aceste date. O astfel de vedere poate fi partajata între mai multi utilizatori, colectionarea acestor vederi constituind schema externa.
Între aceste doua extreme se gaseste schema conceptuala, care este o definitie abstracta a bazei de date. Aceasta este vederea “lumii reale” a firmei modelate de catre aceasta baza de date.
Figura 2.1 Arhitectura ANSI/SPARC
Descrierea arhitecturii ANSI/SPARC tinand cont de functionalitatile sale genereaza o vedere considerabil mai complexa, prezentata in Figura 2.2. Chenarele reprezinta functii de procesare, iar hexagoanele sunt rolurile administrative. Sagetile indica fluxurile de date, comenzi, programe si descriere si interfetele sunt reprezentate prin bare de forma “ ”.
Rolurile administrative pot ajuta la definirea unei interpretari functionale a arhitecturii ANSI/SPARC. Cele trei roluri sunt:
administrator baza de date : responsabil pentru definirea schemei interne
administrator societate:: responsabil pentru definirea schemei conceptuale
administrator aplicatie: persoana cu un punct de interes în utilizarea informatiilor din cadrul unei societati; responsabil cu promovarea schemelor externe pentru aplicatii.
Aceste roluri pot fi indeplinite de o persoana sau mai multe. Sistemul trebuie sa ofere suport pentru indeplinirea tuturor rolurilor mai sus mentionate. Pe langa aceste trei clase de utilizatori definiti prin roluri, mai sunt doua: programatorii de aplicatie si programatorii de sistem.
Figura 2.2 Schema partiala a modelului arhitectural ANSI/SPARC
2.2. Modele arhitecturale pentru SGBDD
Se considera modurile in care mai multe baze de date pot fi puse impreuna pentru a fi gestionate de mai multe sisteme. Se va folosi o clasificare a sistemelor de gestiune tinand cont de autonomia sistemelor locale, distributia lor si eterogenitatea lor.
Autonomia se refera la distribuirea controlului, nu a datelor. Indica gradul de independenta al SGBD-urilor individuale. Autonomia depinde de un numar de factori, cum ar fi schimbul de informatie intre componentele sistemului sau executarea independenta a tranzactiilor de catre aceste componente. Tinand cont de autonomie, avem trei alternative de modelare: integrarea stransa, care poate fi stocata pe mai multe baze de date si in care o imagine a intregii baze de date este disponibila oricarui utilizator care vrea sa imparta informatia. Din punctul de vedere al utilizatorului datele sunt centralizate logic intr-o singura baza de date.
Sistemele semiautonome contin SGBD-uri care pot (si de obicei o fac) opera independent, dar aleg sa participe intr-o federatie pentru a-si imparti datele locale. Fiecare din aceste SGBD-uri determina ce parti din baza lor de date pot fi accesate de utilizatorii altor SGBD-uri. Ele nu sunt sisteme complet autonome pentru ca trebuie modificate pentru a fi capabile sa schimbe informatia intre ele.
Ultima alternativa o reprezinta izolarea totala, unde sistemele individuale, sunt de sine statatoare, nestiind de existenta altor SGBD-uri, sau cum sa comunice cu ele. In aceste sisteme, procesarea tranzactiilor care acceseaza baze de date multiple este dificila deoarece nu exista un control global al executiei asupra SGBD-urilor individuale.
Distributia se refera la distributia fizica a datelor intre mai multe locatii. Exista mai multe moduri in care datele au fost distribuite, insa cele mai importante clase pot fi: distributia client/server si distributia peer-to-peer.
Distributia client/server, devenita destul de populara in ultimii ani, concentreaza gestionarea datelor la server, in timp ce partea de client se ocupa cu mediul aplicatiei, inclusiv interfata utilizator. Gestionarea comunicarii este impartita intre server si client. Intr-o retea, se face diferenta intre masini client si server, iar functionalitatile lor sunt diferite.
In sistemele peer-to-peer nu exista diferenta intre masinile client si server. Fiecare masina are functionalitatile unui SGBD si poate comunica cu alte masini pentru a executa interogari si tranzactii.
Eterogenitatea se poate manifesta in multe moduri in sistemele distribuite, de la eterogenitatea hardware si diferenta intre protocoluri de retea la diferente intre managerii de date.
Se identifica astfel mai multe modele arhitecturale, dintre care cele mai importante sunt (A0, D2, E0) (e.g. autonomie – integrare stransa, distributie – peer-to-peer, omogen) si (A2, D2, H1) (autonomie – total izolata, distributie – peer-to-peer, eterogena).
2.3. Arhitectura SGBD distribuite
Din cele aproape treizeci de modele arhitecturale posibile obtinute prin combinarea unor grade diferite de autonomie, distributie si eterogenitate, trei sunt mai importante, ele reprezentand extreme ale acestor combinatii: sistemele client/server, baze de date distribuite si sistemele multi-baze de date.
2.3.1. Sistemele Client/Server
Sistemele de gestiune a bazelor de date client/server au aparut la inceputul anilor 90 si au avut un impact important asupra tehnologiilor SGBD. Ideea generala este foarte simpla si eleganta: diferentierea functionalitatilor care trebuie oferite in functii de server si de client. Astfel se obtine o arhitectura pe doua nivele care face mai usoara gestiunea si distribuirea SGBD-urilor moderne.
Termenul client/server se refera la masinile de calcul, nu la procese. De aceea, trebuie sa stim ce software ruleaza pe masinile client si ce software ruleaza pe cele server.
Primul lucru care trebuie remarcat este ca serverul este responsabil pentru gestiunea datelor. Deci procesarea cererilor, optimizarea, gestiunea tranzactiilor si stocarii sunt facute la server. Clientul, pe langa aplicatie si interfata utilizator, are un modul SGBD client, responsabil cu gestionarea datelor de pe masina client. Aceasta arhitectura, reprezentata si grafic in Figura 2.3, este comuna in sistemele relationale unde comunicarea intre client si server se face la nivelul limbajului SQL. In alte cuvinte, clientul trimite la server cereri SQL, fara a incerca optimizarea lor. Serverul intoarce relatia rezultat la client.
Exista mai multe arhitecturi client/server. Cea mai simpla este cea in care exista un singur server, accesat de mai multi clienti. Din perspectiva gestionarii datelor aceasta nu este diferita foarte mult de sistemele centralizate, intrucat baza de date este stocata pe o singura masina (serverul), care contine si software de gestionare. O arhitectura client/server mai complicata este cea in care exista mai multe servere. In acest caz, exista doua modalitati de gestionare: fie fiecare client isi gestioneaza conexiunea la serverul potrivit, fie fiecare client nu cunoaste decat un server, care comunica la randul sau cu celelalte servere. Prima alternativa simplifica codul de la server, dar incarca clientul cu mai multe responsabilitati. Cea de-a doua, insa, concentreaza gestionarea datelor la server, astfel transparenta datelor fiind oferita la nivelul interfetei server.
Dintr-un punct de vedere al logicii datelor, sistemele client/server nu se deosebesc de cele peer-to-peer, in sensul ca utilizatorul vede o singura baza de date la nivel logic, in timp ce la nivel fizic, datele pot fi distribuite. Astfel, prima diferenta dintre cele doua tipuri de sisteme nu tine de transparenta oferita utilizatorilor, ci de arhitectura folosita pentru a obtine acest nivel de transparenta.
Figura 2.3 Arhitectura client/server de referinta
2.3.2. Sistemele peer-to-peer distribuite
Descrierea acestei arhitecturi trebuie sa inceapa cu o privire asupra organizarii datelor. Organizarea fizica a datelor poate fi diferita pe fiecare calculator. De aceea trebuie sa existe o schema individuala de definite la fiecare locatie, care se numeste schema interna locala. Vederea societatii asupra datelor este descrisa de schema conceptual globala. Este numita globala, deoarece descrie structura logica a datelor din toate locatiile.
Cum intr-o baza de date distribuita datele sunt fragmentate si replicate, organizarea logica a datelor de la fiecare locatie trebuie descrisa. De aceea este necesar un al treilea strat in aceasta arhitectura: schema conceptuala locala. In acest model arhitectural schema conceptual globala este uniunea schemelor conceptual locale. In sfarsit, aplicatiile utilizatorului si accesul utilizatorului la baza de date sunt suportate de schemele externe, definite ca fiind deasupra schemei conceptual globale.
Componentele unui SGBD distribuit sunt prezentate in Figura 2.4. Una din ele se ocupa de interactiunea cu utilizatorii, si alta se ocupa cu stocarea datelor. Prima componenta majora, numita procesorul utilizator este format din patru elemente:
Gestionarul interfetei utilizator este responsabil cu interpretarea comenzilor date de utilizator, si formatarea rezultatelor cand sunt trimise catre utilizator.
Controlorul semantic al datelor foloseste constrangerile de integritate si autorizatiile definite ca parte a schemei conceptual globale pentru a verifica daca cererile utilizatorului pot fi procesate.
Optimizator global al cererilor determina strategiile de minimizare a costurilor unei functii si traduce cereri globale in cele locale folosind schemele conceptual locale, ca si directorul global. Optimizatorul global al cererilor este responsabil si de generarea celei mai bune strategii pentru executarea operatiilor join distribuite.
Monitorul executiei distribuite coordoneaza executia distribuita a unei cereri a utilizatorului. Mai este numit si managerul tranzactiilor distribuite. In executarea unei interogari intr-un mod distribuit, monitorii de executie comunica intre ei.
Cea de-a doua componenta a unui SGBD distribuit este procesorul datelor, care este alcatuit din trei elemente:
Optimizatorul local al cererilor, care se comporta ca un selector al caii de acces, este responsabil cu alegerea celei mai bune cai de acces catre orice data. O cale de acces tipica este un index sau unul sau mai multe atribute ale unei relatii.
Managerul local de recuperare local se asigura ca baza de date ramane consistenta chiar in cazul unor dereglari.
Procesorul de sustinere a rularii acceseaza fizic baza de date, in concordanta cu programul dictat de optimizatorul cererilor.
Impartirea arhitecturii in “procesorul utilizator” si “procesorul datelor’ nu implica o functionalitate similara cu cea a sistemelor client/server. In sistemele peer-to-peer este de asteptat sa gasim ambele module pe fiecare masina. Totusi au existat sugestii de a separa locatiile “cereri exclusiv” de cele cu functionalitate deplina. In acest caz, primele au nevoie numai de procesorul utilizator.
Figura 2.4 Componentele unui SGBD distribuit
3. PROIECTAREA BAZELOR DE DATE DISTRIBUITE
Proiectarea unui sistem de calcul distribuit implica luarea de decizii privind plasarea datelor si programelor in cadrul nodurilor unei retele de calculatoare, cat si proiectarea retelei insasi. In cazul bazelor de date distribuite, presupunand ca reteaua a fost proiectata deja si ca exista o copie a software-ului SGBD la fiecare nod din retea unde sunt inmagazinate date, ramane sa ne concentram atentia asupra distribuirii datelor.
3.1. Strategii alternative de proiectare
Exista doua strategii majore de proiectare a bazelor de date distribuite:
Proiectarea top-down
Proiectarea bottom-up
Dupa cum indica si numele, aceste strategii reprezinta abordari foarte diferite ale procesului de proiectare. Majoritatea aplicatiilor insa nu sunt atat de simple incat sa se incadreze complet in una din aceste strategii, deci este important de stiut ca aceste strategii trebuie folosite impreuna, ca un complement al uneia fata de cealalta.
3.1.1. Proiectarea top-down
Acest proces este descris în Figura 4.1. Activitatea începe cu analiza cerintelor care definesc mediul sistemului. Documentul cerintelor este intrarea pentru doua activitati paralele: proiectarea conceptuala si proiectarea vederilor. Activitatea de proiectare a vederii defineste interfetele pentru utilizatorii finali. Proiectarea conceptuala este procesul prin care sistemul este examinat pentru a determina tipurile de entitati care îl compun si relatiile dintre acestea. Proiectarea conceptuala poate fi interpretata ca fiind integrarea vederilor utilizator. Acest lucru este foarte important, deoarece modelul conceptual trebuie sa suporte nu numai aplicatiile existente, dar si pe cele viitoare.
Schema conceptuala globala si informatiile despre tiparele de acces colectate ca si un rezultat al proiectarii vederilor sunt intrari pentru pasul de proiectare distribuita. Obiectivul în acest moment este proiectarea schemelor locale conceptuale prin distribuirea entitatilor peste nodurile din sistemul distribuit. În cazul unui model relational, entitatile corespund relatiilor. Mai curand decat distribuirea relatiilor se foloseste împartirea acestora în subrelatii, numite fragmente, si acestea sunt distribuite. Deci activitatea de proiectare distribuita consta din doi pasi: fragmentare si alocare.
Ultimul pas în procesul de proiectare este procesul de proiectare fizica, care face legaturile între schemele conceptuale locale si perifericele fizice de înmagazinare ale datelor din cadrul nodurilor corespunzatoare. Intrarile în acest proces sunt schemele conceptuale locale si tiparele de acces la informatie.
Figura 3.1 Procesul proiectarii Top-Down
3.1.2. Proiectare Bottom-Up
Abordarea top-down este potrivita în momentul în care facem proiectarea unei BDD plecand de la zero. Dar, se întampla deseori ca anumite baze de date sa existe deja, si activitatea de proiectarea trebuie sa realizeze si integrarea acestora. Abordarea bottom-up este potrivita pentru astfel de medii.
Punctul de pornire în cadrul proiectarii bottom-up este schema conceptuala locala. Procesul consta în integrarea schemelor locale în schema conceptuala globala.
3.2. Activitati in proiectarea distribuita
S-a afirmat anterior ca relatiile din cadrul schemei unei baze de date distribuite sunt descompuse in fragmente, dar nu s-a oferit o justificare sau detalii referitoare la acest proces. Lucrarea prezinta in continuare raspunsul la mai multe intrebari legate de fragmentare, corectitudinea descompunerii si alocare.
3.2.1. Ratiuni pentru fragmentare
Este foarte important sa avem o unitate potrivita de distribuire. O relatie nu poate fi o astfel de unitate, din mai multe motive. In primul rand, vederile unor aplicatii sunt de obicei subseturi ale relatiilor. De aceea e natural sa consideram subseturi ale relatiilor, adica fragmente, ca unitati de distribuire.
In al doilea rand, putem avea aplicatii care au vederi pe aceeasi relatie, dar se afla in locatii diferite. Considerand relatia ca unitate de distribuire, putem avea doua alternative: relatia sa nu fie replicata, si atunci vom avea un numar prea mare de operatiuni de acces de la distanta, sau relatia este replicata pe un numar de noduri sau la toate, fapt ce conduce la ingreunarea actualizarilor, cat si la probleme ce tin de capacitatea de inmagazinare.
In sfarsit, descompunerea unei relatii in fragmente permite executarea concurenta a tranzactiilor. De asemenea, fragmentarea relatiilor duce la executia concurenta a cererilor prin impartirea lor in subcereri care opereaza pe fragmente. Deci fragmentarea duce la marirea gradului de concurenta in sistem.
3.2.2. Alternative de fragmentare
Instantele relatiilor sunt in general tabele, deci se pune problema gasirii unor modalitati prin care sa putem imparti un tabel in cateva mai mici. Exista astfel doua alternative: impartire pe orizontala sau impartire pe verticala.
Exemplul 3.1
Vom folosi un model de baza de date pentru a exemplifica cele doua alternative
de fragmentare. Figura 3.2 prezinta schema relationala unei baze de date. In Figurile 3.3 si 3.4 se prezinta partitionarea orizontala, respectiv partitionarea verticala.
Figura 3.2 Exemplu de relatie din baza de date
Figura 3.3 Exemplu de partitionare pe orizontala
Figura 3.4 Exemplu de partitionare pe verticala
3.2.3. Reguli de corectitudine a fragmentarii
Exista similitudini intre fragmentarea datelor pentru distribuire si normalizarea relatiilor. Astfel, pot fi definite niste reguli ale fragmentarii, asemanatoare cu principiile normalizarii. Trei dintre ele sunt mai importante, asigurand consistenta bazei de date in timpul fragmentarii.
Completitudinea. Daca o instanta a unei realtii R este descompusa in fragmentele R1, R2, … Rn, atunci fiecare element din R poate fi gasit intr-unul sau mai multe fragmente Ri. Aceasta proprietate este importanta pentru fragmentare deoarece asigura faptul ca o relatie globala nu pierde informatie atunci cand este fragmentata. Este de remarcat ca in cazul unei fragmentari orizontale, “element” se refera la un tuplu, iar in cazul fragmentarii verticale, “element” se refera la un atribut.
Reconstructia. Daca o relatie R este descompusa in fragmentele R1, R2, … Rn, atunci ar trebui sa se poata defini un operator relational “” astfel incat:
R = Ri, RiFR
Operatorul “” va fi diferit pentru diferitele forme de fragmentare, dar este important ca el sa poata fi definit. Capacitatea de reconstructie a unei relatii din fragmentele sale asigura pastrarea constrangerilor definite.
3. Disjunctia. Daca o relatie este descompusa orizontal in fragmentele R1, R2, … Rn, si elementul di este in Rj, atunci nu mai este in nici un alt fragment Rk (k≠j). Acest criteriu asigura faptul ca fragmentele orizontale sunt dijuncte. Daca relatia R este descompusa vertical, atributele care reprezinta cheile primare se intalnesc de obicei in toate fragmentele. Deci in cazul partitionarii verticale, disjunctia se defineste numai pentru atributele relatiei care nu sunt chei primare.
3.2.4. Alternativele alocarii
Presupunand ca fragmentarea bazei de date s-a facut corect, trebuie decisa alocarea fragmentelor la diferite noduri din retea. Cand datele sunt alocate, ele pot fi replicate sau mentinute ca o singura copie. Motivele pentru replicare sunt eficienta si siguranta in interogari read-only. Daca exista mai multe copii ale unui element de date, atunci exista o sansa mare ca acesta sa poata fi accesat undeva chiar daca intervin probleme in sistem. Mai mult, interogari read-only care acceseaza aceleasi date pot fi executate in paralel daca exista mai multe copii ale acelor date in locatii diferite. Pe de alta parte, executia unor cereri de reactualizare (update queries) poate provoca probleme intrucat reactualizarea trebuie facuta corect pentru toate copiile datelor. De aceea decizia privind replicarea datelor depinde de raportul dintre cererile read-only si cele de actualizare.
O baza de date nereplicata, (numita si baza de date partitionata) contine fragmente alocate la mai multe noduri, si in retea exista numai o singura copie a unui fragment. In cazul replicarii, fie baza de date exista in intregime in fiecare nod din retea (baza de date replicata total), fie fragmente sunt distribuite in noduri astfel incat este posibil sa avem copii ale unui fragment pe mai multe noduri din retea (baza de date replicata partial). In ultimul caz, numarul de copii ale unui fragment poate fi o data de intrare pentru algoritmul de alocare sau o variabila de decizie a carei valoare e calculata de algoritm. Figura 3.5 prezinta o comparatie intre alternativele alocarii, tinand seama de diferitele functii ale unui SGBD distribuit:
Figura 3.5 Comparatie intre alternativele de alocare
3.3. Fragmentare
Am vazut deja ca exista doua modalitati fundamentale de fragmentare: pe orizontala si pe verticala. Exista si o modalitate de a incuibari fragmentele intr-un mod hibrid.
3.3.1. Fragmentare pe orizontala
S-a observat mai devreme ca fragmentarea orizontala partitioneaza o relatie in tupluri sau grupuri de tupluri. Astfel, un fragment are un subgrup de tupluri ale relatiei. Exista doua versiuni de fragmentare pe orizontala: primara si derivata. Partitionarea orizontala primara se realizeaza folosind predicatele definite pe acea relatie. Pe de alta parte, partitionarea orizontala derivata se realizeaza folosind predicate definite pe alte relatii. Inainte de a prezenta un algoritm pentru ambele partitionari, este necesara investigarea informatiilor necesare fragmentarii orizontale:
Informatiile despre baza de date se refera la schema conceptuala globala. În acest context este important sa mentionam legaturile între relatii, mai ales join-urile între relatii. În alte modele, de exemplu si în modelul entitate-relatie, legaturile între entitati se dau explicit. În continuare, legaturi orientate se deseneaza între relatiile care sunt în legatura printr-o operatie de equi-join.
Exemplul 3.2
Figura 3.6 descrie legaturile intre relatiile unei baze de date. Directia legaturilor arata relatiile one-to-many. De exemplu, un client poate face mai multe comenzi, deci legatura este de la CLIENT la COMANDA. Legatura many-to-many dintre COMANDA si PRODUS este prezentata prin intermediul celor doua legaturi spre relatia CONTINE.
Figura 3.6 Expresia relatiilor intre relatii folosind legaturi
Aceste legaturi ajuta la simplificarea prezentarii modelului de distributie. Relatia care se afla la inceputul legaturii se numeste relatia proprietar (owner), iar cea de la sfarsit se numeste relatie membru (member). Definim doua functii: owner si member, amandoua avand domeniu de definitie legaturile, iar domeniul valorilor fiind multimea functiilor. Astfel, fiind data o legatura, acestea dau proprietarul respectiv membrul legaturii. Data legatura L1 din Figura 3.6, valorile acestor functii sunt:
Owner(L1) = CLIENT
Member(L1) = COMANDA
Informatia cantitativa necesara pentru o baza de date este data de cardinalitatea fiecarei relatii R, notata card(R).
Informatii despre aplicatii. În proiectarea bazelor de date distribuite avem nevoie de informatii calitative si cantitative despre aplicatii. Informatiile calitative conduc activitatea de fragmentare, iar cele cantitative sunt încorporate în modelele de alocare.
Informatiile calitative constau din predicatele folosite în interogarile utilizatorilor. Daca nu este posibil sa analizam toate aplicatiile pentru a afla aceste predicate, va trebui sa le gasim pe cele mai “importante”. S-a acceptat ca 80% din accesul total la date sunt 20% din interogarile utilizatorilor, acestea fiind interogarile cele mai des folosite.
Devine interesanta in acest punct determinarea predicatelor simple. Fiind data o relatie de forma R(A1, A2, …, An) unde Ai este un atribut din domeniul Di, un predicat simplu pj definit pe R are forma:
Pj : Ai θ Valoare,
unde θ{═ , < , ≤ , ≠ , > , ≥} si Valoare apartine domeniului lui Ai ( Valoare Di). Se noteaza cu Pri multimea predicatelor simple ale unei relatii Ri. Elementele lui Pri sunt notate cu pij.
Exemplul 3.3
Fiind data relatia CLIENT din figura 3.2 ,
NUME = “Mihai”
este un exemplu de predicat simplu.
Desi predicatele simple sunt elegante, interogarile utilizatorilor includ destul de des predicate mai complicate, combinatii Booleene ale predicatelor simple. O astfel de combinatie este conjunctia predicatelor simple, numita si predicat minterm. Deoarece transformarea expresiilor Booleene in forma normala conjunctiva este posibila intotdeauna, predicatele minterm pot si folosite in algoritmii de proiectare fara a pierde din generalitate.
Avand un set de predicate simple Pri = {pi1, pi2,…, pim} pentru relatia Ri , multimea Mi = {mi1, mi2, …miz} a predicatelor minterm se defineste ca:
Mi = { }, ,
unde sau . Deci fiecare predicat simplu poate apare în predicatul minterm simplu sau negatia lui.
Este important sa amintim aici, ca negatia unui predicat are sens daca acesta este un predicat de egalitate de forma:
Atribut = Valoare
Pentru predicate de inegalitate, negatia poate fi tratata ca si complement. De exemplu, negatia predicatului:
Atribut Valoare
este
Atribut > Valoare
Pe langa dificultatea teoretica de a defini complementul in multimi infinite, exista si problema practica a definirii complementului unui predicat. De aceea, se considera numai predicatele simple de egalitate.
Exemplul 3.4
Fie o relatie CLIENT de forma:
Cateva predicate minterm care pot fi definite sunt:
m1: NUME = “Ionescu” VARSTA 30
m2: NUME = “Ionescu” VARSTA > 30
m3: -(NUME = “Ionescu”) VARSTA 30
m4: -(NUME = “Ionescu”) VARSTA 30
m5: NUME = “Velescu” VARSTA 30
m6: NUME = “Velescu” VARSTA 30
Acestea nu sunt singurele predicate minterm ce pot fi definite. De asemenea, unele din aceste predicate pot sa fie fara sens. In ceea ce priveste informatiile cantitative despre aplicatiile utilizatorilor, trebuie sa avem doua multimi de date:
Selectivitate minterm: numarul tuplurilor unei relatii care vor fi accesate de o interogare a utilizatorului specificata in functie de un predicat minterm. De exemplu, selectivitatea lui m1 este 1, deoarece un singur tuplu din relatia R satisface predicatul minterm. Vom nota selectivitatea prin sel(m1).
Frecventa de acces: frecventa cu care interogarile utilizatorului acceseaza data. Daca Q = {q1, q2, …, qq} este o multime de interogari, acc(qi) indica frecventa de acces a interogarii qi intr-o perioada data.
Fragmentarea orizontala primara este definita de un operator de selectie pe o relatie proprietar. Fiind data o relatie R, fragmentele sale orizontale sunt date de:
Ri = σFi(R), 1 ≤ i ≤ w
unde Fi este formula de selectie folosita pentru a obtine fragmentul Ri. Este de notat ca daca Fi este in forma normala conjunctiva, atunci este predicat minterm (mi). Algoritmul care va urma va cere ca Fi sa fie un predicat minterm.
Exemplul 3.5
Descompunerea relatiei CLIENT in fragmentele orizontale CLIENT1 si CLIENT2 , din Exemplul 3.1 este definita astfel:
CLIENT1 = σVARSTA ≤ 30(CLIENT)
CLIENT2 = σVARSTA > 30(CLIENT)
Daca domeniul atributelor participante în formule de selectie este continuu si infinit, este dificil de a defini multimea formulelor , care va fragmenta relatia. Problema este de a manipula punctele de frontiera. De exemplu, daca se introduce un tuplu nou în relatia CLIENT cu valoarea pentru VARSTA egala cu 65, trebuie sa decidem daca acest tuplu se introduce în CLIENT2 sau se refragmenteaza relatia astfel:
CLIENT2 = σ 30 < VARSTA < 60(CLIENT)
CLIENT3 = σVARSTA > 60(CLIENT)
Aceste probleme pot fi rezolvate limitand domeniul atributelor in functie de cerintele aplicatiilor.
Exemplul 3.6
Fiind data relatia CLIENT din figura 3.2 putem defini o fragmentare orizontala bazata pe orasul de domiciliu al clientului. In figura 3.7 sunt prezentate fragmentele rezultate.
CLIENT1 = σORAS = “Bucuresti” (CLIENT)
CLIENT2 = σORAS = “Cluj” (CLIENT)
CLIENT3 = σORAS = “Pitesti” (CLIENT)
Figura 3.7 Fragmentarea orizontala primara a relatiei CLIENT
Poate fi definita acum o fragmentare orizontala cu mai multa grija. O fragmentare orizontala Ri a relatiei R este alcatuita din toate tuplurile lui R care satisfac predicatul minterm mi. Deci, fiind data o multime M de predicate minterm, se obtin atatea fragmente ale relatiei R cate predicate minterm sunt. Aceasta multime de fragmente orizontale mai este numita si multimea fragmentelor minterm.
Este clar ca definitia fragmentarii orizontale depinde de predicatele minterm. De aceea, primul pas al oricarui algoritm de fragmentare este determinarea unei multimi de predicate simple care vor forma predicatele minterm.
Doua aspecte importante ale predicatelor simple sunt completitudinea si minimalitatea. O multime Pr este completa daca si numai daca exista o probabilitate egala de acces pentru fiecare aplicatie la oricare dintre tuplurile apartinand oricarui fragment minterm raportat la Pr.
Exemplul 3.7
Este considerata fragmentarea relatiei CLIENT din figura 3.7. Daca o aplicatie acceseaza CLIENT numai in functie de oras, atunci multimea este completa, deoarece tuplu din fiecare fragment are aceeasi probabilitatea de a fi accesat. Daca exista insa o a doua aplicatie care acceseaza numai clientii cu o varsta mai mica de 30 de ani, atunci Pr nu este completa, deoarece unele tupluri din fragmentele CLIENTi au o probabilitate mai mare de a fi accesate. Pentru a face multimea Pr completa, trebuie sa adaugam doua predicate: (VARSTA ≤ 30, VARSTA > 30). Astfel, multimea predicatelor devine:
Pr ={ORAS = “Bucuresti”, ORAS = “Cluj”, ORAS = “Pitesti”,
VARSTA ≤ 30, VARSTA > 30}
Motivul pentru care completitudinea este importanta este faptul ca fragmentele obtinute in raport cu o multime completa de predicate simple sunt logic uniforme deoarece toate satisfac predicatul minterm, si sunt ,de asemenea, omogene fata de felul in care sunt accesate de aplicatii. De aceea un set complet de predicate este baza unei fragmentari orizontale primare.
A doua proprietate pe care ar trebui sa o aiba o multime de predicate este minimalitatea. Daca un predicat influenteaza realizarea fragmentarii el se numeste relevant. Daca toate predicatele dintr-o multime Pr sunt relevante, atunci Pr este minimala.
Exemplul 3.8
Multimea Pr definita in Exemplul 3.7 este completa si minimala. Daca adaugam predicatul
Nume = “Ionescu”
la multimea Pr, aceasta nu mai este minimala, deoarece noul predicat nu este relevant penru Pr. Nu exista o aplicatie care sa acceseze noile fragmentele rezultate folosind noul predicat.
In continuare este prezentat un algoritm de generare a unei multimi Pr’ complete si minimale de predicate, fiind data o multime de predicate simple Pr. Sunt folosite urmatorele notatii:
Regula 1: regula fundamentala de completitudine si minimalitate afirma ca o relatie sau un fragment este partitionat in cel putin doua parti care sunt accesate diferit de cel putin o aplicatie.
fi din Pr ’ : fragmentul fi fi este definit corespunzator unui predicat minterm definit peste predictele din Pr ’.
Algoritm 3.1 COM_MIN
intrare: R:relatie; Pr: multime de predicate simple
iesire: Pr’ : multime de predicate simple
declare: F: multime de fragmente minterm
begin
cauta pi Pr astfel incat pi partitioneaza R dupa Regula 1
Pr’ pi
Pr Pr – pi
F fi {fi este un fragment minterm corespunzator lui pi}
do
begin
cauta un pj Pr astfel ca pj partitioneaza un fk din Pr’ conform Regulii1
Pr’ Pr’ pj
Pr Pr – pj
F F fj
if pk Pr’ care este nerelevant then
begin
Pr’ Pr’ – pk
F F – fk
end
end-if
end-begin
until Pr’ este completa
end. {COM_MIN}
Algoritmul incepe prin gasirea unui predicat relevant care partitioneaza relatia de intrare. Ciclul do-until adauga iterativ predicate la aceasta multime asigurand minimalitatea la fiecare pas. Astfel, la sfarsit, multimea Pr’ este atat minimala cat si completa.
Al doilea pas in procesul de partitionare orizontala primara este derivarea predicatelor minterm care se definesc pe baza predicatelor din Pr’. Determinarea unui predicat minterm este triviala, dar dificultatea vine din faptul ca pot fi foarte multe. De aceea e important sa reducem numarul predicatelor minterm care trebuie luate in considerare pentru fragmentare.
Al treilea pas este eliminarea unor fragmente minterm care pot fi fara sens. Eliminarea se face identificand acele fragmente care ar putea intra in contradictie cu o multime de implicatii I. De exemplu, daca Pr’ = {p1, p2}, cu
p1 : atr = valoare_1
p2 : atr = valoare_2
si domeniul lui atr este {valoare_1, valoare_2} este clar ca multimea I contine doua implicatii:
i1: (atr = valoare_1) – (atr = valoare_2)
i2: – (atr = valoare_1) (atr = valoare_2)
Se definesc urmatoarele patru predicate minterm, conform Pr’:
m1: (atr = valoare_1) (atr = valoare_2)
m2: (atr = valoare_1) – (atr = valoare_2)
m3:- (atr = valoare_1) (atr = valoare_2)
m4: – (atr = valoare_1) – (atr = valoare_2)
In acest caz predicatele minterm m1 si m4 sunt contradictorii in raport cu implicatiile din I si deci pot fi eliminate din M.
Algoritmul fragmentarii orizontale primare este dat in Algoritmul 3.2. Datele de intrare sunt relatia R, care va fi fragmentata, si multimea de predicate simple Pr.
Algoritmul 3.2 Fr_ORIZONTAL
intrare: R: relatie; Pr : multime de predicate simple
iesire: M: multime de fragmente minterm
begin
Pr’ – COM_MIN(R, Pr)
determinarea multimii M de predicate minterm
determinarea multimii I de implicatii intre pi Pr’
for each mi M do
if mi este in contradictie cu I then
M M – mi
end-if
end-for
end. {Fr-ORIZONTAL}
Exemplul 3.9
Sa consideram relatia CLIENT reprezentata in Figura 3.6. Se presupune ca exista doua aplicatii care utilizeaza aceste date. Prima se afla pe trei noduri in retea si gaseste numele si varsta clientilor avand dat login-ul lor. In limbaj SQL, cererea arata astfel:
SELECT NUME, VARSTA
FROM CLIENT
WHERE LOGIN=Valoare
Pentru aceasta aplicatie, predicatele simple care vor fi folosite sunt:
p1: ORAS = “Bucuresti”
p2: ORAS = “Cluj”
p3: ORAS = “Pitesti”
A doua aplicatie se gaseste pe doua noduri. Informatiile despre clientii care au o varsta mai mica de 30 de ani sunt gestionate de un nod, iar celelate pe alt nod. Rezulta ca predicatele simple care trebuie folosite pentru fragmentare conform cu cea de-a doua aplicatie sunt:
p4: VARSTA 30
p5: VARSTA > 30
Daca se urmareste algoritmul COM_MIN, multimea Pr’ = { p1, p2, p3, p4, p5 } este, evident atat completa cat si minimala. Plecand de la Pr’, pot fi definite urmatoarele predicate minterm, care formeaza multimea M:
m1: (ORAS = “Bucuresti”) (VARSTA 30)
m2: (ORAS = “Bucuresti”) (VARSTA > 30)
m3: (ORAS = “Cluj”) (VARSTA 30)
m4: (ORAS = “Cluj”) (VARSTA > 30)
m5: (ORAS = “Pitesti”) (VARSTA 30)
m6: (ORAS = “Pitesti”) (VARSTA > 30)
Acestea nu sunt singurele predicate minterm care pot fi generate. De exemplu, putem defini predicate de forma:
p1 p2 p3 p4 p5
Totusi, sunt evidente implicatiile:
i1: p1 – p2 – p3
i2: p2 – p1 – p3
i3: p3 – p2 – p1
i4: p4 – p5
i5: p5 – p4
i6: -p4 p5
i7: -p5 p4
Ele elimina predicatele minterm cu care intra in contradictie, deci raman cele de la m1 la m6.
Rezultatul fragmentarii orizontale primare a relatiei CLIENT este format din sase fragmente FCLIENT = {CLIENT1, CLIENT2, CLIENT3, CLIENT4, CLIENT5, CLIENT6} conform cu predicatele minterm din multimea M (Figura 3.8). Trebuie notat ca unele dintre aceste fragmente sunt goale(CLIENT2, CLIENT5), deci ele nu sunt reprezentate in figura.
Figura 3.8 Partitionare orizontala a relatiei CLIENT
Fragmentarea orizontala derivata este definita pe relatia membru a unei legaturi dupa o operatie de selectie specificata pe proprietarul legaturii. Este bine de amintit doua lucruri. Mai intai, legatura dintre relatiile proprietar si membru este definita ca un equi-join. Apoi, ca un equi-join poate fi implementat cu ajutorul semi-join-urilor. Acest lucru este important pentru scopurile noastre, deoarece vrem sa partitionam relatia membru corespunzator fragmentarii proprietarului, dar vrem deasemenea ca fragmentul rezultat sa fie definit numai pe atributele relatiei membru.
Astfel, avand data o legatura L unde owner(L) = S si member(L) = R, fragmentele orizontale derivate ale lui R sunt definite astfel:
Ri = R Si, 1 i w
unde w este numarul maxim de fragmente care vor fi definite pe R si Si = σFi(S), unde Fi este formula dupa care se defineste fragmentul orizontal primar Si .
Exemplul 3.10
Consideram legatura L1 din figura 3.6 unde owner(L1)=CLIENT si member(L1)=COMANDA. Putem grupa comenzile dupa orasul unde au fost efectuate, presupunand ca fiecare client face comanda in orasul sau de domiciliu. Fragmentele rezultate sunt definite astfel:
COM1 = COMANDA CLIENT1
COM2 = COMANDA CLIENT2
COM3 = COMANDA CLIENT3
Figura 3.9 Fragmentarea orizontala derivata a ralatiei COMANDA
unde
CLIENT1 = σORAS = “Bucuresti” (CLIENT)
CLIENT2 = σORAS = “Cluj” (CLIENT)
CLIENT3 = σORAS = “Pitesti” (CLIENT)
Pentru a finaliza o fragmentare orizontala derivata este nevoie de trei date de intrare: setul de partitii a relatiei proprietar (owner) (e.g. CLIENT1, CLIENT2, CLIENT3 in exemplul 3.10), relatia membru, si setul de predicate semijoin intre proprietar si membru (e.g. CLIENT.LOGIN = COMANDA.LOGIN).
Exista totusi o posibila complicatie a algoritumului. Este de asteptat ca intr-o schema a unei baze de date sa intalnim mai mult de o legatura la o relatie. (e.g. in figura 3.6 relatia CONTINE are doua legaturi de intrare). In acest caz sunt posibile mai multe fragmentari orizontale derivate a relatiei R. Decizia alegerii fragmentarii este bazata pe doua criterii:
Fragmentarea cu cele mai bune caracteristici de join.
Fragmentarea folosita in cele mai multe aplicatii.
Al doilea criteriu este usor de inteles daca ne gandim la frecventa cu care aplicatiile acceseaza unele date. Daca este posibil, accesul utilizatorilor “grei” trebuie facilitat, astfel incat impactul lor asupra performantei sistemului sa fie minimizat.
Aplicarea primului criteriu este totusi putin mai dificila. Considerand, spre exemplu, fragmentarea din exemplul 3.10, efectul (si obiectivul) acestei fragmentari este ca join-ul dintre relatiile CLIENT si COMANDA care sa raspunda interogarilor este asistat de (1) aplicarea lui pe relatii mai mici (e.g. fragmente) si (2) posibila aplicare a lui intr-o maniera distribuita.
Primul punct este evident. Fragmentele relatiei COMANDA sunt mai mici decat relatia insasi. Astfel, un join intre oricare fragment CLIENT si oricare fragment COMANDA este mai rapid decat un join intre relatii. Al doilea punct este mai important, si sta la baza bazelor de date distribuite. Daca, pe langa executarea unui numar de interogari la diferite locatii, putem executa o interogare in paralel este de asteptat ca timpul de raspuns al sistemului sa se imbunatateasca. In cazul join-urilor acest lucru este posibil in anumite circumstante. Sa luam de exemplu legaturile dintre fragmentele derivate ale relatiilor COMANDA si CLIENT rezultate in exemplul 3.10 (figura 3.9) Exista o singura legatura care iese sau intra dintr-un fragment.Un astfel de graf al join-urilor se numeste graf simplu. Avantajul unei modelari unde relatia de join intre fragmente este simpla este ca proprietarul si membrul unei legaturi pot fi alocati la o locatie si operatiile de join intre diferitele perechi de fragmente pot fi executate independent si in paralel.
Trebuie sa mai retinem doua lucruri despre fragmentarea orizontala derivata:
Fragmentarea derivata poate urma un lant, unde o relatie este fragmentata ca rezultat al modelarii altei relatii, si ea, la randul sau cauzeaza fragmentarea altei relatii.
De obicei sunt posibile mai multe fragmentari ale unei relatii. Alegerea finala a schemei de fragmentare poate fi o problema adresata in timpul alocarii.
Verificarea corectitudinii
Vom verifica algoritmii fragmentarii tinand cont de criteriile de corectitudine prezentare in sectiunea 3.2.3
Completitudinea. Este bazata pe predicatele de selectie folosite. Atat timp cat predicatele de selectie sunt complete, fragmentarea rezultata este si ea completa. Deoarece baza fragmentarii este un set de predicate complete si minimale, Pr’, completitudinea este garantata atat timp cat nu exista greseli in definirea predicatelor Pr’.
Completitudinea unei fragmentari orizontale derivate este oarecum mai dificil de definit. Aceasta dificultate vine din faptul ca predicatul care determina fragmentarea implica doua relatii. Regula de completitudine se defineste formal astfel:
Fie R o relatie membru a unei legaturi, si S relatia proprietar, care este fragmentata dupa FS = {S1, S2, … Sw}. Fie A atributul de join intre R si S. Atunci, pentru fiecare tuplu t sin R, exista un tuplu t’ in S astfel incat
t{A] = t’[A].
De exemplu, nu ar trebui sa existe un tuplu in realtie COMANDA care sa aiba un LOGIN care nu exista in relatia CLIENT. Aceasta regula este cunoscuta ca integritate referentiala si garanteaza faptul ca orice fragment din relatia membru se regaseste si in relatia proprietar.
Reconstructia. Reconstructia unei relatii globale din fragmentele sale este facuta prin operatorul de reuniune in fragmentarea orizontala primara si derivata. Astfel, pentru o relatie cu fragmentarea FR = {R1, R2, …, Rw}
R = U Ri, RiFR
Disjunctia. Este mai usor de determinat disjunctia in cazul fragmentarii orizontale primare decat in cazul celei derivate. In primul caz disjunctia este garantata atata timp cat predicatele minterm care determina fragmentarea sunt mutual exclusive.
In fragmentarea derivata, insa, exista un semijoin care adauga complexitate considerabila. Disjunctia poate fi garantata daca graful join este simplu. Daca nu este simplu, atunci este necesara investigarea valorilor tuplurilor. In general, nu este de dorit sa avem un tuplu al relatiei membru in jonctiune cu doua sau mai multe tupluri ale relatiei proprietar cand aceste tupluri se alfa in fragmente diferite ale relatiei proprietar. Acest lucru nu este usor de stabilit, si acesta un din motivele pentru care sunt de dorit fragmentarile ale caror scheme implica graful join simplu.
3.3.2. Fragmentare pe verticala
S-a spus mai devreme ca fragmentarea verticala a unei relatii R produce fragmentele R1, R2, … Rn, fiecare continand o submultime de atribute ale lui R si cheia primara a lui R. Obiectivul fragmentarii pe verticala este de a partitiona o relatie in relatii mai mici astfel incat aplicatiile utilizatorului sa ruleze pe un singur fragment. In acest context, o fragmentare “optima“ este una care duce la minimizarea timpului de executie a aplicatiilor utilizatorului care ruleaza pe fragmentele rezultate.
Fragmentarea verticala a fost investigata atat in contextul bazelor de date centralizate cat si in cel al celor distribuite. Rolul sau in contextul bazelor de date centralizate este de unealta de modelare, care permite interogarilor utilizatorilor sa opereze cu relatii mai mici [Navathe et al., 1984]. S-a sugerat de altfel, ca cele mai “active” subrelatii pot fi identificate si puse intr-o memorie mai rapida, in cazul in care sunt suportate ierarhiile de memorie [Eisner and Severance, 1976]
Partitionarea verticala este mai complicata decat cea orizontala datorita numarului mare de alternative disponibile. De exemplu, in partitionarea orizontala daca numarul total de predicate simple din Pr este n, atunci exista 2n predicate minterm posibile. Dar unele dintre aceste predicate intra in contradictie cu implicatiile existente, deci numarul fragementelor candidate se reduce si mai mult. In cazul partitionarii verticale insa, daca o relatie are m atribute care nu sunt chei primare numarul fragmentelor posibile este B(m), care este al m-lea numar Bell [Niamir, 1978]. Pentru valori mari ale lui m, B(m)≈mm; de exemplu, pentru m=10, B(m) ≈115.000, pentru m=15, B(m) ≈109 [Hammer and Niamir, 1979]
Aceste valori arata faptul ca este inutil sa cautam solutii optime ale problemei partitionarii verticale. Exista doua abordari euristice ale fragmentarii verticale a relatiilor globale:
Gruparea: incepe prin a atribui fiecare atribut unui fragment, si la fiecare pas, se face jonctiunea cu unele din fragmente pana ce un anumit criteriu e satisfacut.
Divizare: porneste de la o relatie si decide asupra partitionarii optime avand in vedere accesul aplicatiilor la atribute. Tehnica a fost discutata prima data pentru baze de date centralizate in [Hoffer and Severance, 1975]. A fost apoi extinsa la mediul distribuit in [Navathe et al., 1984]
Vom discuta in cele ce urmeaza tehnica divizarii, intrucat se potriveste mai bine metodologiei top-down de modelare, deoarece solutia “optima” este probabil mai aproape de intreaga relatie decat de un set de fragmente unde fiecare fragment este alcatuit dintr-un singur atribut. Deasemenea, divizarea genereaza fragmente care nu se suprapun, in timp ce fragmentele rezultate in urma gruparii se suprapun de obicei. Desigur, nesuprapunerea fragmentelor se refera numai la atributele care nu sunt chei primare.
Replicarea cheii primare este o caracterisitica a fragmentarii verticale care permite reconstructia relatiei globale. Astfel, divizarea se aplica numai atributelor care nu participa la cheia primara.
In ciuda problemelor evidente cauzate de replicarea atributelor care reprezinta chei, exista si un avantaj puternic, care tine de intarirea integritatii semantice. Daca avem o baza de date in care atributele cheie sunt parte a unui fragment alocat intr-un anumit loc, iar atributele care refera aceste chei sunt parte a altui fragment, aflat la o locatie diferita, atunci fiecare cerere de reactualizare care cauzeaza o verificare de integritate va necesita comunicarea intre cele doua locatii. Replicarea atributelor cheie la fiecare fragment reduce aceste costuri de comunicatie, dar nu le elimina definitiv.
O alternativa a replicarii atributelor cheie este folosirea identificatorilor de tupluri (tuple identifiers – TIDs), care sunt valori unice atribuite de sistem fiecarui tuplu al unei relatii. Deoarece identificatorii sunt mentinuti de sistem, fragmentele sunt disjuncte din punctul de vedere al utilizatorului.
Informatii necesare pentru fragmentarea verticala
Principalele informatii necesare pentru fragmentarea verticala tin de aplicatii. Cum partitionarea verticala aseaza intr-un fragment acele atribute care sunt de obicei accesate impreuna, se impune definirea mai precisa a notiunii de “impreuna”. Aceasta masura este “afinitatea” atributelor, care indica cat de stranse sunt relatiile dintre atribute. Din pacate, aceste valori nu pot fi specificate usor. Astfel, ele pot fi obtinute din date mai primitive. Frecventa accesarii datelor este una din principalele caracteristici ale aplicatiilor. Fie Q = {q1, q2, …, qn } un set de interogari (aplicatii) care ruleaza pe relatia R(A1, A2, …, An). Atunci, pentru fiecare interogare qi si pentru fiecare atribut Aj asociem o valoare de folosire a atributului, use(qi , Aj), definita astfel:
Exemplul 3.11
Considerand relatia CLIENT din figura 3.2, presupunem ca urmatoarele aplicatii ruleaza pe aceasta relatie. Este prezentat si codul SQL pentru fiecare interogare:
q1: Gaseste varsta unui client fiind dat codul clientului.
SELECT VARSTA
FROM CLIENT
WHERE CLIENT_NR = Valoare
q2: Gaseste numele si prenumele tuturor clientilor.
SELECT NUME, PRENUME
FROM CLIENT
q3: Gaseste numele clientilor dintr-un oras dat.
SELECT NUME
FROM CLIENT
WHERE ORAS = Valoare
q4: Gaseste numarul de clienti dintr-un anumit oras.
SELECT COUNT(CLIENT_NR)
FROM CLIENT
WHERE ORAS = Valoare
Tinand cont de aceste aplicatii putem defini valorile de utilizare ale atributelor, pe care le notam cu: A1 = CLIENT_NR, A2 = NUME, A3 = PRENUME, A4 = VARSTA, A5 = ORAS. Valorile sunt scrise in matricea urmatoare, unde pozitia (i,j) reprezinta valoarea use(qi , Aj) .
Figura 3.10 Exemplu de matrice a valorilor de utilizare a atributelor
Valorile de utilizare a atributelor nu sunt insa destul de generale pentru a reprezenta baza divizarii si fragmentarii atributelor. Ele nu exprima de cate ori este utilizat un atribut de o anumita cerere, ci numai daca este utilizat sau nu.Astfel, masura freventei poate fi inclusa in definitia afinitatii dintre doua atribute, notata aff(Ai, Aj), care masoara legatura dintre doua atribute relativ la modul in care ele sunt accesate de aplicatii.
Masura afinitatii atributelor dintre atributele Ai si Aj ale unei relatii R(A1,A2,…An) referitor la setul de interogari Q = { q1, q2, …, qn } este:
unde refl(qk) este numarul de accesari ale atributelor (Ai , Aj) pentru fiecare executie a aplicatiei qk la locatia Sl si accl(qk) este masura frecventei de acces definita anterior, modificata acum astfel incat sa includa si frecventele de la alte locatii.
Rezultatul acestui calcul este o matrice n x n, in care fiecare element este una din masurile de mai sus. Aceasta matrice se numeste “matricea afinitatii atributelor” – attribute affinity matrix (AA).
Exemplul 3.12
Continuam cu cazul examinat la exemplul anterior. Presupunem pentru simplificare ca refl(qk) = 1, pentru toatea aplicatiile qk si locatia Sl. Daca frecentelor aplicatiilor sunt:
Atunci masura afinitatii dintre atributele A1 si A3 este:
Observam ca se aduna valorile frecventelor de la toate locatiile corespunzatoare aplicatiei q1, deoarece aceasta este singura care utilizeaza atributele A1 si A3. Se calculeaza astfel toata matricea, chiar si valorile de pe diagonala principala care nu sunt utile.
Attribute affinity matrix va fi folosita in continuare in eforturile de fragmentare. Procesul include, mai intai, gruparea atributelor care au o mare afinitate intre ele si apoi impartirea corespunzatoare a relatiei.
Figura 3.11 Attribute Affinity Matrix
Algoritmul de grupare (clustering)
Principala problema in fragmentarea verticala o reprezinta gasirea unor metode de grupare a atributelor unei relatii bazate pe valorile din attribute affinity matrix, AA. Algoritmul energiei de legatura (bond energy algorithm) a fost sugerat de [Hoffer and Soverance, 1975] si [Navathe et al., 1984]. Este considerat a fi potrivit din urmatoarele motive:
Grupeaza atributele cu valori de afinitate mai mare.
Gruparile finale nu sunt afectate de ordinea in care atributele sunt prezentate algoritmului
Timpul de calcul este rezonabil, O(n2), unde n este numarul de atribute
Relatiile dintre atributele organizate deja in grupuri sunt identificabile
Algoritmul energiei de legatura are ca parametru de intrare attribute affinity matrix. Prin permutarea randurilor si coloanelor, se obtine matricea afinitatilor grupate (clustered affinity matrix – CA) . Permutarea se face astfel incat masura globala a afinitatii (global affinity measure – AM) sa fie maxima:
unde
Attribute affinity matrix (AA) este simetrica, deci relatia de mai sus se poate scrie:
Generarea matricei CA (clustered affinity matrix) se face in trei pasi:
Initializare. Fixarea unei coloane arbitrare din matricea AA in matricea CA. In algoritm se alege coloana 1.
Iteratia. Fiecare din cele n-i coloana ramase se fixeaza in cele i+1 pozitii ramase libere in matricea CA. Se alege pozitia care are cea mai mare contributie la masura afinitatii globale, formulate mai sus. Se repeta acest pas pana nu mai raman coloane.
Ordonarea randurilor. Ultimul pas consta in schimbarea asezarii randurilor astfel incat pozitiile lor relative sa se potriveasca cu pozitiile relative ale coloanelor.
Algoritmul 3.3 BEA
input: AA: attribute afiinity matrix
output: CA: clustered affinity matrix
begin
{initializare: AA este o matrice n x n}
CA(●,1) AA(●,1)
CA(●,2) AA(●,2)
index 3
while index ≤ n do (alege cea mai buna pozitie pentru atributul Aindex)
begin
for i from 1 to index – 1 by 1 do
calculate cont(Ai-1, Aindex, Ai)
end-for
calculate cont(Aindex-1, Aindex, Aindex+1)
loc pozitia data de valoarea maxima a lui cont
for j from index to loc by -1 do {amestecarea celor doua matrici}
CA(●, j) CA(●, j)
end-for
CA(●, loc) AA(●, index)
index index + 1
end-while
ordoneaza randurile relativ la ordonarea coloanelor
end. {BEA}
Am intalnit in algoritm functia cont care reprezinta contributia unui atribut la masura afinitatii. Ea poate fi dedusa astfel. Formula afinitatii globale a fost definita mai sus:
care poate fi rescrisa
Definim legatura (bond) dintre doua atributa ca fiind
Atunci AM poate fi scris:
Se considera acum urmatoarele atribute:
Masura afinitatii globale pentru aceste atribute poate fi scrisa:
AMold = AM’ + AM’’
+
Se considera asezarea unui nou atribut Ak intre atributele Ai si Aj in clustered affinity matrix. Noua masura a afinitatii globale poate fi scrisa astfel:
Astfel, contributia neta la masura afinitatii globale a plasarii atributului Ak intre Ai si Aj este:
Exemplul 3.13
Se considera matricea AA din figura 3.11, iar contributia mutarii atributului A4 intre atributele A1 si A2 este data de formula:
Calculand fiecare termen, obtinem:
Avem deci
Se observa ca masura bond intre doua atribute sa calculeaza inmultind elementele din cele doua coloane reprezentand atributele in Attribute Affinity Matrix. Aceste produse se aduna, obtinandu-se astfel masura bond.
Exemplul 3.14
Se considera gruparea (clustering) relatiei CLIENT si Attribute Affinity Matrix din figura 3.11.
(a) (b)
(d)
(e)
Figura 3.12 Calculul matricei Clustered Affinity Matrix (CA)
Conform algoritmului, se copiaza coloanele 1 si 2 din matricea AA in matricea CA, si se incepe cu coloana 3, corespunzatoare atributului A3. Exista trei alternative pentru asezarea coloanei 3: la stanga coloanei 1, rezultand ordinea (3-1-2), intre coloanele 1 si 2 (1-3-2), si in fine, la dreapta coloanei 2, rezultand ordinea (1-2-3). Pentru a calcula contributia ultimei ordonari trebuie calculat cont(A2, A3, A4), dar aici indexul 4 se refera la coloana 4 din matricea Cam care e goala. Se calculeaza masura afinitatii globale pentru fiecare din aceste alternative.
Ordonarea (0-3-1):
Se stie ca
Deci
Ordonarea (1-3-2):
Deci:
Ordonarea (2-3-4):
Deci:
Cum contributia ordonarii (2-3-4) este cea mai mare, alegem sa plasam coloana 3 la dreapta coloanei 2, obtinand astfel matricea din figura 3.12 (b). Calcule similare arata ca A4 ar trebuie plasat la stanga coloanei 1, si A5 va fi plasat pe pozitia 3, intre coloanele 1 si 2.
Se observa in figura 3.12 crearea a doua grupuri: unul este in coltul din stanga sus si contine valorile de afinitate mai mici, iar celalalt, aflat in coltul din dreapta jos, contine valorile de afinitate mai mari. Aceste grupuri sugereaza o anumita impartire a atributelor relatiei CLIENT. In general insa, frontiera acestei impartiri nu este foarte clara, iar daca matricea CA este mare, se obtin mai multe grupuri, rezultand astfel mai multe alternative de partitionare. Aceasta problema trebuie abordata sistematic.
Algoritmul de partitionare
Obiectivul partitionarii este de a gasi atribute care sunt accesate de seturi diferite de aplicatii. De exemplu, daca este posibila identificarea a doua atribute, A1 si A2, care sunt accesate numai de aplicatia q1 si atributele A3 si A4 sunt accesate de aplciatiile q2 si q3, atunci fragmentarea este evidenta. Sarcina consta in a gasi o metoda algoritmica pentru gasirea acestor grupuri de atribute.
Figura 3.13 Localizarea unui punct de impartire
Se considera matricea CA din Figura 3.13. Daca se fixeaza un punct pe diagonala principala, atunci putem identifica doua seturi de atribute. Primul set, {A1, A2, … Ai} se afla in coltul din stanga sus al matricii, iar cel de-al doilea, {Ai+1, …, An} in coltul din dreapta jos. Notam cele doua seturi TA (top attribute), respectiv BA (bottom attribute). Fie setul de aplicatii Q={q1, q2, …qq}. Definim multimile aplicatiilor care acceseaza numai TA, numai BA sau pe amandoua:
Prima ecuatie defineste multimea atributelor care sunt accesate de aplicatia qi: TQ si BQ sunt multimile de aplicatii care acceseaza numai TA, respectiv BA, si OQ este multimea aplicatiilor care le acceseaza pe amandoua.
Exista acum o problema de optimizare. Daca sunt n atribute intr-o relatie, atunci exista n-1 posibilitati de a plasa punctul de impartire de-alungul diagonalei principale a matricii CA. Cea mai buna pozitie pentru acest punct este una care produce multimi TQ si BQ astfel incat numarul total al accesarilor unui singur fragment sa fie maximizat, in timp ce numarul total al accesarilor ambelor fragmente trebuie minimizat. Asadar, se definesc urmatoarele ecuatii ale costurilor:
Fiecare din ecuatiile de mai sus descrie numarul total de accesari ale atributelor de catre aplicatiile corespunzatoare lor. Tinand cont de aceste masuri, problema de optimizare se reformuleaza astfel: trebuie gasit un punct x astfel incat expresia z=CTQ*CBQ-COQ2 sa fie maxima.
Inainte de prezentarea algoritmului, mai trebuie tinut cont de alte doua puncte importante: primul tine de impartirea fragmentelor. Daca mai sus a fost prezentata o procedura de impartire in doua fragmente, pentru multimi mari de atribute este necesara impartirea in m fragmente. Modelarea unui algoritm de partitionare in m fragmente este posibila, dar scumpa din punct de vedere al timpului de executie. Solutia alternativa este aplicarea recursiva a partitionarii binare, prezentata mai sus. Se calculeaza TQ, BQ si OQ, si fiecare se partitioneaza mai departe, urmand acelasi algoritm.
Al doilea punct important tine de locatia unui bloc de atribute care formeaza un framgent. S-a presupus pana acum ca punctul de impartire este unic si imparte matricea CA intr-o partitie stanga-sus, si inca o partitie formata din restul atributelor. Insa partitita se poate forma si in mijlocul matricii. In acest caz algoritmul trebuie usor modificat. Prima coloana din matricea CA se muta astfel incat sa devina ultima, iar randul de sus se muta jos. Operatia de mutare este urmata de o verificare a celor n-1 pozitii de pe diagonala pentru a se gasi pozitia care produce o valoare z maxima.
Presupunand ca o procedura SHIFT (MUTARE) a fost deja implementata, putem prezenta algoritmul de partitionare. Datele de iesire sunt doua relatii, R1 si R2, astfel incat si atributul cheie primara al relatiei R.
Algoritmul 3.4 PARTITIONARE
input: CA: clustered affinity matrix; R: relatie; ref: matricea utilizarii atributelor;
acc: matricea frecventelor accesarilor;
output: FR: multime de fragmente
begin
{determinarea valorii z pentru prima coloana}
{indicii din ecuatiile de cost indica punctul de impartire}
calculeaza CTQn-1
calculeaza CBQn-1
calculeaza COQn-1
best CTQn-1* CBQn-1-( COQn-1)2
do
begin
for i from n-2 to 1 by -1 do
begin
calculeaza CTQi
calculeaza CBQi
calculeaza COQi
z CTQi* CBQi-( COQi)2
if z>best then
begin
bestz
memoreaza punctul de impartire
end-if
end-for
Apeleaza SHIFT(CA)
end-begin
until nu mai este posibil SHIFT {nu mai sunt posibile alte mutari}
reconstruieste matricea conform mutarilor facute
{K este multimea atributelor cheie primara ale lui R}
end. {PARTITIONARE}
Verificarea corectitudinii
Completitudine. Completitudinea este garantata de algoritmul PARTITIONARE intrucat fiecare atribut al relatiei globale este atribuit unuia dintre fragmente.
Reconstructia. Reconstructia unei relatii globale este posibila prin operatii de join. Asadar, pentru o relatie cu fragmentarea verticala FR = {R1, R2, … Rr} si atributele cheie K, avem:
Este deasemenea important de notat ca fiecare fragment Ri trebuie sa contina fie atributele cheie ale relatiei R, fie identificatorii de tupluri atribuiti de sistem (TIDs).
Disjunctia. Disjunctia nu este la fel de importanta in fragmentarea verticala precum in cea orizontala. Se disting aici doua cazuri:
Se folosesc TIDs (identificatori de tupluri), caz in care fragmentele sunt disjuncte, intrucat identificatorii care sunt replicati in fiecare fragment sunt entitati atribuite si gestionate de sistem, total invisibile utilizatorului
Atributele cheie sunt replicate in fiecare fragment, caz in care nu se poate spune ca fragmentele sunt disjuncte, in adevaratul sens al cuvantului. Totusi, aceasta dublare este cunoscuta si gestionata de sistem si nu are aceleasi implicatii ca dublarea tuplurilor in fragmentarea orizontala. Cu alte cuvinte, cat timp atributele sunt disjuncte, cu exceptia celor care formeaza cheia primara, fragmentele pot fi numite disjuncte.
3.3.3. Fragmentare hibrida
In cele mai multe cazuri o simpla partitionare orizontala sau verticala a unei baza de date nu este suficienta pentru a satisface cererile aplicatiilor utilizatorilor. In acest caz, o partitionare varticala poate fi urmata de una orizontala, sau invers, obtinandu-se astfel o structura arborescenta. Aceasta alternativa este cunoscuta drept fragmentare hibrida. A mai fost numita si fragmentare mixta.
Figura 3.14 Fragmentare hibrida
Regulile de corectitudine pentru fragmentarea hibrida le urmeaza natural pe cele de la fragmentarea verticala si orizontala. De exemplu, pentru reconstructia unei relatii globale, se pleaca de la “frunze” si prin relatii de join si union se obtine relatia initiala. Fragmentarea este completa daca fragmentele intermediare si cele “frunza” sunt complete. Similar, disjunctia este garantata daca fragmentele intermediare si frunza sunt disjuncte.
3.4. Alocarea fragmentelor
Alocarea resurselor intre nodurile unei retele de calculatoare este o problema veche care a fost idelung studiata. Cea mai mare parte a acestei activitati nu tine insa de modelarea bazelor de date distribuite, ci de plasarea fisierelor individuale pe o retea de calculatoare.
3.4.1. Problema alocarii
Fie o multime de fragmente F = {F1, F2, …, Fn} si o retea alcatuita din nodurile S = {S1, S2, …, Sn} pe care ruleaza o multime de aplicatii Q = {q1, q2, …qn}. Problema alocarii consta in gasirea distribuirii optime a multimii F la S.
Una din problemele fundamentale care trebuie abordate este definirea optimalitatii. Aceasta poate fi definita avand in vedere doua masuri:
Costul minim. Functia cost consta in costul stocarii fiecarui fragment Fi la o localie Sj, costul interogarii lui Fi la locatia Sj, costul reactualizarii lui Fi la toate locatiile unde este stocat, si costul comunicarii de date. Problema alocarii incearca asadar gasirea unei scheme de alocare care sa minimizeze functia cost.
Performanta. Strategie de alocare trebuie sa mentina anumite masuri ale performantei. Din cele mai cunoscute doua sunt minimizarea timpului de executie si maximizarea rezultatelor obtinute de sistem.
O formulare foarte simplista a problemei este: fie F si S sunt multimile definite mai sus si Fk un fragment din multimea F. O serie de presupuneri si definitii vor permite modelarea problemei alocarii:
Se presupune ca multimea Q poate fi modificata astfel incat este posibila identificarea cererilor de reactualizare si de recuperarea a datelor. Se defineste urmatoarele multimi pentru un singur fragment Fk:
T ={t1,t2,…tm}
unde ti este traficul read-only generat la locatia Si pentru Fk si
U = {u1, u2, …, um}
unde ui este traficul de reactualizare (update) generat la locatia Si pentru Fk.
Se presupune ca este fixat un cost de comunicatie intre oricare doua locatii Si si Sj pentru o unitate de transmisie. Deasemenea, se presupune ce este diferit pentru reactualizari si recuperare astfel incat este posibila definirea urmatoarelor multimi:
C(T) = {c12, c13, …, c1m,…, cm-1,m}
C’(U) = {c’12, c’13, …, c’1m, …, c’m-1,m}
unde cij este unitatea de cost al comunicatiei pentru cererile de recuperare intre locatiile Si si Sj, si c’ij este unitatea de cost al comunicatiei pentru operatii de reactualizare intre Si si Sj
Fie di costul stocarii fragmentului la locatia Si. Se defineste astfel D={d1, d2, …, dm} costul de stocare al fragmentului Fk la toate locatiile.
Se presupune ca nu exista limite de capacitate pentru locatii sau pentru caile de comunicatie.
Atunci problema alocarii devine o problema de minimizare a costului in care se incearca gasirea unei multimi care specifica unde se vor stoca copiile fragmentului. Variabila xj exprima decizia plasarii fragmentului astfel:
xj = 1, daca fragmentul Fk este atribuit locatiei Sj
0, altfel
Mai exact, trebuie aflat
,
cand xj = 0 sau 1
Aceasta formulare a problemei este una simplista, care nu este potrivita pentru modelarea bazelor de date distribuite. Alte formulari s-au dovedit la fel de dificil de formulat, iar pentru un numar mare de fragmente obtinerea de solutii optime nu este fezabila din punctul de vedere al puterii de calcul implicate. De aceea cercetarile s-au concentrat pe gasirea unor solutii apropiate de cea optima.
Nu exista modele euristice care primeasca ca date de intrare o multime de fragmente si sa produca o alocare optima. De aceea, in continuare este prezentat un model general .
3.4.2. Informatii necesare
In etapa alocarii sunt necesare informatii cantitative despre baza de date, aplicatiile care ruleaza pe aceasta, reteaua de comunicatie, posibilitatile de procesare si limitarile de stocare pe retea.
Informatii despre baza de date
Pentru a efectua fragmentarea orizontala s-a definit selectivitatea predicatelor minterm. Aceasta definitie trebuie extinsa acum la fragmente, selectivitatea fragmentului Fj fiind definita referitor la aplicatia qi. Aceasta este reprezentata de numarul de tupluri din fragmentul Fj care trebuie accesate pentru a procesa cererea qi. Aceasta valoare va fi notata seli(Fj).
Alta informatie necesara despre fragmentele bazei de date este marimea lor. Marimea fragmentului Fj este data de:
unde length(Fj) este lungimea in bytes unui tuplu al fragmentului Fj
Informatii despre aplicatie
Cele mai importante doua masuri sunt numarul de accesari de citire pe care o interogare qi o face pe un fragment Fj la executia sa (notat cu RRij) si omologul acestui numar pentru accesarile de reactualizare (URij). Se definesc deasemenea si matricile UM si RM, cu elementele uij, respectiv rij :
uj = 1, daca interogarea qi reactualizeaza fragmentul Fj
0, altfel
rj = 1, daca interogarea qi recupereaza date de la Fi
0, altfel
Se defineste si un vector O, unde o(i) specifica locatia de unde este executata cererea qi. In fine, pentru a defini constrangerea care tine de timpul de raspuns, se specifica timpul maxim permis pentru a obtine un raspuns de la fiecare aplicatie.
Informatii despre locatie
Pentru fiecare calculator din retea trebuie cunoscuta capacitatea de stocare si procesare. Evident, aceste valori pot fi calculate cu ajutorul unor functii elaborate sau prin simple estimari. Costul unitar al stocarii de date la locatia Sk va fi notat USCk (Unit Storage Cost). Deasemenea este necesara specificarea unei masuri a costului de procesare: LPCk. Aceasta este costul procesarii unei unitati de la locatia Sk. O astfel de unitate ar trebui sa fie similara cu masurile RR si UR, mentionate mai sus.
Informatii despre retea
In modelul prezentat se presupune existenta unei retele simple, in care costul comunicatiei este definit in termeni de pachete de date. Astfel, gij exprima costul comunicarii unui pachet standard intre locatiile Si si Sj. Pentru a calcula numarul mesajelor folosim fsize ca fiind masura (in bytes) a unui pachet. Desigur exista modele de retele mai elaborate in care sa iau in considerare capacitatile canalelor de comunicatie, distantele dintre noduri etc.
3.4.3. Model de alocare
Modelul de alocare prezentat incearca minimizarea costului total al procasarii si stocarii datelor, respectand, in acelasi timp, anumite constrangeri care tin de timpul de raspuns.
Costul total
Functia cost total are doua componente: costul procesarii cererilor si stocarii fragmentelor. Ea poate fi exprimata astfel:
unde QPCi este costul procesarii cererii qi (Query Processing Cost), iar STCjk (Storage Total Cost) este costul stocarii fragmentului Fj la locatia Sk.
Costul stocarii este descris de ecuatia:
iar calculul celor doua sume duce la costul total al stocarii tuturor fragmentelor la toate locatiile.
Costul procesarii cererilor este insa mai greu de specificat. Acesta contine doua componente: costul procesarii propriu-zise (PC) si costul transmisiei (TC). Astfel costul procesarii aplicatiei qi este:
QPCi = PCi +TCi
Costul procesarii este suma dintre trei costuri: costul de acces (Acces Cost – AC), costul asigurarii integritatii (Integrity Enforcement – IE) si costul controlului concurentei (Concurrency Control – CC).
PCi = ACi + IEi + CCi
Costul transmisiei poate fi exprimat urmand modelul costului de acces, dar intre cererile de reactualizare si cele de recuperare de date exista diferente din punctul de vedere al costului de transmisie. Cat timp in cazul cererilor de recuperare a datelor cererea nu trebuie sa acceseze decat o locatie unde se afla datele vizate, in cazul cererilor de reactualizare trebuie accesate toate locatiile unde se afla copii ale datelor vizate de respectiva. Deasemenea, in timp ce cererile de reactualizare nu trimit inapoi decat un mesaj de confirmare, cele de recuperare a datelor pot trimite inapoi un important volum de date. Costul de transmisie pentru cererea qi poate fi exprimat ca:
TCi = TCUi + TCRi
unde TCUi este costul de transmisie pentru reactualizari, iar TCRi este costul de transmisie pentru operatii de recuperare a datelor.
Constrangeri
Functiile de constrangere pot fi descrise astfel:
Constrangerea referitoare la tiumpul de raspuns:
timpul de raspuns al cererii qi timpul maxim de raspuns al cererii qi,
Constrangerea de stocare este:
capacitatea de stocare a locatiei Sk,
Iar constrangerea de procesare este:
procesarea lui qi la locatia Sk capacitatea de procesare la Sk,
4. CONTROLUL SEMANTIC AL DATELOR
Este important pentru un SGBD centralizat sau distribuit sa suporte controlul semantic al datelor. Controlul semantic al datelor include de obicei gestiunea vizualizarilor, controlul securitatii si controlul semantic al integritatii. Altfel spus, aceste functii trebuie sa se asigure ca utilizatorii autorizati efectueaza operatii corecte asupra bazei de date, astfel mentinand integritatea bazei de date.
Sunt prezentate in sectiunile urmatoare ale capitolului gestiunea vizualizarilor, controlul securitatii si controlul semantic al integritatii. Pentru fiecare din acestea sunt prezentate solutiile implementate intr-un SGBD centralizat, si apoi solutiile pentru mediile distribuite, care sunt de obicei extensii ale celor din mediul centralizat.
Gestiunea vizualizarilor
Unul dintre principalele avantaje ale modelului relational este ca ofera independenta logica totala a datelor. Intr-un sistem relational o vizualizare, sau vedere, este o relatie virtuala, definita ca rezultatul unei interogari a relatiilor de baza, dar nematerializata, spre deosebire de relatiile reale, care sunt stocate in baza de date. O vizualizare este o fereastra dinamica, in sensul ca reflecta toate reactualizarile efectuate asupra bazei de date. Vizualizarile sunt folosite pentru a asigura securitatea datelor intr-un mod foarte simplu. Selectand o submultime a bazei de date, vederile ascund o parte din date. Daca utilizatorii acceseaza baza de date numai prin intermediul vederilor, ei nu pot accesa sau manipula datele ascunse, care astfel sunt sigure.
Vizualizari in SGBD-uri centralizate
In acest context o vizualizare este o relatie derivata dintr-o relatie de baza prin intermnediul unei interogari. Este definita prin asocierea numelui vizualizarii cu interogarea care o caracterizeaza.
Exemplul 4.1
Vederea PROD_NOTEBOOK derivata din relatia PRODUS (PRODUS_ID, NUME, PRET, CATEGORIE) poate fi definita de urmatoarea interogare SQL:
CREATE VIEW PROD_NOTEBOOK(PRODUS_ID, NUME)
AS SELECT PRODUS_ID, NUME
FROM PRODUS WHERE CATEGORIE=’NOTEBOOK’
Singurul efect al cererii este stocarea definitiei vederii in catalog. Nici o alta informatie nu trebuie memorata. Cu toate ca nu cererea nu produce o relatie, vizualizarea PROD_NOTEBOOK poate fi manipulata ca o relatie de baza.
Figura 4.1 Relatia corespunzatoare vizualizarii PROD_NOTEBOOK
Exemplul 4.2
Vizualizarea C_ORAS restrictioneaza accesul oricarui utilizator astfel incat acesta nu poate “vedea” decat acei clienti din acelasi oras cu el.
CREATE VIEW C_ORAS
AS SELECT * FROM CLIENT C1, CLIENT C2
WHERE C1.ORAS = C2.ORAS
AND C1.NUME = USER
Prima conditie din clauza WHERE semnifica operatia de INNER JOIN pe relatia CLIENT. A doua conditie identifica tuplul pe care se face operatia de join cu utilizatorul curent. Daca utilizatorul curent este din Bucuresti, atunci el nu are acces decat la clientii din Bucuresti.
Reactualizari prin intermediul vizualizarilor
Vizualizarile pot fi definite prin intermediul unor interogari arbitrare constand in operatii de selectie, proiectie, join, functii agregat etc. Toate vizualizarile pot fi interogate ca relatii de baza, dar nu toate pot fi manipulate asa. Actualizarile pe o vedere pot fi gestionate automat numai daca ele pot fi propagate corect pana la relatia de baza. Vederile pot fi actualizabile sau nu. O vedere poate fi actualizata numai daca aceste operatii pot fi propagate pana la relatia de baza fara ambiguitati. Vederea PROD_NOTEBOOK, de exemplu, poate fi actualizata. La o operatie de inserare atributele care sunt ascunse prin intermediul vizualizarii primesc valoarea null. Urmatoarea vedere nu poate fi actualizata:
CREATE VIEW CC(NUME, COMANDA_ID)
AS SELECT NUME, COMANDA_ID
FROM CLIENT, COMANDA
WHERE CLIENT.CLIENT_ID = COMANDA.CLIENT_ID
Stergerea unui tuplu cu o anumita valoare a atributului CLIENT_ID nu poate fi propagata. Atat stergerea unui client cu acest cod din tabela CLIENT cat si stergerea unei comenzi efectuate de acest client din tabela COMANDA au sens, dar sistemul nu stie care este corecta.
Sistemele actuale sunt foarte restrictive in ceea ce priveste reactualizarea datelor prin intermediul vederilor. Aceasta este posibila numai daca vederile provin dintr-o singura relatie, printr-o operatie de selectare sau proiectie. Este interesant de notat ca vederile derivate prin operatii de join pot fi totusi actualizate daca ele contin cheile relatiilor de baza.
Vizualizari in SGBD-uri distribuite
Definitia unei vizualizari in SGBD-urile distribuite este similara cu cea din mediile centralizate. In mediile distribuite insa, o vedere poate fi derivata din relatii fragmentate, stocate in locatii diferite. Cand este creata o vizualizare, numele sau si interogarea sunt stocate in catalog.
Deoarece vizualizarile pot fi utilizate ca relatii de baza de aplicatii, definitiile lor ar trebui stocate in director, la fel ca descrierile relatiilor de baza. Tinand cont de gradul de autonomie oferite de sistem la fiecare locatie, definitiile vederilor pot fi centralizate la un singur site, partial duplicate, sau total duplicate. In oricare din cazuri, informatia care asociaza numele unei vederi cu site-ul unde e definita trebuie duplicata. Daca definitia vederii nu este prezenta la locatia unde este efectuata interogarea, este necesar accesul de la distanta la definitia vizualizarii.
In capitolul precedent au fost prezentate alternative de fragmentare ale relatiilor de baza. Definitia fragmentelor este, de fapt, foarte similara cu definitia vederilor. In [Adiba, 1981] este propus un mecanism unificat pentru a gestiona atat vederile cat si fragmentele. Acesta este bazat pe observatia ca vizualizarile intr-un SGBD distribuit sunt definite cu reguli similare cu cele de definire a fragmentelor. Deasmenea, datele replicate pot fi manipulate in acelasi mod. Importanta unui astfel de sistem tine facilitarea administrarii unei baze de date distribuite. Obiectele manipulate de administratorul bazei de date pot fi ordonate intr-o ierarhie in care frunzele sunt fragmente din care pot fi derivate vizualizari si relatii.
Evaluarea vizualizarilor derivate din relatii distribuite poate fi costisitoare. Deoarece intr-o organizatie este foarte probabil ca multi utilizatori sa acceseze aceeasi vedere, s-au facut anumite propuneri pentru optimizarea derivarii vederilor. O astfel de propunere este folosirea unor “poze” (snapshots) ale vizualizarilor. O astfel de poza reprezinta o stare particulara a bazei de date si este deci “statica”, adica nu reflecta actualizarile relatiilor de baza. Ele sunt folositoare atunci cand utilizatorii nu sunt interesati sa vada cea mai recenta versiune a bazei de date. Ele sunt gestionate ca niste relatii temporare, in sensul ca nu au alte metode de acces decat scanarea secventiala. Asadar, o interogare pe o poza nu va utliliza indescii existenti pe relatia de baza din care poza a fost derivata. Accesul prin poze este recomandat pentru interogarile care au o selectivitate slaba si care scaneaza intreaga poza. In acest caz, poza se comporta ca un raspuns predefinit al interogarii. Este necesara calcularea periodica a pozelor. Aceasta se poate face insa cand sistemul este inactiv. Deasemenea, in cazul pozelor derivate din operatii de selectare sau proiectie, numai diferenta trebuie calculata.
Securitatea datelor
Securiatea datelor este o functie importanta a unui sistem de baze de date, care protejeaza datele impotriva accesului neautorizat. Securitatea datelor are doua componente: protejarea datelor si controlul accesului autorizat.
Protejarea datelor este necesara pentru a nu permite utilizatorilor neautorizati sa inteleaga continutul fizic al datelor. Aceasta functie este oferita, de obicei, de sistemele de operare, centralizate sau distribuite. Principala abordare a protejarii datelor este criptarea lor, lucru util atat in cazul in care informatia este stocata pe disc, cat si cand informatia este transmisa intr-o retea. Datele criptate pot fi decriptate numai de utilizatorii autorizati, care “stiu” codul.
Controlul accesului autorizat trebuie sa se asigure ca numai utilizatorii autorizati efectueaza operatii care le sunt permise asupra bazei de date. Multi utilizatori diferiti pot avea acces la un volum larg de date sub controlul unui singur sistem centralizat sau distribuit. SGBD-ul, centralizat sau distribuit, trebuie sa fie capabil sa restrictioneze accesul unei parti din utilizatori la o parte din date. Controlul accesului autorizat a fost oferit mult timp de catre sistemul de operare, si mai de curand de sisteme de operare distribuite, ca serviciu al sistemului de fisiere. In acest context, este oferit un control centralizat.
Controlul accesului autorizat in sistemele de baze de date difera in anumite privinte de cel din sistemele traditionale de fisiere. Autorizarile trebuie sa ofere unor utilizatori diferiti drepturi diferite pe aceleasi obiecte ale bazei de date. Aceasta necesitate implica specificarea obiectelor mai precis decat dupa nume si diferentierea intre grupurile de utilizatori. Deasemenea, controlul descentralizat al accesului autorizat este important intr-un context distribuit.
Din solutiile pentru controlul autorizat in sistemele centralizate, le putem deduce pe cele din SGBD-uri distribuite. Totusi, exista o complexitate aditionala care provine din faptul ca obiectele si utilizatorii pot fi distribuiti.
4.2.1 Controlul accesului autorizat in sistemele centralizate
Trei actori principali sunt implicati in controlul accesului autorizat: utilizatorii, care declanseaza executia aplicatiilor; operatiile, care sunt incluse in aplicatii; obiectele bazei de date asupra carora se efectueaza operatiile. Controlul accesului autorizat consta in validarea unui triplet: (utilizator, operatie, obiect). O autorizare poate fi vazut ca un triplet (utilizator, tipul operatiei, definitia obiectului) care specifica daca acel utilizator are dreptul de a efectua o operatie de acel tip asurpa obiectului. Pentru a controla autorizarile corect, un SGBD necesita definirea utilizatorilor, a obiectelor si a drepturilor.
Introducerea unui utilizator (o persoana sau un grup de persoane) in sistem se face de obicei printr-o pereche (nume utilizator, parola). Numele utilizatorului identifica in mod unic utilizatorul, in timp ce parola, stiuta numai de acel utilizator, autentifica utilizatorul. Amandoua sunt cerute la conectarea la sistem.
Obiectele care trebuie protejate sunt submultimi ale bazei de date. Intr-un sistem relational obiectele poti fi definite dupa tipul lor (vederi, relatii, tupluri, atribute) cat si dupa continutul lor, folosind predicate de selectie. Deasemenea, mecanismul vizualizarilor permite protejarea obiectelor prin simpla ascundere a unor submultimi ale relatiilor (atribute sau tupluri).
Un drept exprima o relatie intre un utilizator si un obiect pentru un anumit set de operatii. Controlul accesului autorizat poate fi caracterizat prin cine anume acorda drepturile. In cea mai simpla forma a sa, controlul este centralizat: un singur utilizator, sau o clasa de utilizatori, respectiv administratorul bazei de date are toate privilegiile asupra obiectelor. El este singurul care are acces la instructiunile GRANT (acordare) si REVOKE (revocare).
O forma mai flexibila dar mai complexa a controlului este cea descentralizata: creatorul unui obiect devine proprietarul acestuia si are toate privilegiile asupra lui.
Privilegiile utilizatorilor asupra obiectelor sunt memorate in director (dictionarul de date?) ca reguli de autorizare. Aceste autorizari pot fi stocate in mai multe feluri. Cea mai convenabila modalitate este de a considera privilegiile ca elemente ale unei matrici in care liniile sunt utilizatori, coloanele sunt obiecte, iar elementele matricei corespunzatoare unei perechi (utilizator, obiect) sunt operatiile autorizate.
Figura 4.2 Exemplu de matricea autorizarilor
Matricea autorizarilor poate fi stocata in trei moduri: dupa linie, dupa coloana, sau dupa element.
Controlul accesului autorizat in sistemele distribuite
Problemele aditionale care apar intr-un mediu distribuit provin din faptul ca obiectele si utilizatorii sunt distribuiti. Aceste probleme sunt: autentificarea utilizatorilor de la distanta, gestionarea regulilor de autorizare distribuite, ca si manipularea vizualizarilor si grupurilor de utilizatori.
Autentificarea utilizatorilor la distanta este necesara deoarece orice locatie a unui SGBD distribuit poate accepta programe initiate si autorizate la alte locatii, aflate la distanta. Pentru a preveni accesul de la distanta al utilizatorilor neautorizati (de exemplu, dintr-o locatie care nu face parte din SGBD-ul distribuit) este necesara o identificare si autentificare a utilizatorilor la locatia care este accesata. Sunt posibile doua solutii:
Informatia de autentificare (nume utilizator si parola) este replicata la toate locatiile. Programele locale, initiate de la o locatie aflata la distanta trebuie deasemenea sa indice numele utilizatorului si parola.
Toate locatiile din SGBD-ul distribuit se identifica si autentifica ele insesi, intr-un mod similar utilizatorilor. Comunicarea intre locatii este astfel protejata de parola fiecarei locatii. Odata autentificata locatia de unde se initiaza un proces, nu mai este necesara autentificarea utilizatorilor.
Prima solutie este mai costisitoare avand in vedere faptul ca introducerea unui utilizator devine o operatiune distribuita. Avantajul consta in faptul ca utilizatorii pot accesa baza de date distriuita de la orice locatie. A doua solutie este necesara daca informatia utilizatorului nu este replicata. Ea poate fi implementata insa si daca aceasta informatie este replicata. Daca aceste informatii nu sunt replicate, ele trebuie stocate la locatia de unde respectivul utilizator acceseaza sistemul. Ultima solutie se bazeaza pe presupunerea realista ca utilizatorii sunt mai statici, ca ei acceseaza intotdeauna baza de date de la aceeasi locatie.
Vizualizarile pot fi considerate ca fiind obiecte de catre mecanismul de autorizare. Ele sunt de fapt compuse din obiecte. Astfel, acordarea accesului la o vizualizare se traduce in acordarea accesului la obiectele care o compun. Daca definitia vederii si regulile de autorizare a obiectelor sunt replicate aceasta traducere este simpla si poate fi facuta local. Traducerea este mai dificila atunci cand definitia vizualizarii si obiectele care o alcatuiesc sunt stocate separat. In acest caz, traducerea este o operatiune distribuita. Autorizarile acordate pe vedere depind de drepturile de acces catre obiecte pe care cel care a creat vederea le-a acordat.
Gestionarea grupurilor de utilizatori pentru autentificare simplifica administrarea bazelor de date distribuite. Intr-un SGBD distribuit, toti utilizatorii pot fi referiti prin cuvantul public. Si in SGBD-urile exista aceeasi notiune, dar aici exista si un nivel intermediar, care specifica toti utilizatorii de la o anumita locatie. Public este un grup de utilizatori particular. Se pot defini grupuri mai precise prin comanda
DEFINE GROUP <group_id> AS <lista codurilor utilizatorilor>
Gestionarea grupurilor in mediul distribuit implica cateva probleme deoarece membrii unui grup pot fi la locatii diferite si accesul la un obiect poate fi acordat mai multor grupuri care sunt, la randul lor, distribuite. O solutie pentru aceste probleme poate fi replicarea definitiei grupului la fiecare nod care contine un obiect care poate fi accesat de unul din membrii grupului. Aceasta solutie tinde sa micsoreze autonomia locatiei.
In concluzie, replicarea totala a informatiei de autorizare are doua avantaje puternice: controlul accesului autorizat este mult mai simplu si poate fi facut chiar la momentul compilarii. Totusi, costul total al gestionarii catalogului ditribuit poate fi semnificativ.
Controlul semantic al integritatii
O alta problema importanta si dificila pentru un sistem de baze de date este garantarea integritatii bazei de date. O stare a bazei este consistenta daca baza satisface o serie de constrangeri, numite constrangeri semantice de integritate. Mentinerea unei baze de date consistente necesita diferite mecanisme, cum ar fi controlul concurentei, protectia, controlul semantic al integritatii.
In general, constrangerile semantice de integritate sunt reguli care reprezinta “cunoasterea” unor proprietati ale unei aplicatii. Pot fi diferentiate doua astfel de constrangeri: constrangeri structurale, cum ar fi constrangerea de cheie primara in modelul relational si constrangeri de comportare, care reglementeaza comportarea aplicatiei.
4.3.1. Controlul semantic al integritatii in sistemele centralizate
Constrangerile de integritate trebuie manipulate de administratorul bazei de date prin intermediul unui limbaj de nivel inalt. Este prezentat in cele ce urmeaza un astfel de limbaj, care permite specificarea, citirea sau stergerea unei constrangeri de integritate. Aceste constrangeri pot fi definite la crearea relatiei, sau la orice alt moment, chiar daca relatia contine deja tupluri. In ambele cazuri, sintaxa este asemanatoare.
Sunt prezentate in continuare exemple de constrangeri definite pe urmatoarea baza de date:
CLIENT (LOGIN, NUME, VARSTA, ORAS)
COMANDA(COMANDA_ID, CLIENT_ID, PRET_TOTAL)
PRODUS(PRODUS_ID, NUME, PRET)
Constrangerile predefinite sunt bazate pe cuvinte cheie. Prin intermediul lor este posibila exprimarea concisa a celor mai comune constrangeri ale modelului relational, cum ar fi nonnull, unique, foreign key sau functional dependency.
Exemplul 4.3 Nonnull Attribute
Codul clientului in CLIENT nu poate fi null
CLIENT_ID NOT NULL IN CLIENT
Exemplul 4.4 Unique Key
Perechea (CLIENT_ID, COMANDA_ID) este cheie unica in COMANDA
(CLIENT_ID, COMANDA_ID) UNIQUE IN COMANDA
Exemplul 4.5 Foreign Key
Codul clientului CLIENT_ID in relatia COMANDA este cheie straina (foreign key) corespunzatoare cheii primare CLIENT_ID in relatia CLIENT. Cu alte cuvinte, un client referit in relatia COMANDA trebuie sa exista in relatia CLIENT.
CLIENT_ID IN COMANDA REFERENCES CLEINT_ID IN CLIENT
Exemplul 4.6 Functional Dependency
Codul clientului determina functional numele clientului
CLIENT_ID IN CLIENT DETERMINES NUME
Constrangerile precompilate exprima conditii care trebuie respectate de toate tuplurile dintr-o relatie pentru o actualizare de un anumit tip. Tipul actulizarii poate fi INSERT, DELETE sau MODIFY. Pentru a permite identificarea tuplurilor care sunt subiectul actualizarii sunt definite implicit doua variabile NEW si OLD. Constrangerile precompilate pot fi exprimate cu instructiunea SQL CHECK, la care se adauga tipul actualizarii. Sintaxa acestei instructiuni este:
CHECK ON <numele relatiei> WHEN <tipul actualizarii>
( <conditie> )
Cateva exemple de constrageri precompilate sunt prezentate in continuare:
Exemplul 4.7 Domain Constraint
Pretul unui produs este intre 500 si 10.000.000
CHECK ON PRODUS (PRET 500 AND PRET 10000000)
Exemplul 4.8 Domain Constraint on Deletion
Doar produsele cu pretul 0 pot fi sterse
CHECK ON PRODUS WHEN DELETE (PRET = 0)
Exemplul 4.9 Transition Constraint
Pretul unui produs poate numai sa creasca
CHECK ON PRODUS (NEW.PRET > OLD.PRET
AND NEW.PRODUS_ID = OLD.PRODUS_ID)
Constrangerile generale sunt formule de calcul relational incare toate variabilele sunt cuantificate. Sistemul trebuie sa se asigure ca aceste formule sunt intotdeauna adevarate. Constrangerile generale sunt mai concise decat cele precompilate. O astfel de constrangere poate fi exprimata prin urmatoarea sintaxa:
CHECK ON lista de <nume variabila>:<nume relatie>( <conditie> )
Sunt prezentate in continuare doua exemple de constrangeri generale:
Exemplul 4.10 Functional Dependency
Constrangerea din Exemplul 4.6 poate fi exprimata si astfel:
CHECK ON c1:CLIENT, c2:CLIENT
(c1.NUME = c2.NUME IF c1.CLIENT_ID = c2.CLIENT_ID)
Exemplul 4.11 Constraint with Aggregate Function
Suma totala a comenzilor efectuate de clientul “Ionescu” este mai mica 20.000.000
CHECK ON cl:CLIENT, co:COMANDA (SUM(co.PRET_TOTAL
WHERE cl.CLIENT_ID = co.CLIENT_ID) < 20000000 IF cl.NUME = ‘IONESCU’ )
Intarirea integritatii
Intarirea integritatii consta in refuzarea unor programe de actualizare care violeaza unele constrangeri de integritate. O constrangere este violata cand ea devine falsa in noua stare a baze de date, obtinuta in urma actualizarii. O dificultate majora in modelarea unui subsistem de mentinere a integritatii este gasirea unor algoritmi eficienti de intarirea integritatii. Doua metode de baza permit anularea actualizarilor inconsistente. Prima se bazeaza pe detectarea inconsistentelor. Actualizarea u este executata, cauzand o schimbarea in starea bazei de date de la D la Du. Algoritmul de intarire verifica, prin aplicarea unor teste bazate pe aceste constrangeri, ca toate constrangerile relevante sunt validate in starea Du. Daca starea Du este inconsistenta, SGBD-ul poate sa incerce atingerea unei stari consistente Du’, prin modificarea lui Du, sau sa aduca baza de date in starea initiala, D. Deoarece aceste teste se fac dupa ce se schimba starea bazei de date, ele se numesc postteste.
A doua metoda este bazata pe prevenirea inconsistentelor. O actualizare este efectuata numai daca schimba starea bazei de date intr-o stare consistenta. Tuplurile actualizate sunt disponibile direct (in cazul inserarii) sau trebuie extrase din baza de date (in cazul stergerii sau modificarii). Algortimul de intarire verifica mentinerea tuturor constrangerilor dupa actualizarea acelor tupluri. Acest lucru se face, de obicei, prin testarea acelor tupluri cu niste teste deriate din constrangerile de integritate. Acestea sunt preteste.
Algoritmul de modificare al cererilor [Stonebracker, 1975] este un exemplu de metoda preventiva, care este foarte eficienta in intarirea constrngerilor de domeniu. Acesta adauga conditiile unei constrangeri la conditiile interogarii cu un operator AND (SI), astfel incat cererea modificata intareste integritatea.
Exemplul 4.12
Cererea de crestere a pretului produsului cu codul 300 cu 10% care ar fi specificata astfel
UPDATE PRODUS
SET PRET = PRET * 1.1
WHERE PRODUS_ID = 300
va fi modificata in urmatoarea cerere care va intari constrangerea de domeniu discutata in Exemplul 4.7 :
UPDATE PRODUS
SET PRET = PRET * 1.1
WHERE PRODUS_ID = 300
AND NEW.PRET 500
AND NEW.PRET 10000000
Algoritmul modificarii interogarilor, cunoscut pentru eleganta sa, produce teste la rulare prin conjuctia conditiilor constrangerilor cu conditiile de actualizare. Se considera urmatoarea propozitie: , unde F(x) este o expresie in algebra relationala in care x este singura variabila. O actualizare a relatiei R poate fi scrisa unde Q(x) este o expresie in algebra relationala unde x este singura variabila. Atunci, modificarea cererii consta in generarea actualizarii .
4.3.2 Controlul semantic al integritatii in sistemele distribuite
In aceasta sectiune sunt prezentati algoritmi pentru asigurarea integritatii bazelor de date distribuite. In cele ce urmeaza, se presupune existenta autonomiei locatiilor. Adica fiecare nod proceseaza interogarile locale si efectueaza controlul datelor ca un SGBD centralizat. Principalele dificultati in modelarea unui subsistem responsabil cu integritatea in SGBD-uri distribuite sunt definirea si stocarea conditiilor constrangerilor si intarirea acestor conditii.
Definirea conditiilor de integritate distribuite
O conditie de integritate este exprimata in relatii de algebra relationala intre tupluri. Fiecare conditie este vazuta ca o conditie a unei interogari, care este adevarata sau falsa pentru fiecare tuplu din produsul cartezian al relatiilor. Cum aceste conditii pot implica date stocate la diferite locatii, stocarea lor trebuie decisa astfel incat sa minimizeze costul verificarii integritatii. Se disting trei clase de conditii:
Conditii individuale: pe o singura relatie, pe o singura variabila. Refera numai tuplurile care vor fi actualizate independent de restul bazei de date. Exemplul 4.7 reprezinta o astfel de conditie
Conditii orientate pe multimi: constrangeri pe o singura relatie, bazate pe mai multe variabile, Exemplul 4.6. Deasemenea si constrangeri pe mai multe relatii, bazate pe mai multe variabile, in Exemplul 4.5, constrangerea de cheie straina.
Conditii cu agregate: necesita procesare speciala datorita costului evaluarii agregatelor. Propozitia din Exemplul 4.11 este reprezentativa pentru aceasta clasa.
Principala problema in controlul integritatii in mediul distribuit o reprezinta costul comunicarii si procesarii intaririi unor conditii de constrangeri distribuite. Principalele teme ale modelarii unui subsistem de integritate desitribuit sunt definirea propozitiilor conditionale distribuite si algoritmii de intarire, care micsoreaza costul verificarii integritatii. O mai buna performanta a intaririi integritatii distribuite poate fi obtinuta daca fragmentele sunt definite cu atentie. Specificarea constrangerilor distribuite de integriatate este, asadar, o parte importanta in modelarea bazelor de date distribuite.
Controlul semantic al datelor include gestiunea vizualizarilor, controlul securitatii si controlul semantic al integritatii. In modelul relational, aceste functii pot fi obritnute prin reguli de intarire care specifica controlul manipularii datelor. Exista solutii bine cunoscute pentru controlul acestor functii in sistemele centralizate. Totusi, putine solutii exista pentru sistemele distribuite. Motivul principal este costul controlului semantic al integritatii in sistemele centralizate, care poate fi semnificativ in sistemele distribuite. Principalele teme ale efectuarii controlului datelor eficient sunt definirea si stocarea regulilor si modelarea unor algoritmi de intarire care minimizeaza costul comunicarii. Problema este una dificila deoarece functionalitatea marita tinda se creasca costul comunicarii intre locatii. Solutiile pentru controlul distribuit al datelor sunt extensii ale solutiilor pentru mediul centralizat. Problema este simplificata daca regulile de control sunt replicate in toate locatiile si mai dificila daca autonomia locatiilor este pastrata. Specificarea controlului datelor distribuite trebuie inclusa in procesul de modelare a bazelor de date distribuite pentru a fi luat in cosiderare costul controlului pentru programe de actualizare.
Copyright Notice
© Licențiada.org respectă drepturile de proprietate intelectuală și așteaptă ca toți utilizatorii să facă același lucru. Dacă consideri că un conținut de pe site încalcă drepturile tale de autor, te rugăm să trimiți o notificare DMCA.
Acest articol: Proiectarea Bazelor de Date Distribuite (ID: 149152)
Dacă considerați că acest conținut vă încalcă drepturile de autor, vă rugăm să depuneți o cerere pe pagina noastră Copyright Takedown.