ACADEMIA DE STUDII ECONOMICE A MOLDOVEI Catedra „Cibernetică şi Informatică Economică”

Vitalie Cotelea Marian Cotelea

Chişinău-2016

2

CZU 004.65(075.8) C 76 Manualul Baze de date a fost elaborat în cadrul Catedrei „Cibernetică şi Informatică Economică” şi recomandat pentru editare de Senatul Academiei de Studii Economice din Moldova (proces verbal nr.4 din 02 martie 2016).

Lucrarea prezintă, de la simplu la complex, cunoştințele teoretice şi practice necesare și oferă o bază solidă privind fundamentele tehnologiei bazelor de date.

Chiar dacă tematica cuprinsă între copertele acestei lucrări nu comportă un caracter exhaustiv, ceea ce s-ar dori prin intermediul unui manual voluminos, el prezintă principalele concepte şi mecanisme cu ajutorul cărora se pot efectua proiectarea, mentenanța şi restructurarea bazelor de date. Alegerea variantelor de soluții şi aplicarea eficientă a instrumentelor descrise rămân la latitudinea şi depind de imaginația şi nevoile personale ale fiecărui utilizator, care dezvoltă un proiect.

Volumul de față se adresează: studenților, oricărei persoane care doreşte să se inițieze în domeniul bazelor de date, angajaților companiilor de software sau potențialilor angajați, care nu sunt neapărat programatori, dar lucrează, într-un fel sau altul, cu baze de date, implementatorilor, consultanților, instructorilor, analiştilor, administratorilor de sistem sau de baze de date, programatorilor care nu au luat contact cu bazele de date şi doresc o familiarizare cu modelele obiectual-relaționale.

Recenzenți: Prof. univ., dr. hab. în informatică Ion Bolun Conf. cercet., dr. hab. în informatică Svetlana Cojocaru

Descrierea CIP a Camerei Naționale a Cărții Cotelea, Vitalie

Base de date / Vitalie Cotelea, Marian Cotelea; Acad. de Studii Econ. a Moldovei, Catedra „Cibernetică şi Informatică Economică” – Chişinău: S. n., 2016 (F.E.-P. "Tipografia Centrală"). – 340 p.

În red. aut. – Bibliogr.: p. 333-338. – 150 ex.

ISBN 978-9975-53-633-2.

CZU 004.65(075.8) C 76

Autori: © Vitalie Cotelea (ASEM) © Marian Cotelea (Endava)

ISBN 978-9975-53-633-2.

Întreprinderea de Stat. Firma editorial-poligrafică „Tipografia Centrală”

3

CUPRINS

INTRODUCERE ............................................................................................................. 13

FAZE GENERALE DE PROIECTARE A BAZELOR DE DATE ...................................................... 13

STRUCTURA ȘI CONȚINUTUL LUCRĂRII ............................................................................... 14

1. EVOLUȚIA BAZELOR DE DATE DE LA ORIGINI ȘI PÂNĂ ÎN PREZENT ........................................................................................................................................ 19

1.1. SISTEME PRERELAȚIONALE ............................................................................................ 19 1.1.1. Sisteme bazate pe fișiere ............................................................................................... 19 1.1.2. Sisteme orientate pe baze de date .................................................................................. 20 1.1.3. Conceptele de bază de date și sistem de gestiune a bazelor de date .............................. 21

1.2. OBIECTIVELE BAZELOR DE DATE ................................................................................... 22 1.2.1. Evitarea redundanței și inconsistenței datelor ............................................................. 22 1.2.2. Facilitarea accesului la date .......................................................................................... 23 1.2.3. Facilitarea elaborării programelor de prelucrare a datelor ........................................... 23 1.2.4. Asigurarea accesului concurent la date ....................................................................... 23 1.2.5. Asigurarea accesului securizat la date ......................................................................... 24 1.2.6. Păstrarea integrității datelor ........................................................................................ 25

1.3. PRIMELE SISTEME DE BAZE DE DATE ............................................................................. 25 1.3.1. Baze de date ierarhice ................................................................................................... 26 1.3.2. Baze de date de tip rețea ............................................................................................... 26 1.3.3. Dezavantajele primelor SGBD-uri ............................................................................... 27 1.3.4. Sisteme de baze de date relaționale ............................................................................... 28

