Les Bases de données pas à pas

Préface

Merci de signaler toute erreur, de toute sorte (orthographe, grammaire, typographie, contenu ), à . Des suggestions pour améliorer les explications seront également appréciées.

Table des matières

I Le Modèle Relationnel  5

1 Préliminaires   6

2 La Structure du Modèle Relationnel   7

2.1  Relations . . . . . . . .   7

2.2  Bases de données . . . . 8

2.3  Clé primaire et clé étrangère . . . . . . 9

2.4  La contrainte UNIQUE . . . . . . . . . . 10

2.5  Le bouche-trou NULL . .  10

2.6  La perspective “Unnamed”   . . . . . . 11

3 L’Algèbre Relationnelle  12

3.1  Syntaxe . . . . . . . . .   12

3.2  Sémantique . . . . . . .  13

3.3  Exemples   . . . . . . . .   13

3.4  Inclusion et équivalence   . . . . . . . .   14

3.5  Non-redondance des opérateurs . . . . 15

3.6  Fermeture transitive . .   16

3.7  La perspective “Unnamed”   . . . . . . 16

3.7.1  Syntaxe . . . . .   16

3.7.2  Sémantique . . .  17

3.7.3  Exemple . . . . .  17

4 Le Calcul Relationnel 18

4.1  Syntaxe . . . . . . . . .   18

4.2  Sémantique . . . . . . .  19

4.3  Indépendance du domaine . . . . . . .  20 4.4 Des requêtes dites safe . . . . . . . . . 22 4.5 Discussions approfondies . . . . . . . .   23

   4.6  Le calcul relationnel TRC . . . . . . .  24

4.3.1  TRC par l’exemple . . . . . . . 24

4.3.2  Syntaxe . . . . .   25 4.6.3 Sémantique . . .  26

  4.6.4  Du TRC au SQL . . . . . . . . 27

5 SQL 28

5.1  La base de données . . .  28 5.2 Création de domaines et de tables . . 28 5.3 Retrouver des informations   . . . . . .   29

5.4  Mises à jour . . . . . . .  33

5.5  Intégration de SQL à des langages de programmation  . . . . . . .  34

5.6  Vues . . . 35

5.1.1  Définition des Vues . . . . . . . 35

5.1.2  Interrogation au travers de vues . . . . . . .  35

5.1.3  Mise à jour au travers de vues . . . . . . . .  35

6 Les Dépendances Fonctionnelles  36

6.1  Introduction . . . . . . . 36

6.2  Syntaxe et sémantique . . . . . . . . . 36

6.3  Fermeture d’un ensemble d’attributs . . . . . . . . .  37

6.4  Autres dépendances  . . 38

6.4.1  Dépendances de jointure et dépendances multivaluées   . . . 38

6.4.2  Dépendances d’inclusion . . . .   39

7 Les Formes Normales   41

7.1  La redondance  . . . . . 41

7.2  BCNF . .   41

7.3  Décompositions . . . . .  42

7.4  Décomposition en BCNF . . . . . . . . 43

7.5  3NF . . .   44

7.6  Dépendances fonctionnelles singulières . . . . . . . .  45

7.7  Décomposition en 3NF . . . . . . . . . 45

7.8  1NF, 2NF, 4NF, 5NF   . . . . . . . . .  46

7.8.1  1NF et 2NF . . . 46

7.8.2  4NF . . . . . . .   47

7.8.3  5NF . . . . . . .   47

8 Le Modèle Entité-Association   49

8.1  Énoncé . .  49

8.2  Le diagramme entité-association  . . . 50

8.3  Traduction vers le modèle relationnel . . . . . . . . . 50

II Gestion des Transactions   52

9 Two-Phase Locking (2PL)   53

9.1  Cadre théorique . . . . .  53

9.2  Les exécutions sérielles . . . . . . . . . 54

9.3  Les exécutions sérialisables  . . . . . . 54

9.4  L’écriture aveugle . . . . 55

9.5  Spécification du protocole 2PL . . . .   55

