Bases dedonnes

GEORGES GARDARIN

E Y R O L L E S

Bestf o

E Y R O L L E S

Best f o

Bases de donnes

La rfrence en langue franaise sur les bases de donnes

Les bases de donnes jouent un rle sans cesse croissant dans lessystmes dinformation dentreprise, quil sagisse dapplications degestion traditionnelles (comptabilit, ventes, dcisionnel) ou dappli-cations intranet, e-commerce ou de gestion de la relation client.Comprendre les principes des bases de donnes, les langages dinter-rogation et de mise jour, les techniques doptimisation et de contrledes requtes, les mthodes de conception et la gestion des transac-tions devient une ncessit pour tous les professionnels et futursprofessionnels de linformatique.Complet et didactique, louvrage se caractrise par des dfinitionsprcises des concepts, une approche clairante des algorithmes etmthodes, de nombreux exemples dapplication, une bibliographiecommente en fin de chaque chapitre et un recueil dexercices en findouvrage. Il traite aussi bien des bases de donnes relationnelles, quedes bases de donnes objet et objet-relationnelles.

Au sommaire

Les fondements. Principes et architecture des SGBD (systmes de ges-tion de bases de donnes) Fichiers, hachage et indexation Bases dedonnes rseau et hirarchiques Logique et bases de donnes. Basesde donnes relationnelles. Le modle relationnel : rgles dintgritet algbre relationnelle Le langage SQL2 Contraintes dintgrit etdclencheurs Gestion des vues Optimisation des requtes. Bases dedonnes objet et objet-relationnelles. Le modle objet et la persis-tance des objets Le standard de lOMG : ODL, OQL et OML Lobjet-relationnel et SQL3 Optimisation des requtes objet. Au-del duSGBD. Bases de donnes dductives Gestion des transactions Conception des bases de donnes : schmas conceptuel et logiqueavec UML, dpendances fonctionnelles, formes normales Bases dedonnes et dcisonnel, Web et bases de donnes, bases de donnesmultimdias.

Georges Gardarin Chercheur renomm dans le domaine des bases de donnes et professeur luniversit Paris 6 puis luniversit de Versailles Saint-Quentin, Georges Gardarina cr et dirig successivementun projet de recherche INRIAsur les BD relationnellesparallles (1980-89), le laboratoire PRiSM de Versailles(1990-99), qui regroupe une centaine de spcialistes en rseaux, bases de donnes et paralllisme, et enfin la socite-XMLmedia (2000-2002),diteur de composants XML. Il est aujourdhui professeur luniversit de Versailles et participe des projets de recherche europens en mdiation de donneshtrognes.

Code diteur : G11281ISBN : 2-212-11281-5

Con

cept

ion

Nor

d Com

po

Basesde donnes

Basesde donnes

Georges Gardarin

5e tirage 2003

EYROLLES

EDITIONS EYROLLES61, bd, Saint-Germain75240 Paris cedex 05

www.editions-eyrolles.com

En application de la loi du 11 mars 1957, il est interdit de reproduire intgralement oupartiellement le prsent ouvrage, sur quelque support que ce soit, sans autorisation de lditeur ou duCentre Franais dExploitation du Droit de Copie, 20, rue des Grands-Augustins, 75006 Paris. Groupe Eyrolles 1999 Groupe Eyrolles 2003, pour la nouvelle prsentation, ISBN 2-212-11281-5

Cet ouvrage a fait lobjet dun reconditionnement loccasion de son 5e tirage (format semi-poche et nouvelle couverture).

Le texte de louvrage reste inchang par rapport aux tirages prcdents.

ma petite fille, Marie, ne la fin de la gestation de ce livre,

avec lespoir que les Bases de Donnes laideront mieux vivre et comprendre.

REMERCIEMENTS

Je tiens exprimer mes vifs remerciements tous ceux qui, par leurs travaux, leursides, leurs prsentations, leurs collaborations ou leurs relectures, ont particip de prsou de loin la ralisation de cet ouvrage, en particulier :

Catherine Blirando, Christophe Bobineau, Luc Bouganim, Mokrane Bouzeghoub,Tatiana Chan, Jean-Luc Darroux, Thierry Delot, Franoise Fabret, Batrice Finance,Dana Florescu, lisabeth Mtais, Philippe Pucheral, Fei Sha, ric Simon, Tuyet TramDang Ngoc, Patrick Valduriez, Yann Vimont, Fei Wu, Karine Zeitouni.

Une mention particulire Hlne qui ma support pendant tous ces nombreuxweek-ends et vacances passs rdiger.

AVANT-PROPOS

Jai commenc travailler dans le domaine des bases de donnes en 1968 luniver-sit de Paris VI (non, pas en lanant des pavs), alors que le modle rseau pointaitderrire les fichiers squentiels puis indexs. Sous la direction de Michel Rocher quifut plus tard directeur dOracle France, avec Mireille Jouve, Christine Parent, RichardGomez, Stefano Spaccapietra et quelques autres, nous avions dvelopp une famillede Systmes de Fichiers pour Apprendre Les Autres : les SFALA. Nous enseignionsessentiellement les mthodes daccs squentielles, indexes, haches, et surtout lesystme. Bientt (en 1972), nous avons introduit les Systmes de Donnes pourApprendre Les Autres (SDALA). Il y eut un SDALA bas sur le modle rseau, puisbientt un bas sur le modle relationnel. Aujourdhui, on pourrait faire un SDALAobjet, multimdia, et bientt semi-structur...

Le premier systme de gestion de donnes que jai construit lHopital Necker graitun disque SAGEM ttes fixes de 256 K octets ! Ceci me semblait norme par rap-port au 8 K de mmoire. Le systme grait les dossiers des malades avec des fichiershachs. Ctait en 1969 alors que jtais encore lve lENSET et stagiaire TITN.Le deuxime le fut OrdoProcesseurs, une socit franaise qui vendait des mini-ordinateurs franais. Ctait en 1974 et les disques atteignaient dj 10 mga-octets.Le troisime le fut lINRIA au dbut des annes 1980 : ctait lun des trop raressystmes relationnels franais commercialiss, le SGBD SABRE. Les disques dpas-saient dj 100 M octets ! Aujourdhui, les disques contiennent plusieurs giga-octetset lon parle de ptabases (10 puissance 15 octets). Demain, et demain est dj l,avec lintgration des rseaux et des bases de donnes, tous les serveurs de donnesdu monde seront interconnects et lon grera des volumes inimaginables de donnesen ligne par des techniques plus ou moins issues des bases de donnes...