1.4. COMPONENTELE UNUI SISTEM ORIENTAT PE BAZE DE DATE ....................................... 29 1.4.1. Hardware-ul ................................................................................................................. 30 1.4.2. Programe-aplicații ........................................................................................................ 30 1.4.3. Datele............................................................................................................................ 30 1.4.4. Metadatele .................................................................................................................... 32 1.4.5. Componenta software ................................................................................................... 32 1.4.6. Utilizatorii bazei de date .............................................................................................. 33

1.5. ARHITECTURA BAZEI DE DATE CU TREI NIVELE ........................................................... 35 1.5.1. Nivelul intern ............................................................................................................... 36 1.5.2. Nivelul logic ................................................................................................................. 37 1.5.3. Nivelul extern............................................................................................................... 37 1.5.4. Independența datelor .................................................................................................... 38 1.5.5. Funcționarea arhitecturii cu trei nivele ....................................................................... 39

1.6. BAZE DE DATE POSTRELAȚIONALE ............................................................................... 39 1.6.1. Baze de date orientate pe obiecte ................................................................................... 40

4

1.6.2. Baze de date obiect-relaționale ..................................................................................... 41 1.6.3. Baze de date temporale ................................................................................................. 42

1.6.3.1. De ce o bază de date temporală? .................................................................................................. 42 1.6.3.2. Concepte de reprezentare temporală .......................................................................................... 43 1.6.3.3. Elemente primitive de reprezentare temporală ......................................................................... 44 1.6.3.4. Tipuri de baze de date temporale ................................................................................................ 45

1.6.4. Baze de date spațiale .................................................................................................... 45 1.6.5. Baze de date paralele și distribuite ............................................................................... 48

1.7. BAZE DE DATE AVANSATE ............................................................................................. 48 1.7.1. Baze de date active ....................................................................................................... 49 1.7.2. Baze de date multimedia .............................................................................................. 50 1.7.3. Bazele de date și tehnologiile Web ............................................................................... 50 1.7.4. Magazii de date ............................................................................................................ 51 1.7.5. Utilizarea XML în baze de date ................................................................................... 52 1.7.6. Descoperirea cunoştinţelor în baze de date .................................................................. 53 1.7.7. Baze de date deductive şi baze de cunoştinţe ............................................................... 55

2. BAZE DE DATE RELAȚIONALE ............................................................................57

2.1. STRUCTURA MODELULUI RELAȚIONAL ......................................................................... 57 2.1.1. Atribute și domenii ...................................................................................................... 57 2.1.2. Tupluri ......................................................................................................................... 59 2.1.3. Scheme și relații ........................................................................................................... 59

2.2. CONSTRÂNGERI DE INTEGRITATE ................................................................................. 61 2.2.1. Constrângeri de integritate structurale ....................................................................... 61

2.2.1.1. Constrângerile de unicitate și minimalitate a cheii ................................................................... 61 2.2.1.2. Constrângerea entității .................................................................................................................. 62 2.2.1.3. Constrângerea referențială ........................................................................................................... 63

2.2.2. Constrângeri de integritate de comportament ............................................................. 63 2.2.2.1. Constrângeri de comportament al domeniului ......................................................................... 64 2.2.2.2. Constrângeri de comportament al tuplului ................................................................................ 65 2.2.2.3. Constrângeri de comportament al relației .................................................................................. 65 2.2.2.4. Constrângeri de comportament al bazei de date ....................................................................... 66

2.3. ALGEBRA RELAȚIONALĂ ............................................................................................... 66

2.4. OPERAȚIILE TRADIȚIONALE PE MULȚIMI ...................................................................... 67 2.4.1. Scheme relaționale compatibile .................................................................................... 67 2.4.2. Uniunea ....................................................................................................................... 68 2.4.3. Diferența ...................................................................................................................... 69 2.4.4. Intersecția .................................................................................................................... 69 2.4.5. Produsul cartezian ....................................................................................................... 70 2.4.6. Operația de redenumire ............................................................................................... 71 2.4.7. Complementul .............................................................................................................. 72

2.5. OPERAȚIILE RELAȚIONALE NATIVE .............................................................................. 74 2.5.1. Proiecția ....................................................................................................................... 74

5

