Baze de Date Statistice

ASPECTE TEORETICE RELATIV LA ORGANIZAREA ȘI PRELUCRAREA INFORMAȚIILOR

C A P I T O L U L I

I. Organizarea logică a datelor.

1.1 Informații, date, tipuri de date.

Informația, este, alături de materie și energie, o noțiune de largă generalizare filozofică și reprezintă reflectarea în conștiința noastră a legăturilor cauză-efect din lumea reală înconjurătoare.

Pentru utilizarea corectă a noțiunii de informație trebuie scoasă în evidență distincția între fenomenele lumii reale, informațiile despre aceste fenomene și reprezentarea ca date a informațiilor corespunzătoare.

Informația este un mesaj cu caracter de noutate despre evenimentele care au avut, au sau vor avea loc în interiorul sau exteriorul sistemului natural sau social. Prin urmare, informația definește elementele noi pe care le conține semnificația unui simbol sau grup de simboluri (mesaje verbale sau scrise, semnale de natură tehnică, economică, etc.) cu ajutorul cărora se comunică date referitoare la anumite evenimente, stări sau acțiuni ale sistemului considerat. Presupunând că pentru un sistem oarecare există o mulțime de stări posibile la fel de probabile, lucru care generează o nedeterminare a stărilor, primirea informației despre una sau mai multe stări, dar nu despre toate, face ca nedeterminarea să fie înlăturată într-o oarecare măsură.

Măsura care caracterizează înlăturarea nedeterminării se numește cantitatea de informații, iar măsura cantității de informații se exprimă prin categoria de entropie, definită prin relația:

H(A) = H(p1, p2, …….., pn)

(1)

unde: p1, p2, …….., pn reprezintă probabilitățile rezultatelor

a1, a2, ……….., an în care se concretizează experimentul A.

Expresia matematică a lui H a fost dată pentru prima dată în anul 1448 de C.E. Shannon, astfel:

H(p1, p2, …….., pn) = -∑ pkxlogbpk (2)

Dacă baza logaritmului, b, se alege egală cu 2 înseamnă că avem de-a face cu un experiment ce conține două evenimente echiprobabile (p1 = p2 = ½ ). In acest caz, unitatea de măsură a nedeterminării se numește unitate diadică, binară sau bit (cifră binară = binary digit).

In țara noastră, academicianul Octav Onicescu a observat că pentru scopurile pur statistice se poate păstra ca informație probabilitatea însăși și nu logaritmul ei. Cu alte cuvinte, se poate considera ca informație medie expresia (3) numită și energie informațională, pe baza căreia a fost creată o disciplină nouă, anume statistica informațională.

E =

Informația este caracterizată, în general, de următoarele trei niveluri: sintactic, semantic și pragmatic.

Nivelul sintactic se referă la sistemul de semne și la regulile de reunire a acestora în construcții sintactice utilizate pentru prezentarea informațiilor în procesul culegerii, transmiterii și prelucrării acestora. Acestui nivel îi corespunde conceptul de dată, concept central în informatică, exprimat prin formulă BNF (Backus – Naur Form) astfel:

<data> : : = <identificator> <atribute> <valoare>

(entitate)

Cu alte cuvinte o informație este o triadă a elementelor: entitate, atribut, valoare. Entitatea formează obiectul informației. Atributul (sau caracteristica) este elementul de descriere a entității respective, caracterul sau o proprietate a acesteia. Valoarea este o măsură a proprietății sau atributului asociat. De exemplu, informația despre rezultatului unui concurs se poate reprezenta astfel: entitatea “concurent”, atributul “rezultate”, iar valoarea “admis”.

O entitate se caracterizează de obicei prin mai multe proprietăți, având astfel asociate mai multe atribute și valorile lor. Se impune, cu necesitate, caracterizarea completă a entității, prin toate atributele sale. De exemplu, entitatea “concurent” nu poate să nu aibă atributul “nume – concurent”; sau dacă pentru entitatea “drapele naționale” s-ar preciza numai atributul “ culoare”, ar fi incomplet definit, știind că mai multe drapele au aceleași culori, ar trebui să adăugăm atributul “model”.

Datele constituie materializarea, reprezentarea simbolică a informațiilor (prin semne, litere, cifre) într-o formă convențională (scrisă, vorbită, luminoasă, semne grafice, desene), convenabilă unei comunicări.

Apare astfel clară distincția între informație și dată , ca deosebire dintre obiect și modelul său.

Finalitatea procesului de informare presupune trecerea de la structură la sens, adică de la nivelul sintactic la cel semantic.

Sub aspect semantic, informația poate fi caracterizată ca semnificație a datelor. Sensul informației la nivel semantic este corespondența dintre o dată, pe de o parte, și obiectul real sau situația pe care o reprezintă, pe de altă parte.

Nivelul cel mai concret de considerarea a informației este însă cel pragmatic, singurul care raportează informația la scopurile observatorului.

Prin tipul unei date se precizează mulțimea valorilor pe care le poate lua data și operațiile care se pot efectua asupra ei. Este o caracteristică a fiecărui limbaj de prelucrare a datelor, dar în general datele pot fi de: tipuri simple sau nestructurate: numerice, caracter, logice sau de tipuri structurate: statice (tablouri, articol, mulțime, fișiere), sau dinamice (liste, arbori).

1.2 Structuri de date

De cele mai multe ori, în aplicații, datele se reprezintă sub forma unor mulțimi sau colecții, iar prelucrarea lor nu poate fi concepută fără o organizare corespunzătoare.

O colecție de date pe care s-a definit o structură ( adică un anumit mod de ordonare pentru a facilita prelucrarea datelor), căreia îi este specific un anumit mecanism de selecție și identificare a componentelor, constituie o STRUCTURA DE DATE.

Structura de date poate fi creată pentru memoria internă sau pentru un suport extern. Există structuri interne (pentru date temporare) sau structuri externe (fișiere, baze de date) pentru datele cu caracter permanent sau de mai lungă durată.

*** Considerații privind definirea structurilor de date:

Definirea structurilor de date necesare într-o aplicație este o activitate complexă care condiționează în mare măsură eficiența prelucrării. Pentru realizarea ei trebuie să se țină seama de o serie de factori:

Volumul datelor;

Operațiile de prelucrare și frecvența lor;

Indicele de activitate se definește ca raport între numerele de componente ale structurii utilizate într-o operație și număr de componente explorate pentru această operație;

Durata de viața a structurii;

Utilizarea rațională a spațiului de memorie (comprimare, blocare, segmentare);

Complexitatea programării;

Asigurarea integrității datelor (alegerea structurii care să permită protecția împotriva distrugerilor accidentale și posibilitatea refacerii datelor)

1.3 Evoluția metodelor și tehnicilor de organizare a datelor

Metodele și tehnicile de organizare a datelor au evoluat în cadrul procesului de perfecționare a sistemelor informatice, fiind determinate de: creșterea continuă a complexității activităților, creșterea ritmului de dezvoltare a societății, evoluția mijloacelor de culegere, transmitere, arhivare și prelucrare a datelor.

Prima etapă a fost organizarea datelor în “fișiere de aplicații” când proiectanții de aplicații informatice gestionau fișierele secvențiale, indexate, selective etc., într-un mod izolat, în vederea rezolvării problemelor particulare ale unui compartiment (contabilitate, personal-salarizare, producție etc.)

A doua etapă se caracterizează prin separarea nivelului logic față de nivelul fizic de organizare a datelor, cu păstrarea însă a tendinței de proiectare a colecțiilor de date pentru deservirea optimă a unei singure aplicații. Se utilizează fișiere organizate indexat sau aleator, regimul de lucru conversațional, timp real.

Cerințele complexe impuse sistemelor informatice moderne au creat necesitatea ca mai mulți utilizatori să aibă acces la aceeași colecție de date care să satisfacă în mod optim cerințele de prelucrare specifice fiecărui utilizator. Utilizarea metodelor clasice cu fișiere duce și la o creștere a redundanței datelor și la o creștere a timpului de răspuns. In aceste condiții a apărut ca necesară cerința de integrare a datelor: fișiere integrate sau sisteme de fișiere (etapa a III-a).

Trecerea la fișiere integrate nu a rezolvat problema independenței programelor de aplicații de modul de organizare a datelor. Soluția a fost detașarea din programul de aplicații a descrierii fișierelor și a legăturilor dintre ele. Se ajunge astfel la primele bănci de date (etapa a IV-a care marchează un salt calitativ în organizarea datelor). O BANCA DE DATE (BD) este formată din:

O BAZA DE DATE: colecție voluminoasă de date aflate în interdependență, împreună cu descrierea lor ;

Un SISTEM DE GESTIUNE A BAZEI DE DATE (SGBD), respectiv un set de programe și proceduri specializate, destinate gestiunii și prelucrării complexe a datelor din baza de date;

Un SET DE PROCEDURI MANUALE și AUTOMATE specifice domeniului pentru care se organizează baza de date, precum și reglementări administrative destinate bunei funcționări a întregului sistem.

În etapa ulterioară, preocuparea principală a constat în a degaja pe utilizator de sarcina de a cunoaște întreaga structură a bazei de date.

1.4 Organizarea datelor în baze de date

1.4.1 Definiție

Termenul de bază de date are mai multe definiții posibile:

Bază de date este un ansamblu de date, interconectate, împreună cu descrierea lor, care răspunde calităților de centralizare, coordonare, integrare și difuzie a informațiilor și care asigură satisfacerea tuturor necesităților de prelucrare ale tuturor utilizatorilor din sistem.

Baza de date este o colecție de date operaționale utilizate de sistemul de aplicații al unei instituții [Engles, Date] “Instituție” estre un termen generic prin care se poate înțelege o întreprindere, o bancă, spital, universitate, minister etc. Datele operaționale sunt acele informații care au o anumită stabilitate, importantă în sistemul informațional al instituției.

O bază de date este o colecție structurată de date împreună cu descrierea lor, necesare și suficiente unei anumite liste de decizii.

Oricare ar fi definiția, reținem că baza de date este o colecție de date creată pentru a satisface nu un utilizator oarecare ci pe mai mulți, asigurând redundanță minimă, o independență a programelor fața de date, o optimizare a structurilor fizice care vor fi ignorate cu totul de utilizatori, o protecție a datelor memorate.

1.4.2 Terminologie

Arhitectura bazelor de date evidențiază componentele acestora, care sunt:

baza de date propriu-zisă în care se memorează datele;

sistemul de gestiune a bazei de date, care realizează gestiunea și prelucrarea complexă a datelor;

un dicționar al bazei de date (metabaza de date), ce conține informații despre date, despre structura acestora, statistici, documentație;

mijloacele hard utilizate (comune sau specializate);

reglementări administrative destinate bunei funcționări a întregului sistem

personalul implicit (utilizatori finali, administrator, programatori, utilizatori).