Alors que les bases de donnes semblaient au dbut rserves quelques applicationssophistiques de gestion, toute application moderne utilise aujourdhui une base dedonnes sous une forme ou sous une autre. Certes, il y a encore beaucoup de donnesdans des fichiers, mais lquilibre o plutt le dsquilibre se dplace. Toute

application de gestion non vieillotte utilise une BD relationnelle, les BD objets per-cent dans les applications donnes complexes, et les serveurs Web sappuient deplus en plus sur des bases de donnes. Pourquoi ? Car les BD offrent le partage, la fia-bilit, les facilits de recherche et bientt la souplesse et lintelligence avec le supportde donnes multimdia et semi-structures, et de techniques venues de lintelligenceartificielle, telles le data mining. Les BD sont de plus en plus distribues, intgresavec les rseaux Intranet et Internet. Do leur gnralisation.

Voil donc un domaine que jai eu la chance de traverser depuis sa naissance qui acr beaucoup demplois et qui va continuer en crer dans le millnaire qui vient. Levingt et unime sicle devrait tre celui des sciences et techniques de linformation, aumoins son dbut. Certains mobjecteront que lon a cr beaucoup de formulaires,alourdi la gestion et plus gnralement la socit, et aussi dtruit les petits emplois.Peut-tre, mais ce nest pas lobjectif, et ceci devrait tre corrig (notamment avec lesformulaires en ligne). Dautres objecteront que nous crons (avec Internet notamment)une civilisation deux vitesses : je le crains malheureusement, et voil pourquoi il esttrs ncessaire de simplifier et dmystifier, par exemple en crivant des livres essayantde mettre ces techniques la porte de tous.

Dans le domaine des bases de donnes, comme dans beaucoup dautres, la France agch beaucoup de chances, mais reste encore trs comptitive, au moins en comp-tences sinon en produits. En fait, depuis septembre 1997, lindustrie franaise ne pos-sde plus de SGBD important. Auparavant, elle avait possd SOCRATE, IDS II,SABRE (un SGBD important pour lauteur), et enfin O2. vrai dire, le seul bienvendu fut IDS.II, un produit issu des tats-Unis. Mais enfin, nous avions la matrisede la technologie...

Ce livre prsente une synthse des principes et des techniques actuelles en matire debase de donnes. Il traite des bases de donnes relationnelles et des bases de donnesobjet. Ces paradigmes sont au cur des systmes dinformation daujourdhui. Ilssont essentiels pour les entreprises et mritent dtre connus de tout tudiant lUniversit ou en cole dingnieur.

Ce livre est accompagn dun compagnon plus petit traitant des nouvelles techniques :data warehouse, data mining, BD Web et BD multimdia. Il sagit l des nouveauxthmes en vogue du domaine, qui vont sans doute profondment rvolutionner linfor-matique de demain. Nous avons choisi de ne pas intgrer ces sujets ce livre mais un volume spar, car ils ne sont pas encore stabiliss, alors que le relationnel etlobjet ainsi que le mlange des deux, connu sous le nom objet-relationnel le sontbeaucoup plus.

En rsum, cet ouvrage est le fruit dune exprience de trente ans denseignement, deformation et de conseil luniversit et dans lindustrie. Il aborde tous les sujets aucur des systmes dinformation modernes. Chaque chapitre traite un thme particu-lier. laide de notions prcisment dfinies une technique denseignement inven-

IV BASES DE DONNES : OBJET ET RELATIONNEL

te par Michel Rocher dans les annes 1970, procdant par dfinitions informelles ,nous clarifions des concepts souvent difficiles.

En annexe de cet ouvrage, vous trouverez une cinquantaine de textes dexercices quidrivent de sujets dexamens proposs aux tudiants Paris VI ou Versailles depuis1980, adapts et moderniss.

Avec cet ouvrage, nous esprons mettre entre les mains des gnrations actuelles etfutures denseignants, dingnieurs et de chercheurs une exprience pratique et tho-rique exceptionnelle en matire de bases de donnes.

Avant-propos V

NOTATIONS

Afin de prsenter la syntaxe de certains langages, nous utiliserons les notations sui-vantes :

[a] signifie que llment a est optionnel ;

[a]... signifie que llment a peut-tre rpt 0 n fois (n entier positif) ;

{a b} signifie que les lments a et b sont considrs comme un lment unique ;

{a | b} signifie un choix possible entre lalternative a ou b ;

< a > signifie que a est un paramtre qui doit tre remplac par une valeur effective.

SOMMAIRE

CHAPITRE I INTRODUCTION ............................................................................................................ 3

1. QUEST-CE QUUNE BASE DE DONNES ?.................................................................. 3

2. HISTORIQUE DES SGBD .................................................................................................................... 6

3. PLAN DE CET OUVRAGE.................................................................................................................. 7

4. BIBLIOGRAPHIE.......................................................................................................................................... 10

CHAPITRE II OBJECTIFS ET ARCHITECTURE DES SGBD .......................... 13

1. INTRODUCTION........................................................................................................................................... 13

2. MODLISATION DES DONNES............................................................................................... 152.1 Instances et schmas ........................................................................................................................ 152.2. Niveaux dabstraction ..................................................................................................................... 16

2.2.1. Le niveau conceptuel........................................................................................................ 172.2.2. Le niveau interne ................................................................................................................. 182.2.3. Le niveau externe................................................................................................................. 182.2.4. Synthse des niveaux de schmas.......................................................................... 19

2.3. Le modle entit-association..................................................................................................... 20

3. OBJECTIFS DES SGBD.......................................................................................................................... 233.1. Indpendance physique.................................................................................................................. 243.2. Indpendance logique ..................................................................................................................... 253.3. Manipulation des donnes par des langages non procduraux.................... 263.4. Administration facilite des donnes................................................................................. 26

PARTIE 1 LES BASES