2.5.2. Selecția .......................................................................................................................... 75 2.5.3. Joncțiunea naturală ...................................................................................................... 76 2.5.4. Semijoncțiunea ............................................................................................................. 79 2.5.5. Joncțiunea theta ............................................................................................................ 80 2.5.6. Joncțiuni externe .......................................................................................................... 80 2.5.7. Divizarea ...................................................................................................................... 81

2.6. INTEROGĂRI ÎN ALGEBRA RELAȚIONALĂ ..................................................................... 82 2.6.1. Expresii algebrice ......................................................................................................... 83 2.6.2. Selecții generalizate ...................................................................................................... 84 2.6.3. Interogări conjunctive .................................................................................................. 84 2.6.4. Interogări neconjuctive ................................................................................................ 86

2.6.4.1. Interogări cu diferențe................................................................................................................... 86 2.6.4.2. Complementul unei mulțimi ........................................................................................................ 86 2.6.4.3. Cuantificarea universală ............................................................................................................... 87

2.6.5. Un exemplu integrator ................................................................................................. 87

3. SQL: INTEROGAREA ȘI ACTUALIZAREA BAZELOR DE DATE................ 89

3.1. PREZENTARE GENERALĂ ............................................................................................... 89 3.1.1. Premisele apariției limbajului SQL .............................................................................. 89 3.1.2. Scurt istoric .................................................................................................................. 90 3.1.3. Categoriile de instrucțiuni SQL ................................................................................... 91

3.2. CELE MAI SIMPLE INTEROGĂRI ..................................................................................... 92 3.2.1. Instrucțiunea SELECT ................................................................................................ 92 3.2.2. Clauza DISTINCT ....................................................................................................... 93 3.2.3. Clauza ORDER BY...................................................................................................... 94 3.2.4. Aliasuri de atribut ........................................................................................................ 95

3.3. INTEROGĂRI CU CRITERII DE SELECȚIE .......................................................................... 95 3.3.1. Clauza WHERE ........................................................................................................... 95 3.3.2. Operatorii de comparație .............................................................................................. 96 3.3.3. Operatorii logici ........................................................................................................... 97

3.3.3.1. Operatorul AND ............................................................................................................................ 97 3.3.3.2. Operatorul OR ................................................................................................................................ 97 3.3.3.3. Operatorul NOT ............................................................................................................................. 97 3.3.3.4. Ordinea de evaluare a operatorilor logici .................................................................................. 98

3.3.4. Operatorul IS NULL .................................................................................................... 98 3.3.5. Funcții cu utilizarea valorii NULL .............................................................................. 99

3.3.5.1. Funcția COALESCE ....................................................................................................................... 99 3.3.5.2. Funcția NVL ................................................................................................................................... 99 3.3.5.3. Funcția NULLIF ........................................................................................................................... 100

3.3.6. Operatorul IN............................................................................................................. 100 3.3.7. Operatorul BETWEEN .............................................................................................. 101 3.3.8. Operatorul LIKE ........................................................................................................ 101 3.3.9. Limitarea numărului de tupluri returnate ................................................................. 103

6

3.4. INTEROGĂRI CU AGREGĂRI ȘI GRUPĂRI ...................................................................... 103 3.4.1. Funcții de agregare .................................................................................................... 103

3.4.1.1. Funcția COUNT ........................................................................................................................... 104 3.4.1.2. Funcția AVG ................................................................................................................................. 105 3.4.1.3. Funcția SUM ................................................................................................................................. 105 3.4.1.4. Funcțiile MAX și MIN ................................................................................................................. 105

3.4.2. Clauza GROUP BY ................................................................................................... 106 3.4.3. Clauza HAVING ....................................................................................................... 107

3.5. INTEROGĂRI CU JONCȚIUNI ........................................................................................ 108 3.5.1. Produsul Cartezian .................................................................................................... 109 3.5.2. Joncțiuni interne ........................................................................................................ 110

3.5.2.1. Joncțiuni interne de egalitate ...................................................................................................... 110 3.5.2.2. Clauza USING .............................................................................................................................. 112 3.5.2.3. Joncțiuni naturale ......................................................................................................................... 113 3.5.2.4. O problemă a joncțiunii naturale ............................................................................................... 114 3.5.2.5. Aliasuri de relații sau variabile-tuplu ....................................................................................... 114 3.5.2.6. Joncțiunea unei relații cu ea însăși ............................................................................................. 115 3.5.2.7. Joncțiuni interne de inegalitate .................................................................................................. 116