In funcție de modul de exploatare a bazelor de date, utilizatorii pot fi împărțiți în următoarele clase:

Utilizatorii obișnuiți, care pot să obțină informații fără să aibă cunoștințe de programare. Ei obțin informațiile dorite prin comenzi cunoscute și, eventual, răspunzând la diferitele opțiuni pe care le indică sistemul de calcul la un moment date.

Programatorii de aplicații, care pot scrie programe în LC, acestea fiind apoi compilate și memorate în fișiere, putând fi lansate în execuție de utilizatori prin invocarea numelui asociat lor.

Administratorul bazei de date, care stabilește structura inițială a bazei de date și modul de memorare a datelor la nivel fizic, acordă utilizatorilor drepturi de acces la baza de date sau părți ale ei, stabilește condițiile pentru asigurarea securității, integrității datelor, modifică structura bazei de date dacă este nevoie, asigură întreținerea bazei de date făcând ă obțină informații fără să aibă cunoștințe de programare. Ei obțin informațiile dorite prin comenzi cunoscute și, eventual, răspunzând la diferitele opțiuni pe care le indică sistemul de calcul la un moment date.

Programatorii de aplicații, care pot scrie programe în LC, acestea fiind apoi compilate și memorate în fișiere, putând fi lansate în execuție de utilizatori prin invocarea numelui asociat lor.

Administratorul bazei de date, care stabilește structura inițială a bazei de date și modul de memorare a datelor la nivel fizic, acordă utilizatorilor drepturi de acces la baza de date sau părți ale ei, stabilește condițiile pentru asigurarea securității, integrității datelor, modifică structura bazei de date dacă este nevoie, asigură întreținerea bazei de date făcând periodic copii și reconstituind eventual baza de date în cazul în care au apărut erori datorate componentelor soft, hard sau utilizării și răspunde, în general, de modul de utilizare al bazei de date.

Administratorul sistemului de baze de date, care stabilește bazele de date pe un sistem de calcul alocă spații de memorare și asigură drepturi de acces.

1.4.3 Niveluri de organizare a datelor în baze de date

Spre deosebire de sistemele clasice de organizare a datelor, în care se disting două niveluri de organizare (logic și fizic), la bazele de date se definește și un al treilea nivel: nivelul virtual.

Structura virtuală sau conceptuală a unei baze de date se referă la datele necesare tuturor utilizatorilor unei baze de date, în condiții de redundanță minimă și controlată a datelor.

Descrierea acestui nivel (ansamblu de date, legături, proprietăți) se face printr-un limbaj de descriere a bazei de date și poartă numele de SCHEMA CONCEPTUALA. Schema este unică, se memorează pe suportul fizic și este “invocată” la fiecare solicitare a unui subset de date de către un program de aplicație. Ea este realizată de administratorul baze de date.

Schema conceptuală descrie informațiile stocate în baza de date “ așa cum sunt ele de fapt”, deci prin semnificația lor reală: putem spune că modelul conceptual este un model al lumii reale restrâns la un subdomeniu de interes specific (în speță la activitatea unei instituții, în sensul generic al termenului).

Structura logică a datelor se referă la forma în care fiecare utilizator vede datele în funcție de aplicația căreia încearcă să-I găsească rezolvare. Descrierea structurii logice a datelor se numește SUBSCHEMA și este un subset de date necesar unui program.

Relativ la o SCHEMA pot fi concepute mai multe SUBSCHEME (dar un program de aplicații va apela o singură subschemă). Este nivelul extern al organizării datelor

Structura fizică se referă la modul de memorare a datelor pe suportul magnetic. Sistemul de stocare al datelor pe disc trebuie să fie eficient atât din punct de vedere al spațiului cât și din punct de vedere al timpului de acces. Acest lucru se referă la conținutul datelor așa apar ele reprezentate pe suport. Este nivelul intern al reprezentării datelor

Niveluri de organizare a datelor

Ce se întâmplă când utilizatorul emite o cerere de interogare?

Un set de rutine specializate determină modelul logic de date sau modelul exterior invocat de programul de aplicații. Un alt set de rutine efectuează apoi “proiecția”în modelul conceptual, determinând care sunt articolele conceptuale din care trebuie completat articolul logic.

Intr-o fază de date sunt necesare trei nivele de independență a datelor:

Independența fizică asigură posibilitatea modificării schemei fizice a datelor fără ca aceasta să oblige la modificarea schemei conceptuale, schemei logice și a programelor de aplicație.

Independența logică asigură posibilitatea modificării schemei conceptuale a datelor fără ca aceasta să oblige la modificarea schemei logice și a programelor de aplicație.

Independența față de strategiile de acces permite programului să precizeze data pe care dorește să o acceseze, dar nu modul cum accesează această dată. SGBD va stabili drumul optim de acces la date.

Cerințele care se impun unei baze de date :

să furnizeze în timp util informațiile solicitate (timp de răspuns la o interogare);

să asigure costuri minime de prelucrare și întreținere, redundanța minimă;

să aibă capacitatea de a satisface cu aceleași date, necesități informaționale ale unui număr mare de utilizatori, să permit adaptarea la cerințe noi, răspunsuri la interogări neprevăzute inițial (flexibilitate);

să permită exploatarea simultană a datelor de către mai mulți utilizatori (sincronizare);