3.5. Efficacit des accs aux donnes........................................................................................... 273.6. Redondance contrle des donnes..................................................................................... 283.7. Cohrence des donnes.................................................................................................................. 283.8. Partage des donnes.......................................................................................................................... 283.9. Scurit des donnes ........................................................................................................................ 29

4. FONCTIONS DES SGBD....................................................................................................................... 294.1. Description des donnes ............................................................................................................... 304.2. Recherche de donnes..................................................................................................................... 324.3. Mise jour des donnes ................................................................................................................ 334.4. Transformation des donnes...................................................................................................... 354.5. Contrle de lintgrit des donnes..................................................................................... 374.6. Gestion de transactions et scurit....................................................................................... 374.7. Autres fonctions ................................................................................................................................... 38

5. ARCHITECTURE FONCTIONNELLE DES SGBD..................................................... 395.1. Larchitecture trois niveaux de lANSI/X3/SPARC ......................................... 395.2. Une architecture fonctionnelle de rfrence................................................................ 425.3. Larchitecture du DBTG CODASYL ................................................................................ 44

6. ARCHITECTURES OPRATIONNELLES DES SGBD........................................... 456.1. Les architectures client-serveur .............................................................................................. 456.2. Les architectures rparties........................................................................................................... 49

7. CONCLUSION ................................................................................................................................................. 50

8. BIBLIOGRAPHIE.......................................................................................................................................... 51

CHAPITRE III FICHIERS, HACHAGE ET INDEXATION..................................... 55

1. INTRODUCTION........................................................................................................................................... 55

2. OBJECTIFS ET NOTIONS DE BASE........................................................................................ 572.1. Gestion des disques magntiques.......................................................................................... 572.2. Indpendance des programmes par rapport

aux mmoires secondaires........................................................................................................... 602.3. Utilisation de langages htes .................................................................................................... 612.4. Possibilits daccs squentiel et slectif....................................................................... 622.5. Possibilit dutilisateurs multiples ....................................................................................... 632.6. Scurit et protection des fichiers......................................................................................... 64

X BASES DE DONNES : OBJET ET RELATIONNEL

3. FONCTIONS DUN GRANT DE FICHIERS................................................................... 643.1. Architecture dun gestionnaire de fichiers .................................................................... 643.2. Fonctions du noyau dun gestionnaire de fichiers .................................................. 66

3.2.1. Manipulation des fichiers............................................................................................. 663.2.2. Adressage relatif................................................................................................................... 663.2.3. Allocation de la place sur mmoires secondaires ................................... 673.2.4. Localisation des fichiers sur les volumes ....................................................... 683.2.5. Classification des fichiers en hirarchie ......................................................... 693.2.6. Contrle des fichiers......................................................................................................... 71

3.3. Stratgie dallocation de la mmoire secondaire..................................................... 713.3.1. Objectifs dune stratgie ............................................................................................... 713.3.2. Stratgie par granule ( rgion fixe).................................................................. 723.3.3. Stratgie par rgion ( rgion variable) ......................................................... 72

4. ORGANISATIONS ET MTHODES DACCS PAR HACHAGE ................. 734.1. Organisation hache statique .................................................................................................... 734.2. Organisations haches dynamiques..................................................................................... 76

4.2.1. Principes du hachage dynamique ......................................................................... 764.2.2. Le hachage extensible...................................................................................................... 774.2.3. Le hachage linaire ........................................................................................................... 79

5. ORGANISATIONS ET MTHODES DACCS INDEXES.............................. 815.1. Principes des organisations indexes ................................................................................. 81

5.1.1. Notion dindex........................................................................................................................ 815.1.2. Variantes possibles............................................................................................................. 825.1.3. Index hirarchis ................................................................................................................. 845.1.4. Arbres B ....................................................................................................................................... 845.1.5. Arbre B+ ..................................................................................................................................... 88

5.2 Organisation indexe IS3 ............................................................................................................. 895.3. Organisation squentielle indexe ISAM....................................................................... 91

5.3.1. Prsentation gnrale...................................................................................................... 915.3.2. tude de la zone primaire ............................................................................................ 925.3.3. tude de la zone de dbordement.......................................................................... 925.3.4. tude de la zone index .................................................................................................... 935.3.5. Vue densemble...................................................................................................................... 94

5.4. Organisation squentielle indexe rgulire VSAM ............................................ 955.4.1. Prsentation gnrale...................................................................................................... 955.4.2. tude de la zone des donnes ................................................................................... 955.4.3. tude de la zone index .................................................................................................... 975.4.4. Vue densemble...................................................................................................................... 98

6. MTHODES DACCS MULTI-ATTRIBUTS................................................................... 996.1. Index secondaires................................................................................................................................ 99

Sommaire XI

6.2. Hachage multi-attribut.................................................................................................................... 1016.2.1. Hachage multi-attribut statique .............................................................................. 1016.2.2. Hachages multi-attributs dynamiques ............................................................... 101

6.3. Index bitmap............................................................................................................................................ 104

7. CONCLUSION ................................................................................................................................................. 106

8. BIBLIOGRAPHIE.......................................................................................................................................... 107

CHAPITRE IV BASES DE DONNES RSEAUX ET HIRARCHIQUES .......................................................................................................................................... 111

1. INTRODUCTION........................................................................................................................................... 111

2. LE MODLE RSEAU............................................................................................................................. 1122.1. Introduction et notations............................................................................................................... 1122.2. La dfinition des objets.................................................................................................................. 1132.3. La dfinition des associations .................................................................................................. 1152.4. Lordonnancement des articles dans les liens............................................................. 1192.5. La slection doccurrence dun type de lien................................................................ 1212.6 Les options dinsertion dans un lien................................................................................... 1222.7. Le placement des articles ............................................................................................................. 1222.8. Exemple de schma........................................................................................................................... 125

3. LE LANGAGE DE MANIPULATION COBOL-CODASYL................................. 1273.1. Sous-schma COBOL..................................................................................................................... 1273.2. La navigation CODASYL ........................................................................................................... 1283.3. La recherche darticles ................................................................................................................... 129

3.3.1. La recherche sur cl .......................................................................................................... 1303.3.2. La recherche dans un fichier ..................................................................................... 1303.3.3. La recherche dans une occurrence de lien .................................................... 1313.3.4. Le positionnement du curseur de programme ............................................ 132