9.5.1  Le comportement d’une transaction . . . . . 56

9.5.2  L’exécution globale . . . . . . . 56

9.6  Implémentation du protocole 2PL . . . 57

9.7  Le verrou mortel . . . .   59

9.8  Strict 2PL . . . . . . . .  60

10 Résistance aux Pannes et Reprise 62

10.1 Le buffer . . . . . . . . . 62

10.2 Undo/Redo . . . . . . .   63

10.3 Le journal . . . . . . . . 64

10.4 Procédure de Reprise . . 64

10.5 Exemple . . . . . . . . .  64

10.6 Checkpointing . . . . . .   65

10.7 Undo/No-Redo et Redo/No-Undo . . . 66

III   Exercices  67

A Les Grandes Découvertes en Bases de Données  118

A.1 Introduction . . . . . . . 118

A.2 Les BD Hiérarchiques  . . . . . . . . . 118

A.3 Les BD de Type Réseau . . . . . . . . 119

A.4 Les BD Relationnelles . . . . . . . . . 122

A.5 Le Web, une BD? . . . 124

A.5.1  Un Manque de Structure   . . . 124

A.5.2  Traiter le Futur Web comme BD . . . . . . . 125

Première partie Le Modèle Relationnel

Chapitre 1

Préliminaires

L’ensemble vide est dénoté par ? ou {}.