3.5.3. Joncțiuni externe ........................................................................................................ 117 3.5.3.1. Returnarea tuplurilor nejoncționabile ....................................................................................... 117 3.5.3.2. Joncțiunea externă de stânga ...................................................................................................... 118 3.5.3.3. Joncțiunea externă de dreapta .................................................................................................... 118 3.5.3.4. Joncțiunea externă completă ...................................................................................................... 119

3.6. SUBINTEROGĂRI .......................................................................................................... 120 3.6.1. Tipuri de subinterogări .............................................................................................. 120 3.6.2. Subinterogări cu operatori de comparație .................................................................. 121 3.6.3. Subinterogări cu operatorul IN ................................................................................. 123 3.6.4. Subinterogări cu operatorul ANY ............................................................................. 125 3.6.5. Subinterogări cu operatorul ALL .............................................................................. 126 3.6.6. Subinterogări corelate și necorelate ........................................................................... 127 3.6.7. Subinterogări cu operatorul EXISTS ........................................................................ 129 3.6.8. Subinterogări în clauza FROM ................................................................................. 131 3.6.9. Subinterogări în clauza HAVING și în alte clauze ................................................... 132

3.7. INTEROGĂRI CU OPERATORI DIN TEORIA MULȚIMILOR.............................................. 132 3.7.1. Operatorii UNION și UNION ALL ......................................................................... 133 3.7.3. Operatorii EXCEPT și EXCEPT ALL ...................................................................... 134

3.8. INSTRUCȚIUNI DE ACTUALIZARE A BAZEI DE DATE ................................................... 135 3.8.1. Inserarea tuplurilor ................................................................................................... 135 3.8.2. Modificarea tuplurilor ............................................................................................... 136 3.8.3. Suprimarea tuplurilor ............................................................................................... 137

4. LIMBAJELE DE DEFINIRE ȘI CONTROL A DATELOR. SQL INTEGRAT ...................................................................................................................................... 139

4.1. DEFINIREA DATELOR ÎN SQL ...................................................................................... 139

7

4.1.1. Tipuri de date numerice ............................................................................................. 139 4.1.2. Tipuri de date secvențe de caractere ........................................................................... 140 4.1.3. Tipuri de date temporale............................................................................................. 141

4.2. DEFINIREA SCHEMEI BAZEI DE DATE .......................................................................... 141 4.2.1. Definirea constrângerilor de integritate ..................................................................... 141

4.2.1.1. Constrângerea NOT NULL ........................................................................................................ 142 4.2.1.2. Constrângerea DEFAULT........................................................................................................... 143 4.2.1.3. Definirea cheilor primare............................................................................................................ 143 4.2.1.4. Definirea cheilor externe ............................................................................................................. 143 4.2.1.5. Constrângerea UNIQUE ............................................................................................................. 144 4.2.1.6. Constrângerile de comportament CHECK ............................................................................... 145 4.2.1.7. Constrângeri de comportament CHECK la nivel de bază de date ....................................... 145

4.2.2. Definirea atributelor ................................................................................................... 146 4.2.3. Crearea schemei relaționale ........................................................................................ 147 4.2.4. Modificarea și suprimarea schemei relaționale .......................................................... 149

4.2.4.1. Adăugarea, modificarea și suprimarea atributelor ................................................................. 149 4.2.4.2. Adăugarea, modificarea și suprimarea constrângerilor ......................................................... 151 4.2.4.3. Amânarea verificării constrângerilor ........................................................................................ 153 4.2.4.4. Suprimarea schemei relaționale ................................................................................................. 153

4.3. GESTIUNEA VIZIUNILOR .............................................................................................. 154 4.3.1. Ce este o viziune? ....................................................................................................... 154 4.3.2. Crearea și suprimarea viziunilor ................................................................................ 155 4.3.3. Consultarea și actualizarea viziunilor ....................................................................... 157

4.3.3.1. Consultarea viziunilor ................................................................................................................ 157 4.3.3.2. Viziuni definite pe proiecții de atribute .................................................................................... 157 4.3.3.3. Viziuni definite pe selecții de tupluri ........................................................................................ 158 4.3.3.4. Viziuni definite pe o relație de interogări cu DISTINCT sau GROUP BY ........................... 159 4.3.3.5. Viziuni definite pe mai multe relații ......................................................................................... 161

