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 An est défini comme suit :
An :={ha1, ,ani | a1, ,an ? 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 queb 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 etf0 : A0 ?BAtelle que pour chaque0 ?A. La restriction dea ?fAà l’ensemble0, f0(a) = f(Aa)0., 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,A1,B1,C1, ; 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.
|
Prénom |
Genre |
|
Jean Anne |
? |
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),,(GenreGenre},?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,R1,S1,T1, , 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) = {A1, ,An}.
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,
|
Cru |
Millésime |
Qualité |
|
Volnay |
1983 |
A |
|
Volnay |
1979 |
B |
|
Chablis |
1983 |
A |
|
Julienas |
1986 |
C |
|
Buveur |
Cru |
Millésime |
|
Jean |
Volnay |
1983 |
|
Jean |
Volnay |
1979 |
|
Pierre |
Volnay |
1979 |
|
Pierre |
Julienas |
1986 |
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(A1,A2, ,Ak), (2.1)
avecdont le schéma contientt1,t2 A?1R,AI2, ,A1 1k 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 RI. La syntaxe est comme suit :
S FOREIGN KEY(B1,B2, ,Bk) REFERENCES R, (2.2)
avecbase de données dont le schéma contientS un nom de relation et B1,B2, ,BIRk 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 deis ?S , il existe un tuple (unique)1 k constituent la clé primaire (2.1).RIten 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 Bi 6= Ai (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.
|
Plaque |
Châssis |
Type |
Année |
|
CGD.123 |
13459ABC |
Renault 19 |
1992 |
|
SAP.346 |
CBA54321 |
Peugeot 404 |
1994 |
VOITURES
|
Plaque |
Accessoire |
|
CGD.123 |
radio |
|
CGD.123 |
système antivol |
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 contientt? RI tel que t2(BR)) =respecte ces contraintes si et seulementt1(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(A1,A2, ,Ak), avec R un nom de relation et A1,A2, ,Ak des attributs distincts appartenant à sorte(R).
Cette contrainte est satisfaite par une bases de donnéestout t1,t2 ? RI, si t1[A1A2 ···Ak] = t2[A1A2 ···Ak I (1dont le schéma contient= t2. 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
|
NN |
Prénom |
Nom |
NPermisConduire |
|
94.04.01-001.31 |
Alex |
Astaire |
123456789 |
|
15.09.11-001.47 |
Bart |
Bretelle |
NULL |
|
91.06.22-001.31 |
Cloé |
Camp |
NULL |
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 t1,t2 tels que t1(Châssis) = NULL et t2(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 domn.
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 surRRdansest 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 E1 et E2 sont des expressions algébriques, alors E1E2 est une expression algébrique avec sorte(E1 1 E2) = sorte(E1) ? sorte(E2). 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 E1 et E2 sont des expressions algébriques avecsorte(E1?· E2) =sortesorte((EE11) =). Noter que le symbolesorte. Si aucune confusion(E2), alors E1?·E?·2 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 E1 et E2 sont des expressions algébriques avec sorte(E1) = sorte(E2), alors E1? E2 est une expression algébrique avec sorte(E1? E2) = sorte(E1).
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 EI la relation qui est le résultat de l’évaluation de E sur I. La définition de JEKI est comme suit :J K
— Si R est un nom de relation, alors RI := RI. 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 JRKI =6JRKJ .
— ?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(E1) et Y = sorte(E2).
Alors E1 1 E2I := {t | t[X] ? JE1KI et t[Y ] ? JE2KI}.
J K
— Soit XJ =A7?IsorteB (EKI) \ {:I=A{t}.| il existeI s ? JEKI tel que s[X] = t[X] et s[A] = t[B]}.
Alors ? (E)
— JE1?· E2KI :=JE1KI ?JE2KI, avec? l’union ensembliste.
— E1? E2K := JE1K \ JE2K , avec \ la différence ensembliste.
J
Une expression algébrique E est aussi appelée une requête, et EI 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?A6=“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 deE4 rend la relation {{}}, i.e., laE4 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 E1v E2, si pour toute base de données I, JE1KI ?JE2KI.
On dira que les expressions E1 et E2 sont équivalentes, dénoté par E1? E2, si E1v E2 et E2 vE1.
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.
|
A |
B |
|
a |
1 |
|
a |
2 |
|
A |
B |
|
a |
1 |
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 JE0KJ (JE0EKI, il est correct de conclure que soit6?E0. E de l’algèbre SPJRU,JEKJIE=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, JEKI ? (Jvoir figure 3.1), on a bien queEKJ . La base de l’induction estREI==RR, oùI est un sous-ensemble deR est un nom de relation. Par notreRJ = 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 est1). 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(E1). Raisonnement similaire au premier point.
— E est une projection ?X(E1). Raisonnement similaire au premier point.
— E est un renommage ?C?7 D(E1). 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 JEKI ?JEKJ . 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 E1 rend un tuple {(A,a),(B,b)} dès que la base de données contient deux tuples comme suit :
L’expression
E2 := ?{}(E1? 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 relationR
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.