Soient A et B deux ensembles. On écrit A ( B si A ? B et A  =6B.

On dénote par |A| le nombre d’éléments dans _A.

Le produit cartésien de A et B, dénoté par A × B, est l’ensemble A × B := {(a,b) | a ? A,b ? B}.

Une relation binaire sur _A est un sous-ensemble de _A × A.

Soit R une relation binaire sur A. On dit que R est transitive si pour tout a,b,c ? A, si (a,b) ? R) et (b,c) ? R, alors (a,c) ? R. La fermeture transitive de R est la plus petite (par rapport à ? relation binaire qui contient R et qui est transitive.

Soit _n un entier non-négatif. L’ensemble _Aⁿ est défini comme suit :

Aⁿ :⁼{ha₁, ,a_ni | a₁, ,a_n ? A}.

Unepour toutfonction totalea ? A, il existe exactement un élémentf de A vers B, dénotée f : Ab??BB, est un sous-ensemble detel que (_a,b) ?_f ; cet unique élémentA × B tel que_b est alors dénoté par _f(_a). On appelle _A le domaine de _f.

Soitf[_A0]^f, est la fonction totale: A ?^B une fonction totale et_f0 : _A0 ?_BAtelle que pour chaque⁰ ?^A. La restriction de_a ?f_Aà l’ensemble0, _f0(_a) = _f(A_a)⁰., dénoté par

Un cas particulier est la restriction de _f à l’ensemble vide : _f[?] = {}.

Exemple 1. Soient A = {a,b,c} et ^B = {1^,2^,3^,4}. Soit ^f = {(^a,1)^,(^b,2)^,(^c,2)}. Alors ^f est une fonction totale de _A vers _B.

Noter la différence entre f(a) = b et f[{a}] = {(a,b)}.

Chapitre 2

La Structure du Modèle

Relationnel

Future users of large data banks must be protected from having to know how the data is organized in the machine (the internal representation).

J.F. Codd, 1970 [5, page 377]

Le modèle relationnel a été introduit en 1970 par E.F. Codd [5]. Un premier prototype de système de base de données relationnelle, appelé “System R”, a été développé à partir de 1974 [3]. C’était le début d’une technologie révolutionnaire qui est maintenant omniprésente : le SGBDR, Système de Gestion de Base de Données Relationnelle.

Les ouvrages suivants présentent, de façon rigoureuse, les fondements théoriques des bases de données relationnelles :

— “The Theory of Relational Databases” par D. Maier [11];

— “Principles of Database and Knowledge-Base Systems” par J.D. Ullman [12, 13]; — “Foundations of Databases” par S. Abiteboul, R. Hull et V. Vianu [1].

Les livres [1] et [11] sont gratuitement disponibles en ligne.

2.1   Relations

Supposons

— un ensemble infini dom dont les éléments sont appelés des valeurs (ou des constantes);

— un nombre d’ensembles non vides, appelés domaines. Chaque domaine est un sous-ensemble de dom;

— un nombre infini d’attributs A,B,C,A₁,B₁,C₁, ; et

— une fonction Dom qui fait correspondre, à chaque attribut, un domaine.

Un schéma-de-relation (ou simplement schéma si aucune confusion n’est possible) est alors un ensemble fini A d’attributs.

Figure 2.1 – Une relation présentée sous forme de table.

Un tuple sur ce schéma-de-relation est une fonction totale t : A ?dom telle que pour tout attribut A ? A, t(A) ? Dom(A). Une relation sur ce schéma-de-relation est un ensemble fini de tuples sur ce schéma.

Exemple 2. Soit N l’ensemble des prénoms autorisés en Belgique. Soient _Prénom et _Genre deux attributs avec Dom(^Prénom) = ^N et Dom(^Genre) = ^{?^,?^}. Alors(_Prénom^{Prénom,Jean),,(^Genre_Genre^},?est un)} et schéma-de-relation. Deux tuples sur ce schéma-de-relation sont {

{(_Prénom,Anne), (_Genre,?)}. L’ensemble qui contient ces deux tuples est une relation. 

Les relations seront souvent présentées sous forme de table. La table de la figure 2.1 présente la relation de l’exemple 2. Ensuite, il est habituel de parler de “la première rangée” pour dénoter le tuple {(Prénom,Jean), (Genre,?)}, ou de “la première colonne”. Noter cependant que des relations et des schémas-de-relation sont des ensembles non-ordonnés.

Dans la théorie, on va souvent négliger les domaines, en supposant que pour chaque attribut _A, Dom(_A) = dom.

Si A1,A2, ,A` sont des attributs, on écrira souvent A1A2 ···A` pour dénoter l’ensemblepour dénoter . Si X et Y sont des ensembles d’attributs, on écrira souvent XY

peut être abrévié commePar exemple, si A et B sont des attributs, etXAB. X est un ensemble d’attributs, alors X ? {A,B}

2.2 Bases de données

Supposons un nombre infini de noms de relation R,S,T,R₁,S₁,T₁, , et une fonction sorte qui fait correspondre, à chaque nom de relation, un schéma-de-relation. La notation _R[_{A1, ,An}] est utilisée pour dénoter que R est un nom de relation avec sorte(R) = {A₁, ,A_n}.

Un schéma-de-base-de-données (ou simplement schéma si aucune confusion n’est possible) est donnéesalors un ensemble fini) sur ce schéma-de-base-de-données est une fonction totale avec domaineR de noms de relation. Une base de données (ou instance de base dequi fait correspondre, à chaque nom de relation R dans R, une relation sur, on dénote parsorte(R). Le symboleRI la relation quiR I sera souvent utilisé pour dénoter une base de données; pourcorrespond à _R.  R ? R

Il est habituel de présenter une base de données comme un ensemble de tables, comme illustré

dans la figure 2.2. Le schéma de cette base de données estMillésime, Qualité} et sorte(ABUS) = {Buveur, Cru, Millésime{VINS},.ABUS} avec sorte(_VINS) = {Cru,

VINSABUS

Figure 2.2 – Une base de données présentée sous forme de tables. Exemple issu de [8].

2.3   Clé primaire et clé étrangère

On fait correspondre, à chaque nom de relation _R, une clé primaire, en utilisant la syntaxe suivante :

R PRIMARY KEY(A₁,A₂, ,A_k),   (2.1)

avecdont le schéma contientt1,t2 A?¹R,AI², ,A1 1^k des attributs distincts appartenant à2  R. On dit quek 2   1 I2 k], alorsI t1 =sortet2. C’est-à-dire, la base de données(^R). Soit I une base de donnéessi pour toutI  I satisfait (ou respecte) la clé primaire de _R