4.3.4. Clasificarea viziunilor ................................................................................................ 161 4.3.5. Din nou despre opțiunea WITH CHECK OPTION ................................................. 163 4.3.6. Viziuni materializabile ............................................................................................... 164 4.3.7. Utilitatea viziunilor ................................................................................................... 164

4.4. SINONIME .................................................................................................................... 165

4.5. INDECȘI ........................................................................................................................ 166 4.5.1. Crearea și suprimarea indecșilor ................................................................................ 167 4.5.2. Utilitatea indecșilor .................................................................................................... 168 4.5.3. Tipuri de indecși ......................................................................................................... 169

4.5.3.1. Indecșii B+-arbori ......................................................................................................................... 169 4.5.3.2. Indecșii bitmap ............................................................................................................................. 169 4.5.3.3. Indexul de tip tabele cu dispersie .............................................................................................. 170 4.5.3.4. Indecși pe valori de funcții ......................................................................................................... 170

4.6. CONTROLUL ACCESULUI LA BAZA DE DATE ............................................................... 170 4.6.1. Drepturi de acces ........................................................................................................ 170 4.6.2. Acordarea și retragerea drepturilor ............................................................................ 171

4.7. ADMINISTRAREA TRANZACȚIILOR ............................................................................. 172

8

4.7.1. Proprietățile tranzacțiilor .......................................................................................... 172 4.7.2. Modele de tranzacții .................................................................................................. 173

4.7.2.1. Tranzacții în SQL ......................................................................................................................... 173 4.7.2.2. Tranzacții imbricate ..................................................................................................................... 173 4.7.2.3. Puncte de reluare ......................................................................................................................... 174

4.7.3. Anomalii de execuție concurentă a tranzacțiilor ....................................................... 174 4.7.4. Blocarea relațiilor și gestiunea tranzacțiilor .............................................................. 175 4.7.5. Serializarea tranzacțiilor ........................................................................................... 176 4.7.6. Niveluri de izolare a tranzacțiilor .............................................................................. 176

4.8. LIMBAJUL SQL INTEGRAT ........................................................................................... 178 4.8.1. Structura unui program cu SQL încorporat ............................................................. 179

4.8.1.1. Delimitatoarele ............................................................................................................................. 179 4.8.1.2. Aria de comunicație a SQL ......................................................................................................... 180 4.8.1.3. Variabilele programului .............................................................................................................. 181

4.8.2. Manipularea datelor fără cursoare............................................................................. 182 4.8.3. Manipularea datelor cu cursoare ............................................................................... 183 4.8.4. Un exemplu integrator .............................................................................................. 184

5. PROPRIETĂȚI OBIECT-RELAȚIONALE ÎN STANDARDUL SQL3 .......... 187

5.1. DECLANȘATOARELE ȘI STANDARDUL SQL3 .............................................................. 187 5.1.1. Definirea declanșatoarelor ......................................................................................... 188 5.1.2. Evenimente ................................................................................................................ 189

5.1.2.1. Momentul de activare.................................................................................................................. 189 5.1.2.2. Granularitatea ............................................................................................................................... 190 5.1.2.3. Nume de corelație ........................................................................................................................ 190

5.1.3. Condiții ...................................................................................................................... 191 5.1.4. Acțiuni ....................................................................................................................... 191 5.1.5. Gestionarea constrângerilor de integritate ................................................................ 192

5.1.5.1. Gestionarea constrângerilor de domeniu ................................................................................. 193 5.1.5.2. Gestionarea constrângerilor de tuplu........................................................................................ 194

5.2. LIMBAJUL SQL3 ȘI MODELUL OBIECT-RELAȚIONAL................................................... 196 5.2.1. Tipuri de date compuse .............................................................................................. 196

5.2.1.1.Tipul de date ARRAY ................................................................................................................... 196 5.2.1.2. Tipul de date ROW ...................................................................................................................... 196

5.2.2. Tipuri colecție ............................................................................................................ 197 5.2.3. Tipuri de date definite de utilizator ........................................................................... 197

5.2.3.1. DISTINCT TYPES ........................................................................................................................ 197 5.2.3.2. Tipuri de date structurate definite de utilizator ...................................................................... 198

5.2.4. Relații cu tupluri-obiecte ........................................................................................... 199 5.2.5. Moștenirea ................................................................................................................. 199 5.2.6. Referire la tip ca la domeniul unui atribut ................................................................ 201 5.2.7. Relații imbricate ......................................................................................................... 202