3.4. Les changes darticles .................................................................................................................. 1323.5. Les mises jour darticles........................................................................................................... 132

3.5.1. Suppression darticles ..................................................................................................... 1333.5.2. Modification darticles ................................................................................................... 1333.5.3. Insertion et suppression dans une occurrence de lien......................... 133

3.6. Le contrle des fichiers.................................................................................................................. 1343.7. Quelques exemples de transaction ....................................................................................... 134

4. LE MODLE HIRARCHIQUE...................................................................................................... 1364.1. Les concepts du modle ................................................................................................................ 136

XII BASES DE DONNES : OBJET ET RELATIONNEL

4.2. Introduction au langage DL1.................................................................................................... 1384.3. Quelques exemples de transactions..................................................................................... 141

5. CONCLUSION ................................................................................................................................................. 143

6. BIBLIOGRAPHIE.......................................................................................................................................... 144

CHAPITRE V LOGIQUE ET BASES DE DONNES ..................................................... 147

1. INTRODUCTION........................................................................................................................................... 147

2. LA LOGIQUE DU PREMIER ORDRE...................................................................................... 1482.1. Syntaxe de la logique du premier ordre........................................................................... 1482.2. Smantique de la logique du premier ordre ................................................................. 1502.3 Forme clausale des formules fermes ............................................................................... 151

3. LES BASE DE DONNES LOGIQUE....................................................................................... 1533.1. La reprsentation des faits........................................................................................................... 1533.2. Questions et contraintes dintgrit..................................................................................... 155

4. LE CALCUL DE DOMAINES........................................................................................................... 1564.1 Principes de base ................................................................................................................................. 1564.2. Quelques exemples de calcul de domaine ..................................................................... 1574.3. Le langage QBE................................................................................................................................... 158

5. LE CALCUL DE TUPLES..................................................................................................................... 1665.1. Principes du calcul de tuple ....................................................................................................... 1665.2. Quelques exemples de calcul de tuple .............................................................................. 167

6. LES TECHNIQUES DINFRENCE........................................................................................... 1686.1. Principe dun algorithme de dduction ............................................................................ 1686.2. Algorithme dunification.............................................................................................................. 1696.3. Mthode de rsolution .................................................................................................................... 170

7. CONCLUSION ................................................................................................................................................. 172

8. BIBLIOGRAPHIE.......................................................................................................................................... 173

CHAPITRE VI LE MODLE RELATIONNEL..................................................................... 179

1. INTRODUCTION : LES OBJECTIFS DU MODLE .................................................. 179

2. LES STRUCTURES DE DONNES DE BASE................................................................. 181

PARTIE 2 LE RELATIONNEL

Sommaire XIII

2.1. Domaine, attribut et relation...................................................................................................... 1812.2. Extensions et intentions................................................................................................................. 184

3. LES RGLES DINTGRIT STRUCTURELLE........................................................... 1853.1. Unicit de cl.......................................................................................................................................... 1853.2. Contraintes de rfrences............................................................................................................. 1863.3. Valeurs nulles et cls........................................................................................................................ 1883.4. Contraintes de domaines............................................................................................................... 188

4. LALGBRE RELATIONNELLE : OPRATIONS DE BASE............................. 1894.1. Les oprations ensemblistes ...................................................................................................... 190

4.1.1. Union ............................................................................................................................................. 1904.1.2. Diffrence ................................................................................................................................... 1914.1.3. Produit cartsien.................................................................................................................. 192

4.2. Les oprations spcifiques .......................................................................................................... 1934.2.1. Projection ................................................................................................................................... 1934.2.2. Restriction.................................................................................................................................. 1944.2.3. Jointure......................................................................................................................................... 195

5. LALGBRE RELATIONNELLE : OPRATIONS DRIVES........................ 1985.1. Intersection ............................................................................................................................................... 1985.2. Division ....................................................................................................................................................... 1995.3. Complment ............................................................................................................................................ 2005.4. clatement................................................................................................................................................. 2015.5. Jointure externe..................................................................................................................................... 2025.6. Semi-jointure .......................................................................................................................................... 2035.7. Fermeture transitive .......................................................................................................................... 204

6. LES EXPRESSIONS DE LALGBRE RELATIONNELLE ................................. 2066.1. Langage algbrique ........................................................................................................................... 2066.2. Arbre algbrique.................................................................................................................................. 207

7. FONCTIONS ET AGRGATS........................................................................................................... 2097.1. Fonctions de calcul ............................................................................................................................ 2097.2. Support des agrgats ........................................................................................................................ 210

8. CONCLUSION ................................................................................................................................................. 211

9. BIBLIOGRAPHIE.......................................................................................................................................... 212

CHAPITRE VII LE LANGAGE SQL2 ............................................................................................. 217

1. INTRODUCTION........................................................................................................................................... 217

XIV BASES DE DONNES : OBJET ET RELATIONNEL

2. SQL1 : LA DFINITION DE SCHMAS............................................................................... 2192.1. Cration de tables ............................................................................................................................... 2192.2. Expression des contraintes dintgrit .............................................................................. 2202.3. Dfinition des vues ............................................................................................................................ 2212.4. Suppression des tables.................................................................................................................... 2222.5. Droits daccs......................................................................................................................................... 222

3. SQL1 : LA RECHERCHE DE DONNES.............................................................................. 2233.1. Expression des projections ......................................................................................................... 2233.2. Expression des slections............................................................................................................. 2243.3. Expression des jointures ............................................................................................................... 2263.4. Sous-questions....................................................................................................................................... 2273.5. Questions quantifies....................................................................................................................... 2283.6. Expression des unions..................................................................................................................... 2303.7. Fonctions de calculs et agrgats............................................................................................. 230

4. SQL1 : LES MISES JOUR ............................................................................................................... 2324.1. Insertion de tuples .............................................................................................................................. 2324.2. Mise jour de tuples ........................................................................................................................ 2334.3. Suppression de tuples...................................................................................................................... 233

5. SQL1 : LA PROGRAMMATION DE TRANSACTIONS.......................................... 2345.1. Commandes de gestion de transaction.............................................................................. 2345.2. Curseurs et procdures ................................................................................................................... 2355.3. Intgration de SQL et des langages de programmation..................................... 236