, si t [A A ···A ] = t [A A ···A

la même valeur pour (les attributs de) la clé primaire; chaque tuplerespecte la clé primaire si pour chaque tuple t ? R , il n’existe pas d’autre tuple danst ? RI est donc identifiéR  avec de façon unique par sa valeur pour la clé primaire. Il est habituel de souligner les attributs qui constituent la clé primaire.

La clé primaire de _R peut être utilisée ailleurs pour faire référence aux tuples d’une relation _R^I. La syntaxe est comme suit :

S  FOREIGN KEY(B₁,B₂, ,B_k) REFERENCES R, (2.2)

avecbase de données dont le schéma contientS un nom de relation et B₁,B₂, ,B^IR_k des attributs appartenant àet S. On dit que I satisfait (ou respecte) la clésorte(^IS)tel que pour. Soit I une étrangère (2.2) si pour tout tuplechaque ^{i ? {}1^{, ,k}}, ^s(^Bi ^I fait référence à un tuple unique dei_s ?_S , il existe un tuple (unique)1   k constituent la clé primaire (2.1)._R^I_ten copiant sa valeur?_R

) = _t(_A ), où les attributs _{A , A}

C’est-à-dire, chaque tuple de _S

pour la clé primaire. Noter que la longueur _k de la clé étrangère est identique à la longueur de la clé primaire de R. Il est cependant possible que B_i 6= A_i (pour un ou plusieurs i ? {1, ,k}). Il est aussi possible que _S = _R.

Les clés primaires et étrangères constituent un mécanisme élégant pour relier des tuples de différentes relations, tout en évitant des références “artificielles” telles que les pointeurs ou les auto-incréments. Les clés primaires et étrangères sont des contraintes que l’on ajoute à un schéma-de-bases-de-données pour restreindre les bases de données qui sont admissibles.

Exemple 3. Pour la base de données de la figure 2.2, on peut raisonnablement imposer les clés primaires et la clé étrangère suivantes :

VINS PRIMARY KEY(Cru,Millésime)

ABUS PRIMARY KEY(Buveur,Cru,Millésime)

ABUS FOREIGN KEY(Cru,Millésime) REFERENCES VINS

La clé primaire de _VINS exprime qu’aucun cru ne peut avoir deux qualités différentes pour une même année.  

VOITURES

ACCESSOIRES

Figure 2.3 – Base de données. Chaque voiture a une plaque et un numéro de châssis qui lui sont propres.

Exemple 4. Cet exemple artificiel montre l’importance de l’ordre des attributs dans la spécification des clés primaires et étrangères.

R[A,B]

R PRIMARY KEY(A,B)

R FOREIGN KEY(B,A) REFERENCES R

Une base de donnéessi pour tout ^t1 ^{? RI}, il existeI (dont le schéma contient^{t? R}I tel que _t2(_B^R)) =respecte ces contraintes si et seulement_t1(_A) et _t2(_A) = _t1(_B). Noter que la clé primaire dans cet exemple sera toujours respectée, car une relation est un ensemble (sans doublons).

2.4   La contrainte _UNIQUE

La syntaxe de la contrainte UNIQUE est comme suit :

R UNIQUE(A₁,A₂, ,A_k), avec R un nom de relation et A₁,A₂, ,A_k des attributs distincts appartenant à sorte(R).

Cette contrainte est satisfaite par une bases de donnéestout t1,t2 ? R^I, si t1[A1A2 ···Ak] = t2[A1A2 ···Ak ^I (1dont le schéma contient_{= t}2_.  ^R) si pour

_{], alors t}

Exemple 5. La base de données de la figure 2.3 enregistre les accessoires présents dans différentes voitures. La contrainte UNIQUE exprime que chaque voiture a un numéro de châssis qui lui est unique.

VOITURES [Plaque,Châssis,Type,Année]

VOITURES PRIMARY KEY(Plaque)

VOITURES UNIQUE(Châssis)

ACCESSOIRES [Plaque,Accessoire]

ACCESSOIRES PRIMARY KEY(Plaque,Accessoire)

ACCESSOIRES FOREIGN KEY(Plaque) REFERENCESS VOITURES

CITOYENS

Figure 2.4 – Base de données avec des NULLs.

généralement de remplacer la valeur absente par le symbole NULL. Dans la base de données de la figure 2.4, _NN dénote le numéro national, et _{NPermisConduire} le numéro de permis de conduire. Le numéro national de Bart Bretelle indique qu’il est né à la date du 11 septembre 2015; il est trop jeune pour avoir un permis de conduire. La situation est moins claire pour Cloé Camp : soit elle n’a pas de permis de conduire, soit elle a un permis de conduire dont le numéro est manquant dans la base de données actuelle.

Le bouche-trou NULL n’étant pas une valeur (i.e., NULL 6?doms. Par exemple, est-ce-que la relation), il est nécessaire d’étendre les définitions des sections 2.1–2.4 pour tenir compte des NULL

VOITURES de la figure 2.3 pourrait contenir deux tuples distincts t₁,t₂ tels que t₁(_Châssis) = NULL et t₂(Châssis) = NULL, tout en respectant la contrainte VOITURES UNIQUE(Châssis)? Cependant, cette extension avec NULL est hors de portée du présent syllabus.

2.6 La perspective “Unnamed”

Le formalisme expliqué précédemment utilise des attributs pour dénoter une valeur dans un tuple; on parle de la perspective “Named”, dans le sens où les attributs portent un nom.

Dans la perspective “Unnamed”, les attributs sont remplacés par des indices 1_,2_,3_,

Soit _n un entier non-négatif. Une relation d’arité_n est un sous-ensemble fini de domⁿ.

On définit la fonction arité qui fait correspondre, à chaque nom de relation _R, un entier non-négatif tel que arité(_R) = |sorte(_R)|.

aritéSoit R un schéma-de-base-de-données. Unequi fait correspondre, à chaque nom de relationbase de données sur_RRdansest une fonction totale avecR, une relation d’arité domaine R

(_R).

Les définitions de clé primaire, clé étrangère et la contrainte UNIQUE peuvent facilement être adaptées à la perspective “Unnamed”.

Dès que l’on ajoute un ordre aux attributs dans la perspective “Named”, une correspondance évidente émerge entre les perspectives “Named” et “Unnamed”. Cet ordre est généralement l’ordre dans lequel on liste les attributs dans la notation _R[_{A1, ,An}]. Alors, un tuple “Named” {(A1,a1), ,(An,an)} correspond, un-à-un, à sa version “Unnamed” ha1, ,ani.

Chapitre 3

L’Algèbre Relationnelle

Soit R un schéma-de-base-de-données (i.e., un ensemble fini de noms de relation). On peutrequête comme un programme informatique qui prend en entrée une base de

concevoir une

données I sur R et qui donne en sortie une relation. Le “langage de programmation” introduitalgèbre relationnelle. Ce langage est moins puissant que les langages Java dans ce chapitre est l’ ou Python, mais est beaucoup plus simple et se prête mieux aux analyses théoriques. Dans un premier temps, on introduira l’algèbre relationnelle dans la perspective “Named”. Cette algèbre est dénotée par le sigle SPJRUD, qui contient la première lettre de chaque opérateur de l’algèbre.

3.1   Syntaxe

Soit R un schéma-de-bases-de-données.

Noms de relation Chaque nom de relation R dans R est une expression algébrique (atomique).

Sélection “attribut égal constante”A=“a” Si E est une expression algébrique, AA=?“asorte”(E)() =E), et a ?dom, alors ? (E) est une expression algébrique avec sorte(? sorte(E).

Sélection “attribut égal attribut”alors _?A=B(_E) est une expression algébrique avecSi E est une expression algébrique etsorte(_?A=B  A,B ?). sorte(E),

(_E)) = sorte(_E

Projection Si ^E est une expression algébrique et X ? sorte(^E), alors ?^X(^E) est une expression algébrique avec sorte(_?X(_E)) = _X.

Jointure Si E₁ et E₂ sont des expressions algébriques, alors E₁E₂ est une expression algébrique avec sorte(E₁ 1 E₂) = sorte(E₁) ? sorte(E₂). 1

Renommage Si E est une expression algébrique,A?B A ? sorte(E), et B est un attribut telsorte(?A?B(E)) = que B ?6 sorte(E), alors ?7 (E) est une expression algébrique avec 7 (sorte(E) \ {A}) ? {B}.

Unionest une expression algébrique avecSi E₁ et E₂ sont des expressions algébriques avecsorte(^{E1?· E2}) =sortesorte((E^E₁¹) =). Noter que le symbolesorte. Si aucune confusion(E₂), alors E₁?·E^?·₂ est utilisé ici pour marquer la différence avec l’union ensembliste ? n’est possible, on peut écrire _E1 ?_E2 au lieu de _E1 ?·_E2.

Différence Si E₁ et E₂ sont des expressions algébriques avec sorte(E₁) = sorte(E₂), alors E₁? E₂ est une expression algébrique avec sorte(E₁? E₂) = sorte(E₁).

Des parenthèses sont utilisées pour préciser l’ordre d’évaluation. En absence de parenthèses, la jointure est prioritaire sur l’union et la différence. Par exemple, l’expressionêtre évaluée comme (?_A(R) 1 S) ?· T.  ?_A(R) 1 S ?· T doit

3.2   Sémantique

Soit I une base de données sur R.

Si _E est une expression algébrique, on dénote par _E^I la relation qui est le résultat de l’évaluation de E sur I. La définition de _JE_K^I est comme suit :J K

— Si _R est un nom de relation, alors _R^I := _R^I. Donc, le résultat de l’expression _R est la relation dans la base de données qui correspond àJ K _R. Noter que pour deux bases de données différentes,II et JI , il est possible que _JR_K^I =6_JR_K^J .

   —  ?A=“a”(E)IK :=JEIK | t(A) = a}.