5.3. OBIECTE MARI .............................................................................................................. 203

6. MULȚIMI DE DEPENDENȚE FUNCȚIONALE ............................................... 205

9

6.1. NOȚIUNI ȘI CONCEPTE DE BAZĂ ................................................................................. 205

6.2. IMPLICAȚII LOGICE ALE DEPENDENȚELOR ................................................................. 207 6.2.1. Reguli de inferență ..................................................................................................... 208 6.2.2. Axiomele Armstrong .................................................................................................. 209

6.3. MODELE DE DERIVĂRI ................................................................................................. 211 6.3.1. RAP–derivări ............................................................................................................. 211 6.3.2. Arbori de derivare ....................................................................................................... 212 6.3.3. DDA-graf derivări ..................................................................................................... 213 6.3.4. Derivarea maximală ................................................................................................... 214

6.4. ASPECTE ALGORITMICE ............................................................................................... 216

6.5. ACOPERIRI DE DEPENDENȚE FUNCȚIONALE .............................................................. 218 6.5.1. Mulțimi echivalente de dependențe funcționale ......................................................... 218 6.5.2. Acoperiri neredundante .............................................................................................. 219 6.5.3. Acoperiri reduse ......................................................................................................... 220 6.5.4. Acoperiri canonice ...................................................................................................... 222

6.6. RELAȚII DE ECHIVALENȚĂ PE MULȚIMI DE DEPENDENȚE FUNCȚIONALE ................. 223 6.6.1. Clase de echivalență .................................................................................................... 223 6.6.2. Acoperiri minimale ..................................................................................................... 224 6.6.3. Acoperiri optimale ...................................................................................................... 227 6.6.4. Relațiile între acoperiri ............................................................................................... 227

7. PROIECTAREA SCHEMELOR RELAȚIONALE NORMALE ........................ 229

7.1. SCHEMA BAZEI DE DATE ȘI PROPRIETĂȚILE ACESTEIA ............................................... 230 7.1.1. Ipoteza schemei universale ......................................................................................... 230 7.1.2. Proprietatea joncțiunii fără pierderi ........................................................................... 231 7.1.3. Conservarea dependențelor ........................................................................................ 231

7.2. REDUNDANȚA DATELOR ȘI ANOMALII LA ACTUALIZARE ......................................... 234

7.3. FORME NORMALE CU DEPENDENȚE FUNCȚIONALE ................................................... 235 7.3.1. Forma normală unu ................................................................................................... 235 7.3.2. Forma normală doi ..................................................................................................... 237 7.3.3. Forma normală trei ..................................................................................................... 239 7.3.4. Forma normală Boyce-Codd ....................................................................................... 241

7.4. NORMALIZAREA BAZELOR DE DATE PRIN DESCOMPUNERE ...................................... 243 7.4.1. Descompunerea în două scheme relaționale ............................................................... 243 7.4.2. Descompunerea fără pierderi în forma normală Boyce-Codd .................................... 243 7.4.3. Descompunerea fără pierderi în forma normală trei .................................................. 244 7.4.4. Descompunerea fără pierderi în forma normală trei cu conservarea dependențelor .. 245 7.4.5. Dezavantajele normalizării prin descompunere ......................................................... 246

7.5. NORMALIZAREA BAZELOR DE DATE PRIN SINTEZĂ ................................................... 248 7.5.1. Validitatea în normalizarea prin sinteza .................................................................... 248 7.5.2. Algoritmul de sinteză ................................................................................................. 249

10

7.5.3. Un exemplu de normalizare prin sinteză .................................................................. 251

8. SCHEME NORMALE CU DEPENDENȚE MULTIVALOARE ȘI DEPENDENȚE JONCȚIUNE ................................................................................. 253

8.1. DEPENDENȚE MULTIVALOARE .................................................................................... 253 8.1.1. Proprietăți ale dependențelor multivaloare................................................................ 254 8.1.2. Reguli de inferență a dependențelor multivaloare ..................................................... 255 8.1.3. Reguli de inferență redundante ................................................................................. 256 8.1.4. Reguli de inferență mixte ........................................................................................... 257