6. SQL2 : LE STANDARD DE 1992 ................................................................................................... 2386.1. Le niveau entre ................................................................................................................................... 2386.2. Le niveau intermdiaire ................................................................................................................. 239

6.2.1. Les extensions des types de donnes................................................................... 2396.2.2. Un meilleur support de lintgrit ........................................................................ 2406.2.3. Une intgration tendue de lalgbre relationnelle............................... 2416.2.4. La possibilit de modifier les schmas ............................................................. 2426.2.5. Lexcution immdiate des commandes SQL .............................................. 242

6.3. Le niveau complet .............................................................................................................................. 242

7. CONCLUSION ................................................................................................................................................. 243

8. BIBLIOGRAPHIE.......................................................................................................................................... 244

CHAPITRE VIII INTGRIT ET BD ACTIVES ................................................................ 247

1. INTRODUCTION........................................................................................................................................... 247

Sommaire XV

2. TYPOLOGIE DES CONTRAINTES DINTGRIT................................................... 2492.1. Contraintes structurelles................................................................................................................ 2492.2. Contraintes non structurelles..................................................................................................... 2502.3. Expression des contraintes en SQL..................................................................................... 251

3. ANALYSE DES CONTRAINTES DINTGRIT.......................................................... 2543.1. Test de cohrence et de non-redondance ........................................................................ 2543.2. Simplification oprationnelle ................................................................................................... 2553.3. Simplification diffrentielle ....................................................................................................... 256

4. CONTRLE DES CONTRAINTES DINTGRIT..................................................... 2584.1. Mthode de dtection ...................................................................................................................... 2584.2. Mthode de prvention................................................................................................................... 2594.3. Contrles au vol des contraintes simples........................................................................ 262

4.3.1. Unicit de cl .......................................................................................................................... 2624.3.2. Contrainte rfrentielle .................................................................................................. 2624.3.3. Contrainte de domaine ................................................................................................... 263

4.4. Interaction entre contraintes ...................................................................................................... 263

5. SGBD ACTIFS ET DCLENCHEURS...................................................................................... 2645.1. Objectifs...................................................................................................................................................... 2645.2. Types de rgles...................................................................................................................................... 2645.3. Composants dun SGBD actif.................................................................................................. 266

6. LA DFINITION DES DCLENCHEURS............................................................................ 2676.1. Les vnements..................................................................................................................................... 267

6.1.1. vnement simple................................................................................................................ 2686.1.2. vnement compos .......................................................................................................... 269

6.2. La condition............................................................................................................................................. 2696.3. Laction ........................................................................................................................................................ 2696.4. Expression en SQL3......................................................................................................................... 270

6.4.1. Syntaxe.......................................................................................................................................... 2706.4.2. Smantique................................................................................................................................ 271

6.5. Quelques exemples............................................................................................................................ 2716.5.1. Contrle dintgrit........................................................................................................... 2716.5.2. Mise jour automatique de colonnes................................................................ 2726.5.3. Gestion de donnes agrgatives ............................................................................. 273

7. EXCUTION DES DCLENCHEURS ..................................................................................... 2737.1. Procdure gnrale ............................................................................................................................ 2747.2. Priorits et imbrications ................................................................................................................ 2757.3. Couplage la gestion de transactions ............................................................................... 276

XVI BASES DE DONNES : OBJET ET RELATIONNEL

8. CONCLUSION ................................................................................................................................................. 276

9. BIBLIOGRAPHIE.......................................................................................................................................... 277

CHAPITRE IX LA GESTION DES VUES ................................................................................... 281

1. INTRODUCTION........................................................................................................................................... 281

2. DFINITION DES VUES....................................................................................................................... 283

3. INTERROGATION AU TRAVERS DE VUES.................................................................... 285

4. MISE JOUR AU TRAVERS DE VUES................................................................................ 2884.1. Vue mettable jour............................................................................................................................ 2884.2. Approche pratique.............................................................................................................................. 2884.3. Approche thorique........................................................................................................................... 289

5. VUES CONCRTES ET DCISIONNEL............................................................................... 2905.1. Dfinition ................................................................................................................................................... 2905.2. Stratgie de report .............................................................................................................................. 2925.3. Le cas des agrgats ............................................................................................................................ 294

6. CONCLUSION ................................................................................................................................................. 296

7. BIBLIOGRAPHIE.......................................................................................................................................... 297

CHAPITRE X OPTIMISATION DE QUESTIONS............................................................. 301

1. INTRODUCTION........................................................................................................................................... 301

2. LES OBJECTIFS DE LOPTIMISATION................................................................................ 3032.1. Exemples de bases et requtes................................................................................................. 3032.2. Requtes statiques ou dynamiques ...................................................................................... 3042.3. Analyse des requtes........................................................................................................................ 3052.4. Fonctions dun optimiseur........................................................................................................... 308

3. LOPTIMISATION LOGIQUE OU RCRITURE........................................................ 3103.1. Analyse et rcriture smantique .......................................................................................... 310

3.1.1. Graphes support de lanalyse................................................................................... 3103.1.2. Correction de la question ............................................................................................. 3123.1.3. Questions quivalentes par transitivit ............................................................ 3123.1.4. Questions quivalentes par intgrit .................................................................. 314

3.2. Rcritures syntaxiques et restructurations algbriques.................................... 3153.2.1. Rgles de transformation des arbres .................................................................. 3153.2.2. Ordonnancement par descente des oprations unaires...................... 319

Sommaire XVII

3.3. Ordonnancement par dcomposition ................................................................................. 3203.3.1. Le dtachement de sous-questions ....................................................................... 3213.3.2. Diffrents cas de dtachement.................................................................................. 322

3.4. Bilan des mthodes doptimisation logique................................................................. 325

4. Les Oprateurs physiques......................................................................................................................... 3254.1. Oprateur de slection .................................................................................................................... 325

4.1.1. Slection sans index .......................................................................................................... 3264.1.2. Slection avec index de type arbre-B ................................................................. 327

4.2. Oprateur de tri ..................................................................................................................................... 3284.3. Oprateur de jointure ....................................................................................................................... 329