J

— J?_A=B(EI)K := {tJEK | tI(^A) = ^t(^B)}.

— J?_X(E)K := {t[X] | t ? JEK }.

— Soit X = sorte(E₁) et Y = sorte(E₂).

Alors E₁ 1 E₂^I := {t | t[X] ? JE₁K^I et t[Y ] ? JE₂K^I}.

 J  K

 — Soit ^XJ =_A7?Isorte_B (^EK^I) ^{\ {}:I=^A{t^}.| il existeI s ? JEK^I tel que _s[_X] = _t[_X] et _s[_A] = _t[_B]}.

   Alors _?   (_E)

— JE₁?· E_2KI :⁼_JE_1KI ?_JE_2KI^{, avec}? l’union ensembliste.

   —  E₁? E₂K := JE₁K \ JE₂K , avec \ la différence ensembliste.

J

Une expression algébrique _E est aussi appelée une requête, et _E^I est la réponse à la requête _E sur la base de données I. J K

3.3   Exemples

Les buveurs exigeants Disons qu’un buveur est exigeant s’il ne boit que des vins de qualité A. Pour la base de données de la figure 2.2, on souhaite encoder la requête “Quels buveurs sont exigeants?”. Soit

E1 := ?{Buveur,Qualité}(ABUS 1 VINS).