8.2. DEDUCEREA DEPENDENŢELOR MULTIVALOARE ........................................................ 257 8.2.1. Baza dependențelor .................................................................................................... 257 8.2.2. Algoritmul de calcularea a bazei dependențelor ........................................................ 259 8.2.3. Problema calității de membru .................................................................................... 260 8.2.4. Acoperiri neredundante cu dependențe multivaloare ................................................ 260 8.2.5. Dependențe multivaloare incluse .............................................................................. 261 8.2.6. Dependențe multivaloare noncontradictorii .............................................................. 262

8.3. DEPENDENȚE JONCȚIUNE ........................................................................................... 263 8.3.1. Dependențe joncțiune complete și incluse ................................................................. 263 8.3.2. Testarea dependențelor joncțiune .............................................................................. 264

8.3.2.1. Tablouri ......................................................................................................................................... 264 8.3.2.2. Un algoritm de testare a dependențelor joncțiune .................................................................. 266

8.3.3. Reguli de inferență a dependențelor joncțiune .......................................................... 268

8.4. FORMA NORMALĂ PATRU ........................................................................................... 269 8.4.1. Concepte și noțiuni utilizate ...................................................................................... 269 8.4.2. Algoritmul de descompunere în FN4 ........................................................................ 270

8.5. FORMA NORMALĂ PROIECȚIE-JONCȚIUNE ................................................................. 272

8.6. DENORMALIZAREA BAZEI DE DATE ............................................................................ 272 8.6.1. Două dezavantaje ale normalizării ............................................................................ 273 8.6.2. Când normalizarea este necesară? Semnele și cazurile ............................................. 273

8.6.2.1. Un număr mare de joncțiuni intre relații .................................................................................. 273 8.6.2.2. Expresii cu valori calculate ......................................................................................................... 274 8.6.2.3. Volume mari de date ................................................................................................................... 274

8.6.3. Cum se determină când denormalizare este justificată? ........................................... 275 8.6.3.1. Costuri și beneficii ....................................................................................................................... 275 8.6.3.2. Frecvența interogărilor și de performanță a durabilității ....................................................... 275

8.6.4. Cum denormalizarea poate fi aplicată în mod corect? ............................................... 275

9. ORGANIZAREA FIȘIERELOR ÎN BAZA DE DATE ....................................... 277

9.1. STOCAREA DATELOR ................................................................................................... 277 9.1.1. Dispozitive de stocare a datelor ................................................................................. 277 9.1.2. Funcționarea discului magnetic ................................................................................ 278

9.1.2.1. Dispozitivul .................................................................................................................................. 278 9.1.2.2. Accesul la date .............................................................................................................................. 279

11

9.1.3. Optimizarea accesului la date .................................................................................... 280 9.1.3.1. Regruparea datelor ...................................................................................................................... 280 9.1.3.2. Reordonarea accesului la date ................................................................................................... 282 9.1.3.3. Utilizarea memoriei tampon ...................................................................................................... 282

9.1.4. Tehnologiile RAID ..................................................................................................... 283 9.1.4.1. Distribuirea fără paritate a datelor (RAID 0) ........................................................................... 284 9.1.4.2. Duplicarea datelor (RAID 1) ...................................................................................................... 284 9.1.4.3. Coduri corectoare de erori de tip Hamming (RAID 2) ........................................................... 285 9.1.4.4. Discuri paralele cu paritate (RAID 3) ........................................................................................ 285 9.1.4.5. Distribuirea blocurilor cu paritate (RAID 4) ............................................................................ 286 9.1.4.6. Distribuirea datelor de paritate (RAID 5) ................................................................................. 288 9.1.4.7. Deteriorarea simultană (RAID 6) ............................................................................................... 289 9.1.4.8. Selectarea și implementarea tehnologiilor RAID .................................................................... 289

9.2. CONCEPTE GENERALE DE ORGANIZARE A FIȘIERELOR .............................................. 290 9.2.1. Câmpuri și înregistrări .............................................................................................. 291

9.2.1.1. Câmpuri cu lungime fixă și lungime variabilă ........................................................................ 291 9.2.1.2. Antetul înregistrării ..................................................................................................................... 292

9.2.2. Blocuri ........................................................................................................................ 293 9.2.2.1. Structura blocului ........................................................................................................................ 293 9.2.2.2. Blocuri cu înregistrări de lungime variabilă ............................................................................ 294

9.2.3. Chei ............................................................................................................................. 295