4.3.1. Jointure sans index............................................................................................................. 3304.3.2. Jointure avec index de type arbre-B.................................................................... 334

4.4. Le calcul des agrgats ..................................................................................................................... 334

5. LESTIMATION DU COT DUN PLAN DEXCUTION.................................. 3355.1. Nombre et types de plans dexcution.............................................................................. 3355.2. Estimation de la taille des rsultats intermdiaires................................................ 3375.3. Prise en compte des algorithmes daccs ....................................................................... 339

6. LA RECHERCHE DU MEILLEUR PLAN ............................................................................ 3406.1. Algorithme de slectivit minimale .................................................................................... 3416.2. Programmation dynamique (DP) .......................................................................................... 3416.3. Programmation dynamique inverse..................................................................................... 3426.4. Les stratgies de recherche alatoires ............................................................................... 343

7. CONCLUSION ................................................................................................................................................. 344

8. BIBLIOGRAPHIE.......................................................................................................................................... 344

CHAPITRE XI LE MODLE OBJET .............................................................................................. 353

1. INTRODUCTION........................................................................................................................................... 353

2. LE MODLE OBJET DE RFRENCE .................................................................................. 3542.1. Modlisation des objets ................................................................................................................. 3542.2. Encapsulation des objets............................................................................................................... 3572.3. Dfinition des types dobjets..................................................................................................... 3582.4. Liens dhritage entre classes................................................................................................... 3612.5. Polymorphisme, redfinition et surcharge..................................................................... 365

PARTIE 3 LOBJET ET LOBJET-RELATIONNEL

XVIII BASES DE DONNES : OBJET ET RELATIONNEL

2.6. Dfinition des collections dobjets....................................................................................... 3672.7. Prise en compte de la dynamique.......................................................................................... 3702.8. Schma de bases de donnes objets................................................................................ 371

3. LA PERSISTANCE DES OBJETS ................................................................................................. 3733.1. Quest-ce-quune BD objets ? ............................................................................................. 3733.2. Gestion de la persistance .............................................................................................................. 3753.3. Persistance par hritage ................................................................................................................. 3773.4. Persistance par rfrence.............................................................................................................. 3783.5. Navigation dans une base dobjets....................................................................................... 380

4. ALGBRE POUR OBJETS COMPLEXES............................................................................ 3824.1. Expressions de chemins et de mthodes ......................................................................... 3824.2. Groupage et dgroupage de relations ................................................................................ 3854.3. Lalgbre dEncore ............................................................................................................................ 3864.4. Une algbre sous forme de classes ...................................................................................... 387

4.4.1. Les oprations de recherche ...................................................................................... 3884.4.2. Les oprations ensemblistes....................................................................................... 3894.4.3. Les oprations de mise jour................................................................................... 3904.4.4. Les oprations de groupe ............................................................................................. 3914.4.5. Arbres doprations algbriques ........................................................................... 392

5. CONCLUSION ................................................................................................................................................. 394

6. BIBLIOGRAPHIE.......................................................................................................................................... 395

CHAPITRE XII LE STANDARD DE LODMG : ODL, OQL ET OML ....... 401

1. INTRODUCTION........................................................................................................................................... 401

2. CONTEXTE......................................................................................................................................................... 4012.1. L ODMG (Object Database Management Group)............................................... 4022.2. Contenu de la proposition............................................................................................................ 4032.3. Architecture ............................................................................................................................................. 404

3. LE MODLE DE LODMG .................................................................................................................. 4063.1. Vue gnrale et concepts de base .......................................................................................... 4063.2. Hritage de comportement et de structure..................................................................... 4083.3. Les objets instances de classes................................................................................................ 4093.4. Proprits communes des objets ............................................................................................ 4093.5. Les objets structurs ......................................................................................................................... 4103.6. Les collections....................................................................................................................................... 410

Sommaire XIX

3.7. Les attributs.............................................................................................................................................. 4123.8. Les associations (Relationships)............................................................................................ 4123.9. Les oprations........................................................................................................................................ 4133.10.Mta-modle du modle ODMG........................................................................................... 414

4. EXEMPLE DE SCHMA ODL......................................................................................................... 415

5. LE LANGAGE OQL.................................................................................................................................... 4175.1. Vue gnrale............................................................................................................................................ 4175.2. Exemples et syntaxes de requtes......................................................................................... 418

5.2.1. Calcul dexpressions......................................................................................................... 4195.2.2. Accs partir dobjets nomms.............................................................................. 4195.2.3. Slection avec qualification ....................................................................................... 4205.2.4. Expression de jointures .................................................................................................. 4205.2.5. Parcours dassociations multivalues

par des collections dpendantes............................................................................. 4215.2.6. Slection d une structure en rsultat ................................................................ 4215.2.7. Calcul de collections en rsultat............................................................................ 4225.2.8. Manipulation des identifiants dobjets ............................................................. 4225.2.9. Application de mthodes en qualification et en rsultat ................... 4225.2.10. Imbrication de SELECT en rsultat ................................................................. 4235.2.11. Cration dobjets en rsultat.................................................................................. 4235.2.12. Quantification de variables ..................................................................................... 4245.2.13. Calcul dagrgats et oprateur GROUP BY............................................. 4245.2.14. Expressions de collections........................................................................................ 4255.2.15. Conversions de types appliques aux collections................................. 4265.2.16. Dfinition dobjets via requtes ........................................................................... 427

5.3. Bilan sur OQL ....................................................................................................................................... 427

6. OML : LINTGRATION C++, SMALLTALK ET JAVA.................................... 4276.1. Principes de base ................................................................................................................................. 4276.2. Contexte transactionnel ................................................................................................................. 4286.3. Lexemple de Java .............................................................................................................................. 429

6.3.1. La persistance des objets .............................................................................................. 4296.3.2. Les correspondances de types .................................................................................. 4306.3.3. Les collections........................................................................................................................ 4306.3.4. La transparence des oprations.............................................................................. 4306.3.5. Java OQL ................................................................................................................................... 4316.3.6. Bilan ............................................................................................................................................... 431

7. CONCLUSION ................................................................................................................................................. 432

8. BIBLIOGRAPHIE.......................................................................................................................................... 433

XX BASES DE DONNES : OBJET ET RELATIONNEL