Un tuple {(Buveur,b),(Qualité. L’expression suivante rend alors les buveurs qui ont déjà bu un vin,q)} dans l’évaluation de E1 signifie que b est un buveur qui a

déjà bu un vin de qualité q qui n’est pas de qualité A :

E2 := ?{Buveur}(E1 ? ?Qualité=“A”(E1)).

Si on substitue dans cette expression la définition de _E1, on obtient :

E2 = ?{Buveur}(?{Buveur,Qualité}(ABUS 1 VINS) ? ?Qualité=“A”(?{Buveur,Qualité}(ABUS 1 VINS))).

Cependant, cette substitution nuit à la lisibilité. L’expression demandée _E3 doit rendre tout buveur qui n’est pas dans l’évaluation de _E2.

Donc,

E3 := ?Buveur(ABUS) ? E2.

L’expression?A₆=“a” E2 peut être simplifiée si on introduit l’abréviation suivante. SiA=“a” A ? 2sortepeut s’écrire(R), alors

(R) est une abréviation pour R ? ?  (R). Avec cette abréviation, E comme

E2 := ?{Buveur}(?Qualité6=“A”(E1)).

parLa table sans colonnesE4 3 La définition de ?_X(^E) permet ^X = {}. Quelle requête est encodée := _?{}(_E )?