să asigure securitatea datelor prin mecanisme de protecție împotriva accesului neautorizat (confidențialitate;

să conțină facilități destinate validării datelor și recuperării lor în cazul unor deteriorări accidentale (integritate);

să permită valorificarea eforturilor anterioare și anticiparea nevoilor viitoare (compatibilitate și expandabilitate);

să permită, prin ierarhizarea datelor după criteriul frecvenței acceselor, reorganizări (eventual dinamice) care sporesc performanțele bazei de date .

1.4.4 Limbaje pentru baze de date

In lumea bazelor de date, funcțiile de declarare și de manipulare a datelor sunt realizate cu ajutorul unor limbaje diferite:

limbaje pentru definirea datelor (LDD);

limbaje pentru manipularea datelor (LMD);

Limbaje pentru controlul datelor (LCD)

Limbaje universale

** Sistemul de programe care permite construirea unor baze de date, introducerea informațiilor în bazele de date, și dezvoltarea de aplicații privind bazele da date se numește sistem de gestiune a bazelor de date (SGBD). Funcția centrală a acestuia este de a permite utilizatorului să acceseze date dintr-o bază de date folosind un limbaj de nivel înalt, apropiat de modul obișnuit de exprimare, pentru a obține informații, utilizatorul făcând abstracție de algoritmii aplicați pentru selecționarea datelor implicate și a modului de memorare a lor. SGBD-ul este o interfață între utilizatori și sistemul de operare. Aceste sisteme informatice (software) specializate în stocarea și prelucrarea unui volum mare de date, volumul de prelucrări implicat fiind relativ mic (spre deosebire de programele orientate spre rezolvarea problemelor matematice, de exemplu, care necesită un volum mai mare de prelucrări asupra unui volum relativ mic de date).

* Cele mai multe SGBD-uri conțin și o colecție de utilitare folosite în diferitele aplicații, cum sunt: procesoare pentru limbaje de cereri, editoare de rapoarte, subsistemul de reprezentări grafice, posibilități de lucru tabelar, procesoare de limbaje naturale, programe statistice, posibilități de copiere, generatoare de aplicații (procesoare inteligente de tip “4GL”) și alte posibilități de dezvoltare a unor aplicații de tip CASE (computer-aided software engineering).

Pentru a ușura munca administratorului de sistem, SGBD conține o serie de componente ce permit încărcarea (crearea unei versiuni inițiale a bazei de date plecând de la unul sau mai multe fișiere), salvarea și reîncărcarea (efectuarea de copii periodice și posibilitatea refacerii bazei de date), reorganizare (pentru a obține performanțe superioare), statistici, analize etc.

1.5 Obiectivele sistemelor de gestionare a bazelor de date .

independența fizică;

independența logică;

manipularea datelor de către neinformaticieni;

eficacitatea accesului la date;

administrarea centralizată a datelor;

neredundanța datelor;

partajabilitatea datelor.

Securitatea și confidențialitatea datelor: datele trebuie protejate de un acces neautorizat sau rău intenționat.

Există mecanisme care permit identificarea și autentificarea utilizatorilor și există proceduri de acces autorizat care depind de date și de utilizator.

SGBD trebuie să asigure securitatea fizică și logică a informației și să garanteze că doar utilizatorii autorizați pot efectua operații corecte asupra bazei de date. Această funcție complexă presupune trei elemente fundamentale:

gestiune autorizațiilor;

controlul validității operațiilor;

protecția datelor împotriva accesului neautorizat (parolă, criptare) și în cazul defecțiunilor.

De exemplu: operațiile de modificare efectuate asupra datelor sunt salvate în jurnalul tranzacțiilor. Dacă există pană (fizică), utilizând baza de date în forma actuală și jurnalul tranzacțiilor, baza poate să fie reconstituită așa cum era înaintea avariei.

1.6 Componentele unui SGBD

În general un SGBD trebuie să includă cel puțin cinci clase de module:

programe de gestionare a bazei de date (PGBD)

module pentru tratamentul limbajului de definire a datelor;

module pentru tratamentul limbajului de manipulare a datelor

module utilitare, ce permit întreținerea corectă și ușoară a bazei de date.

Lista acestor programe depinde de complexitatea SGBD. Aceste programe pot efectua următoarele operații:

încărcarea bazei de date ;

crearea și reactualizarea jurnalelor tranzacțiilor efectuate asupra bazei de date ;

reorganizarea bazei de date pentru a recupera spațiul vid;

reorganizarea structurii fizice și logice după o modificare;

restabilirea bazei de date după o pană fizică sau logică;

obținerea unor statistici ce permit cunoașterea activității și utilizării bazei;

reactualizarea și modificarea schemei;

realizarea unei copii permanente a bazei pentru motive de securitate;

detectarea violării constrângerilor de integritate.

module de control a datelor.

SGBD gestionează un dicționar de date care este alimentat prin comenzi de definire a schemei (de exemplu: CREATE ENTITY, CREATE INDEX) și prin comenzi de definire a vizualizărilor (de exemplu: CREATE VIEW). Aceste comenzi, precum și cererile de manipulare (de exemplu: APPEND, DELETE, MODIFY)sunt analizate și tratate de un procesor numit analizor.

1.7 Evoluția sistemelor de gestionare a bazelor de date

Un SGBD este un sistem de programe de bază dintr-un sistem informatic de gestiune care intuitiv permite utilizatorilor concurenți să manipuleze (insereze, modifice, caute) eficient date conținute în baza de date .

Istoria SGBD poate fi rezumată în 3 generații:

modele ierarhice și rețea;

modele relaționale;

sisteme avansate: SGBD orientate obiectiv;

SGBD deductive;

SGBD distribuite;

Pentru modelele ierarhice și rețea, datele sunt reprezentate la nivel de articol prin legături ierarhice (arbore)sau de tip graf. Slaba independența fizică a datelor complică administrarea și manipularea acestora.

A II-a generație de SGBD este legată de apariția modelelor relaționale (1970), care tratează entitățile ca niște relații. Piața actuală de baze de date este acoperită în majoritate de sisteme relaționale. Acestea, ca și modelele de prima generație, au fost concepute pentru aplicații clasice: contabilitate, gestiunea stocurilor etc.

Bazele de date relaționale sunt caracterizate de structuri de date simple, intuitive, inexistența pointerilor vizibili pentru utilizator, constrângeri de integritate, o mulțime de operatori aplicații relațiilor care permit definirea, căutarea și reactualizarea datelor.

Bazele de date relaționale oferă avantaje:

independența completă în descrierea logică a datelor (în termen de relații ) și în descrierea fizică a datelor (în termen de fișiere);

un ansamblu integrat de utilizare bazat pe un limbaj de generația a 4-a, și anume generatoare de meniuri, generatoare de aplicații, generatoare de forme, generatoare de etichete etc.

existența unor limbaje speciale de definire și manipulare a datelor.

Bazele de date relaționale nu folosesc însă obiecte complexe și dinamice, nu realizează gestiunea datelor distribuite și nici gestiunea cunoștințelor.

A III-a generație de GBD ce cuprinde sistemele avansate încearcă să depășească aceste limite ale sistemului relațional:

gestiunea obiectelor complexe (baze de date orientate obiect);

gestiunea cunoștințelor (baze de date deductive);

gestiunea datelor distribuite (baze de date distribuite).

1.7.1 Diagrama entitate-relație

O bază de date poate fi definită ca o mulțime de date ce modelează un univers. Acest univers este format din obiecte legate între ele. Obiectele de același tip constituie o entitate, iar legătura între două entități definește o relație (asociere). Entitățile și relațiile au anumite caracteristici (atribute).

Procesul de descriere a entităților și a asocierilor este numit modelare și este realizat cu ajutorul unui model de date. Modelarea unei baze de date permite trecerea de la percepția unor fapte din lumea reală la reprezentarea lor prin date.

Fiecare entitate este descrisă de o mulțime de proprietăți esențiale numite atribute, care pentru diferitele elemente ale entității, pot să primească valori din anumite mulțimi numite domeniul atributului respectiv.

De exemplu, entitatea AUTOMOBILE poate fi descrisă prin atributele: tip-motor, model, nr.-de-portiere, forma-caroseriei etc., dacă sistemul informațional este la o unitate de fabricare a automobilelor. Dacă, însă, entitatea AUTOMOBIL se referă la obiectele supuse vânzării într-o unitate comercială, atunci va trebui să conțină: seria-motorului, firma-producătoare, prețul etc. Domeniile pot fi deci numere întregi, șiruri etc.

Un atribut sau o mulțime de atribute pentru care valorile asociate determină în mod unic orice element al entității respective se numește cheie.

1.7.2 Modelul relațional

Modelul relațional a fost conceput și dezvoltat de E.F.Codd. El este un model formal de organizare conceptuală a datelor, destinat reprezentării legăturilor dintre date, baza pe teoria matematică a relațiilor. Este modelul cel mai accesibil pentru utilizatorul bazei de date deoarece are aceiași structură fizică cu date le care trebuie prelucrate. In general, datele se prezintă sub forma unor tabele (relații) în care liniile constituie entități, iar coloanele sunt atribute ce caracterizează aceste entități.

Spre deosebire de modelul ierarhic și rețea unde apar două elemente , și anume tipul entității și relațiile dintre două entități, modelul relațional este alcătuit numai din relații și prin urmare, orice interogare asupra bazei de date este tot o relație.

De exemplu, în modelul ierarhic entitățile din sistemul informatic școlar al unui oraș pot forma o structură arborescentă:

In modelul rețea avem următoarea reprezentare:

Referitor la partea de manipulare a datelor, modelul relațional este orientat spre mulțimi, în timp ce modelele ierarhic și rețea sunt orientate spre fișiere.

Fie mulțimile M1, M2, …, MN finite și nu neapărat distincte. Se numește produs cartezian al mulțimilor M1, M2,…MN mulțimea tuturor N-tuplelor (x1, x2,…xN) unde x1, x2,…..xN aparțin respectiv mulțimilor M1, M2,……MN o submulțime a produsului cartezian M1x M2x…xMN.

Fie deci relația REL definită peste aceste mulțimi. Se spune despre elementele x1, x2,…..xN că sunt în relația REL dacă N-tuplul (x1, x2,…..xN) aparține lui REL. Numărul N al mulțimilor ce intră în relație se numește gradul relației, iar numărul N-tuplelor ce formează relația se numește cardinalul relației.

Observăm că o entitate este o relație definită peste domeniile atributelor sale, deoarece fiecare realizare a sa aparține produsului cartezian al domeniilor D1, D2, …..Dn. Realizările unei entități sunt de forma (a1, a2,…an) și aparțin produsului D1x D2x ….xDn

Corespondența între termenii generali și cei specifici modelului relațional

Modelul relațional, deși are unele imperfecțiuni, a fost adoptat în ultimul deceniu de majoritatea programatorilor din domeniu, tocmai datorită celor trei calități: este simplu, este riguros din punct de vedere matematic și nu este orientat spre sistemul de calcul.

Definirea unui SGBD relațional impune analizarea caracteristicilor pe care trebuie să le prezinte un model de date pentru a fi considerat relațional.

Există diferite modalități pentru a defini acest concept:

prezentarea datelor în tabele supuse anumitor operații: proiecție, selecție, reuniune, compunere, intersecție (definiție simplă);

un sistem de baze de date ce suportă un limbaj de tip SQL –Structured Query Language (limbaj pentru căutări structurate)- def. Practică;

un sistem de baze de date care respectă principiile modelului relațional introdus de Codd –definiția cea mai frecvent folosită.

1.7.3 Operatorii modelului relațional

Comparativ cu operatorii clasici ai sistemelor de prelucrare automată a datelor (duplicare, conversie, sortare, fuzionare, separare, asociere, scindare, ștergere și actualizare) care au un caracter mult mai sintactic, operatorii relaționali posedă o orientare semantică.

Cercetările în acest domeniu au demonstrat că operatorii relaționali plus sortarea pot răspunde tuturor solicitărilor din domeniul prelucrării automate a datelor. Prin definirea și utilizarea acestor operatori teoria relațiilor permite fundamentarea cercetărilor care se efectuează în domeniul proiectării bazelor de date relaționale și a conceperii limbajelor relaționale.

Modelul relațional oferă două mulțimi de operatori pe relații, și anume: algebra relațională și calculul relațional (orientat pe tupluri sau orientat pe domenii ).

Operatorii realizează următoarele funcții:

SELECT (selecție) – extrage tupluri ce satisfac o condiție specificată;

PROJECT (proiecție) – extrage atributele specificate;

DIFFERENCE (diferență) – elimină tupluri care apar într-o relație, dar nu apar în cealaltă;

PRODUCT (produs cartezian) – generează toate perechile posibile de tupluri, primul element al perechii fiind luat din prima relație, iar cel de-al II-lea element din cealaltă relație;

UNION (reuniune) – reunește două relații;

INTERSECT (intersecție) – extrage tupluri care apar în ambele relații;

DIVISION (diviziune) – extrage valorile atributelor dintr-o relație, care apar în toate valorile atributelor din cealaltă relație;

JOIN (compunere) – extrage tupluri din mai multe relații corelate

*** reuniunea – a două relații: X cu n-tupluri(realizări) și Y cu m-tupluri, are ca rezultat o mulțime Z cu m + n – tupluri.

Exemplu: colecția pentru gestiunea materialelor de cod între 1001 – 2000 reunită cu colecția pentru gestiunea materialelor între 1500 – 2500 are ca rezultat colecția cu toate materialele între 1001 – 2500.

*** intersecția –a două relații X și Y presupune realizarea unei colecții noi Z cu elemente comune celor două colecții inițiale.

Exemplu: colecția de materiale cu coduri între 1001 – 2000 intersectată cu colecția materialelor de cod între 1500 – 2500 are ca rezultat colecția materialelor având coduri între 1500 – 2000.

*** produsul – a două relații X și Y este reprezentat de mulțimea perechilor posibile de realizat prin concatenarea unei realizări x din X cu o proprietate y din Y.

Exemplu: Fie o colecție PERSOANE și o colecție COPIL. Produsul acestora este o nouă colecție unde fiecare persoană are alături copilul ei.

*** diviziunea –realizează operația inversă produsului, adică dintr-o relație de grad m + n obținemdouă relații de grade m respectiv n.

Exemplu: avem colecția PRODUS în care apar numele și prenumele copiilor; operația de diviziune extrage numele de familie separat de numele copiilor.

*** compunerea (joncțiunea)- se aplică asupra a două relații X și Y care au în structura lor o caracteristică comună, permițând obținerea unei noi relații cu o structură mai largă, formată din atributele relațiilor.

Exemplu: pentru o relație “ELEVI” și una “PROIECTE” care au numărul matricol ca legătură se poate obține relația “COMPUNERE”.

*** selecția –aplicată unei relații X cu n-tupluri are ca rezultat o relație Y definită pe aceiași structură de caracteristici dar cu m-tupluri, în funcție de satisfacerea anumitor condiții

Exemplu: relația “ELEVI”, selector “adresa = Iași”.

*** scăderea sau diferența – a două relații este dată de mulțimea n-tuplurilor care aparțin primei relații și nu aparțin celei de-a doua.

Exemplu: pentru aceleași colecții de gestiune a materialelor (prima cu numere de cod între 1001 – 2000, iar a doua între 1500 – 2500 ), a face diferența înseamnă a realiza colecția cu materiale de cod între 1001 – 1499.

*** proiecția – aplicată asupra unei relații X cu n-tupluri are ca rezultat o relație cu structură simplificată Y definită prin eliminarea tuplurilor duplicat.

Exemplu: Pentru relația “ELEVI” aplicăm proiecția “adresa”:

Acum vom exemplifica modul de implementare a acestor operatori pentru manipularea datelor în limbajul SQL. In majoritatea dialectelor SQL, doar doi operatori (UNION, SELECT) sunt expliciți, iar restul sunt derivați. Prezentarea standardului SQL va fi făcută în subcapitolul 1.7.4.

Exemplele au fost introduse aici pentru a marca analogia între transpunerea cererilor în limbaj algebric și implementarea SQL. Exemplele se referă la schemele relaționale:

SALARIAT (cod_salariat, prenume, sex, job_cod, forma_plată, nr._depart)

DEPARTAMENT (cod_departament, nume, nr_clădire),

ATASAT_LA (cod_salariat, nr._proiect, funcția),

PROIECT (nr._proiect, descriere, buget).

Operatorul UNION (reuniune în SQL):

SELECT nume, prenume, sex

FROM salariat

WHERE job_cod = ‘programator’

UNION

SELECT nume, prenume, sex

FROM salariat

WHERE sex = ‘m’

Sunt utilizate diferite notații: X U Y; UNION (X, Y), OR (X, Y), APPEND (X, Y), unde X și Y sunt relațiile introduse mai sus.

Operatorul DIFFERENCE (ștergerea tuplurilor dintr-o relație)

Diferența este o operție binară necomutativă care permite obținerea tuplurilor ce apar numai într-o relație. Sunt utilizate diferite notații: X – Y, DIFFERENCE (X, y), REMOVE (X, Y), MINUS (X, Y).

Operatorul INTERSECT

Sunt utilizate diferite notații: INTERSECT (X, Y), X ∩ Y, AND (X, Y)

Intersecție în SQL:

SELECT cod_salariat

FROM ag

WHERE EXISTS

(SELECT cod_salariat

FROM pl

WHERE pl.cod_salariat = ag.cod _salariat);

Diferență în SQL

SELECT cod_salariat

FROM ag

WHERE NOT EXISTS

(SELECT cod_salariat

FROM pl

WHERE pl.cod_salariat = ag.cod_salariat);

“ag” reprezintă o vizualizare ce conțin informații despre agenții teritoriali, iar “pl” o vizualizare care conține informații despre salariații plătiți “cu_ora”.

Operatorul PROJECT

Proiecție cu dubluri în SQL:

SELECT nume, prenume, sex

FROM salariat

Proiecție fără dubluri în SQL:

SELECT DISTINCT nume, prenume, sex

FROM salariat

Sunt utilizate diferite notații: п A1, A2,…..Am(X),

PROJECT (X, A1, ……,Am), X [A1, ……,Am], unde A1, ……,Am sunt parametrii proiecției relativ la relația X.

Operatorul SELECT

Sunt utilizate diferite notații:

σconditie (X), X[condiție], SELECT (X, condiție),

RESTRICT (X, condiție)

Selecție în SQL:

SELECT *

FROM salariat

WHERE sex = ‘m’

Proiecție și selecție în SQL:

SELECT nume, prenume, job_cod

FROM salariat

WHERE sex = ‘f ’

Operatorul DIVISION

Sunt utilizate diferite notații: DIVIDE (X, Y), DIVISION (X, Y), X ÷ Y

Diviziune în SQL prin care se obțin codurile salariaților atașați tuturor proiectelor pentru care s-a alocat un buget egal cu 1000:

SELECT UNIQUE (cod_salariat)

FROM atașat la sx

WHERE NOT EXISTS

(SELECT *

FROM proiect

WHERE proiect buget = ‘1000’

AND NOT EXISTS

(SELECT *

FROM atașatla

WHERE proiect nr_proiect = atașat _la nr.proiect

AND atașat_la cod.salariat = sx.cod_salariat));

Diviziunea poate fi simulată și cu ajutorul funcției COUNT (funcție pe care o vom defini mai încolo):

SELECT cod_salariat

FROM atașat la

WHERE nr_proiect IN

(SELECT nr_proiect

FROM proiect

WHERE buget = ‘1000’

GROUP BY cod_salariat

HAVING COUNT (nr_proiect) = (SELECT COUNT (*)

FROM proiect

WHERE buget = ‘ 1000’)

Operatorul PRODUCT

Sunt utilizate diferite notații: X x Y, PRODUCT (X, Y), TIMES (X, Y)

Produsul cartezian poate fi exprimat în SQL prin:

SELECT *

FROM salariat, departament;

Operatorul JOIN

Operatorul combină produsul cartezian, selecția și proiecția. In general, se construiește un produs cartezian, se elimină tupluri prin selecție, se elimină atribute prin proiecție.

1.7.4 Limbaje pentru manipularea datelor relaționale

Un limbaj de manipulare a datelor se compune dintr-o mulțime de comenzi care permit interogarea unei baze de date și dintr-o mulțime de comenzi care permit modificarea acesteia. Modificarea bazei de date implică inserare, eliminare și reactualizare. In general, un limbaj de manipulare a datelor este încorporabil într-un limbaj de programare clasic numit limbaj gazdă. Aproape orice SGBD dispune de un limbaj de manipulare extern, conversațion+al și propune o integrare a acestui limbaj într-un limbaj propriu al sistemului.

O relație poate fi definită ca o mulțime sau ca un predicat. Conform dualității definiției unei relații, limbajele de manipulare a datelor relaționale pot fi grupate în limbaje algebrice (SQL, SEQUEL), bazate pe teoria mulțimilor și limbaje predicative (relaționale: QUEL, ALPHA), fondate pe calculul predicatelor.

SQL este unul din limbajele relaționale de cereri care formează nucleul multor sisteme de gestiune a bazelor de date. In mai 1986 a fost recunoscută de ANSI (American National Standards Institute) standardizarea limbajului SQL. Acest limbaj a fost dezvoltat în laboratoarele IBM Research din San Jose, California. Au fost concepute și dezvoltate diferite versiuni ale standardului SQL de către ANSI, IBM, Microsoft, Borland, SAG (SQL ACCES GROUP) ETC.

După cum i-o spune și numele, domeniul în care limbajul SQL este de cel mai mare folos este accesarea bazelor de date pentru a efectua căutări de orice fel. Vocabularul său conține însă comenzi pentru toate necesitățile: creare de tabele, actualizări / modificări / ștergeri, indexări, sortări etc. Unele companii producătoare de SGBD pun la dispoziție pentru manipularea datelor limbajului SQL așa cum este, iar ale companii preferă să-și dezvolte propriul limbaj de programare dar să încorporeze și unele comenzi SQL. Acest lucru vorbește de la sine despre puterea limbajului SQL.

Comenzile SQL sunt diferite de cele ale altor limbaje în primul rând pentru că programatorul comunică parametrii datelor care îl interesează, iar SQL stabilește singur metodele de căutare cele mai bune.

Microsoft FoxPro nu integrează decât patru comenzi SQL: CREATE TABLE și CREATE CURSOR pentru definirea de tabele, INSERT pentru adăugarea de înregistrări într-o tabelă și SELECT pentru efectuarea de căutări într-una sau mai multe tabel.

SQL este un limbaj care permite definirea și modificarea schemei unei baze de date relaționale, interogarea și modificarea (neprocedurală) unei baze de date relaționale, controlul securității și integrității bazei.

Definirea schemei unei baze de date relaționale

Limbajul de definire a datelor include instrucțiuni ce permit crearea schemei bazei de date, adăugarea relațiilor la schema bazei, ștergerea unor relații existente, adăugarea de noi atribute relațiilor existente, optimizarea bazei (index, grup, declanșator), definirea structurii fizice și logice a unei baze de date.

O schemă de baze de date descrie relațiile, atributele relațiilor, domeniul în care aceste atribute iau valori, restricții de integritate, drepturi de utilizare a relațiilor și vizualizărilor, detalii cu privire la implementarea fizică a relațiilor.

Definirea unei scheme cuprinde clauza CREATE SCHEMA, o clauză AUTHORIZATION ce permite identificarea creatorului schemei, atâtea clauze CREATE VIEW corespunzătoare vizualizărilor conținute în schemă și operații de acordare a privilegiilor (GRANT).

Crearea structurii unui tabel de bază se face prin comanda CREATE TABLE. Prin această comandă pot fi specificate anumite constrângeri declarative prin care se exprimă o condiție care trebuie respectată de toate tuplurile uneia sau mai multor relații. Constrângerile pot fi definite și cu ajutorul comenzilor ALTER TABLE, CREATE ASSERTION, CREATE DOMAIN. Constrângerilor le pot fi asociate nume unice.

Comanda fundamentală a standardului SQL care permite interogarea unei baze de date este SELECT. Sintaxa generală a comenzii SELECT este următoarea:

SELECT [ALL | DISTINCT | UNIQUE] listă de selecție

FROM listă de tabele

WHERE condiție de căutare asupra liniilor

GROUP BY listă de atribute care permit partiționarea

HAVING condiție asupra partițiilor

ORDER BY listă de atribute

Clauzele SELECT și FROM sunt obligatorii și specifică datele care se selectează și relațiile din care se selectează. Restul clauzelor sunt opționale și permit rafinarea selecției.

Strategia pentru scrierea comenzii SELECT este dată de următorul algoritm:

se determină tabelele implicate și se include în clauza FROM

se determină atributele ce vor fi vizualizate și se include în clauza SELECT.

Dacă clauza SELECT include “funcții de grupuri”, atunci se introduce clauza GROUP BY și se reiau toate atributele citate în clauza SELECT (fără funcții).

Se determină condițiile care limitează cercetarea. Condițiile care de referă la grup apar în clauza HAVING, iar cele care se referă la valori individuale apar în clauza WHERE.

Dacă este necesară valoarea unui atribut din alt tabel sau este necesară o funcție pe grupuri în clauza WHERE, atunci se utilizează o cerere îmbrăcată.

Dacă este necesară fuzionarea rezultatelor din două clauze SELECT, se utilizează clauza UNION.

Cu ajutorul clauzei ORDER BY se precizează ordinea în care apar tuplurile rezultatului.

Pentru a marca posibilitățile complexe ale comenzii SELECT vom considera câteva cereri concrete implementate în SQL*PLUS.

Schemele relaționale, asupra cărora se vor face următoarele operații, sunt:

CARTE (codel, titlu, autor, preț, nrex, codel)

IMPRUMUTATA (codel, codec, dataim, datares, dataef)

DOMENIU (codel, intdom)

CITITOR (codec, nume, dep)

Descrierea tabelelor corespunzătoare acestor scheme relaționale:

CARTE codul cărții: codel

titlul cărții: titlul

autorul cărții: autor

numărul de exemplare: nrex

prețul unui exemplar: preț

codul domeniului căruia îi aparține cartea: codel

DOMENIU codul domeniului: coded

numele domeniului: intdom

CITITOR codul cititorului: codec

numele cititorului: nume

IMPRUMUTA codul cititorului: codec

codul cărții împrumutate: coded

data împrumutulu : dataim

data la care trebuie restituită cartea: datares

data la care este restituită cartea: dataef

Pentru ficare carte împrumutată se cere codul cărții și numărul de exemplare care nu au fost încă restituite:

SELECT codel, COUNT (*)

FROM împrumută

WHERE dataef IS NULL

GROUP BY coded;

Pentru fiecare domeniu să se specifice numărul de cărți, media prețurilor și numărul total de exemplare:

SELECT codel, COUNT (*), AVG (preț), SUM (nrex)

FROM carte

GROUP BY coded;

Să se afișeze codul domeniului, numărul de cărți și numărul mediu de exemplare pentru fiecare domeniu ce conține mai mult de o carte, iar prețul oricărei cărți din acest domeniu nu depășește o valoare dată ca parametru:

SELECT codel, COUNT (*), AVG (nrex)

FROM carte

GROUP BY coded

HAVING COUNT (*)>1 AND MAX (preț) NOT>& preț-max.

După cum se observă, limbajul SQL permite calculul funcțiilor statistice: COUNT, SUM, AVG, MAX și MIN.

Calcule statistice cu datele din tabele folosește și limbajul de programare FoxPro:

Comanda COUNT:

COUNT: [<domeniu>][FOR<expL1>][WHILE<expL2>]

[ TO<var>]

[NOOPTIMIZE]

numără înregistrările din domeniul specificat prin <domeniu>, FOR și WHILE (domeniul implicit este ALL), depunând rezultatul în variabila <var>, care va fi creată în cazul când nu există anterior execuției comenzii.

Un alt tip de calcul ce se poate efectua asupra unei tabele este reprezentat de însumarea valorii unor câmpuri numerice din înregistrările selectate. Comanda folosită este SUM și are sintaxa:

SUM [<listă expresii>]

[<domeniu>][FOR<expL1>][WHILE<expL2>]

[TO<listă variabile>| TO ARRAY <masiv>]

[NOOPTIMIZE]

<listă expresii> este formată din expresii care conțin câmpuri numerice ale tabelei, valorile acestor expresii urmând să fie însumate, pentru toate înregistrările selectate prin <domeniu>, FOR și WHILE. Dacă lista lipsește, se vor însuma toate câmpurile numerice ale tabelei Rezultatele obținute, adică sumele corespunzătoare expresiilor din lista de expresii, vor fi depuse fie în variabilele respective din <listă variabile>, fie în elementele masivului <masiv>.

O comandă asemănătoare cu comanda SUM este AVERAGE (calculează media aritmetică a valorilor expresiilor).

Exempu: Avem următoarea bază de date MFIXE.DBF

Să se calculeze valoarea medie a unui automobile folosindu-se datele de mai sus:

USE mfixe

AVERAGE valoare FOR upper (substr(cod,1,1) = ‘A’ TO medie

@ 10,10 SAY ‘valoarea medie a unui automobil: ’ + medie

USE

Se va afișa: Valoarea medie a unui automobil: 5432000

Același lucru se poate realiza și folosindu-se comenzile SUM și COUNT, cu ajutorul cărora se poate simula comanda AVERAGE.

USE mfixe

SUM valoare FOR upper (substr(cod,1,1) = ‘A’ TO val_tot

COUNT FOR upper (substr(cod,1,1)= ‘A’ TO nr_auto

Medie = val_tot /nr_auto

@ 10,10 SAY ‘valoarea medie a unui automobil:’ +medie

USE

Pentru o serie de calcule financiare și statistice asupra câmpurilor tabelei se folosește comanda CALCULATE, cu următoarea sintaxă:

CALCULATE [<listă expresii>]

[<domeniu>][FOR<expL1>][WHILE expL2>]

[TO<listă variabile>TO ARRAY<masiv>]

[NOOPTIMIZE]

Diferența față de comenzile anterioare constă în conținutul expresiilor din lista de expresii. In alcătuirea unei expresii din această listă pot intra următoarele funcții:

AVG (<expN>) NPV (<expN1>, <expN2>[,<expN3>])

CNT () STD (<expN>)

MAX (<expr>) SUM (<expN>)

MIN (<expr>) VAR (<expN>)

Semnificația acestor funcții este următoarea:

AVG (<expN>) calculează media aritmetică a valorilor lui <expN>, care poate conține câmpuri numerice ale tabelei;

CNT() returnează nr. de înregistrări ce aparțin domeniului selectat prin <domeniu>, FOR și WHILE;

MAX (<expr>) returnează valoarea maximă a expresiei;

MIN (<expr>) returnează valoarea minimă a expresiei;

NPV (<expN1>,<expN2>[,<expN3>]) calculează, valoarea prezentă netă a unei serii de plăți diminuate de o rată a dobânzii constantă <expN1> reprezintă rata dobânzii, iar <expN2> reprezintă expresia care, calculată pentru o înregistrare selectată, ne dă o plată din seria de plăți considerate <expN3> reprezintă valoarea inițială a investiției. Dacă aceasta lipsește, investiția inițială va fi dată de prima înregistrare selectată;

STD (<expN>) calculează deviația standard a valorilor lui <expN>, pentru înregistrările selectate:

SUM (<expN>) calculează suma valorilor lui <expN>;

VAR(<expN>) calculează abaterea pătratică medie (deviația standard la pătrat):

Abaterea pătratică medie (“Standard deviation”), în statistică, este o măsură care arată cât de mult se abat de la valoarea medie numerele dintr-o listă de valori. Cu cât abaterea pătratică medie este mai mică, cu atât valorile sunt mai apropiate de medie. Formula de calcul a abaterii pătratice medii este:

Unde:

N este nr. de valori;

x1, x2, ………, xN sunt valorile numerice;

x este media valorilor numerice,

Exemplu: Să presupunem că avem o tabelă în care am stocat rezultatele unei experiențe, valori numerice. Vom lua spre exemplu următoarea serie de valori: 13, 47, 35, 9, 89, 123, 75, depozitate în câmpul NUMĂR al tabelei NUMERE.DBF.

USE numere

CALCULATE avg (număr) TO media

?’Media numerelor este:’, media

CALCULATE cnt() TO nr_inreg

?’Numărul de valori este:’, nr_inreg

CALCULATE max (număr), min (număr), sum (număr);

TO maxim, minim, suma

?’Valoarea maximă este:’, maxim

?’Valoarea minimă este:’, minim

?’Suma numerelor este:’, suma

CALCULATE npv (0.1, număr, 100) TO val_p

?’Valoarea prezentă este:’, val_p

CALCULATE std (număr) TO dev_std, ad_patr

?’Deviația standard este:’, dev-std

?’Abaterea pătratică medie este:’, ab-patr

USE

Controlul securității și integrității unei baze de date relaționale

Controlul unei baze de date cu ajutorul limbajului SQL se referă la asigurarea

confidențialității și securității datelor, la organizarea fizică a datelor și la realizarea unor performanțe, la reluarea în cazul unor defecțiuni, la garantarea coerenței datelor în cazul manipulării concurente.

Sistemul de gestiune trebuie să pună la dispoziția unui număr mare de utilizatori o mulțime coerentă de date și trebuie să garanteze coerența datelor în cazul manipulării simultane de către diferiți utilizatori. Coerența este asigurată cu ajutorul conceptelor de tranzacție și acces curent. O tranzacție constă dintr-o succesiune de comenzi elementare care trebuiesc executate ca o singură operație.

Integritatea datelor este asigurată respectând constrângerile de integritate definite în momentul creării bazei. Concurența datelor constă în a asigura o coordonare a acceselor curente, pentru mai mulți utilizatori, la aceleași date. Un utilizator care folosește datele bazei pentru a le citi sau reactualiza, trebuie să le lase neschimbate ( într-o stare consistentă) până la sfârșitul operației chiar dacă alte tranzacții încearcă să modifice starea consistentă.

Confidențialitatea datelor presupune protecția acestora față de un acces ilegal, neautorizat la baza de date. Confidențialitatea datelor în SQL este asigurată de mecanismul vizualizărilor și de operatorul de acordare a privilegiilo (GRANT). Un utilizator efectuează o anumită operație doar dacă deține privilegiul acordării acestei operații.

Dacă utilizatorul dorește executarea unei comenzi (de ex, SELECT), sistemul verifică dacă identificatorul furnizat de utilizator dispune de privilegiul ce-i permite această operație. Există privilegii asupra datelor (acordate de utilizator) și privilegii asupra utilizatorilor (acordate de administratorul bazei de date ).

Acordarea privilegiilor se face prin ordinul GRANT care are forma generală:

GRANT privilegiu 1 [, privilegiu 2…]

ON numetabel sau vizulaizare

TO utilizator 1 [, utilizator2…]

[WITH GRANT OPTION]

Eliminarea privilegiilor (dar nu a utilizatorului) se realizează prin comanda REVOKE care are o sintaxă similară ordinului GRANT.

Acordarea privilegiilor de interogare și inserare utilizatorului observator se obține prin secvența:

CREATE VIEW V1

AS SELECT *FROM carte WHWERE coded = ’i’

GRANT SELECT, INSERT ON V1 TO observator

Utilizatorului observator i se acordă toate privilegiile referitoare la tabelul CITITOR cu excepția celei de ștergere:

GRANT ALL ON cititor TO observator

REVOKE DELETE ON cititor FROM observator.

SECURITATEA DATELOR

Generalități

Asigurarea securității, unei baze de date presupune interzicerea accesului la date, interzicerea modificării și distrugerii datelor de către utilizatori neautorizați. Referitor la sfera de acțiune a metodelor utilizate pentru securitatea datelor, pot fi puse în evidență trei direcții:

controlul accesului la sistem al unor utilizatori neidentificați sau neautentificați;

controlul accesului ilegal la date (confidențialitate)

controlul modificării incorecte a datelor (integritate)

Parola, criptarea (codificarea) și matricele de acces reprezintă mecanisme clasice ale sistemului de operare care asigură securitatea datelor.

Majoritatea sistemelor folosesc parole pentru identificarea utilizatorilor. Parolele permit accesul la resursele sistemului și sunt, în general, asociate cu anumite drepturi de acces la date. Pentru fiecare utilizator, identificat prin parolă, sistemul întreține o listă a privilegiilor acestuia, iar aceste privilegii depind de clasa căreia îi aparține utilizatorul.

Gestionarea privilegiilor se face cu ajutorul matricei de acces. Coloanele acestei matrice corespund elementelor care definesc un privilegiu: subiectul, obiectul, acțiunea și, uneori, restricția. Subiectul poate fi un utilizator, un grup de utilizatori, o aplicație sau un terminal. Obiectul este reprezentat de datele care trebuie protejate (înregistrare, relație, baza de date etc). Acțiunea definește operațiile pe care subiectul le poate efectua asupra obiectului (citire, inserare, reactualizare, ștergere etc). Restricția reprezintă condiții suplimentare care trebuie respectate când un subiect execută o acțiune asupra unui obiect.

Administratorul unei baze de date poate să stabilească privilegii pentru un fișier de date (schemă de privilegii) prin atribuirea nivelurilor de acces pentru operațiile pe care un utilizator le poate executa asupra acestuia.

Se pot asigna nivele de acces în orice combinație, pentru privilegii de tip “actualizare”, “adăugare” și ”ștergere”. Aceste privilegii vor permite utilizatorului următoarele :

– vizualizarea înregistrărilor dintr-un fișier de date (read privilege);

– modificarea conținutului înregistrărilor unui fișier de date (update privilege);

– adăugarea unor noi înregistrări la un fișier de date (extend privilege);

– ștergerea înregistrărilor dintr-un fișier de date (delete privilege).

Administratorul va acorda fiecărui utilizator un număr de nivel, între 1 și 8 (1 fiind cel mai ridicat dret de acces).

Cele 8 drepturi de acces sunt:

supervisor

acces control

modify (modificare)

file scan (scanare)

erase (ștergere)

create (creare)

write (scriere)

read (citire )

Când se creează o schemă de privilegii a fișierelor, toate cele patru privilegii sunt acordate până când se va modifica nivelul de acces al acestora. Acest lucru înseamnă că toate nivelurile de acces pentru fișiere au valoare implicită 8.

Exemplu: Presupunem activitățile de aprivizionare și fișierele FACTURI (care păstrează ce s-a primit), CONTRACTE (ce trebuia să se primească), FURNIZORI (de la ce parteneri ne aprovizionăm)

Privilegiile pentru fișierele CONTRACTE arată astfel:

Semnificația este următoarea: “toate nivelele mai mari decât * au interdicție la operația respectivă”. Deci, dacă directorului îi acordăm nivelul 8, el va putea doar să citească informațiile din fișier, nu și să intervină în modificarea acestuia! Nivelul de acces al utilizatorului are valoarea implicită 1 (nivelul cel mai puternic).

Operațiile permise unui utilizator pot fi controlate chiar la nivel de câmp. Se pot oferi privilegii de tip complet (FULL), numai citire (R/O) sau nici un privilegiu (NONE) pentru fiecare câmp al unui fișier și pentru fiecare nivel de acces.

De exemplu acordarea privilegiilor fișierului CONTRACTE se poate face în felul următor:

Interpretare: pentru nivelul 2 este posibilă doar modificarea câmpului nume, vizualizarea câmpurilor n_contract și data, fiind interzis accesul la celelalte câmpuri.

Observație: Privilegiile de fișier sunt mai puternice decât privilegiile de câmp. De exemplu, dacă privilegiul unui fișier este configurat pentru citire și nu pentru actualizare, singurele activități permise la câmpuri vor fi read only sau none.

Observație: Trebuie să restricționăm privilegiile de fișier pentru a ne proteja datele împotriva comenzilor orientate pe fișier ca ZAP; restricționarea privilegiilor de câmp la R/O sau N nu va realiza această protecție (pentru nivelul de acces 1 vom pune * la operația de ștergere).

Criptarea este operația de codificare a datelor pe timpul stocării sau al transportului, a.î. descifrarea lor să poată fi făcută numai de posesorii de cod. Problema securității cheii de criptare, iar mecanismul gestiunii cheilor de criptare este complex.

Necesitatea unei protecții de o mare finețe și insuficiența mecanismelor propuse de sistemul de securitateal SO au condus la definirea unor sisteme de securitate specifice fiecărui SGBD.

In SGBD relaționale, parola nu mai este utilizată pentru protecția datelor, iar gestiunea acceselor este dinamică. Pentru a asigura securitatea sistemului de manipulare a datelor trebuie controlat fluxul datelor pentru a evita ca informațiile să ajungă la persoane care nu au dreptul să le utilizeze (controlul fluxului). Trebuie evitată situația în care un utilizator poate, în funcție de datele la care are acces, să ajungă la informații care îi sunt interzise (controlul interferenței). Trebuie evitat ca un program să comunice altui program date la care are doar el acces sau anumite rezultate intermediare (divulgarea informației).

Conceptul de vizualizare din modelul relațional corespunde noțiunii de subschemă. Vizualizarea este o bază de date virtuală a cărei schemă și conținut este derivat dintr-o bază de date reală prin aplicarea unei mulțimi de condiții (filtre). Vizualizările sunt importante deoarece asigură independența logică a datelor și conservă securitatea datelor.Ele protejează baza împotriva accesului neautorizat. Utilizatorul poate manipula numai relații și atribute care aparțin vizualizării sale.

Un sistem de securitate cuprinde un modul de autorizare și un modul de control.

Cantitatea de informații necesară întreținerii securității datelor poate fi redusă stocând doar constrângerile de bază și obținând restul constrăngerilor cu ajutorul unor algoritmi. La bazele de date moderne controlul se face într-o manieră declarativă: constrângerile de integritate și de confidențialitate sunt descrise într-o formă aserțională la nivelul schemei relaționale.

Confidențialitatea datelor

Pentru asigurarea confidențialității datelor pot fi considerate două tipuri de controale: controlul accesului direct și controlul accesului indirect. Accesul direct poate fi făcut la nivel intern sau în majoritatea cazurilor la nivel extern. Controlul accesului intern (acces “microscopic”) solicită ca sistem de gestiune să utilizeze un mecanism de codificare a datelor și să existe un sistem de securitate fiabil sistemului de operare. Controlul accesului extern depinde de numele atributelor, de numele relațiilor, de context, de valoarea efectivă a unui atribut, de timpul de acces.

Fie schema relațională SALARIAT (cod_salariat, nume, funcție, salariu) și fie câteva drepturi pe care un utilizator le poate avea asupra relației SALARIAT:

Toate drepturile

Nici un drept

Reactualizarea tuturor atributelor, cu excepția salariilor

Citirea tuturor salariilor, cu condiția ca cererile să nu refere simultan atributele: “cod_salariat” și “salariu”

Citirea informațiilor referitoare la salariații al căror salariu este mai mic ca 200000 lei

Citirea de către director a informațiilor referitoare la orice salariat

Inserarea și eliminarea tuplurilor de către director.

Din acest exemplu se pot remarca factorii de care depinde controlul accesului:

de tipul accesului – citire, inserare, eliminare, modficare

de nume – în funcție de numele relației și/sau numele atributelor se poate decide

dacă este permisă sau nu execuția unor cereri. Acest control static se

face o singură dată, înaintea execuției (1, 2, 3, 4)

de valoarea unui atribut – decizia de a permite accesul la informație depinde de

valoarea unui atribut (5, 6, 7)

de context – acesta permite restrângerea datelor care pot fi accesate. In cazul 4, se

interzice utilizatorului să cunoască salariul unui salariat particular.

Controlul care depinde de valoarea unui atribut se face la execuție. Controlul care depinde de context și de nume poate fi făcut la compilare sau chiar înainte. Acest control se referă la analiza globală a cererii de intrare (un control pe cerere), în timp ce controlul dependent de valoare se face pentru fiecare tuplu (un control pe tuplu).

Controlul accesului indirect corespunde la ceea ce utilizatorul poate face cu ajutorul informațiilor manipulate sau deduse. Utilizatorul are dreptul să manipuleze anumite informații confidențiale (de exemplu să mărească salariile cu 10%), dar nu are dreptul să acceseze aceste informații (controlul accesului temporar). Utilizatorul, prin datele la care are acces, poate obține informații confidențiale (controlul accesului funcțional) Această problemă este legată de existența unor funcții, furnizate utilizatorului, pentru manipularea bazei. Cunoscând funcția și anumite date particulare, utilizatorul poate obține date confidențiale.

Ce este o bază de date statistică?

Numim o bază de date statistică o bază de date din care se pot obține informații despre submulțimi de elemente conținute în aceasta. Prin formularea unor întrebări, unii utilizatori pot să obțină informații la care în mod obișnuit nu au acces. Putem avea anumite aplicații: un fișier de personal, un fișier cu pacienții unui spital, evidența plătitorilor de taxe, în general baze cu cantități de date asupra cărora se efectuează anumite operații statistice.

O bază de date statistică trebuie să îndeplinească două proprietăți importante pentru existența acesteia:

să conțină un număr vast de înregistrări confidențiale;

să furnizeze numai informații statistice utilizatorilor săi și nu informații referitoare la o anumită înregistrare.

Cu alte cuvinte, singurele cereri care sunt permise sunt cele care aplică unele funcții statistice cum ar fi COUNT (numărare), SUM (suma valorilor), sau AVERAGE (media valorilor) asupra submulțimilor înregistrărilor din baza de date.

In plus față de problema clasică de a interzice accesul neautorizat sau modificarea neautorizată a datelor, într-o bază de date statistică apare problema mai subtilă de a permite cereri ca: “afișarea venitului mediu al locuitorilor dintr-un oraș”, în timp ce trebuie să interzicem accesul la venitul unei persoane particulare.

Nu este suficient să se interzică cererile care cer informații referitoare la o singură înregistrare. De exemplu, o persoană, George, poate cere “venitul mediu a două persoane: George și Florin” și cunoscându-și venitul îl poate deduce pe cel al lui Florin. Confidențialitatea datelor referitoare la Florin este astfel încălcată.

De asemenea, nu este suficient să se impună restricția ca cererile să se refere la o mulțime de cel puțin m entități, De exemplu, George ar putea lua o mulțimede m-1 sau mai multe persoane și să obțină venitul mediu al acestor persoane plus Florin și apoi ventul mediu al acestor persoane plus el. Cunoscându-și venitul, el poate afla venitul lui Florin, confidențialitatea fiind compromisă.

Problema de mai sus nu a fost permiterea cererilor asupra unor mulțimi mici ; nu poate fi oricât de mare. De fapt problema constă în abilitatea interogatorului să facă cereri care sunt oarecum asemănătoare. Acest lucru ne obligă să punem o limită nu atât mărimii mulțimii la care se referă statisticile cerute, ci mai degrabă, trebuie limitată mărimea intersecției a două mulțimi asupra cărora se fac cereri. Vom observa mai târziu că această restricție ajută în sensul că nu putem preveni dezvăluirea datelor confidențiale, dar această acțiune poate fi mult mai dificilă.

Modelul unei baze de date statistice

Vom considera în continuare o bază de date statistică simplificată constând într-un singur fișier, de înregistrări. Fiecare înregistrare are câteva câmpuri. Iar o cerere specifică valori pentru anumite câmpuri și produce informații agregate (totale sau combinate) cum ar fi suma sau media valorilor dintr-un câmp pentru toate înregistrările care satisfac condițiile impuse de cerere. De exemplu o astfel de cerere ar putea solicita salariul mediu al tuturor persoanelor cu numele de familie Stanciu dintr-un fișier cu personalul unei societăți.

Pentru a prveni situațiile în care anumiți utilizatori obțin informații la care nu au acces se poate folosi un mecanism de protecție prin intermediul căruia unele sisteme de baze de date țin o evidență a cererilor făcute de fiecare utilizator în parte și refuză să răspundă în anumite condiții: sunt implicate mai puține înregistrări decât un număr prevăzut inițial, sau sunt implicate mai mult de n-m înregistrări, unde n este numărul total de elemente, sau sunt implicate mai mult de p înregistrări comune cu o cerere anterioară și altele asemănătoare.

In general, ultima restricție necesită ca sistemul să rețină un vector de biți ce reprezintă mulțimile de înregistrări asupra cărora este făcută la un moment dat o cerere, și acest lucru trebuie făcut pentru o perioadă lungă de timp și de aceea poate să nu fie practic de implementat. De aceea trebuie stabilite anumite limte cu privire la ceea ce va fi reținut, De exemplu, se poate alege să se rețină numai un număr limitat de cereri sau putem împărți înregistrările în grupuri și să reținem ce grupuri au înregistrări implicate într-o cerere dată.

Când sistemul de baze de date va decide dacă să răspundă sau nu la o cerere dată, presupunem că avem cel mai rău caz și anume că pentru fiecare set de grupuri ce corespund unei cereri anterioare, cererea curentă ar putea selecta orice submulțime din fiecare din grupuri. Prima dintre aceste metode, reținând numai un număr limitat, ar putea accepta cereri pe care ar trebui să le refuze, în timp ce a doua metodă, împărțind înregistrările în grupe, ar putea interzice o cerere care ar putea fi acceptată în siguranță.

Cereri liniare

Considerăm o bază de date cu n înregistrări, și ν = (ν1, ν2, ….., νn) vectorul valorilor acestor înregistrări pentru un câmp particular care nu este cheie. Vom numi o cerere liniară o sumă liniară de forma:

, unde (ci) i=1,n este un vector arbitrar de numere reale. Cazurile frecvent folosite sunt sumele pentru o submulțime S cu

ci=

și mediile cu

ci=

In general, abilitatea de a compromite baza de date, adică a deduce o valoare particulară νI, va depinde de numărul ci-uri nenule permis, și nu de valoarea lor exactă sau de faptul că ci-urile sunt egale (c1 = c2 =…..=cn).

Presupunem că vom avea un număr q de cereri, iar a i-a cerere va extrage din baza de date :

Rezultatele acestor cereri pot fi exprimate în formă matriceală

Unde M

este o cerere q cu r Mq ( R ), M Mq, n ( R ), Mn ( R )

M =

Dacă dorim să compromitem baza de date trebuie să calculăm o funcție f(r1,…rq) care este egală cu unul dintre j. Putem presupune, fără a restrânge generalitatea, f(r1,…rq) = 1. O proprietate importantă este dată de următoarea lemă:

Lemă: dacă, cu notațiile de mai sus, există o funcție f astfel încât f(r1,…rq) = 1 atunci f este liniară, adică există d1, d2,….,dq astfel încât:

Demonstrație: pornim de la faptul că:

și deoarece

deci avem:

De aici putem deduce că f este de forma: cu (di)i=1,…n soluția sistemului vom presupune că fq este liniară. Deci există un vector

d = (d1,……. dq) = Inlocuind M νT cu r, vom avea drT = d M νT = ν1

De aceea dM trebuie să fie vectorul (1,0,0,….,0) de lungime n. In termenii bazelor de date statistice asta înseamnă că, pentru a compromite baza de date , fără a restrânge generalitatea de calculare a elementului ν1, trebuie să găsim o colecție de q cereri care formează o matrice M astfel încât să existe un vector d pentru care dM = (1,0,0,….,0).

Dacă punem anumite restricții asupra cererilor, ceea ce înseamnă restricții asupra liniilor matricii M putem arăta că M trebuie să aibă mai multe linii. Asta înseamnă că sunt necesare multe cereri, dacă un astfel de d există.

In particular vom considera două restricții asupra lui M:

Fiecare linie are cel puțin m elemente nenule. Asta înseamnă că cererile trebuie să implice fiecare cel puțin m înregistrări (valori);

Orice două linii nu pot să aibă mai mult de k coloane în care să aibă fiecare elemente nenule. Asta înseamnă, în termenii bazelor de date, că intersecția mulțimilor de înregistrări corespunzătoare a două cereri are cel mult k elemente.

Exemplu: Să considerăm o bază de date cu 7 elemente: ν = (ν1,……, ν7) și folosim următoarele 5 cereri:

Atunci: ν1 = (r3 +r4 + r5 – r1 – r2) /3

De observat că fiecare cerere implică cel puțin 3 valori și oricare două cereri au o intersecție de dimensiune maxim 1. Putem alege deci în acest caz m=3 și k=1. Cererile sunt calculate sub formă matriceală astfel:

=

Vectorul d va fi: d = ( – 1/3 , – 1/3, – 1/3, – 1/3, – 1/3) și dM = (1, 0, 0, 0, 0, 0, 0) vom găsi în continuare limitele pentru numărul de cereri necesare pentru a compromite o bază de date, în ipoteza că fiecare cerere implică cel puțin m elemente, și oricare două cereri nu au în comun mai mult de k elemente. Putem presupune, de asemenea, că p valori sunt deja cunoscute și că pentru a compromite baza de date trebuie să determinăm un element care nu este încă cunoscut.

Avem în acest sens următorul rezultat.

Teoremă: în condițiile de mai sus (cererile implică cel puțin m elemente, oricare două cereri nu pot avea în comun mai mult de k elemente și se presupune că p elemente sunt deja cunoscute), pentru a afla elemente necunoscute trebuie să facel cel puțin:

cereri

Demonstrație: considerăm prima cerere care produce o sumă lineară peste mulțimea S cu mai puțin de m elemente, adică m ≤ | S |.

Fie νi ε S. Dacă νi nu este printre cele p elemente deja cunoscute și νi nu este elementul calculat prin produsul dM, atunci există o altă cerere care folosește νi.

Pentru ca afirmația de mai sus să fie adevărată, am presupus că M are cel mai mic număr posibil de linii, adică nu facem mai multe cereri decât este necesar pentru a compromite o bază de date. Altfel spus, presupunem că vectorul d nu are componente nule.

Astfel, dacă doar o cerere ar implica νI, atunci produsul dM ar avea componenta a i-a nenulă. Vom avea: cel puțin m-p-1 membrii ai mulțimii S care apar în alte cereri, și orice altă cerere intersectează mulțimea S în cel mult k elemente. De aici rezultă că trebuie să mai existe cel puțin

*** q.e.d

Teorema de mai sus are o consecință importantă. Presupunând p, numărul de elemente cunoscute deja, ca fiind mic în comparație cu m, sunt necesare aproximativ m/k cereri pentru a compromite baza de date. Cum m și k sunt parametrii strategiei de protecție, trebuie doar să-i alegem astfel încât raportul lor să fie mai mare (să zicem ~ 1000) și vom avea siguranța că va fi necesar un mare efort pentru a compromite baza de date. Totuși, nu putem să nu observăm că un m mare și un k mic pot pune o piedică în calea utilizatorului interesat în obținerea informațiilor statistice legale. De asemenea, reținerea ultimelor 1000 de cereri pentru fiecare utilizator poate crește rapid spațiul de depozitare al sistemului, așa că se pune întrebarea dacă limitarea dimensiunii și a intersecției este practică în general.

Pe de altă parte, nu cumva teorema este prea pesimistă? Poate trebuie să existe mult mai mult de m/k cereri pentru a compromite baza de date. Din păcate, presupunerea aceasta nu este valabilă, după cum vom vedea din exemplul următor:

Presupunem p=0, k=1 și n= 1+m(m+1)/2. Considerăm o matrice M de (m+1) linii și (1+m(m+1)/2) coloane cu următoarele proprietăți:

prima coloană are un 1 și restul 0;

fiecare dintre celelalte coloane are doar două elemente nenule și oricare două coloane nu au elemente nenule pe aceleași linii. Acest lucru este posibil, pentru că numărul de posibilități de a alege două linii din (m+1) este:

în fiecare coloană de la 2 la 1+m(m+1)/2 există un singur 1 și un singur –1;

Atunci suma tuturor liniilor din matricea M este (1, 0, 0,….,0) ceea ce ne permite să compromitem baza de date calculând ν1. Deoarece oricare două coloane sunt diferite și fiecare coloană are cel mult 2 elemente nenule în mai mult de o coloană.

Pentru m=3 o astfel de matrice va fi:

M=

Inlocuind fiecare coloană în afara celei dintâi cu k coloane identice, putem generaliza strategia de mai sus pentru a compromite o bază de date cu 1+m/k cereri, care este foarte apropiat de limita inferioară din teorema de mai sus.

Poate că cererile liniare generale permit o compromitere rapidă a bazei de date, dar dacă ne mărginim la cereri care solicită sume sau medii, ceea ce este de aștepat ca limbajul de cereri să pună la dispoziția utilizatorilor, atunci putem îmbunătăți limita inferioară din teoremă. Această problemă are aspecte neclare, dar se poate demonstra că pentru k=1 sunt suficiente 2m-1 cereri care solicită sume pentru a compromite o bază de date.

Astfel, presupunem că avem n= 1+m(m-1) și:

prima cerere solicită suma elementelor 2,3,….,(m+1);

a doua cerere solicită suma elementelor m+2, m+3, …., 2m+1;

a treia pentru 2m+2, …., 3m+1;

și așa mai departe.

Ultimele m cereri include primul element și în plus:

cererea m include 2, m+2, 2m+2, …

cererea m+1 include 3, m+3, 2m+3,…

și așa mai departe.

Pentru m=3 matricea corespunzătoare va fi:

M=

In concluzie sunt sufieciente 2m/k-1 cereri, oricare ar fi m și k.

Limite privind structura cererilor

Până acum am presupus cererile specifică submulțimi arbitrare de înregistrări ale bazei de date, având numai o limită inferioară a dimensiunii submulțimilor. Am arătat că pentru a compromite o bază de date, folosind astfel de cereri, nu este imposibil, dar consumă mult timp dacă limităm suprapunerea mulțimilor definite de două cereri. Poate dacă nu admitem toate cererile “mari”, am putea garanta, de fapt, o bază de date care nu poate fi compromisă.

O soluție care a fost studiată se bazează pe faptul că, cheia pentru înregistrări este formată din k biți și că pentru fiecare valoare a cheii sau pentru aproape orice valoare a cheii există o înregistrare. Cererile au permisiunea să specifice valori pentru maximum s din biții cheii și pot obține suma valorilor din înregistrările ale căror chei coincid în cei s biți cu valorile specificate în cerere.

De exemplu, pentru k=3 și s=2 putem da valoarea 1 bitului 1 și 0 bitului 3. Rezultatele cererii va fi suma valorilor din înregistrările cu cheile 100 și 110 (în binar). De observat este asemănarea cu căutarea după cheia parțială în care se inițializează o submulțime a câmpurilor cheii cu valori, căutându-se apoi în bază toate înregistrările care au aceleași valori în câmpurile respective.

Să urmărim următorul exemplu:

Exemplu: Presupunem o bază de date statistică în care fiecare înregistrare conține suma veniturilor tuturor persoanelor ale căror “caracteristici” se potrivesc valorii cheii pentru înregistrarea respectivă. Presupunem cheia formată astfel: 6 biți reprezentând țara în care persoana trăiește, 8 biți indicând localitatea, 1 bit indicând sexul persoanei, 6 biți indicând ocupația și 5 biți indicând marca automobilului personal. Mărimea în biți a cheii va fi: k= 6+8+1+6+5 = 26 biți. Cum 226 este foarte mare (≈ 67 milioane), fiecare înregistrare va conține venitul în medie a câtorva persoane.

Putem lua s=15, astfel încât este acceptată o cerere în care să solicităm suma veniturilor tuturor persoanelor de gen masculin, care locuiesc în Pitești, România (se specifică 1+8+6 = 15 biți), sau suma veniturilor tuturor inginerilor care au ARO (se specifică 6+5 = 11 biți) dar nu putem cere suma veniturilor inginerilor care au ARO și locuiesc în România (se specifică 6+5+6 = 17 biți). Putem teoretic specifica și până la 15 biți care include unii, dar nu toți biții corespunzător țării, corespunzători ocupației, sau altor atribute.

Se dovedește că în exemplul de mai sus nu se poate deduce informația unei anumite înregistrări, indiferent de șirul de cereri făcute cu respectarea restricției s<k, adică în care nu se pot specifica toți biții cheii.

Exemple de compromitere a unei baze de date statistice.

Am introdus noțiuni teoretice referitoare la bazele de date statistice, la limita asupra numărului de cereri necesare pentru a compromite o bază de date statistică, am arătat mijloace de protecția a bazelor de date statistice, iar în continuare vom da exemple din care să vedem cum funcționează efectiv încercările de compromitere a unei baze de date statistice. Vom folosi pentru ilustrarea unor astfel de cereri limbajul SQL.

Exemplu: Vom considera o bază de date ce constă dintr0o singură relație (SALARIAT), după cum se vede în figura 1. Vom presupune că un utilizator autorizat U vrea să descopere salariul și datoriile lui Mitică. Presupunem că utilizatorul știe că Mitică este de sex masculin și este programator. Considerăm cererile c1 și c2 după cum urmează:

Figura 1

Exemplu:

c1: SELECT COUNT (*)

FROM SALARIAT

WHERE SEX =’M’

AND OCUPATIE =’programator’ răspuns: 1

In exemplul de mai sus se cere numărarea salariaților de sex masculin și care sunt programatori: Se găsește un singur programator de sex masculin.

c2: SELECT SUM (SALARIU), SUM (DATORII)

FROM SALARIAT

WHERE SEX =’M’

AND OCUPATIE =’programator’ răspuns: 3500000, 50000

Securitatea bazei de date a fost în mod evident compromisă, chiar dacă utilizatorul U a făcut numai cereri statistice legale. După cum ilustrează exemplul, dacă utilizatorul poate găsi un predicat P care identifică o unică înregistrare din baza de date, atunci înregistrarea respectivă nu mai poate fi considerată protejată. Acest lucru arată că sistemul ar trebui să refuze cererile care implică mai puțin de m înregistrări, după cum am arătat și în subcapitolul

Să mai dăm un exemplu:

Exemplu:

c3: SELECT COUNT (*)

FROM SALARIAT

Răspuns: 10

c4: SELECT COUNT (*)

FROM SALARIAT

WHERE NOT

(SEX =’M’ AND OCUPATIE = ‘PROGRAMATOR’)

Răspuns: 9

Scădem (c3 – c4): 1

c5: SELECT SUM (SALARIU), SUM (DATORII)

FROM SALARIAT

Răspuns: 44700000, 830000

c6: SELECT SUM (SALARIU), SUM (DATORII)

FROM SALARIAT

WHERE NOT (SEX =’M’ AND OCUPATIE = ‘PROGRAMATOR’)

Răspuns: 41200000, 780000

Scădem (C5-C6): 3500000, 50000

Acest exemplu ne sugerează că ssitemul ar trebui să refuze cererile ce implică submulțimi de înregistrări cu cardinalul mai mare de n-m (unde n este numărul înregistrărilor din baza de date).

Este totuși ușor de arătat că simpla refuzare a cererilor cu rezultatele de cardinal c care nu este în intervalul [ m, n-m] nu este în general suficientă pentru asigurarea securității.

Considerăm în exemplul de mai sus că m=2 și deci sunt acceptate numai cererile al căror rezultat este o mulțime cu cardinal c cu 2 ≤ c ≤ 8.

Astfel predicatul

SEX = ‘M’ AND OCUPATIE = ‘programator’

nu este admisibil

Considerăm următoarele cereri:

c7: SELECT COUNT (*)

FROM SALARIAT

WHERE SEX =’M’

Răspuns: 4

c8: SELECT COUNT (*)

FROM SALARIAT

WHERE SEX =’M’

AND NOT (OCUPATIE=’programator’)

Răspuns: 3

Din cererile c7 și c8 utilizatorul poate deduce că există exact un singur programator de sex masculin, care trebuie să fie Mitică, deoarece se știe că aceste două caracteristici i se potrivesc acestuia. In continuare se poate deduce salariul lui Mitică și datoriile lui:

c9: SELECT SUM(SALARIU), SUM(DATORII)

FROM SALARIAT

WHERE SEX =’M’

Răspuns: 22500000, 330000

c10: SELECT SUM(SALARIU), SUM(DATORII)

FROM SALARIAT

WHERE SEX =’M’

AND NOT (OCUPATIE=’programator’)

Răspuns: 19000000, 280000

Scădem: (c9-c10): 3500000, 50000

Predicatul SEX =’M’ ND NOT (OCUPATIE=’programator’) este numit tracker individual pentru Mitică. In general, dacă utilizatorul cunoaște un predicat P care identifică o înregistrare particulară r, și dacă P poate fi exprimat în forma P1 AND P2, atunci predicatul P1 AND NOT P2 este un tracker pentru R (cu condiția ca predicatele P1 și (P1 AND NOT P2) sunt amândouă admisibile, adică amândouă corespund unor mulțimi cu cardinalul în intervalul [m, (m-1)]. Aceasta deoarece mulțimea înregistrărilor identificate de predicatul P este aceeași cu diferența dintre mulțimea identificată de predicatul P1 și cea identificată de predicatul (P1 AND NOT P2).

De observat că această idee nu merge pentru orice situație. Trackerul individual funcționează numai pentru cereri ce implică numai anumite predicate neadmisibile. Vom defini noțiunea de tracker general, ca fiind un predicat care poate fi folosit să găsim răspuns la orice cerere neadmisibilă. De fapt, orice predicat al cărei mulțimi de adevăr are cardinalul c cu 2m ≤ c ≤ n-2m este un tracker general (cu condiția evidentă ca m ≤ n/4 , condiție care de obicei este îndeplinită în situațiile reale). Odată ce un astfel de predicat este găsit, o cerere ce implică un atribut inadmisibil P poate fi rezolvată după cum ne arată exemplul de mai jos.

Exemplul: Presupunem că m =2 și atunci un tracker general este un predicat cu mulțimea de adevăr de cardinal c și 4 ≤ c ≤6. In aceleași condiții de la exemplele anterioare, predicatul P este: SEX = ‘M’ AND OCUPATIE = ‘programator’. Vom folosi un tracker general de două ori : prima dată pentru a stabili că predicatul P este într-adevăr un identificator pentru Mitică și apoi pentru a determina salariul lui Mitică. Metoda constă în aplicarea mai multor pași.

Pas 1: încercăm să ghicim un predicat T care să reprezinte un tracker general.

In cazul de față luăm T ca fiind VECHIME=0

Pas 2: Găsim numărul total de înregistrări, folosind predicatele T și NOT T

c11: SELECT COUNT (*)

FROM SALARIAT

WHERE VECHIME= 0

Răspuns: 3

c12: SELECT COUNT (*)

FROM SALARIAT

WHERE NOT (VECHIME= 0)

Răspuns: 7

Se adună (c11+c12): 10

Se observă pentru acest exemplu că predicatul T considerat este un tracker general

Pas 3: folosind predicatele P OR T și P OR NOT T, găsim suma dintre numărul total de înregistrări și numărul de înregistrări care satisfac predicatul P.

c13: SELECT COUNT (*)

FROM SALARIAT

WHERE (SEX= ‘M’ AND OCUPATIE=’programator’)

OR VECHIME = 0

Răspuns: 4

c14: SELECT COUNT (*)

FROM SALARIAT

WHERE (SEX= ‘M’ AND OCUPATIE=’programator’)

OR NOT (VECHIME = 0)

Răspuns:7

Insumăm (c13+c14): 11

Pas 4: din rezultatele de până acum avem numărul celor care satisfac predicatul P: rezultatul pasului 3 – rezultatul pasului 2. In cazul de față P îl identifică pe Mitică în mod unic.

Următorii pași sunt identici, dar utilizând SUM în loc de COUNT

Pas 5: calculăm suma salariilor

c15: SELECT SUM (SALARIU)

FROM SALARIAT

WHERE VECHIME=0

Răspuns: 18500000

c16: SELECT SUM (SALARIU)

FROM SALARIAT

WHERE NOT (VECHIME = 0)

Răspuns: 26200000

Se adună (c15+c16):44700000

Pas 6: găsim suma dintre salariul total și cel al lui Mitică

c17: SELECT SUM (SALARIU)

FROM SALARIAT

WHERE (SEX = ‘M’ AND

OCUPATIE=’programator’)

OR VECHIME=0

Răspuns:22000000

c18: SELECT SUM (SALARIU)

FROM SALARIAT

WHERE (SEX = ‘M’ AND OCUPATIE=’programator’)

OR NOT (VECHIME=0)

Răspuns:26200000

Insumând (c17+c18):

Pas 7: găsim salariu lui Mitică prin scăderea rezultatelor de la cei doi pași precedenți:

48200000 – 44700000

Acest algoritm se bazează pe următoarea egalitate: |Mp| = | M(P OR T) | +|M(P OR NOT T) | – |M(T OR NOT T) |.

Astfel dacă inițial T se alege în mod greșit (nu este un tracker general) atunci unul din predicatele (P OR T ) sau (P OR NOT T) poate să nu fie admisibil. Dacă p și t sunt cardinalele pentru mulțimile de adevăr pentru P și respectiv T cu p<m (analog și pentru p>n-m) și m ≤ t ≤ 2m , atunci este posibil ca mulțimea corepunzătoare pentru (P OR T ) să fie mai mică decât 2m. In astfel de situații este necesar să ‘ghicim’ din nou un tracker general T. Practica arată că nu este greu de găsit un tracker general.

Concluzia celor spuse mai sus este că securitatea în bazele de date statistice este o problemă destul de dificil de rezolvat.