CHAPITRE XIII LOBJET-RELATIONNEL ET SQL3 ................................................ 435

1. INTRODUCTION........................................................................................................................................... 435

2. POURQUOI INTGRER LOBJET AU RELATIONNEL ?.................................... 4362.1. Forces du modle relationnel.................................................................................................... 4362.2. Faiblesses du modle relationnel........................................................................................... 4372.3. Lapport des modles objet......................................................................................................... 4382.4. Le support dobjets complexes................................................................................................ 439

3. LE MODLE OBJET-RELATIONNEL ..................................................................................... 4403.1. Les concepts additionnels essentiels .................................................................................. 4413.2. Les extensions du langage de requtes............................................................................. 442

4. VUE DENSEMBLE DE SQL3......................................................................................................... 4444.1. Le processus de normalisation................................................................................................. 4444.2. Les composants et le planning................................................................................................. 4444.3. La base ......................................................................................................................................................... 445

5. LE SUPPORT DES OBJETS................................................................................................................ 4465.1. Les types abstraits .............................................................................................................................. 446

5.1.1. Principes ..................................................................................................................................... 4465.1.2. Syntaxe.......................................................................................................................................... 4475.1.3. Quelques exemples ............................................................................................................. 448

5.2. Les constructeurs dobjets complexes............................................................................... 4495.3. Les tables.................................................................................................................................................... 4505.4. Lappel de fonctions et doprateurs dans les requtes ...................................... 4505.5. Le parcours de rfrence............................................................................................................... 4525.6. La recherche en collections........................................................................................................ 4535.7. Recherche et hritage ...................................................................................................................... 454

6. LE LANGAGE DE PROGRAMMATION PSM ................................................................. 4546.1. Modules, fonctions et procdures ......................................................................................... 4546.2. Les ordres essentiels......................................................................................................................... 4556.3. Quelques exemples............................................................................................................................ 4566.4. Place de PSM dans le standard SQL.................................................................................. 457

7. CONCLUSION ................................................................................................................................................. 457

8. BIBLIOGRAPHIE.......................................................................................................................................... 459

CHAPITRE XIV OPTIMISATION DE REQUTES OBJET .................................. 463

1. INTRODUCTION........................................................................................................................................... 463

Sommaire XXI

2. PROBLMATIQUE DES REQUTES OBJET .................................................................. 4652.1. Quest-ce quune requte objet ?........................................................................................... 4652.2. Quelques exemples motivants.................................................................................................. 466

2.2.1. Parcours de chemins ......................................................................................................... 4662.2.2. Mthodes et oprateurs .................................................................................................. 4672.2.3. Manipulation de collections....................................................................................... 4682.2.4. Hritage et polymorphisme ........................................................................................ 468

3. MODLE DE STOCKAGE POUR BD OBJET.................................................................. 4693.1. Identifiants dobjets........................................................................................................................... 4693.2. Indexation des collections dobjets ..................................................................................... 4713.3. Liaison et incorporation dobjets........................................................................................... 4723.4. Groupage dobjets .............................................................................................................................. 4743.5. Schma de stockage.......................................................................................................................... 476

4. PARCOURS DE CHEMINS ................................................................................................................. 4774.1. Traverse en profondeur dabord .......................................................................................... 4784.2. Traverse en largeur dabord..................................................................................................... 4794.3. Traverse lenvers........................................................................................................................... 4804.4. Traverse par index de chemin................................................................................................ 481

5. GNRATION DES PLANS QUIVALENTS................................................................... 4815.1. Notion doptimiseur extensible............................................................................................... 4815.2. Les types de rgles de transformation de plans ........................................................ 483

5.2.1. Rgles syntaxiques ............................................................................................................. 4845.2.2. Rgles smantiques............................................................................................................ 4845.2.3. Rgles de planning ............................................................................................................. 486

5.3. Taille de lespace de recherche................................................................................................ 4875.4. Architecture dun optimiseur extensible......................................................................... 489

6. MODLE DE COT POUR BD OBJET.................................................................................. 4896.1. Principaux paramtres dun modle de cot ............................................................... 4906.2. Estimation du nombre de pages dune collection groupe.............................. 4916.3. Formule de Yao et extension aux collections groupes ..................................... 4936.4. Cot dinvocation de mthodes .............................................................................................. 4946.5. Cot de navigation via expression de chemin............................................................ 4956.6. Cot de jointure.................................................................................................................................... 496

7. STRATGIES DE RECHERCHE DU MEILLEUR PLAN...................................... 4977.1. Les algorithmes combinatoires ............................................................................................... 4977.2. Lamlioration itrative (II)........................................................................................................ 497

XXII BASES DE DONNES : OBJET ET RELATIONNEL

7.3. Le recuit simul (SA) ...................................................................................................................... 4987.4. Loptimisation deux phases (TP)........................................................................................... 4997.5. La recherche taboue (TS)............................................................................................................. 5007.6. Analyse informelle de ces algorithmes ............................................................................ 500

8. UN ALGORITHME DOPTIMISATION GNTIQUE ............................................ 5018.1. Principe dun algorithme gntique.................................................................................... 5018.2. Bases de gnes et population initiale ................................................................................. 5038.3. Oprateur de mutation .................................................................................................................... 5048.4. Oprateur de croisement ............................................................................................................... 505

9. CONCLUSION ................................................................................................................................................. 507

10. BIBLIOGRAPHIE.......................................................................................................................................... 508

CHAPITRE XV BD DDUCTIVES .................................................................................................... 517

1. INTRODUCTION........................................................................................................................................... 517

2. PROBLMATIQUE DES SGBD DDUCTIFS.................................................................. 5182.1. Langage de rgles ............................................................................................................................... 5182.2. Couplage ou intgration ?............................................................................................................ 5192.3. Prdicats extensionnels et intentionnels.......................................................................... 5202.4. Architecture type dun SGBD dductif intgr ........................................................ 521

3. LE LANGAGE DATALOG.................................................................................................................... 5223.1. Syntaxe de DATALOG................................................................................................................... 5223.2. Smantique de DATALOG ......................................................................................................... 526