S’il existe au moins un buveur exigeant, alors l’évaluation derelation qui contient le tuple vide. S’il n’existe pas de buveur exigeant, alors l’évaluation deE₄ rend la relation {{}}, i.e., la_E4 rend la relation vide4{}encode alors la requête booléenne. Il est habituel d’interpréter {{}}“Existe-t-il des buveurs exigeants?”et {} respectivement comme true .et false.

L’expression E

Les buveurs ayant bu plusieurs crus Pour la base de données de la figure 2.2, on souhaite encoder la requête “Quels buveurs ont déjà bu deux ou plusieurs crus différents?”. Soit

E1 := ?{Buveur,Cru}(ABUS) 1 ?Cru7?Vin(?{Buveur,Cru}(ABUS)).

La requête finale _E2 est comme suit :

E2 := ?{Buveur}(E1 ? ?Cru=Vin(E1)).

3.4  Inclusion et équivalence

Dans les définitions suivantes, un schéma-de-bases-de-données R est sous-entendu.

Soient _E1 et _E2 deux expressions algébriques. On dira que l’expression _E1 est inclue dans _E2, dénoté par E₁v E₂, si pour toute base de données I, _JE_1K^I ?_JE_2K^I.

On dira que les expressions E₁ et E₂ sont équivalentes, dénoté par E₁? E₂, si E₁v E₂ et _E2 v_E1_.

Exemple 6.On peut facilement prouver queSoit _R et _S deux noms de relation avec?_X(R ?· S) ? ?_X(R) ?·sorte?_X(S(_R).) = sorte(_S). Soit _X ? sorte(_R).

Il a été prouvé [1, Corollary 6.3.2] que l’équivalence des expressions algébriques est indécidable. C’est-à-dire, il n’existe pas d’algorithme qui prend en entrée deux expressions algébriques, et détermine si, oui ou non, ces deux expressions sont équivalentes.

Proposition 1.L’équivalence des expressions algébriques en SPJRUD est indécidable.

Figure 3.1 – Bases de données I (à gauche) et J (à droite).

3.5   Non-redondance des opérateurs

Un exercice intéressant est de démontrer qu’aucun des six opérateurs de l’algèbre SPJRUD n’est redondant. Démontrons ici que la différence est un opérateur non-redondant. Dénotons par SPJRU l’algèbre relationnelle qui ne contient pas la différence.

La démonstration fera appel aux bases de donnéesalgébrique I et J de la figure 3.1, et l’expression

E0 := ?A(?B=“1”(R)) ? ?A(?B=“2”(R)).