9.3. FIȘIERE SECVENȚIALE .................................................................................................. 296 9.3.1. Fișiere secvențiale ordonate ........................................................................................ 296

9.3.1.1. Consultarea cu cheia de acces diferită de cheia de ordonare ................................................ 298 9.3.1.2. Consultarea cu cheia de acces egală cu cheia de ordonare .................................................... 298 9.3.1.3. Inserarea înregistrărilor .............................................................................................................. 298 9.3.1.4. Suprimarea înregistrărilor .......................................................................................................... 299 9.3.1.5. Modificarea înregistrărilor ......................................................................................................... 299 9.3.1.6. Lectura exhaustivă a înregistrărilor .......................................................................................... 300

9.3.2. Fișiere secvențiale ordonate la nivel logic de pointeri ................................................ 300 9.3.2.1. Consultarea înregistrărilor ......................................................................................................... 301 9.3.2.2. Includerea înregistrărilor ............................................................................................................ 301 9.3.2.3. Excluderea și modificarea înregistrărilor ................................................................................. 302

9.3.3. Fișiere secvențiale cu spațiu de tranzacții .................................................................. 302 9.3.3.1. Fișiere secvențiale cu toate operațiile în fișierul de tranzacții ............................................... 303 9.3.3.2. Fișiere secvențiale cu unele operații în fișierul principal ....................................................... 304 9.3.3.3. Reorganizarea fișierelor .............................................................................................................. 305

9.3.4. Căutarea secvențială cu blocuri de înregistrări .......................................................... 306

9.4. INDECȘI ........................................................................................................................ 306 9.4.1. Concepte preliminare .................................................................................................. 307 9.4.2. Indecși ordonați .......................................................................................................... 309

9.4.2.1. Indecși primari ............................................................................................................................. 309 9.4.2.2. Indecși secundari ......................................................................................................................... 310 9.4.2.3. Indecși multinivel ........................................................................................................................ 310

9.4.3. Indecși cu dispersie ..................................................................................................... 310

9.5. FIȘIERE INDEXAT SECVENȚIALE ................................................................................... 311 9.5.1. Structuri ale fișierelor indexat secvențiale ................................................................. 311

12

9.5.2. Fișierele indexat secvențiale și dispozitivele de stocare ............................................. 313 9.5.3. Operații cu fișiere indexat secvențiale ....................................................................... 314

9.5.3.1. Deschiderea și închiderea fișierelor ........................................................................................... 314 9.5.3.2. Consultarea înregistrărilor.......................................................................................................... 315 9.5.3.3. Inserarea înregistrărilor............................................................................................................... 315 9.5.3.4. Excluderea înregistrărilor ........................................................................................................... 316 9.5.3.5. Modificarea înregistrărilor .......................................................................................................... 316 9.5.3.6. Lectura exhaustivă a înregistrărilor .......................................................................................... 317 9.5.3.7. Reorganizarea fișierelor .............................................................................................................. 317

9.6. FIȘIERE INDEXATE ........................................................................................................ 317 9.6.1. Structuri și operații în fișierele indexate ................................................................... 318 9.6.2. Fișiere inversate ......................................................................................................... 319 9.6.3. Indecși Bitmap ........................................................................................................... 320 9.6.4. Arborii binari ............................................................................................................. 320 9.6.5. B-arbori ...................................................................................................................... 321 9.6.6. B+-arbori .................................................................................................................... 322

9.7. FIȘIERE CU DISPERSIE ................................................................................................... 323 9.7.1. Caracteristicile fișierelor cu dispersie ........................................................................ 323 9.7.2. Adresarea directă ....................................................................................................... 325 9.7.3. Adresarea indirectă .................................................................................................... 326 9.7.4. Calcularea adresei ...................................................................................................... 327

9.7.4.1. Funcția de dispersie “restul de la împărțire” ........................................................................... 328 9.7.4.2. Metoda înmulțirii ......................................................................................................................... 328 9.7.4.3. Metoda transformarea sistemelor de numerație...................................................................... 329 9.7.4.4. Metoda împărțirea polinoamelor ............................................................................................... 329

9.7.5. Tratarea coliziunilor .................................................................................................. 329 9.7.5.1. Tratarea cu adresare deschisă .................................................................................................... 330 9.7.5.2. Tratarea prin înlănțuire ............................................................................................................... 331

BIBLIOGRAFIE ............................................................................................................ 333