3.2.1. Thorie de la preuve ......................................................................................................... 5263.2.2. Thorie du modle .............................................................................................................. 5283.2.3. Thorie du point fixe......................................................................................................... 5293.2.4. Concidence des smantiques ................................................................................... 531

4. LES EXTENSIONS DE DATALOG.............................................................................................. 5324.1. Hypothse du monde ferm ....................................................................................................... 5324.2. Ngation en corps de rgles ....................................................................................................... 5334.3. Ngation en tte de rgles et mises jour...................................................................... 5344.4. Support des fonctions de calcul.............................................................................................. 5374.5. Support des ensembles ................................................................................................................... 539

PARTIE 4 AU-DEL DU SGBD

Sommaire XXIII

5. VALUATION DE REQUTES DATALOG......................................................................... 5415.1. valuation bottom-up...................................................................................................................... 5415.2. valuation top-down ........................................................................................................................ 543

6. LA MODLISATION DE RGLES PAR DES GRAPHES..................................... 5456.1. Arbres et graphes relationnels.................................................................................................. 5466.2. Arbres ET/OU et graphes rgle/but..................................................................................... 5486.3. Autres Reprsentations .................................................................................................................. 550

7. VALUATION DES RGLES RCURSIVES.................................................................... 5537.1. Le problme des rgles rcursives........................................................................................ 5537.2. Les approches bottom-up ............................................................................................................. 556

7.2.1. La gnration nave........................................................................................................... 5567.2.2. La gnration semi-nave ............................................................................................. 558

7.3. Difficults et outils pour les approches top-down .................................................. 5597.3.1. Approches et difficults .................................................................................................. 5597.3.2. La remonte dinformations via les rgles .................................................... 5617.3.3. Les rgles signes ............................................................................................................... 563

7.4. La mthode QoSaQ........................................................................................................................... 5647.5. Les ensembles magiques .............................................................................................................. 5647.6. Quelques mthodes doptimisation moins gnrales........................................... 566

7.6.1. La mthode fonctionnelle ............................................................................................. 5667.6.2. Les mthodes par comptages .................................................................................... 5697.6.3. Les oprateurs graphes .................................................................................................. 570

8. RGLES ET OBJETS................................................................................................................................. 5708.1. Le langage de rgles pour objetS ROL ............................................................................ 5718.2. Le langage de rgles pour objets DEL.............................................................................. 573

9. CONCLUSION ................................................................................................................................................. 574

10. BIBLIOGRAPHIE.......................................................................................................................................... 575

CHAPITRE XVI GESTION DE TRANSACTIONS ........................................................... 585

1. INTRODUCTION........................................................................................................................................... 585

2. NOTION DE TRANSACTION .......................................................................................................... 5862.1. Exemple de transaction.................................................................................................................. 5862.2. Proprit des transactions ............................................................................................................ 588

2.2.1. Atomicit ..................................................................................................................................... 5882.2.2. Cohrence .................................................................................................................................. 588

XXIV BASES DE DONNES : OBJET ET RELATIONNEL

2.2.3. Isolation....................................................................................................................................... 5892.2.4. Durabilit ................................................................................................................................... 589

3. THORIE DE LA CONCURRENCE........................................................................................... 5893.1. Objectifs...................................................................................................................................................... 5893.2. Quelques dfinitions de base..................................................................................................... 5913.3. Proprits des oprations sur granule................................................................................ 5933.4. Caractrisation des excutions correctes ........................................................................ 5943.5. Graphe de prcdence..................................................................................................................... 596

4. CONTRLE DE CONCURRENCE PESSIMISTE......................................................... 5974.1. Le Verrouillage deux phases ..................................................................................................... 5984.2. Degr disolation en SQL2......................................................................................................... 6004.3. Le problme du verrou mortel ................................................................................................. 600

4.3.1. Dfinition.................................................................................................................................... 6004.3.2. Reprsentation du verrou mortel ........................................................................... 6014.3.3. Prvention du verrou mortel...................................................................................... 6044.3.4. Dtection du verrou mortel......................................................................................... 605

4.4. Autres problmes soulevs par le verrouillage.......................................................... 6074.5. Les amliorations du verrouillage ........................................................................................ 608

4.5.1. Verrouillage granularit variable..................................................................... 6094.5.2. Verrouillage multi-versions......................................................................................... 6104.5.3. Verrouillage altruiste........................................................................................................ 6104.5.4. Commutativit smantique doprations ........................................................ 611

5. CONTRLES DE CONCURRENCE OPTIMISTE........................................................ 6125.1. Ordonnancement par estampillage....................................................................................... 6135.2. Certification optimiste .................................................................................................................... 6145.3. Estampillage multi-versions ...................................................................................................... 615

6. LES PRINCIPES DE LA RSISTANCE AUX PANNES .......................................... 6176.1. Principaux types de pannes ........................................................................................................ 6176.2. Objectifs de la rsistance aux pannes ................................................................................ 6186.3. Interface applicative transactionnelle ................................................................................ 6196.4. lments utiliss pour la rsistance aux pannes....................................................... 620

6.4.1. Mmoire stable ...................................................................................................................... 6206.4.2. Cache volatile......................................................................................................................... 6216.4.3. Journal des mises jour ............................................................................................... 6226.4.4. Sauvegarde des bases ...................................................................................................... 6256.4.5. Point de reprise systme ................................................................................................ 625

7. VALIDATION DE TRANSACTION............................................................................................. 6257.1. critures en place dans la base................................................................................................ 626

Sommaire XXV

7.2. critures non en place..................................................................................................................... 6277.3. Validation en deux tapes ............................................................................................................ 628

8. LES PROCDURES DE REPRISE................................................................................................ 6318.1. Procdure de reprise ......................................................................................................................... 6318.2. Reprise chaud..................................................................................................................................... 6328.3. Protocoles de reprise chaud ................................................................................................... 6338.4. Reprise froid et catastrophe ................................................................................................... 634

9. LA MTHODE ARIES ............................................................................................................................. 6349.1. Objectifs...................................................................................................................................................... 6359.2. Les structures de donnes ............................................................................................................ 6369.3. Aperu de la mthode ..................................................................................................................... 637

10. LES MODLES DE TRANSACTIONS TENDUS...................................................... 63810.1.Les transactions imbriques....................................................................................................... 63910.2.Les sagas...........................