On aE0 JJE(0KIE0=I{{. On appelle cette requête(A,a)}} et JE0KJ = {}. Remarquons quenon-monotone : l’insertion de tuples dans la baseJ ajoute un tuple à I, mais que

Jde données peut avoir comme effet la suppression de tuples de la réponse. Intuitivement, laK J K différence est non-redondante car c’est le seul opérateur permettant de ressortir cet effet nonmonotone.

De façon plus formelle, démontrons qu’aucune expression algébrique de l’algèbre SPJRU (i.e., l’algèbre sans la différence) n’est équivalente à _E0. Dans le paragraphe suivant, on prouve que pour toute expression algébriquedeux), et doncet JE0K^J (JE0_EK^I, il est correct de conclure que soit6?_E0. E de l’algèbre SPJRU,JEKJ^IE=6KI J?E0JKEIK, soitJ . À partir deJEKJ =6 JEJE0KKJI ?(soit lesJEKJ

On prouve maintenant, par induction, que pour toute expression algébrique _E de l’algèbre

SPJRU, JEK^I ? (Jvoir figure 3.1), on a bien queEK^J . La base de l’induction est_REI==R_R, oùI est un sous-ensemble deR est un nom de relation. Par notre_RJ = _RJ . choix de I et J

Les autres possibilités pour _E sont comme suit :_{J K J K}

— EqueJ 1est une sélectionKC1 ? sorte1 J(, c’est-à-dire, l’évaluation deE1), carC?=_C“₌c”E_“c1_”(1Epeut contenir un renommage. L’hypothèse d’induction est₁). Noter que même siEC1=sur“c” IC1est un sous-ensemble de l’évaluation=sorte“c”(E(R1)) =Csur=“c{”I(A,BEest un sous-ensemble1)}J, il est possible.

E I ? E

 de E surJJ. Il est alors évident que l’évaluation deK ?

  de l’évaluation de ?  (E ) sur J, i.e., J? (E )KI ? J?   K

— E est une sélection ?_C=D(E₁). Raisonnement similaire au premier point.

— _E est une projection _?X(_E1). Raisonnement similaire au premier point.

— E est un renommage ?_{C?7 D}(E₁). Raisonnement similaire au premier point. — E est une jointure E1 1 E21. L’hypothèse d’induction est2 1 2 JE1KI ? JE1KJ et JE2KI ? JE2KJ .

 Il est alors évident que E 1 E  I ? JE 1 E KJ .

  J  K

— _E est une union _E1 ?· E2. Raisonnement similaire au point précédent.

Le paragraphe précédent démontre en fait que l’algèbre SPJRU ne permet pas d’encoder des requêtes non-monotones. La notion de monotonicité est définie, de façon générale, comme suit.

Soit E une expression algébrique relative à un schéma-de-base-de-données R. On dit que E est

monotoneRI ? RJ pour toutsi la propriété suivante est vérifiée pour toutes bases de donnéesR ? R, alors _JE_KI ?_JE_KJ . Une expression algébrique estInon-monotoneet J sur R : sisi elle n’est pas monotone.

Proposition 2.Chaque requête de l’algèbre SPJRU (i.e., l’algèbre sans la différence) est monotone.

La Proposition 2 explique pourquoi la requête “Quels buveurs sont exigeants?” de la section 3.3 a besoin de la différence. Supposons un buveur _b qui est exigeant selon la base de données actuelle. Insérons ensuite dans la relation _ABUS un tuple qui associe à _b un vin de qualité _C. Dans la nouvelle base de données, le buveur _b ne sera plus exigeant. Ce scénario montre que la requête “Quels buveurs sont exigeants?” est non-monotone, et donc pas exprimable en SPJRU.

3.6 Fermeture transitive

Voir chapitre 1 pour la définition de fermeture transitive. Il est connu [1, page 436] qu’il n’existe pas de requête en SPJRUD qui calcule la fermeture transitive d’une relation binaire. Cependant, l’algèbre permet de tester si une relation binaire est transitive. Soit _R un nom de relation avec sorte(^{R) =}{A,B}^{. Soit} E1 := _?AB(_?B7?C(_R)  _?A7?C(_R))_. 1

L’expression E₁ rend un tuple {(A,a),(B,b)} dès que la base de données contient deux tuples comme suit :

L’expression

E₂ := ?_{}(E₁? R)

teste si _E1 contient un tuple qui n’est pas dans _R. Si c’est le cas, la relation _R n’est pas transitive. Si _E2 retourne la relation vide, la relation _R est transitive. Noter que selon l’encodage de true et false expliqué dans la section 3.3, la requête _E2 demande en fait “Est-ce que la relation_R

n’est pas transitive?”.

3.7 La perspective “Unnamed”

Dans cette section, on définit l’algèbre relationnelle dans la perspective “Unnamed”. Un exercice intéressant est de démontrer que cette algèbre a exactement la même expressivité que l’algèbre SPJRUD.