Bases de Données I
Université de Mons
Jef Wijsen
2017–2018
Merci de signaler toute erreur, de toute sorte (orthographe, grammaire, typographie, contenu ), à . Des suggestions pour améliorer les explications seront également appréciées.
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.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
9 Two-Phase Locking (2PL) 53
9.1 Cadre théorique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
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
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
Chapitre 1
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
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
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.
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 | ? |
?
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}
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}.
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].
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)
) = 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
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
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.
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.
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
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
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
Soit I une base de données sur R.
— 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
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))).
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)).
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).
Proposition 1.L’équivalence des expressions algébriques en SPJRUD est indécidable.
| A | B |
| a | 1 |
| a | 2 |
| A | B |
| a | 1 |
R
R
Figure 3.1 – Bases de données I (à gauche) et J (à droite).
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
— 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.
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 :
| A | B |
| a | c |
| c | b |
R
.
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?”.
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.
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 d’arité arité(R).
Sélection “attribut égal constante”, et a une constante, alors ?i=“a”Si(EE est une expression algébrique d’arité n, 1 ? i ? n) est une expression algébrique d’arité n.
Sélection “attribut égal attribut”, alors ?i=j(E) est une expression algébrique d’aritéSi E est une expression algébrique d’aritén. n et 1 ? i,j ? n
Projection Si E est une expression algébrique d’arité n et 1 ? i1,i2, ,ik ? n, alors ?i1,i2, ,ik(E) est une expression algébrique d’arité k.
Union Si E et F sont deux expressions algébriques de même arité. n, alors E ?· F est une expression algébrique d’arité n
Différence Si E et F sont deux expressions algébriques de même arité n, alors E ? F est une expression algébrique d’arité n.
Soit I une base de données sur R. La définition de JEKI est comme suit :
— Si R est un nom de relation, alors RI = RI.
——— JJJ??iii1==,ij“2a, ,i”(EKk)I(KEI)=KI {=h1a{1h,a2ai21, ,a,ai2n ni ?ikJEIKIa|1ia=i2=aja}}.. n
? (E) ={ha ,a , ,a i ? JEK | I .
I =
——— JJJEE ×?·FFKKI ==J{EhaK1II,a?2J, ,aFKII, où, oùm,b\?1est la différence ensembliste.,best l’union ensembliste.2, ,bni | ha1, ,ami ?JEKI,hb1, ,bni ?JFKI}.
La requête E3 retourne les buveurs exigeants :
| E1 E2 E3 | := := := | ?1,6(?2=4(?3=5(ABUS VINS))) ?1(E1 \ ?2=“A”(E1)) 1 ?1(ABUS) ? E2 |
Noter que la projection permet de permuter et de dupliquer des colonnes. Par exemple,
| 1 | 2 | 3 |
| b | a | a |
| d | c | c |
| 1 | 2 |
| a | b |
| c | d |
R?2,1,1(R)
Chapitre 4
Le calcul relationnel sera introduit dans la perspective “Unnamed”. L’idée est d’utiliser la logique du premier ordre pour interroger une base de données. Prenons la requête “Quels buveurs sont exigeants?” introduite dans la section 3.3. En calcul relationnel, cette requête peut être encodée comme suit :
.
partie gauche partie droite
Notez dés le début l’importance de la partie droite. Substituons b par la valeur “Senseo”. Comme Senseo n’est pas un buveur, la prémisse ABUS(“Senseo”,c,m) de l’implication sera fausse pour tout c et m. Mais alors la partie gauche de la conjonction est vraie! La partie droite de la conjonction joue le rôle de garde-fou : puisque ?c0?m0ABUS(“Senseo”,c0,m0) est fausse, la conjonction sera finalement fausse.
Supposons un nombre infini de variables x,y,z,x1,y1,z1 Aucune variable n’appartient à dom. Soit R un schéma-de-base-de-données.
— Chaque variable x est un terme.
— Chaque constante c ?dom est un terme.
— Si e1 et e2 sont des termes, alors e1 = e2 est une formule (atomique).
— Si R est un nom de relation d’arité k, et e1, ,ek son des termes, alors R(e1, ,ek) est une formule (atomique).
— Si ?1 et ?2 sont des formules, alors ?1? ?2, ?1? ?2 et ¬?1 sont des formules.
— Si ? est une formule et x une variable, alors ?x? et ?x? sont des formules.
L’expression ? ?(???est une abréviation pour?). ¬? ? ?. L’expression ? ? ? est une abréviation pour (? ??) ?
L’ensemble des variables libres d’une formule ?, dénoté par free(?), est défini comme suit :
— free(e1 = e2) = {e1,e2} \dom;
— free(R(e1, ,ek)) = {e1, ,ek} \dom;
— free(?1? ?2) = free(?1? ?2) = free(?1) ? free(?2);
— free(¬?1) = free(?1);
— free(?x?) = free(?x?) = free(?) \ {x}.
Si free(?) = {x1, ,xk}, on écrira ?(x1, ,xk).
La définition mathématique de la sémantique peut sembler plutôt rébarbative. Pourtant, rien
vraie; ?x?(x) est vraie si ? est vraie pour toute valeur de x
De façon plus formelle, le domaine actif d’une base de données I, dénoté par adom(I), est l’ensemble de toutes les constantes qui apparaissent dans I.
tationSoit Idune base de données sur le schéma-de-base-de-donnéestel que R. Fixons un domaine d’interpré-
adom(I) ?d?dom. (4.1)
On définit, pour chaque formule ?(x1, ,xk) etha1, ,aki ?dk, la notion de
I,d|= ?(a1, ,ak),
~xqui exprime que ?(a1, ,ak) 1est vraie dansk I1, relatif au domaine d’interprétationk . d. On écrira et ~a pour respectivement hx , ,x i et ha , ,a i
Le tuple?(xi) = a~aidonne lieu à uneet pour chaque cvaluation?d, ?(c) =? : dc. Intuitivement, la valeur de?{x1, ,xn} ?d telle que pour chaquexi est ai, et la valeur d’unei ? {1, ,n}, constante est la constante elle-même.
— I,d|= t1 = t2 si ?(t1) = ?(t2);
— I,d|= R(e1, ,ek) si h?(e1), ,?(ek)i ? RI ;
— si ?(~x) ? ?1(~x) ? ?2(~x), alors I,d|= ?(~a) si I,d|= ?1(~a) et I,d|= ?2(~a);
— si ?(~x) ? ?1(~x) ? ?2(~x), alors I,d|= ?(~a) si I,d|= ?1(~a) ou I,d|= ?2(~a);
— si ?(~x) ? ¬?1(~x), alors I,d|= ?(~a) si I 6|= ?1(~a);
— si ?(~x) ? ?y?(y,~x), alors I,d|= ?(~a) s’il existe c ?d tel que I,d|= ?(c,~a); — si ?(~x) ? ?y?(y,~x), alors I,d|= ?(~a) si I,d|= ?(c,~a) pour tout c ?d.
Une requête en calcul relationnel est une formule
{x1, ,xk | ?(x1, ,xk)}.
La réponse à cette requête contient tout tuple ha1, ,aki tel que I,d|= ?(a1, ,ak).
Une légère extension consiste à permettre que la même variable apparaisse plusieurs fois à gauche de la bar verticale. Par exemple (voir aussi section 3.7.3),
{x1,x2,x2| R(x2,x1)}.
Noter que le domaine d’interprétation d intervient à trois endroits dans le calcul de la réponse à une requête :
2. dans le teste I,d|= ?y?(y,~a), on cherche la valeur de y dans d; et
3. dans le teste I,d|= ?y?(y,~a), on prend, comme valeur pour y, toute valeur de d.
La question qui vient à l’esprit est : “Est-ce que la réponse à une requête peut varier selon le choix de d?”.
Malheureusement, le calcul relationnel défini précédemment a ses défauts. Prenons la requête :
{b | ?c?m(ABUS(b,c,m) ?VINS(c,m,“A”))}. /1
Comme expliqué dans l’introduction de ce chapitre, la formule à droite de la bar verticale est vraie si l’on remplace b par les valeurs “Senseo” ou “Chablis”, qui appartiennent donc à la réponse, à moins que “Senseo” et “Chablis” soient des valeurs dans d. Cette requête dépend donc du choix du domaine d’interprétation d. En plus, si d est un ensemble infini, la réponse à cette requête sera infinie (parce que chaque base de données est finie). Prenons une autre requête :
{c | ?mVINS(c,m,“A”)}. /2
lequel la qualité dec a été enregistré :
{c | ?m0?q0VINS(c,m0,q0) ? ?m?q (VINS(c,m,q) ? q = “A”)}.
La requête suivante est plus sévère; elle exige que c a été de qualité A dans tout millésimem qui apparaît dans la colonneMillésime:
{c | ?m0?q0VINS(c,m0,q0) ? ?c0?m?qVINS(c0,m,q) ?VINS(c,m,“A”)}.
Comme déjà illustré par la requête 1, contrairement à ce que l’on pouvait penser, une interprétation relative au domaine actif n’est pas toujours naturelle. Soit/ I la base de données suivante :
| Modèle | Couleur |
| Clio | bleu |
| Laguna | bleu |
| Laguna | rouge |
R
.
Considérons la requête “Quels modèles sont disponibles en chaque couleur?”. La réponse attendue est {hLagunai}. Prenons la requête :
{m | ?c0R(m,c0) ? ?cR(m,c)}. /3
Une interprétation relative au domaine actif ne donne pas la bonne réponse : puisquen’est pas un tuple de R et “Clio” appartient au domaine actif, la sous-formule ?cRh(Laguna“Laguna”,Clio,c)i n’est pas vraie. La bonne requête est :
{m | ?c0R(m,c0) ? ?m0?c R(m0,c) ? R(m,c)},
ce qui est équivalent à :
{m | ?c0R(m,c0) ? ¬?m0?c R(m0,c) ? ¬R(m,c)}.
domain independentOn dira qu’une requête) si la réponse à la requête ne dépend pas du choix de{~x | ?(~x)} est indépendante du domaine [d’interprétationd que l’on fait dans (4.1).] (en anglais :
Exemple avec disjonction
| {x | R(a) ? R(b) ? R(x)} Soit 1 la base de données suivante : | /4 |
I R
On a adom(I1) = {a,c}. L’interprétation relative à. L’interprétation relative à{a,c}{a,c,ddonne la réponse} donne la réponse{hai,hci}{h. Soitai,hcid,hunedi}. constante telle que d 6? {a,c}
La requête /4 n’est donc pas indépendante du domaine.
Exemple avec négation
| Soit 2 la base de donnée suivante : | {x | ¬R(x)} | /5 |
. a
On arelative àadom{a,d(I2) =}, d{=6 a}a. L’interprétation relative à, donne la réponse {hdi}. {a} donne la réponse vide. L’interprétation
Exemple avec quantification universelle
| Soit la base de donnée suivante : | {x | ?yR(x,y)} | /6 |
| A | B |
| a | a |
| a | b |
I3 R
.
On arelative àadom{(a,b,dI3) =}{donne la réponse vide, parce quea,b}. L’interprétation relative à {a,bha,d} donne la réponsei 6?RI3. {hai}. L’interprétation
La solution consistera à imposer des restrictions syntaxiques qui garantissent l’indépendance du domaine. Ces restrictions peuvent prendre différentes formes. On introduit ici des restrictions qui sont directement inspirées sur l’algèbre relationnelle. La notion de variable libre reste inchangée et n’est pas répétée ci-après.
Nom de relation Si R est un nom de relation d’arité n, et x1, ,xn sont des variables distinctes, alors R(x1, ,xn) est une formule safe (atomique). La restriction que x1, ,xn soient distinctes fait que chaque variable correspond à exactement un attribut de sorte(R). Sélection Si ? est une formule safe, a est une constante, et x,y ? free(?), alors ??(x = “a”) et ? ? (x = y) sont des formules safe.
Projection Si ? est une formule safe et x ? free(?), alors ?x? est une formule safe.
Jointure Si ?1 et ?2 sont des formules safe, alors ?1? ?2 est une formule safe.
Unionformule safe. La restriction queSi ?1 et ?2 sont des formules safe avec?1 et ?2 aient exactement les mêmes variables libresfree(?1) = free(?2), alors ?1? ?2 est une
provient de la restriction que l’union E1?·E2 est seulement définie si sorte(E1) = sorte(E2). Noter que la formule dans 4 n’est donc pas safe.
Différenceune formule safe. La restriction queSi ?1 et ?2 sont des formules safe avec/ ?1 et ?2 aient exactement les mêmes variables libresfree(?1) = free(?2), alors ?1? ¬?2 est sorteprovient de la restriction que la différence(E2). Intuitivement, la formule ?1 est un garde-fou qui fixe le domaine des variablesE1? E2 est seulement définie si sorte(E1) = libres. Noter que la formule dans /5 n’est donc pas safe.
Une requête {~x | ?(~x)} est safe si la formule ?(~x) est safe. Dénotons par SRC (Safe Relational Calculus) la restriction du calcul relationnel aux formules et requêtes safe.
— Chaque requête en SRC est équivalente à une requête en SPJRUD.
— Chaque requête en SRC est indépendante du domaine (une conséquence des deux assertions qui précèdent).
SRC impose une syntaxe très restrictive aux formules. Malgré ces restrictions, l’assertion suivante est vraie :
— Chaque requête qui est indépendante du domaine est équivalente à une requête en SRC
(voir section 4.5).
Bien que les restrictions syntaxiques ne diminuent donc pas pas l’expressivité, elles rendent le langage SRC rébarbatif à utiliser. Par exemple, la requête(R(x,y) ? x = y)} en SRC. Dans [1, Section 5.4], on trouve des restrictions moins sévères{x | R(x,x)} doit s’écrire comme
{du calcul relationnel qui garantissent aussi l’indépendance du domaine.x | ?y
Sur la base de la Proposition 1, on peut facilement prouver qu’il est indécidable de déterminer si, oui ou non, une formule en calcul relationnel est indépendante du domaine. Considérer une requête de la forme :
{~x |?(~x) ? ¬(?1? ?2)}, (4.2)
avec ?1 et ?2 des formules booléennes (i.e., sans variables libres) en SRC, et ? une formule en calcul relationnel telle que {~x | ?(~x)} n’est pas indépendante du domaine. Deux cas sont possibles :
1. Sitoute base de données, quel que soit le domaine d’interprétation. Dans ce cas, la requête?1? ?2, alors ¬(?1? ?2) est faux, et la requête (4.2) retourne la réponse vide sur est donc indépendante du domaine.
2. Si ?16? ?2, alors ¬(?1? ?2) est vrai, et la requête (4.2) est équivalente à {~x | ?(~x)}, une requête qui n’est pas indépendante du domaine.
On explique maintenant pourquoi chaque requête qui est indépendante du domaine est équivalente à une requête en SRC. Noter d’abord qu’il existe une requête {x | ?(x)} en SRC qui prend en entrée une base de données et qui retourne son domaine actif. Par exemple, supposons que le schéma-de-base-de-données consiste en deux noms de relations, R et S, chacun d’arité 2. Alors ?(x) est la formule suivante :
?(x) := (?yR(x,y) ? ?yR(y,x)) ? (?yS(x,y) ? ?yS(y,x)).
Soit {~x | ?(~x)} une requête en calcul relationnel qui est indépendante du domaine. La requête en SRC équivalente peut être construite comme suit.
— Assurer que toute formule atomique respecte les contraintes syntaxiques imposées par SRC. Par exemple, remplacer(x,y) ? (y = x); R(x,“a”) par R(x,y) ? (y = “a”); remplacer R(x,x) par
R
— remplacer chaque sous-formule x = “a” de ? par ?(x) ? (x = “a”);
— remplacer chaque sous-formule x = y de ? par (?(x) ? ?(y)) ? (x = y);
— remplacer chaque négation ¬?(x1, ,xn) par (?(x1) ? ··· ? ?(xn)) ? ¬?(x1, ,xn);
— assurer que les parties gauche et droite d’une disjonction aient les mêmes variables libres.
Par exemple, remplacer ?1(x,y) ? ?2(y,z) par (?1(x,y) ? ?(z)) ? (?2(y,z) ? ?(x)).
On peut vérifier que ces étapes aboutissent à une requête en SRC qui donne les mêmes réponses que {~x | ?(~x)} avec, comme domaine d’interprétation, le domaine actif. Comme {~x | ?(~x)} est indépendante du domaine, une interprétation relative au domaine actif retourne, par définition, la réponse correcte.
Dans le calcul introduit précédemment, les variables représentent des valeurs de dom. On introduit maintenant brièvement une variante du calcul relationnel dans lequel les variables représentent des tuples. Dans la littérature, on utilise souvent les dénotations DRC et TRC pour distinguer ces deux approches :
Prenons le suivant schéma-de-bases-de-données, pris du livre [7] :
S[S],Sname,Status,City]
P[P],Pname,Color,Weight,City]
SP[S],P],Qty]
Les tables S et P enregistrent respectivement des fournisseurs et des produits. La table SP enregistre quel fournisseur sait fournir quel produit, et en quelle quantité. Chaque quantité est en nombre entier strictement positif.
Requête 7.7.4
Trouver tout couple de villes tel qu’un fournisseur habitant la première ville sait fournir un produit stocké dans la deuxième ville.
La requête en SQL : SELECT s.City, p.City
FROM S AS s, SP AS r, P AS p
WHERE s.S] = r.S]
AND r.P] = p.P]; La requête en SRC :
{s.4,p.5 | S(s) ?P(p) ? ?r (SP(r) ? s.1 = r.1 ? r.2 = p.1)} 4,p.5 | ?r (S(s) ?P(p) ?SP?(r) ? s.1 = r.1 ? r.2 = p.1)}
{s.
Pour améliorer encore la lisibilité, on remplace les indices par les attributs :
{s.City,p.City | S
{s.City,p.City | ?r (S(s) ?P(p) ?SP(r) ? s.S] = r.S] ? r.P] = p.P])} Remarquer que cette dernière requête en TRC est très proche de la requête en SQL.
Requête 7.7.15
Trouver les noms de fournisseurs qui savent fournir tout produit rouge.
En SQL :
SELECT s.Sname
FROM S AS s
WHERE NOT EXISTS ( SELECT *
FROM P AS p
WHERE p.Color = “red”
AND NOT EXISTS ( SELECT *
WHERE r.S] = s.S] AND r.P] = p.P] ) ); En SRC :
{s.2 | S(s) ? ?p ? P (p.3 = “red”
{s.2 | S(s) ? ¬?p ? P (p.3 = “red” ? ¬?r ?SP(r.1 = s.1 ? r.2 = p.1))} Avec les attributs :
{s.Sname | S(s) ? ?p ? P (p.Color
{s.Sname | S(s) ? ¬?p ? P (p.Color = “red” ? ¬?r ?SP(r.S] = s.S] ? r.P] = p.P]))}
Formules On suppose des variables r,s,t, , et une fonction qui fait correspondre, à chaque variable, une arité dans {0,1,2, }.
— Chaque constante c ?dom est un terme. — Si t est une variable d’arité n et i ? {1,2, ,n}, alors t.i est un terme.
— Si e1 et e2 sont des termes, alors e1 = e2 est une formule (atomique).
— Si R est un nom de relation et r une variable de même arité que R, alors R(r) est une formule (atomique).
— Si ?1 et ?2 sont des formules, alors ?1? ?2, ?1? ?2 et ¬?1 sont des formules.
— Si ? est une formule et r une variable, alors ?r? et ?r? sont des formules.
Requêtes Une requête est une expression de la forme {L | ?}
avec L une liste de termes et ? une formule telles que
— pour chaque terme r.i dans L, la variable r est une variable libre de ?; et — chaque variable libre de ? apparaît dans un terme de L. Abréviations On introduit un nombre d’abréviations :
— ?1? ?2 est une abréviation de ¬?1? ?2 ;
— ?r ? R(?) est une abréviation de ?r (R(r) ? ?); — ?r ? R(?) est une abréviation de ?r (R(r) ? ?);
— u1 =6 u2 est une abréviation de ¬(u1 = u2). Noter que ces abréviations sont cohérentes :
?r ? R(?) ???¬¬?¬?¬¬?rr¬rr ((?R¬rRR(r(()r??) ?)) (((logiquelogiqueabréviation:: ¬¬¬?))r?p ?? ?p) r¬? et p ?q ? ¬p ?q)
) ??
?? ¬?¬?r (?RR( ()¬? ¬?)?) ((De Morganabréviation)
Soit I une base de données et d un domaine d’interprétation. — Une variable d’arité n prend ses valeurs dans dn (et non dans d).
— R(r) est vrai si le tuple r appartient à la relation RI.
— ?r? est vrai s’il existe un tuple r ?dn qui rend ? vrai, avec n l’arité de r. — ?r? est vrai si pour tout tuple r ?dn, ? est vrai, avec n l’arité de r.
Dans le calcul TRC, comme dans le calcul DRC, certaines requêtes ne sont pas indépendantes du domaine :
{r.1 | R(r) ? ?s(S(s))}; /
{r.1 | ¬R(r)}. /
SQL est un mixe de l’algèbre relationnelle et le calcul TRC. Par exemple, pour un schéma-de-
bases-de-données qui contientune union en SQL. Noter aussi qu’il serait illogique de vouloir remplacer, dans cette requêteR[A] et S[B], la requête TRC {r.1 | R(r) ? S(r)} donne lieu à
TRC, l’indice 1 par un attribut (A ou B).
Prenons la requête :
Donner des couples (n1,n2) de noms de fournisseurs tels que les produits fournis par n1 sont un sous-ensemble des produits fournis par n2. Il est difficile d’encoder cette requête directement en SQL.
En TRC :
{s1.2,s2.2 | S(r(1s.11 =) ? Ss1(.s12)? ?? ?rr1? SP
{s1.2,s2.2 | S(r(1s.11 =) ? Ss1(.s12)? ¬?? ¬?r2r1??SPSP(r2.1 = s2.1 ? r2.2 = r1.2))}
Avec les attributs :
{s1.Sname,s2.
{s1.Sname,s2.
r1.S] s1.S] ? ¬?r2? SP r2.S] s2.S] ? r2.P] r1.P] } La traduction en SQL : SELECT s1.Sname, s2.Sname
FROM S AS s1, S AS s2
WHERE NOT EXISTS ( SELECT *
WHERE r1.S] = s1.S]
AND NOT EXISTS ( SELECT *
FROM SP AS r2
WHERE r2.S] = s2.S]
AND r2.P] = r1.P] ) );
Chapitre 5
Le langage SQL fera l’objet des Travaux Pratiques. Ce chapitre n’est qu’une brève introduction. La bases de données et les requêtes sont reprises de [7].
| P1 | Nut | Red | 12 | London |
| P2 | Bolt | Green | 17 | Paris |
| P3 | Screw | Blue | 17 | Rome |
| P4 | Screw | Red | 14 | London |
| P5 | Cam | Blue | 12 | Paris |
| P6 | Cog | Red | 19 | London |
| S1 | Smith | 20 | London | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| S2 | Jones | 10 | Paris | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| S3 | Blake | 30 | Paris | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| S4 | Clark | 20 | London | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| S5 | Adams | 30 | Athens
SP S# P# QTY 5.2 Création de domaines et de tablesCREATE DOMAIN COLOR CHAR(6) DEFAULT ‘???’ CONSTRAINT VALID_COLORS CHECK ( VALUE IN ( ‘Red’, ‘Yellow’, ‘Blue’, ‘Green’, ‘???’ ) ) ; CREATE DOMAIN S# CHAR(5) ; CREATE DOMAIN QTY NUMERIC(9) ; CREATE TABLE S ( S# S#, SNAME NAME, STATUS STATUS, CITY CITY, PRIMARY KEY ( S# ) ) ; CREATE TABLE P ( P# P#, PNAME NAME, COLOR COLOR, WEIGHT WEIGHT, CITY CITY, PRIMARY KEY ( P# ) ) ; CREATE TABLE SP ( S# S# NOT NULL, P# P# NOT NULL, QTY QTY NOT NULL, PRIMARY KEY ( S#, P# ), FOREIGN KEY ( S# ) REFERENCES S ON DELETE CASCADE ON UPDATE CASCADE, FOREIGN KEY ( P# ) REFERENCES P ON DELETE CASCADE ON UPDATE CASCADE, CHECK ( QTY > 0 AND QTY < 5001 ) ) ; 5.3 Retrouver des informationsGet color and city for “nonParis” parts with weight greater than 10. SELECT P.COLOR, P.CITY WHERE P.CITY <> ‘Paris’ AND P.WEIGHT > 10 ; SELECT DISTINCT P.COLOR, P.CITY FROM P WHERE P.CITY <> ‘Paris’ AND P.WEIGHT > 10 ; SELECT DISTINCT P.COLOR, P.CITY FROM P WHERE P.CITY <> ‘Paris’ AND P.WEIGHT > 10 ORDER BY CITY DESC ; For all parts, get the part number and the weight of that part in grams. Supposons que le poids est donné en livre (=454 g). SELECT P.P#, P.WEIGHT * 454 AS GMWT FROM P ; Get full details of all suppliers. SELECT * FROM S ; SELECT S.* FROM S ; Get all combinations of supplier number and part number such that the supplier and part in question are colocated. SELECT S.S#, P.P# FROM S, P WHERE S.CITY = P.CITY ; Sémantique. Premièrement, “FROM S, P” donne le produit cartésien de S et P.
Deuxièmement, “WHERE S.CITY = P.CITY” sélectionne les tuples satisfaisant la condition.
Finalement, “SELECT S.S#, P.P#” sélectionne (ou plutôt : projette) les colonnes mentionnées. Get all pairs of city names such that a supplier located in the first city supplies a part stored in the second city. SELECT S.CITY, P.CITY FROM S, SP, P WHERE S.S# = SP.S# AND SP.P# = P.P# ; Get the total number of suppliers. SELECT COUNT(*) AS N FROM S ; Get the maximum and the minimum quantity for part P2. SELECT MAX ( ) AS MAXQ, MIN ( ) AS MINQ FROM SP WHERE SP.P# = ‘P2’ ;
For each part supplied, get the part number and the total shipment quantity. SELECT SP.P#, SUM ( ) AS TOTQTY FROM SP GROUP BY SP.P# ; Sémantique. Premièrement, imaginons que “FROM SP GROUP BY SP.P#” donne la “table” suivante.
Finalement, “SELECT SP.P#, SUM ( ) AS TOTQTY” donne :
SELECT P.P#, ( SELECT SUM ( ) FROM SP WHERE SP.P# = P.P# ) AS TOTQTY FROM P ; Get part number for all parts supplied by more than one supplier. SELECT SP.P# FROM SP GROUP BY SP.P# HAVING COUNT ( SP.S# ) > 1 ; Get supplier names for suppliers who supply part P2. SELECT DISTINCT S.SNAME FROM S WHERE S# IN ( SELECT SP.S# FROM SP WHERE SP.P# = ‘P2’ ) ; SELECT DISTINCT S.SNAME FROM S WHERE EXISTS ( SELECT * FROM SP WHERE SP.P# = ‘P2’ AND SP.S# = S.S# ) ; SELECT DISTINCT S.SNAME FROM S, SP WHERE S.S# = SP.S# AND SP.P# = ‘P2’ ; Get supplier numbers for suppliers with status less than the current maximum status in the S table. SELECT S.S# FROM S WHERE S.STATUS < ( SELECT MAX ( S.STATUS ) FROM S ) ; Get supplier names for suppliers who do not supply part P2. SELECT DISTINCT S.SNAME FROM S WHERE S# NOT IN ( SELECT SP.S# FROM SP WHERE SP.P# = ‘P2’) ; SELECT DISTINCT S.SNAME FROM S WHERE NOT EXISTS ( SELECT * FROM SP WHERE SP.P# = ‘P2’ AND SP.S# = S.S# ) ; Get supplier names for suppliers who supply all red parts. SELECT S.SNAME FROM S WHERE NOT EXISTS ( SELECT * FROM P WHERE P.COLOR = ‘Red’ AND NOT EXISTS ( SELECT * WHERE SP.S# = S.S# AND SP.P# = P.P# ) ) ; Get part numbers for parts that either weigh more than 16 pounds or are supplied by supplier S2, or both. SELECT P.P# FROM P WHERE P.WEIGHT > 16 UNION SELECT SP.P# FROM SP WHERE SP.S# = ‘S2’ ; 5.4 Mises à jourSingle-row INSERT. INSERT INTO P ( P#, PNAME, COLOR, WEIGHT, CITY ) VALUES (‘P8’, ‘Sprocket’, ‘Pink’, 14, ‘Nice’ ) ; Multi-row INSERT. INSERT INTO TEMP ( S#, CITY ) SELECT S.S#, S.CITY FROM S WHERE S.STATUS > 15 ; Multi-row UPDATE. UPDATE P SET COLOR = ‘Yellow’, WEIGHT = P.WEIGHT + 5 WHERE P.CITY = ‘Paris’ ; Multi-row UPDATE. UPDATE P SET CITY = ( SELECT S.CITY FROM S WHERE S.S# = ‘S5’ ) WHERE P.COLOR = ‘Red’ ; Multi-row DELETE. DELETE FROM SP WHERE ‘London’ = ( SELECT S.CITY FROM S WHERE S.S# = SP.S# ) ; 5.5 Intégration de SQL à des langages de programmationEXEC SQL DECLARE X CURSOR FOR SELECT S.S#, S.SNAME, S.STATUS FROM S WHERE S.CITY = :Y ; EXEC SQL OPEN X ; /* execute the query */ EXEC SQL FETCH X INTO :V1, :V2, :V3 ; /* fetch the first row (if any) */ WHILE a row is fetched LOOP EXEC SQL FETCH X INTO :V1, :V2, :V3 ; /* fetch the next row (if any) */ END-LOOP EXEC SQL CLOSE X ; /* deactivate cursor X */ 5.6 Vues5.6.1 Définition des VuesUne vue est une table virtuelle dont le schéma et le contenu sont dérivés de la base réelle par un ensemble de requêtes. CREATE VIEW REDPARTS ( P#, PNAME, WT, CITY ) AS SELECT P.P#, P.PNAME, P.WEIGHT, P.CITY FROM P WHERE P.COLOR = ‘Red’ ; CREATE VIEW PQ AS SELECT SP.P#, SUM ( ) AS TOTQTY FROM SP GROUP BY SP.P# ; 5.6.2 Interrogation au travers de vuesGet red parts that weigh more than 15 pounds. SELECT P# FROM REDPARTS WHERE WT > 15 ; ? SELECT P# FROM P WHERE WEIGHT > 15 AND COLOR = ‘Red’ ; 5.6.3 Mise à jour au travers de vuesUPDATE REDPARTS SET WT = 454 * WT ; ? UPDATE P SET WEIGHT = 454 * WEIGHT WHERE COLOR = ‘Red’ ; UPDATE PQ SET TOTQTY = TOTQTY + 1 ; ? UPDATE SP SET ??? Chapitre 6 Les Dépendances Fonctionnelles6.1 IntroductionLa table suivante enregistre l’horaire du premier quadrimeste. Le premier tuple, par exemple, indique qu’une séance du cours de Physique I aura lieu chaque lundi à 8H15; le titulaire de ce cours est le professeur Albert Einstein.
Les deux contraintes suivantes doivent être respectées à chaque instant : — Chaque cours n’a qu’un seul titulaire. — Aucun professeur ne peut enseigner deux cours distincts à une même plage horaire. Par exemple, on ne peut pas déplacer le cours de Physique I du “lundi, 8H15” au “lundi, 10H15”, car ce déplacement engendrait un conflit horaire pour Albert Einstein. Ces contraintes seront appelées des dépendances fonctionnelles, et dénotées comme suit : Cours ? Prof : À chaque cours ne peut correspondre qu’un seul professeur. Prof,Heure ?Cours: À chaque combinaison d’un professeur et une plage horaire ne peut correspondre qu’un seul cours. Noter qu’en conséquence, à chaque combinaison d’un cours et plage horaire ne peut correspondre qu’un seul professeur : Cours,Heure ? Prof. 6.2 Syntaxe et sémantiqueToutes les définitions dans la suite de ce chapitre sont relatives à un schéma-de-relation A. Syntaxe Une dépendance fonctionnelle (DF) sur A est une expression X ? Y avec X,Y ? A. SémantiqueX ? Y , si pour toutUne relations,t ? R, siR surs[XA] =satisfait (ou respecte) la DFt[X], alors s[Y ] = t[Y ]. 1 X ? Y , dénoté par R |= Soitpar ??|=un ensemble de DF surX ? Y , si pour toute relationA. Une relationR surRAsurest une conséquence logique de= ?A satisfait, alors R?|=, dénoté parX ?Y . R |= ??, dénoté, si R satisfait chaque DF dans ?. Une DF X ?surY A, si R | Dans ce syllabus, si l’on écrit |= pour dénoter une conséquence logique, il est sous-entendufinies. L’exemple 11 illustrera que que l’on se restreint aux relations (et bases de données) l’implication “finie” peut être différente de l’implication “non restreinte”. Exemple 7.{A ? B Soit A = {A,B,C}. On va démonter queune relation quelconque qui respecteA ? C est une conséquence logique deA ? B(Cet) =B ?t(CC).. , B ? C}. Dans ce but, soit R Soit s,tdeux tuples quelconques de R tels que s(A) = t(A). Il faut démontrer que s À partir deà partir de s,ts,t ?? RR,, ss((BA) =) = tt((AB)), etet RR|=|=AB??BC, il est correct de conclure, il est correct de conclures(Bs() =C) =t(Bt()C. Ensuite,). Soiton a??11,?|=2 Xdeux ensembles de DFs sur1 A?. On écrira2 sont équivalents, dénoté par?1 |= ?2 si pour toute DF?1 ? ?X2, si??Y1 dans|= ?2?et2, ? Y . On dira que ? et ?2 |= ?1. Exemple 8. Les ensembles {A ? B,B ? C} et {A ? B,B ? C,A ? C} sont équivalents. Proposition 3= A \ XY . Alors,(Theorème de HeathR = ?XY (R 1 XZ).Soit.R une relation sur A telle que R |= X ?Y et Z ) ? (R) Démonstration. Il est facile de vérifier que l’inclusion R ? ?XY (R) 1 ?XZ(RXY) (est vraie pourR) ?XZ(R). Alorstoute relation[XY ] R surXY (U. Pour la démonstration de l’inclusion opposée, soit) et [ ] XZ(R). Alors, ils existent des tuplest ? ?t1,t2 R1 tels que t ?? R t XZ ?? ? t1[XY ] = t[XY ] et t2[XZ] = t[XZ]. Donc, t1[X] = t[X], t2[X] = t[X] et t1[Y ] = t[Y ]. Puisque t2[X] = t2[X] et R|= X ? Y , on a 2t1=[Yt] =, donct2[Yt], donc?R. t2[Y ] = t[Y ]. À partir de t2[Y ] = t[Y ] et t [XZ] = t[XZ], on peut conclure t ? |= X ?Y . La fermeture d’un ensemble X d’attributs par rapport à un ensemble ? de DFs, dénotée par X?,?, est définie comme suit : X?,? := {A ? A | ? |= X ? A}. Il est facile de vérifier que ? |= X ? Y si et seulement si Y ? X?,?. L’algorithme suivant prend en entrée un ensemble ? de DFs et un ensemble X d’attributs, et retourne X?,?. Algorithme 1.Entrée : un ensemble ? de DFs, un ensembleX d’attributs Sortie : X?,? NonUtilisé := ? Fermeture := X répéter aussi longtemps que NonUtilisé change si W ? Z ? NonUtilisé et W alors i.ii. NonUtiliséFermeture :=:=FermetureNonUtilisé??Z\ {FermetureW ? Z} retourner Fermeture Proposition 4.Avec ? estX en entrée, l’Algorithme 1 calculeX?,?. Démonstration. Il est facile de démontrer que l’algorithme se termine. Soit résultat le résultat retourné par une exécution de l’algorithme. Il est facile de prouver que résultat ? X?,?. Pour prouver l’inclusion opposée,Acomme suit :?6 résultat. Il faut montrer que AX?6?,?X??,?, i.e.,résultat?, soit|6= X ?A un attribut quelconque tel queA. Construisons une relation R Az 1 }| résultatA` { Az `autres attributs+1 }| An{ . attributs de 0 ··· 00 01 ······ 01 0 ··· Démontrons que R |= ?R. Par contradiction, supposons que, on a W ? résultat et Zrésultat?6 résultat, une contradiction.R. D’autre part, puisque l’exécution6|= W ? Z avec W ? Z ? ?. Par notre construction de de l’algorithme 1 s’est terminée, il faut que Z ? 6.4 Autres dépendances6.4.1 Dépendances de jointure et dépendances multivaluéesUne= Sdépendance de jointure`i=1Xi. Une relation R (surDJ) surA satisfait cette DJ siA est une expression 1 [X1,X2, ,X`] avec ` ? 1 et A R = ?X1(R) 1 ?X2(R) 1 ··· 1 ?X`(R). relation R sur A satisfait cette DMV si R |= Uneun cas spécial d’une DJ. Dans l’autre direction, on peut vérifier qu’une DJdépendance multivaluée (DMV) sur A1est une expression[XY,XZ] avec Z =XA \XYY avec. Une DMV est donc[XX,Y1,X2]? Aavec deux. Une composants est équivalente à X1? X2X1 (ce qui est équivalent à X 1 \Exemple 9. Soit R la relation suivante.
R Les projections ci-après permettent de vérifier que[ABC,BCD]. Noter que la DJ [ABC,BCD] est équivalente à la DMVR = ?ABC(R) 1 BC?BCD(RA)(, doncou BCR|=D1). 1
?ABC(R)?BCD(R) Par contre,{(A,1), (B,bR), (|6=C,d1 )[AB,BC,CD, (D,?)}; ce tuple n’appartient pas à]. En effet, ?AB(R) 1 ?BCR.(R) 1 ?CD(R) contient le tuple La proposition suivante exprime une interaction entre les DF et DMV. ensemble de DF surProposition 5.SoitAA. Alorsun ensemble d’attributs, et soit? |=1 [XY,XZ] si et seulement si{X,Y,Z}?une partition de|= X ?Y ou ?A. Soit|= X ?? unZ. Démonstration. ?= Conséquence de la Proposition 3. =? Par contraposition. Supposons ? 6|= X ?Y et ? 6|= X ?Z. On peut supposer des attributs distincts B ?Y et C ?Z tels que ? |6= X ?B et ? |6= X ?C. Construisons une relation R avec deux tuples, t0 et t1, comme suit :
z . ··· ··· (t1) L’étudiant est invité à démontrer comme exercice quedémontre que ?XY 1 XZ( R |= ?(B. Dans le paragraphe suivant, on) =6 t(C), donc R |6=1 [XY,XZ]. (R) ? R) contient un tuple t tel que t Puisquet 0X ?] =Xt?1,[?X,]t,0t[[XY] =] = tt10[[XY ]]. La jointureet t[Z] = t1[Z?]XY. Clairement,(R) 1 ?XZt((RB)) = 0contient un tupleet t(C) = 1. t tel que [X] = t [X 6.4.2 Dépendances d’inclusionSoit R un schéma-de-base-de données. Une dépendance d’inclusion (DI) sur R est une expression R[A1, ,Ak]? S[B1, ,Bk] où — k 1?et1S; sont des noms de relation dansk R (il se peut quesorte(R); R = S); — R — A , ,A sont des attributs distincts dans — B1, ,Bk sont des attributs distincts dans sorte(S). Une base de données I sur le schéma R satisfait cette DI si pour tout r ? RI, il existe s ? SI tel que pour tout i ? {1, ,k}, r(Ai) = s(Bi). Exemple 10. Soit I la base de données contenant les relations suivantes :
R S R[B] ? R[A] S[C,D] ? R[B,A] L’exemple suivant montre que dans certains raisonnements, on utilise le fait que les bases de données sont finies. Ces raisonnements peuvent être faux si l’on acceptait des relations infinies. Cette observation est une motivation pour la théorie des modèles finis [10], une branche de la logique mathématique. Exemple 11. Soit R = {R} un schéma-de-base-de-données avec sorte(R) = {A,B}. Soit ? = {A ?B,R[A] ?R[B]}. Dans le paragraphe suivant, on démontre ? |= R[B] ?R[A]. nombre n Soitndans la colonneI une base de données quelconque surtel queB|deRIR| =I. Puisque le nombre de valeurs distinctes dans la colonnen. PuisquesatisfaitI satisfaitR[AR] ?qui satisfaitAR?[BB], ces, la colonnen?valeurs doivent toutes apparaître. PuisqueA de la relationI est finie, il existe unB Rne peut pasI contient valeurs distinctes. Puisque I être supérieur à n, il est correct de conclure R[B] ? R[A]. Noter cependant qu’il existe une relation infinie qui satisfait ? mais qui ne satisfait pas R[B] ? R[A] :
R Dans la section 6.3, on a vu qu’il existe un algorithme qui prend en entrée un ensemble ? de DFs et une DF ?, et qui détermine si ? |= ? ou ? 6|= ?. Il a été prouvé [1, Theorem 9.2.4] qu’un tel algorithme n’existe pas si ? peut contenir des DIs en plus des DFs. Proposition 6.Le problème suivant est indécidable : pour une DF? et un ensemble ? contenant des DFs et des IDs, décider si ? |= ?. Chapitre 7 Les Formes NormalesCritics of normalization usually miss this point; they claim (quite rightly) that the ideas are all basically common sense, but they typically do not realize that it is a significant achievement to state what “common sense” means in a precise and formal way. C.J. Date [6, page 309] Einstein”. La valeur cachée est stocke deux fois le fait qu’Albert Einstein est le titulaire du cours de Physique I.
Cette redondance complique la maintenance des données. Le jour où Albert Einstein serait remplacé par François Englert comme titulaire du cours de Physique I, il faut faire attention de bien encoder ce remplacement à plusieurs endroits. Noter que cette redondance émerge dès qu’un cours à lieu à deux ou plusieurs plages horaires, ce qui est possible, car la DF Cours? Heure n’est pas imposée. 7.2 BCNFUn schéma-DF est un couple (A,?) avec A un schéma-de-relation et ? un ensemble de DFs sur A. Intuitivement, on dira qu’un schéma-DF (A,?) est en BCNF si dans une relation sur A qui respecte ?, il ne peut pas y avoir des redondances à cause des dépendances fonctionnelles. La définition suivante exprime cette intuition de façon formelle. Un schéma-DF (A,?) ?est en BCNF (|= X ? A. Boyce-Codd Normal Form) si pour toute DF X ? Y ? ? telle que Y ?6 X, on a Exemple 12. Soit A = {Prof,Cours,Heure} avec ? =appartient à{Cours ? Prof?, mais, {Prof?,6|=HeureCours} ??CoursHeure}.. Ce schéma-DF n’est pas en BCNF car Cours ? Prof Exemple 13.schéma-DF Soit A = {Etudiant´ ,Dép,Fac} avec ? =appartient à{Etudiant´ ??etDép? ,|6=DépDép?? FacEtudiant´ }. Le. (A,?) n’est pas en BCNF car Dép ? Fac Noter les redondances dans la table suivante : on stocke plusieurs fois que le département d’Info fait partie de la faculté des Sciences.
La solution consiste à décomposer ce schéma-DF en deux schémas-DF, comme suit.
Après décomposition, les redondances ont disparu : on ne stocke qu’une seule fois que le département d’Info fait partie de la faculté des Sciences. 7.3 DécompositionsLa définition suivante formalise la notion de décomposition. Définition 1. Une décomposition du schéma-DF (A,?) est un ensemble {(A1,?1), ,(A`,?`)} tel que 1.Ai ; 2. ? |=1 [A1, ,A`]; i i 3. pour i ? {1, ,`}, ? ? {X ? Y | XY ? A ,? |= X ? Y }. On dira que cette décompositionappelée un composant de la décomposition.préserve les DFs si S i. Chaque élément (Ai,?i) est La deuxième condition dans la Définition 1 est connue comme la propriété de lossless join dans la littérature. En français, nous parlerons d’une décomposition sans perte ou d’une décomposition qui préserve le contenu. La troisième condition dans la Définition 1 exprime que pour chaque i, l’ensemble ?i encode tout DF sur Ai qui est une conséquence logique de ?. Exemple 14. Continuation de l’exemple 13. Soit A = {Etudiant´ ,Dép,Fac} avec ? = {Etudiant´ ? Dép, Dép? Fac}. Sur la base de Proposition 5, on peut conclure : ? |= 1 [{Etudiant´ ,Dép},{Etudiant´ ,Fac}], ? |= 1 [{Etudiant´ ,Dép},{Dép,Fac}]. Introduisons trois schémas-DF : ED := ({Etudiant´ ,Dép},{Etudiant´ ? Dép}), EF := ({Etudiant´ ,Fac},{Etudiant´ ? Fac}), DF := ({Dép,Fac},{Dép ? Fac}). DF Dép?FacIl est à noter, par ailleurs, que {EF,DF? 6|=}1n’est pas une décomposition, parce que sur la base de[{Etudiant´ ,Fac},{Dép,Fac}]. Proposition 5, on peut conclure que 7.4 Décomposition en BCNFOn dira qu’une décomposition est en BCNF si chaque composant est en BCNF. Proposition 7.Chaque schéma-DF a une décomposition en BCNF. Démonstration.A un seul attribut, tel queSupposons que? |=(XA,??)An’est pas en BCNF. Alors il existe une DFet ? 6|= X ? A. X ? A, avec Sur base de la Proposition 3,est1{(XA,?1), mais que la DF, (XZ,?2)} avec?X?|=1?1etA[XA,XZ?ne provoque plus de violation de BCNF. Si2 comme spécifiés dans la Définition 1. Noter que] avec Z = A \ XA. Donc, une décomposition(XA,?1) ? |= X(XZ,? ?A2) ne sont pas en BCNF, on décompose de même façon chaque composant qui et/ou n’est pas encore en BCNF. Il est facile de voir que cette procédure aboutira finalement à une décomposition où tous les composants sont en BCNF. L’exemple suivant montre qu’il n’existe pas toujours une décomposition en BCNF qui préserve les DFs. ? |= 1 [{Cours,Prof},{Cours,Heure}]. Introduisons deux schémas-DF : CP := ({Cours,Prof},{Cours ? Prof}), CH := ({Cours,Heure},?). Alors {CP,CH} est une décomposition quicontient les trois attributs du schéma-DF, il n’existe pas“perd” la DF {Prof,Heure} ? Cours. Manifestement, puisque la DF {Prof,Heure} ? Cours de décomposition en BCNF qui préserve les DFs. 7.5 3NFL’exemple 15 nous montre qu’il n’existe pas toujours une décomposition en BCNF qui préserve les DFs. Suite à cette observation, on introduit maintenant la notion de 3NF comme un affaiblissement de BCNF. On commence par la définition de la notion de clé. Un sous-ensemble K de A)est appelée unetel que pour toutcléAd’un schéma-DF? A, ? |= K ? (AA. Un attribut,?) si K est un ensembleA est appelé minimal (par rapport à ? premier s’il appartient à une ou plusieurs clés. Exemple 16. Soit A = ABCDE, B, Cetet? =E.{A ? BCD,BC ? AD}. Les clés sont AE et BCE. Les attributs premiers sont A Un schéma-DF (A,?) est en 3NF si pour toute DF X ? Y ? ? telle que Y 6? X, soit ? |= X ? A, soit chaque attribut de Y \X est premier (soit les deux). La différence entre BCNF et 3NF est la phrase “soit chaque attribut de Y \ Xun schéma-DFest premier”. Intuitivement, l’effet de cette phrase peut être aperçu comme suit. Soit (A,?). Cette situation tel que pour un attribut premierreprésente une violation de BCNF, mais n’est pas une infraction contre 3NF. Le paragrapheA ? A, on a ? |= X ?A et ? 6|= X ? A suivant montre que dans cette situation, une décomposition en BCNF divisera une clé en deux, PuisqueK ? XAA. À partir deest premier, il existe une clé, une contradiction. Il est donc correct de conclure? |= X ? A etK? telle que|= XA ? AA ? (Kcar. Supposons, par contradiction, queXA contient une clé), on dériveK 6? XA, i.e., il existe un (?XA,|= ?X1)? Aet tel que2 B ?6XA. Pour enlever la violation de BCNF, une décomposition en= A \XAB. Noter que les attributs A et B de la clé attribut B ?(XBZ,K ? ) s’impose avec Z K sont séparés dans cette décomposition. On dira qu’une décomposition est en 3NF si chaque composant est en 3NF. Le résultat suivant est donné sans démonstration. Proposition 8.Chaque schéma-DF a une décomposition en 3NF qui préserve les DFs. En pratique, un schéma-DF en 3NF, mais pas en BCNF, est acceptable à la condition que le schéma-DF n’ait pas de décomposition en BCNF qui préserve les DFs. C’est le cas pour le schéma-DF de l’exemple 15. L’exemple suivant montre l’existence d’un schéma-DF en 3NF, mais pas en BCNF, qui a une décomposition en BCNF qui préserve les DFs. Dans ce cas, la décomposition en BCNF est préférable.
Exemple 17.n’est pas en BCNF, carBCD Soit A =?ABCD|= ACet?? =D mais{AC??|6=D,CDAC ??B.A(}A. Les clés de,?) est en 3NF. Ce schéma-DF(A,?) sont ABC et . Puisque chaque attribut est premier, le schéma-DF Par Proposition 3, ? |=1 [ACD,ABC], ce qui donne lieu à une décomposition dont les deux composants sont comme suit : (ACD,{AC ? D,CD ? A}) (ABC,?)Cette décomposition est en BCNF (et donc en 3NF) et préserve les DFs. Il est à noter, par ailleurs, que la clé= BCDBCD? est divisée en deux, mais quand-même préservée, parce queABCD. {AC ? D,CD ? A} | Soit (A(,A?),?)un schéma-DF tel que chaque DF dansest en BCNF si pour tout X ?A dans? ?est singulière. Alors,, on a ? |= X ? A. — — (A,?) est en 3NF si pour tout X ? A dans ?, soit ? |= X ? A, soit A est premier (soit les deux). 7.7 Décomposition en 3NFUn schéma-DF (A,?) est irréductible si les trois conditions suivantes sont respectées : 1. Chaque DF dans ? est singulière. 2. Pour chaque DF X ??Aet? ?B, aucun attribut de?X, X n’est superflu. De façon formelle, pour chaque DF X ?A ? (? \ {X ? A}) ? {(X \ B) ? A} 6? ?. 3. Aucune DF de ? n’est redondante. De façon formelle, pour chaque DF X ? A ? ?, (? \ {X ?A}) ?6 ?. Exemple 18. ?1 = {A ? C,AB ? C} n’est pas irréductible, parce que {A ? C} ? ?. ?2 = {A ? C,ABC ? D} n’est pas irréductible, parce que {A ? C,AB ? D} ? ?. Un exercice intéressant (et plutôt facile) est de développer un algorithme qui prend en entrée un schéma-DF (A,?), et qui retourne en sortie un schéma-DF (A,?0) irréductible tel que ?0 ? ?. Noter que la sortie d’un tel algorithme n’est pas déterministe, comme illustré dans l’exemple suivant. Exemple 19. Soit A = ABC et ? = {A ? B, B ? AC,A ? C}. Soient ?1 = {A ? B,B ? A,A ? C}, ?2 = {A ? B,B ? A,B ? C}. Alors, ? ? ?1? ?2. Les schémas-DF (ABC,?1) et (ABC,?2) sont tous les deux irréductibles. Proposition 8 est une conséquence logique de la proposition suivante. {(K,?0),(X1A1,?1), ,(X`A`,?`)}, avec ?0,?1, ,?` comme spécifiés dans la Définition 1. Il est trivial de voir que la décomposition de la Proposition 9 préserve les DFs. Il est plus difficile de démontrer que ? |=1 [K,X1, ,X`] et que chaque composant est en 3NF. Exemple 20. Cet exemple montre l’importance du composant (K,?0) dans l’énoncé de la Proposition 9. Soit A = {Etudiant´ , Dép, Langue}. Un tuple {(Etudiant´ ,“Ed”), (Dép,“Info”), (en espagnol. L’ensemble des DF est le singleton{pas premier est un étudiant peut maîtriser plusieurs langues, i.e.,LangueEtudiant´ ,“,espagnolLangue}”)est la seule clé. Le schéma-DF} signifie que Ed est un étudiant au département d’Info qui sait s’exprimer(A? =,?) n’est pas en 3NF, parce que{Etudiant´??Dép|6= Etudiant}´. En conséquence,?DépLanguen’est. L’application de la Proposition 9 nous donne la décomposition suivante en 3NF : {({Etudiant´ ,Langue},?),({Etudiant´ ,Dép},{Etudiant´ ? Dép})}. Noter que ? |=1 [{Etudiant´ ,Langue},{Etudiant´ ,Dép}] est aussi une conséquence de la Proposition 3. Le composant ({Etudiant´ ,Langue},?) enregistre une association multiple-sur-multiple entre étudiants et langues : un étudiant peut maîtriser plusieurs langues, et la même langue peut être maîtrisée par plusieurs étudiants. Le composantune association un-sur-multiple (ou multiple-sur-un({Etudiant´ ) entre départements et étudiants : un,Dép}, {Etudiant´ ? Dép}) enregistre département peut héberger plusieurs étudiants, mais chaque étudiant n’est associé qu’à un seul département. 7.8 1NF, 2NF, 4NF, 5NF7.8.1 1NF et 2NFEn ce qui concerne 1NF et 2NF, essayer de comprendre la note de bas de page [12, page 402] : Les formes normales 4NF et 5NF concernent la situation où un schéma contient non seulement des DFs, mais aussi des DMVs et DJs. 7.8.2 4NFUncontient des DFs et DMVs surschéma-DF-DMV est un coupleA. (A,?) avec A un ensemble d’attributs et ? un ensemble qui Un schéma-DF-DMVtout X,Y ? A : (A,?) est en 4NF si les deux conditions suivantes sont satisfaites pour 1. si ? |= X ? Y avec Y 6? X, alors ? |= X ? A; et 2. si ? |= XY avec Y 6? X, alors ? |= X ? A. La première condition est égale à celle de BCNF. En s’appuyant sur la Proposition 3, on peut affirmer : Un schéma-DF-DMV (A,?) est en 4NF si et seulement s’il existe un schéma-DF (A,?) en BCNF tel que ? ? ?. Exemple 21. Soit A = {Etudiant´ ,Langage,Plat}. Un tuple {(Etudiant´ ,“Ed”), (Langage,“Java”), (Plat,“spaghetti”)} signifie qu’Ed est un étudiant qui sait programmer en Java et qui sait préparer un spaghetti. Soit ? = {1 [{Etudiant´ .,Langage},{Etudiant´ ,Plat}]}. Noter que ? ? {Etudiant´ Langage} et ? ? {Etudiant´Plat} La table suivante satisfait ?, mais ne satisfait aucune DF singulière. En conséquence, aucun ensemble de DFs ne peut être équivalent à ?, et donc le schéma-DF-DMV (A,?) n’est pas en 4NF.
Il est assez évident que cette relation doit être décomposée en deux relations avec comme schémas-de-relationjamais stocker, dans une même relation, deux renseignements n’ayant rien à voir l’un avec l’autre.{Etudiant´ ,Langage} et {Etudiant´ ,Plat}. Intuitivement, 4NF nous dit de ne Un schéma-DF-DJ (A,?) est en 5NF s’il existe un schéma-DF (A,?) en BCNF tel que ? ? ?. Exemple 22. Soient A = ABCD et ? = {A=?1 [AB,AC,ADBCD,1 [AB,AC,AD]. Donc, ? ]? {}. Il est facile deA ? BCD}. Il démontrer (cf. Proposition 3) que {A ? BCD} | est correct de conclure que le schéma-DF-DJ (A,?) est en 5NF. Exemple 23. Exemple issu de [9]. Soit A = {Agent,Company,Product}. Un tuple {(Agent,“Smith”), (Company,“Ford”), (Product,“car”)} signifie que Smith est un agent qui vend des voitures pour la marque Ford. Soit ? = {1 [{Agent,Companyvend un produit quelconque pour une compagnie},{Agent,Product},{Company,Product}]}, ce qui veut dire, enc, et si cet agent a français, que si un agent a vend un produit p pour une compagnie quelconque, alors l’agent a vend le produit p pour la compagnie c, pourvu que la compagnie c fabrique le produit p. La table suivante satisfait ?, mais ne satisfait aucune DF singulière. En conséquence, aucun ensemble de DFs ne peut être équivalent à ?, et donc le schéma-DF-DJ (A,?) n’est pas en 5NF.
R Il est assez évident que cette relation doit être décomposée en trois relations avec comme schémas-de-relation {Agent,Company}, {Agent,Product} et {Company,Product} : la DJ de ? exprime que cette décomposition est sans perte!
R1R2R3 Observer : — Jones vend des voitures et GM fabrique des voitures, mais Jones ne travaille pas pour GM. Donc, R 6|=1 [{Product,Agent},{Product,Company}]. — Brown travaille pour Ford et Ford fabrique des camions, mais Brown ne vend pas de camions. Donc, R 6|=1 [{Company,Agent},{Company,Product}]. — Brown travaille pour Ford et Brown vend des autobus, mais Ford ne fabrique pas d’autobus. Donc, R 6|=1 [{Agent,Company},{Agent,Product}]. Intuitivement, on peut décomposer R sans perte en trois composants, mais chaque décomposition en deux composants engendre une perte. Il est correct de conclure que la DJ 1 [{Agent,Company},{Agent,Product},{Company,Product}], avec trois composants, ne peut pas être exprimée comme une ou plusieurs DMVs. Chapitre 8 Le Modèle Entité-AssociationLe modèle Entity-Relationship (modèle ER, en français : modèle entité-association) a été introduit par P.P. Chen en 1976 [4]. 8.1 Énoncé— L’entreprise est organisée en plusieurs départements. Chaque département possède un nom unique et est dirigé par un seul employé. Il faut mémoriser la date à laquelle l’employé a commencé la direction du département. Un département peut être localisé à plusieurs endroits. — Un département contrôle un certain nombre de projets. Chaque projet a un nom unique et est localisé à un seul endroit. — On doit connaître les personnes à charge de chaque employé. Pour chaque personne à charge, on stocke le nom, le sexe, la date de naissance et les liens de famille. 8.2 Le diagramme entité-association8.3 Traduction vers le modèle relationnelEMPLOYE(SS#, Sexe, Sal, PréNom, NomFam, TravailleDans, SuperviséPar) PK(SS#) FK(SuperviséPar) REFS EMPLOYE FK(TravailleDans) REFS DEPARTEMENT DEPARTEMENT(DNom, DirigéPar, Depuis) PK(DNom) FK(DirigéPar) REFS EMPLOYE LOCALISATION(DNom, Loc) PK(DNom, Loc) FK(DNom) REFS DEPARTEMENT PROJET(PNom, Localisation, ControléPar) PK(PNom) FK(ControléPar) REFS DEPARTEMENT TRAVAILLE_A(SS#, PNom, Heures) PK(SS#, PNom) FK(SS#) REFS EMPLOYE FK(PNom) REFS PROJET A_CHARGE(Nom, SS#, Sexe, DateNaissance, LiensFamille) FK(SS#) REFS EMPLOYE Deuxième partie Gestion des TransactionsChapitre 9 Two-Phase Locking (2PL)[ ] two-phase locking (I know Jim Gray won [the Turing award] for many contributions, but this one is, I think, the centerpiece) J.D. Ullman [14] 9.1 Cadre théoriqueUne base de données est une ressource partagée parmi plusieurs transactions, où une transaction est définie comme l’exécution d’un programme informatique qui effectue une “unité logique de travail”. Une transaction peut être l’ouverture d’un compte bancaire, un virement, créditer ou débiter un compte L’objectif de la gestion des transactions est d’assurer que ce partage n’engendre pas de conflits. La gestion de transactions sera étudiée dans le cadre théorique suivant. 1. On suppose que la base de données consiste en un nombre d’objets A,B,C, En pratique, un objet peut prendre différentes formes, telle qu’une valeur dans une table, une rangée dans une table, voire une table entière 3. Une transaction est caractérisée par une suite d’actions R et W. Les actions autres que R et W sont des actions de “cuisine interne” et ne seront pas montrées. On fera correspondre, à chaque transaction, un indice unique. On écrira Ri(A) et Wi(A) pour respectivement une lecture et une écriture de l’objet A par la transaction [avec indice] i. Un exemple d’une transaction est R7(A)R7(B)W7(A)W7(B). 4. Une exécution (ou un ordonnancement, en anglais : schedule) est un ensemble de transactions exécutées “en parallèle”, ou de façon plus précise, “en entrelacement”. Par exemple, les transactions T1 = R1(A)R1(B)W1(A)W1(B) et T2 = R2(A)R2(B)W2(C) peuvent être entrelacées comme suit : R1(A)R1(B)R2(A)W1(A)W1(B)R2(B)W2(C). (9.1) Un entrelacement respecte l’ordre des actions à l’intérieur de chaque transaction : si l’on ne retient que les actions avec indice 1, on obtient la transaction T1 ; si l’on ne retient que les actions avec indice 2, on obtient la transaction T2. Il est important de ne pas confondre un programme informatique avec les transactions qui résultent de son exécution. Les actions R et W ne sont pas des instructions à la disposition du programmeur. Un programme informatique accède typiquement à une base de données à l’aide des instructions SQL (SELECT, UPDATE ), imbriquées dans des boucles et des conditions if-then-else. Une transaction n’est qu’une trace, au niveau interne du SGBD, des évènements (lectures et écritures) effectués lors d’une exécution d’un tel programme. 9.2 Les exécutions sériellesOn va argumenter que l’exécution (9.1) risque d’introduire des erreurs dans la base de données. Hypothétiquement, supposons que les lectures et écritures des transactions T1 et T2 ont pour but d’effectuer les copiés-collés suivants. T2 = R2(A)R2(B)W2(C) :T2 modifie la valeur de C ; la nouvelle valeur de C est la concaténation des anciennes valeurs de A et B. Pour pouvoir identifier des erreurs, il faut se mettre d’accord sur ce qui est correct. Il est logique d’accepter qu’une exécution est correcte si aucune transaction ne soit “interrompue” par une autre. Une telle exécution est appelée sérielle (ou succession). Par exemple, pour les transactions T1 et T2 de notre exemple, il existe deux exécutions sérielles : T1T2 = R1(A)R1(B)W1(A)W1(B)R2(A)R2(B)W2(C), T2T1 = R2(A)R2(B)W2(C)R1(A)R1(B)W1(A)W1(B). En général, le nombre d’exécutions sérielles de n transactions est de n! (i.e., factorielle de n). Pour notre exemple, si A = a,B = b avant l’exécution de T1 et T2, alors C = abab après l’exécution sérielle T1T2, et C = ab après l’exécution sérielle T2T1. Noter que l’exécution (9.1) résulte en une base de données où C = aab : la lecture R2(A) lit A = a, la lecture R2(B) lit B = ab, ce qui est la valeur écrite par W1(B). L’état de C = aab est considéré comme erroné, car il ne peut pas être produit par une exécution sérielle. 9.3 Les exécutions sérialisablesOn définit une relation binaire ? sur l’ensemble des exécutions. Intuitivement, ?1 ? ?2 exprime que les exécutions ?1 et ?2 ont les mêmes effets sur toute base de données. Premièrement, deux lectures juxtaposées peuvent être permutées : si i =6 j, alors ?Ri(X)Rj(Y )? ? ?Rj(Y )Ri(X)?. Deuxièmement, une lecture et une écriture juxtaposées peuvent être permutées si elles portent sur des objets différents : si i =6 j et X =6 Y , alors ?Ri(X)Wj(Y )? ? ?Wj(Y )Ri(X)?. Troisièmement, la relation ? est réflexive, symétrique et transitive, c’est-à-dire, pour toutes exécutions ?,?1,?2,?3, et ? ? ? Une exécution estsi?si ???11???; ??22, alorssérialisable2 ?2 ?3, alors?1s’il existe une exécution sérielle; ?1 ? ?3. ?0 telle que ? ? ?0. Le graphe de précédence d’une exécution ? est un graphe orienté G dont les sommets sont les transactions del’exécution est de la forme?. Le graphe de précédence contient une arête orientée de?Ei?Ej? avec EiEj 6? EjEi, où Ei et Ej dénotent des actions (ReadTi à Tj (i =6 j) si ou Write). La preuve de la proposition suivante est un simple exercice. Proposition 10.Une exécution est sérialisable si et seulement si son graphe de précédence est acyclique. Par ailleurs, si le graphe de précédence G d’une exécution ? est acyclique, alors pour tout tri topologique ?0 = Ti1Ti2Ti` de G, on a ? ? ?0. 9.4 L’écriture aveugleUne écriture Wi(A) dans une transaction est aveugle (en anglais : blind write) si elle n’est pas précédée par une lecture Ri(A). Par exemple, l’écriture W2(C) est aveugle dans la transaction T2 = R2(A)R2(B)W2(C) : puisque T2 ne lit pas C, la nouvelle valeur de C est forcément indépendante de l’ancienne valeur de C. Une exécution non sérialisable avec des écritures aveugles peut avoir les mêmes effets qu’une exécution sérielle. Par exemple, l’exécution suivante n’est pas sérialisable : R3(A)W4(A)W3(A)W5(A). (9.2) Cependant, dans la suite, l’exécution (9.2) sera interdite parce qu’elle n’est pas sérialisable. 9.5 Spécification du protocole 2PL2PL est un protocole qui garantit la sérialisabilité des exécutions. 9.5.1 Le comportement d’une transactionLe protocole 2PL fait correspondre, à chaque objet A, plusieurs verrous partagés (en anglais : shared lock ou S-lock sur A) et un seul verrou exclusif (en anglais : exclusive lock ou X-lock sur A). Intuitivement, un S-lock sur un objet A est la permission de lire A; le X-lock sur A est la permission d’écrire A. Le protocole 2PL stipule que chaque transaction Ti doit demander (et obtenir) le X-lock sur A pour pouvoir écrire A; cette demande sera dénotée par Xi(A). Puis, chaque transaction Ti doit demander (et obtenir) un S-lock sur A pour pouvoir lire A; cette demande sera dénotée par Si(A). Par ailleurs, une transaction qui possède le X-lock sur A peut aussi lire A. Dans une transaction Ti, la demande Si(A) peut être suivie de Xi(A). Dans ce cas, la demande Xi(A) est appelée un lock upgrade. Les transactions doivent relâcher (en anglais : unlock) leurs verrous avant de se terminer. On dénote par Ui(A) que la transaction Ti relâche son verrou sur A. Après Si(A), le relâchement Ui(A) porte sur un S-lock; après Xi(A), le relâchement Ui(A) porte sur le X-lock sur A. La terminaison avec succès d’une transaction Ti est appelée Commit et sera dénotée par l’action Ci. On dira qu’une transaction Ti possède un S-lock sur un objet A à partir de (l’acceptation de) la demande Si(A) jusqu’au relâchement Ui(A). On dira qu’une transaction Ti possède le X-lock sur A à partir de Xi(A) jusqu’au Ui(A). En plus de ce qui précède, le protocole 2PL stipule que chaque transaction Ti doit s’exécuter “en deux phases” : La première occurrence de Ui dans une transaction Ti est appelé le lock point de cette transaction. Le lock point divise la transaction en deux phases : avant le lock point, aucune action Ui n’est possible (par la définition de lock point); après le lock point, aucune action Si ou Xi n’est possible (à cause de la règle ci-dessus). Par exemple, la transaction suivante respecte le protocole 2PL S1(A)S1(B)R1(A)R1(B)X1(B)U1(A)W1(B)U1(B)C1, parce que : — la lecture R1(A) s’effectue entre S1(A) et U1(A); — la lecture R1(B) s’effectue entre S1(B) et U1(B); — l’écriture W1(B) s’effectue entre X1(B) et U1(B); — aucune demande S1 ou X1 n’a lieu après le lock point U1(A); et — les verrous sur A et B sont relâchés avant le commit C1. 9.5.2 L’exécution globaleLa règle suivante contrôle les exécutions : 2PL-exécution : Au moment où une transaction possède le X-lock sur un objet A, aucune autre transaction ne peut posséder le X-lock ou un S-lock sur ce même objet A. Une exécution est conforme au protocole 2PL s’il est possible d’ajouter des demandes et relâchements de verrous en respectant les règles 2PL-transaction et 2PL-exécution. Exemple 24. Démontrons que l’exécution W2(A)R1(A)R3(B)W2(B)R1(B) n’est pas conforme au protocole 2PL. Entre W2(A) et R1(A), on doit avoir un relâchement U2(A) suivi d’une demande S1(A). Le relâchement U2(A) doit être précédée par la demande X2(B), à cause de la règle 2PL-transaction. Mais alors T2 possède le X-lock sur B au moment où T3 a besoin d’un S-lock sur B (pour pouvoir effectuer R3(B)), ce qui est une infraction contre la règle 2PL-exécution. Lemme 1.Soit? une exécution qui est conforme au protocole 2PL. Si le graphe de précédence de ? contient une arête orientée de Ti à Tj (i =6 j), alors le lock point de Ti précède le lock point deTj. ?Ri(A)?Wj(A)? ?Wi(A)?Rj(A)? ?Wi(A)?Wj(A)? Dans les trois cas, un relâchement Ui(A) doit être ajouté aux actions de ?, et ce relâchement doit être suivi par une demande de verrou par Tj. Le lock point de Ti précède ou est égal à Ui(A). A cause de la règle 2PL-transaction, le lock point de Tj se situe après la demande de verrou par Tj. Le lock point de Ti précède donc le lock point de Tj. Proposition 11.Si une exécution? est conforme au protocole 2PL, alors? est sérialisable. Démonstration. Preuve par contraposition. Soit ? une exécution qui n’est pas sérialisable. Sur base de la Proposition 10, le graphe de précédence de ?contient un cyclehTi1,Ti2,Ti3, ,Ti`,Ti1i. On démontrera que ? n’est pas conforme au protocole 2PL. Nous procédons par contradiction : supposons que ? est conforme au protocole 2PL. Sur base du Lemme 1, il est correct de conclure que le lock point de Ti1 précède le lock point de Ti2, que le lock point de Ti2 précède le lock point de Ti3 En conséquence, le lock point de Ti1 précède le lock point de Ti1, une contradiction. L’exécution de l’exemple 24 est sérialisable mais n’est pas conforme au protocole 2PL. L’inverse de la Proposition 11 n’est donc pas vraie. 9.6 Implémentation du protocole 2PLÀ quoi sert la restriction des exécutions sérialisables aux exécutions qui sont conformes au protocole 2PL? La réponse est que le protocole 2PL se prête à une implémentation pratique. Chaque programme doit être encodé de façon à ce que son exécution, en tant que transaction, respecte la règle 2PL-transaction. Le respect de la règle 2PL-exécution est assuré par le gestionnaire de verrous, qui fait partie du SGBD. Ce gestionnaire mémorise, dans une table, quelles transactions possèdent quels verrous sur quels objets. En plus, le gestionnaire doit tenir compte des problèmes de la famine (starvation) et du verrou mortel (interblocage ou deadlock). La table de verrouillage contient, pour chaque objet Y , un couple : verrous_acquis, file_d’attente, où — verrous_acquis enregistre les verrous sur l’objet Y en possession des transactions. Cet ensemble contient soit zéro ou plusieurs S-locks, soit un seul X-lock. — file_d’attente est une file qui enregistre les verrous sur Y qui ont été demandés mais qui n’ont pas pu être accordés. Par exemple, une entrée1 2 (A,{S1,S2},h; la transactionX1,X3i) enregistre la situation suivante : les transactionsT1 a été suspendue suite à la demande T et T possèdent un S-lock sur A d’un lock-upgrade X1(A); T3 a été suspendue suite à la demande X3(A). Si la transaction T2 effectue ensuite U2(A), le lock-upgrade peut être accordé à T1 et la nouvelle situation devient (A,{X1},hX3i). En général, les demandes Si et Xi sont traitées comme suit. — Une demande Si(A) est acceptée si à la fois (i) l’ensemble verrous_acquis pour A dans la table de verrouillage contient zéro, un ou plusieurs S-locks, et (ii) la file d’attente file_d’attente est vide. Dans le cas contraire, la demande est mise dans la file d’attente (et la transaction Ti est suspendue). Si l’ensemble verrous_acquis ne contient que des S-locks mais la file d’attente n’est pas vide, la demande Si(A) est quand-même refusée afin d’éviter le problème de la famine. Exemple 25. Supposons que les demandes de verrous arrivent dans l’ordre suivant : S1(A)S2(A)X3(A)X1(A)S4(A)U2(A). La table suivante montre comment l’entrée pour A évolue dans la table de verrouillage. Après l’exécution de : S1(A) S1(A)S2(A) S1(A)S2(A)X3(A) S1(A)S2(A)X3(A)X1(A) S1(A)S2(A)X3(A)X1(A)S4(A)
S1(A)S2(A)X3(A)X1(A)S4(A)U2(A) { } h i Noter qu’une transaction suspendue peut posséder des verrous; c’est le cas pour T1 juste après S1(A)S2(A)X3(A)X1(A). L’implémentation du protocole 2PL discutée ci-dessus traite les demandes S, X et U sans s’occuper des lectures et écritures. En fait, une transaction qui possède un X-lock sur un objet peut lire et écrire l’objet de façon “illimitée”; une transaction qui possède un S-lock sur un objet peut lire l’objet une, deux ou plusieurs fois. La Proposition 11 donne la garantie que les exécutions qui en résultent sont sérialisables. Noter qu’une transaction ne peut apparaître qu’une seule fois dans la colonne file_d’attente de la table de verrouillage : une transaction suspendue ne fait “plus rien” et ne fera donc plus de demandes S ou X, ni de relâchement U. Ce relâchement n’aura jamais lieu, car la transaction T2 est suspendue elle-même.
{ } h i La table suivante montre un verrou mortel entre trois transactions.
h i Dans la table suivante, T2 attendra vainement le relâchement U1(A) par T1. Comme expliqué dans la section 9.6, ce verrou mortel aurait pu être évité si le lock upgrade X1(A) avait été accordé.
{ } h i Le graphe d’attente (en anglais : wait-for graph) est un graphe orienté dont les sommets sont les transactions. Le graphe contient une arête orientée de Ti à Tj si Ti attend le relâchement d’un verrou par Tj ou si Ti se trouve derrière Tj dans une file d’attente. Le graphe d’attente peut être construit sur base de la table de verrouillage. Un verrou mortel correspond à un cycle orienté dans le graphe d’attente. Pour mettre fin au verrou mortel, le SGBD doit annuler une ou plusieurs transactions qui font partie du cycle. Une solution alternative consiste à prévenir que les verrous mortels ne se produisent. Supposons que l’indice d’une transaction correspond à l’instant auquel la transaction a commencé. Disons qu’une transaction Ti est plus ancienne que toute transaction Ti+1, Ti+2, Si Ti est plus ancienne que Tj, alors Tj est plus jeune que Ti. Deux protocoles sont possibles : Dans ces deux protocoles, c’est toujours la transaction la plus jeune qui est annulée. Une transaction annulée est reprise avec le même indice. Elle devient ainsi plus vieille et finit toujours par passer. De cette façon, le problème de la famine est évité. Les protocoles Wait-Die et Wound-Wait risquent d’engendrer des annulations excessives. Par exemple, supposons que la table de verrouillage est comme suit.
{ } hi Dans un système Wait-Die, la transaction T3 sera annulée quand elle demande X3(A). Dans un système Wound-Wait, la transaction T2 sera annulée quand la transaction T1 demande X1(A). 9.8 Strict 2PLSi un verrou mortel se présente, une ou plusieurs transactions doivent être annulées (en anglais : transaction abort). L’annulation de transactions peut aussi être causée par d’autres problèmes : erreur de programmation (par exemple, division par zéro), coupure de courant Il est évident que les modifications effectuées par une transaction annulées doivent être “défaites”. Il s’agit du principe d’atomicité : soit toutes les modifications d’une transaction sont effectuées, soit aucune ne l’est. Considérer, par exemple, la transaction T1 = R1(A)R1(B)W1(A)W1(B) de la section 9.2 qui modifie A = a,B = b en A = B = ab. Supposons que cette transaction est annulée après W1(A), mais avant W1(B). À ce stade, W1(A) a déjà écrit A = ab, mais la valeur de B est toujours B = b. Évidemment, l’état A = ab,B = b est incohérent. Dans le processus d’annulation, le SGBD restaurera l’état cohérent A = a,B = b qui existait avant le début de T1. Le chapitre 10 expliquera comment cette restauration est réalisée concrètement. Atomicité et durabilité sont des principes “de bons sens”. Imaginons que vous faites un virement dans votre système de home banking. Il serait inacceptable que le système vous donne le message “Virement effectué avec succès!” et puis défasse le virement “derrière votre dos” (infraction contre durabilité). Par contre, si le système se plante au milieu du processus de virement, vous vous attendez à ce que que votre compte ne soit pas débité (principe d’atomicité). Malheureusement, il y a des situations où, dans un système 2PL, les principes d’atomicité et durabilité ne peuvent pas être assurés ensemble. Considérons l’exécution suivante qui est conforme au protocole 2PL. La transaction T1 est celle décrite ci-dessus. La transaction T3 change la valeur de A; la nouvelle valeur dépend de l’ancienne valeur lue par R3(A). X1(A)X1(B)R1(A)R1(B)W1(A)U1(A)X3(A)R3(A)W3(A)U3(A)C3 W1(B)U1(B)C1 Supposons, de nouveau, que la transaction T1 est annulée après U1(A) mais avant W1(B), à l’endroit du symbole . Lors de l’annulation, le SGBD va restaurer la valeur de A qui existait avant le début de T1 ( principe d’atomicité). Cependant, cette restauration défera la modification de T3, ce qui est une infraction contre le principe de durabilité, car T3 a déjà effectué son Commit. Le problème dans cette exécution est que la lecture R3(A) lit une valeur qui n’est pas “définitive”; une telle lecture est appelée “sale”. Un problème analogue est que 2PL nécessite des annulations en cascade. Considérez : X1(A)X1(B)R1(A)R1(B)W1(A)U1(A)S4(A)R4(A)X4(B)W4(B) W1(B)U1(B)C1 La valeur écrite par W4(B) risque de dépendre de la valeur de A lue par R4(A), qui est la valeur écrite par W1(A). Si les modifications de T1 sont défaites par la suite, les modifications de T4 doivent être défaites également. On parle d’une annulation en cascade (en anglais : cascading abort). Le protocole Strict 2PL exclut les lecture sales en remplaçant la règle 2PL-transaction par une règle plus sévère : Strict2PL-transaction En plus de 2PL-transaction, les transactions gardent tous leurs verrous jusqu’au Commit. En fait, le relâchement des verrous peut être considéré comme une partie du Commit. Dans Strict 2PL, une transaction Ti peut être annulée “en isolation” (i.e., sans tenir compte des autres transactions) parce qu’aucune autre transaction Tj (i =6 j) ne peut dépendre des modifications de Ti. Il est facile de voir que le protocole Strict 2PL n’exclut pas les verrous mortels. Chapitre 10 Résistance aux Pannes et RepriseIl existe trois principaux types de pannes. — La panne de transaction (transaction failure). Par exemple, une transaction qui est annulée pour résoudre un verrou mortel. — La panne du système (system failure). La mémoire centrale est perdue. Par exemple, une coupure de courant. — La panne de mémoire secondaire (media failure). Ce chapitre explique les techniques mises en œuvre pour pallier la panne du système. Ces techniques permettent aussi de résoudre les pannes de transaction. 10.1 Le bufferCette section est reprise du cours de bases de données par Philippe Rigaux, disponible à l’URL “La partie de la mémoire principale affectée à un SGBD est appelée mémoires tampon, ou buffer. Un buffer est constitué de blocs en mémoire principale, copies des blocs sur le disque. Quand un accès est demandé (limitons-nous aux lectures pour l’instant), deux cas sont possibles : — la donnée est déjà dans un buffer, et peut donc être servie directement au processeur; — sinon il faut d’abord lire un bloc du disque, et le placer en mémoire, pour se ramener au cas précédent. [ ] Quand la mémoire cache est pleine et qu’un nouveau bloc doit être lu sur le disque, un algorithme de remplacement doit être adopté pour retirer un des blocs de la mémoire et le replacer sur le disque (opérations dite de flush). [ ] Ce bloc est alors soustrait de la mémoire centrale (il reste bien entendu sur le disque) et le nouveau bloc vient le remplacer.” Figure 10.1 – Le buffer. panne du système
Figure 10.2 – Transaction T1 est à refaire, T2 à défaire. Les blocs sont aussi appelés pages. Voir figure 10.1. Le page manager a la responsabilité de (i) charger en mémoire centrale les pages demandées par des transactions, et (ii) réécrire sur disque les pages modifiées par ces mêmes transactions (dirty pages). 10.2 Undo/RedoSupposons un protocole qui interdit à une transaction T1 de lire un objet modifié par T2 avant le commit de T2 (i.e., pas de dirty reads). C’est-à-dire, un protocole comme strict 2PL qui ne nécessite pas de cascading aborts. Voir figure 10.2. Il faut être capable de : — “Refaire” (Redo) les modifications effectuées par T1 (principe de la durabilité). Il peut y avoir des pages (1) modifiées en mémoire volatile par T1, mais (2) pas encore stockées dans la base au moment de la panne. — “Défaire” (Undo) les modifications effectuées par T2 (principe de l’atomicité). Il peut y avoir des pages (1) modifiées en mémoire volatile par T2, et (2) déjà stockées dans la base (donc sur disque) au moment de la panne. 10.3 Le journalLa méthode la plus classique pour permettre la validation atomique, l’annulation et la reprise de transactions consiste à utiliser un journal (ou log). Le journal est un fichier append-only gardé sur disque. On enregistre dans le journal l’occurrence des actions suivantes : — (T, begin), où T dénote l’identifiant d’une transaction. La transaction T a commencé. — (T, commit). La transaction T a terminé. Comme pour tout fichier, ces enregistrements sont d’abord produits en mémoire volatile, puis sauvegardés dans le journal sur disque. Les enregistrements sont ajoutés au journal dans l’ordre qu’ils sont produits. On dit qu’une transaction T est commise si (T, commit) se trouve dans le journal sur disque. Ci-après, la terminologie suivante est adoptée : Sauvegarder : copier sur disque une donnée qui se trouve en mémoire volatile Stocker, stockage : sauvegarder dans la base de données sur disque une page modifiée en mémoire volatile Journaliser : sauvegarder dans le journal sur disque En tout cas, il faut obéir aux règles suivantes : Journalisation avant Stockage : Avant de stocker une page modifiée en mémoire volatile par une transaction non-commise, l’image-avant de cette page doit être journalisée (afin de pouvoir défaire). Sauvegarde avant Commit : Toute page modifiée en mémoire volatile par une transaction doit être sauvegardée (stockée ou journalisée) avant le commit de la transaction (afin de pouvoir refaire). 10.4 Procédure de RepriseLa procédure de reprise se déroule en trois phases : Analyse Déterminer quelles transactions sont à défaire/refaire (parcourir le journal en avant). Défaire Parcourir le journal en arrière et stocker dans la base les images-avant des modifications qui sont à défaire. Refaire Parcourir le journal en avant et stocker dans la base les images-après des modifications qui sont à refaire. 10.5 ExempleT1 dépose 1$ sur le compte A. T2 essaie de transférer 1$ du compte B au compte A. Figure 10.3 – Transactions T1 et T4 sont à refaire, T2 et T5 à défaire.
Enregistrements ? panne d’électricité / Au moment de la panne, l’état de la base est indéfini; il y a quatre possibilités : — A = 3,B = 7 : aucune modification n’a été stockée; — A = 3,B = 6; — A = 4,B = 7; — A = 4,B = 6 : toutes les modifications ont été stockées. La procédure de reprise va restaurer l’état A = 4,B = 7. 10.6 CheckpointingComment peut-on réduire le nombre de transactions à refaire lors d’une reprise? La réalisation d’un checkpoint consiste à : 1. journaliser un enregistrement (START CKPT hT1, ,Tki), où T1, ,Tk sont les transactions actives; 2. stocker toutes les pages modifiées dans la base de données sur disque; 3. journaliser un enregistrement (END CKPT). Voir figure 10.3 : la transaction T3 n’intervient pas lors de la reprise après la panne. Une fois que le (END CKPT) apparaît dans le journal, on peut donc supprimer du journal tous les enregistrements concernant les transactions commises avant le START CKPT. 10.7 Undo/No-Redo et Redo/No-UndoIl est généralement nécessaire de défaire les transaction non-commises et refaire les transactions commises. Cependant, différents protocoles peuvent faciliter la reprise : Undo/No-Redo Toujours stocker dans la base de données toutes les pages modifiées par une transaction T avant le commit de T. Cette règle est plus sévère que le principe du Sauvegarde avant Commit introduit ci-dessus. Redo/No-Undo Ne jamais stocker dans la base de données les pages modifiées par une transaction T avant le commit de T. Le principe de la Journalisation avant Stockage est manifestement satisfait. Aucune image-avant ne doit être journalisée. Par contre, les images-après doivent être journalisées (pour pouvoir refaire, principe de la Sauvegarde avant Commit). Il y a un problème si le buffer n’est pas assez large pour stocker toutes les pages modifiées. Troisième partie Exercices Exercices sur le Chapitre 2Question 1. On pourrait choisir de remplacer les deux relations VINS et ABUS par une seule relation avec le schéma-de-relation {Nom,Cru,Millésime,Qualité}. Discutez ce choix. Question 2. Voici deux tables. Ajoutez les clés primaires et étrangères. Motivez votre choix.
Cities
Countries Réponse. Supposons que toutes les villes d’un même pays s’appellent différemment. Cities ( PRIMARY KEY(Name, Country), FOREIGN KEY(Country) REFERENCES Countries ); Countries ( PRIMARY KEY(Name), FOREIGN KEY(Capital, Name) REFERENCES Cities, UNIQUE(Capital) ); — Pourquoi est-il erroné d’écrire FOREIGN KEY(Name, Capital) au lieu de FOREIGN KEY(Capital, Name)?
— UNIQUE(Capital) indique que la table Countries ne peut pas contenir deux tuples différents avec la même valeur pour Capital. 2 Question 3. Voici trois tables d’une agence spécialisée dans les voyages en autobus. Déterminez les identifiants possibles et choisissez, parmi ceux-ci, les clés primaires. Ajoutez les clés étrangères. Motivez votre choix.
TRIPS Date Number_Plate Driver Destination Departure_Time
BUSES Number_Plate Chassis Make Mileage DESTINATIONS Name Antwerp Zoo Ostende Beach Dinant Citadel Brussels Atomium Réponse. Supposons qu’il s’agit d’excursions d’une journée. C’est-à-dire, un bus ou un chauffeur ne fait qu’une excursion par jour. TRIPS ( PRIMARY KEY(Date, Number_Plate), UNIQUE(Date, Driver), FOREIGN KEY(Number_Plate) REFERENCES BUSES, FOREIGN KEY(Destination) REFERENCES DESTINATIONS ); BUSES ( PRIMARY KEY(Number_Plate), UNIQUE(Chassis) ); DESTINATIONS ( PRIMARY KEY(Name) ); 2 Question 4. Voici deux tables d’une entreprise qui gère plusieurs dépôts. La première rangée de la table STOCK signifie que 200 charnières jaunes sont stockées au dépôt D1. Ce dépôt se trouve 6, Rue de l’Eglise à Mons. Les quantités sont des entiers positifs (? 1). Déterminez les identifiants possibles et choisissez, parmi ceux-ci, les clés primaires. Ajoutez les clés étrangères. Motivez votre choix.
WAREHOUSES W# Address City
STOCK W# Product Color Qty Réponse. WAREHOUSES ( PRIMARY KEY(W#), UNIQUE(Address,City) ); STOCK ( PRIMARY KEY(W#,Product,Color), FOREIGN KEY(W#) REFERENCES WAREHOUSES ); 2 Question 5. Le championnat de la Formule 1 se déroule chaque année du mois de mars au mois d’octobre. Dans cette période se déroulent 16 courses, appelées Grands Prix (GP), sur 16 circuits différents. Tout pilote est membre d’une équipe, appelée “écurie”, pendant toute une année. La table AFFILIATION enregistre l’affiliation des pilotes aux écuries par saison. La table PARTICIPATIONS enregistre quels pilotes ont participé à quels Grands Prix. La participation à un Grand Prix est réservée aux pilotes affiliés à une écurie. Néanmoins, il se peut qu’un pilote ne participe pas à tous les Grands Prix. Par exemple, en 2001, M. Häkkinen, membre de l’écurie McLaren, n’a pas participé au Grand Prix de Belgique. Finalement, la table PODIUM enregistre les trois meilleurs pilotes de chaque Grand Prix; bien sûr, seuls les participants peuvent gagner.
PODIUM PARTICIPATIONS
AFFILIATION Déterminez les identifiants possibles et choisissez, parmi ceux-ci, les clés primaires. Ajoutez les clés étrangères. Notez que la base de donnée montrée ci-dessous est cohérente. Question 6. Considérez les tables suivantes : EMPLOYÉ
DÉPARTEMENT Déterminez les identifiants possibles et choisissez, parmi ceux-ci, les clés primaires. Ajoutez les clés étrangères. Question 7. Considérez deux relations : EMPLOYÉS
DÉPARTEMENTS Ces tuples expriment, entre autres, que Ed travaille pour le département Jeux depuis le 8 janvier 1982; ce département est actuellement dirigé par An. Un employé est associé à un ou plusieurs départements. Un département n’a qu’un seul chef et personne n’est chef de plusieurs départements. En plus, le chef d’un département doit toujours figurer parmi les employés de ce département. Donnez les clés primaires et étrangères pour ce schéma-de-base-de-données. Question 8. La table CDA représente un Calendrier de Dates d’Anniversaire. La table MARIAGES stocke les mariages en vigueur; un homme ou une femme ne peut pas avoir plusieurs conjoints en même temps. On maintient l’anniversaire et l’adresse de tous les mariés. On apprend que Tante Odette est née le 27 juin 1936. Elle est mariée avec Oncle Urbain depuis le 1 mai 1950.
CDA Nom Anniversaire Année Adresse Ville | Oncle Urbain | 1 mai | 1950 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Anne Lalo | Jean Crevette | 14 juillet | 1978 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
MARIAGES Femme Mari Jour Année
Déterminez les identifiants possibles et choisissez, parmi ceux-ci, les clés primaires. Ajoutez les clés étrangères. Motivez votre choix.
Question 9. Pour le problème de la question 85, la prochaine décomposition est proposée. Donnez pour chaque table la clé primaire, les clés étrangères et les contraintes de type UNIQUE.
| 2004 | Papillon | 200 | M | 17/8 |
| 2004 | Libre | 200 | M | 16/8 |
| 2000 | Libre | 50 | F | 23/9 |
| 2000 | Papillon | 200 | M | 23/9 |
| 2004 | Athènes |
| 2000 | Sydney |
DATES Année Nage Distance Sexe Date
VILLES Année Ville
| 2004 | M. Phelps | USA |
| 2004 | T. Yamamoto | JAP |
| 2004 | S. Parry | GBR |
| 2000 | I. de Bruijn | NED |
| 2000 | M. Phelps | GBR |
| Athlète | Sexe |
| M. Phelps | M |
| T. Yamamoto | M |
| S. Parry | M |
| I. de Bruijn | F |
NAT Année Athlète Pays ATHLÈTES
2004 Papillon 200 M M. Phelps Or 1 :54.04 2004 Papillon 200 M T. Yamamoto Argent 1 :54.56 2004 Papillon 200 M S. Parry Bronze 1 :55.52 2004 Libre 200 M M. Phelps Bronze 1 :45.32 2000 Libre 50 F I. de Bruijn Or 0 :24.32
2000 Papillon 200 M M. Phelps Argent 1 :55.19
Question 10. La table PROCHES enregistre le sexe et la date de naissance de mes proches; chaque personne est identifiée de manière unique par son nom. Les mariages sont enregistrés dans la table MARIAGES; aucune personne n’est mariée plusieurs fois. La table FAVORIS stocke les bières favorites de mes proches, au maximum trois bières par personne. Notez que Tante Odette n’aime aucune bière. Le petit Nicolas est trop jeune pour boire de la bière!
| Oncle Urbain | M | 9 sep | 1945 |
| Caroline | F | 28 oct | 1960 |
| Jim | M | 24 jan | 1971 |
| An | F | 12 sep | 1974 |
| Pierre | M | 11 feb | 1959 |
| Tante Odette | F | 2 jan | 1947 |
| Nicolas | M | 30 août | 2015 |
| Eric | M | 11 sep | 1981 |
PROCHES Nom Sexe Anniversaire Année
| Oncle Urbain | Duvel |
| Oncle Urbain | Leffe |
| Oncle Urbain | Orval |
| Caroline | Leffe |
| Caroline | Carlsberg |
| Jim | Grimbergen |
| An | Leffe |
| Pierre | Leffe |
| Eric | Chimay |
| Oncle Urbain | Tante Odette |
| Jim | An |
| Pierre | Caroline |
FAVORIS Nom Bière
Déterminez les identifiants possibles et choisissez, parmi ceux-ci, les clés primaires. Ajoutez les clés étrangères.
Question 11. Base de données de la question 2.
Quelle est la population de la capitale du Mali?
Réponse algèbre. Créons d’abord, à l’aide de la requête CC définie ci-dessous, une relation avec attributs Country et Capital, telle qu’un tuple {(Country,x),(Capital,y)} signifie que y est la capitale de x :
CC := ?Name7?Country(?Name,Capital(Countries)).
La requête demandée :
?Population((?Name?7 Capital(Cities)) 1 (?Country=“Mali”(CC))).
2
Question 12. Base de données de la question 2.
Quelle monnaie est utilisée dans plusieurs pays?
Réponse algèbre. Introduisons d’abord une abréviation : ?A6=B(E) est une abréviation pour E ? ?A=B(E), où A,B ? sorte(E). Définissons la requête CURRENCIES comme suit :
CURRENCIES := ?Name,Currency(Countries).
Alors la requête demandée est :
?Currency(?Country6=Name((?Name7?Country(CURRENCIES)) 1 CURRENCIES)).
2
Question 13. Base de données de la question 3.
Quel chauffeur a été à toutes les destinations?
Réponse algèbre. Soit
R := (?Driver(TRIPS) 1 DESTINATIONS) ? ?Destination?7 Name(?Driver,Destination(TRIPS)).
Un tuple {(Driver,d. Donc, if faut retenir tout chauffeur qui ne figure pas dans),(Name,n)} dans R signifie que le chauffeur d n’a jamais fait une excursionR :
à la destination n
?Driver(TRIPS) ? ?Driver(R).
2
Question 14. Base de données de la question 3.
Quelles destinations n’ont jamais été visitées par John?
Réponse algèbre.
DESTINATIONS ? ?Destination7?Name(?Destination(?Driver=“John”(TRIPS))).
2
Question 15. Base de données de la question 3.
Qui a conduit un autobus de la marque Renault pour aller à “Antwerp Zoo”? Réponse calcul.
(TRIPS(u,y,x,“AntwerpZoo”,v)))
?w(?z(BUSES(y,w,“Renault”,z)))
)
2
Question 16. Base de données de la question 4.
Quels produits sont disponibles en plusieurs couleurs dans un même dépôt? ; hinge Réponse calcul.
{y | ?x(?z1(?z2(?q1(?q2(STOCK(x,y,z1,q1) ?STOCK(x,y,z
Question 17. Base de données de la question 4.
Quel entrepôt ne stocke aucun produit rouge? ; D1 etD3
Réponse calcul. On utilisera is_a_warehouse(x) comme abbréviation pour :
?v(?w(WAREHOUSES(x,v,w))).
La requête demandée :
| {x | is_a_warehouse(x) ? ¬?y(?q(STOCK(x,y,“red”,q)))} Une autre solution est : | (10.1) |
| {x |is_a_warehouse(x) ? ?y(?z(?q(¬STOCK(x,y,z,q) ? ¬(z = “red”))))} | (10.2) |
2
Question 18. Base de données de la question 4.
Quel entrepôt ne stocke aucun produit non-rouge? ; D3 et D4
Réponse calcul. Il suffit de remplacer ¬(z = “red”) par (z = “red”) dans la solution (10.2) ci-dessus. 2
Question 19. Base de données de la question 5.
Quels pilotes ont donné forfait pour quels Grands Prix?
Pour la base de données de la question 5, la réponse est comme suit :
| Pilote | GP | Année |
| M. Häkkinen | Belgique | 2001 |
| J. Trulli | Espagne | 2003 |
| K. Räikkönen | Espagne | 2003 |
Le résultat contient le tuple {(Pilote, M. Häkkinen),(GP, Belgique),(Année, 2001)} parce qu’en
2001, M. Häkkinen était inscrit au championnat mais ne figure pas parmi les participants au GP de Belgique. Notez que l’absence de M. Häkkinen dans le GP d’Espagne de 2003 ne peut pas être considéré comme un forfait, car M. Häkkinen n’était pas affilié à une écurie en 2003.
Question 20. Base de données de la question 5.
Donnez les Grands Prix (GP et Année) où le gagneur et le deuxième faisaient partie de la même écurie? seul le GP de Belgique en 2003
Dans l’algèbre, utilisez le moins possible la sélection “attribut égal attribut”.;
Question 21. Base de données de la question 5.
Question 22. Base de données de la question 6.
Quel employé partage son temps moitié-moitié (c’est-à-dire 50%-50%) entre deux départements? ; E3
Question 23. Base de données de la question 6. Qui sont les chefs de E3? ; E1 et E5
Question 24. Bases de données de la question 7.
Donnez tout chef qui ne travaille que pour le département dont il est chef. ; An
Question 25. Base de données de la question 8.
Donnez toute femme mariée qui habite au même endroit que son mari. Tante
Odette ;
Question 26. Base de données de la question 8.
Donnez tout individu qui n’est pas marié. ; Mon chat et Jean Bidon
Question 27. Base de données de la question 9.
Donnez les villes qui ont organisé les jeux olympiques plus qu’une fois.
Question 28. Base de données de la question 9.
Donnez les athlètes qui n’ont jamais changé de nationalité.
Question 29. Base de données de la question 10. On dit qu’un mariage est superbe si les deux conjoints ont une bière favorite commune. Dans l’exemple, seul le mariage de Pierre et Caroline est superbe.
Donne les noms des hommes mariés dont le mariage n’est pas superbe. Oncle
Urbain et Jim ; Dans l’algèbre, utilisez le moins possible la sélection “attribut égal attribut”.
Donnez toute femme qui surpasse-en-matière-de-bière au moins un homme né en 1985 ou avant. ; Caroline et An
Question 31.utilise un nom de relationUne relation binaire est symétrique si pour toutR avec sorte(R) = AB pour stocker une relation binaire.(a,b) ? R, on a (b,a) ? R. On
Est-ce que R est symétrique?
Question 32. Cette question a besoin d’une extension de l’algèbre relationnelle et du calcul relationnel. SoitD (D,?) un domaine ordonné. Soit A,Bsortedeux attributs avec(E). On peut étendre l’algèbre SPJRUDDom(A) = Dom(B) =
. Soit E une expression algébrique telle que A,B ?
avec des sélections qui comparent, en utilisantautre attribut. La sémantique est évidente : pour toute base de données< ou ?, un attribut à une constante ou à unI,
J??AA??“aB”(E)KIII := {t ? JEKIII | t((AA))?? ta(}B; )};
JJJA<A<B“a”((EE))KKKI ::== {{tt??JJEEKKI||tt(A) < t(B)}; ?? (E) := {t ? JEK | t(A) < a}.
De même façon, on peut étendre le calcul relationnel avec des formules atomiques x ? y, x ? “a”, x < y, x < “a”.
Voici une base de données avec deux tables.
| Nom | Prof | Ects |
| Génie logiciel | Mens | 7 |
| Gestion de projets | Mens | 4 |
| Bases de données | Wijsen | 10 |
| Nom | C | Note |
| Ed | Génie logiciel | 13 |
| Ed | Bases de données | 15 |
| Tim | Bases de données | 13 |
COURSNOTES
COURS PRIMARY KEY (Nom)
NOTES PRIMARY KEY(Nom, C)
FOREIGN KEY (C) REFS COURS
1. Donnez les cours de Mens qui n’ont pas été suivis par Ed.
2. Quels étudiants ont obtenu une note supérieure à 10 dans un cours enseigné par Mens?
4. Quels professeurs n’enseignent qu’un seul cours?
5. Quels professeurs n’ont jamais attribué une note inférieure à 10?
6. Donnez la note maximale obtenue en “Bases de Données”.
7. Qui a suivi tous les cours de Mens?
8. Un étudiant est “prodigieux” s’il a obtenu la meilleure note de la classe pour tous les cours qu’il a suivis. Donnez les noms des étudiants prodigieux (s’il y en a).
9. Donnez, pour tout étudiant, le total de ses crédits ECTS (en SQL seulement).
10. Quel professeur donne les notes, en moyenne, les plus basses (en SQL seulement)?
Question 33. La première ligne de la table RESTAURANTS ci-dessous signifie que le Taco est un restaurant mexicain à Anvers. La première ligne de la table VISITES signifie que Jean a déjà été manger au Naxos. Les contraintes sont :
RESTAURANTS(PRIMARY KEY(Nom));
VISITES(PRIMARY KEY(Nom, Restaurant),
FOREIGN KEY(Restaurant) REFERENCES RESTAURANTS);
| Nom | Restaurant |
| Jean | Naxos |
| Jean | Trevi |
| Jean | Pronto |
| Pierre | Naxos |
| Pierre | Trevi |
| An | Campos |
| An | Pronto |
| Nom | Ville | Type |
| Taco | Anvers | mexicain |
| Naxos | Anvers | grec |
| Trevi | Anvers | italien |
| Campos | Mons | italien |
| Pronto | Mons | italien |
VISITES RESTAURANTS
Donnez les noms de tous les restaurants pour lesquels aucune visite n’a été enregistrée.
; Taco
Question 34. Base de données de la question 33.
Qui a déjà visité deux restaurants italiens dans des villes différentes? ; Jean
Question 35. Base de données de la question 33.
Qui n’a jamais visité un restaurant non-italien? ; An
Question 36. Soit sorte(VINS) = {Cru,Millésime,Qualité} et sorte(ABUS) = {Buveur, Cru,
Mill}.
Quels sont les vins (cru et millésime) de qualité A qui ont été bus par Jean mais pas par Pierre.
Réponse algèbre. Soit
les vins de qualité A bus par Jean.
Soit
P := ?Cru,Millésime(VINS 1 ?Mill7?Millésime(?Buveur=“Pierre”(ABUS))),
les vins bus par Pierre. La requête est :
J ? P.
2
Question 37. Soit R un nome de relation avec sorte(R) = {A,B}.
Donnez tout tuplede R. {(A,a),(B,b)} de R pour lequel {(A,b),(B,a)} fait aussi partie
R
| A | B |
| 1 | 1 |
| 1 | 2 |
| 2 | 1 |
| 1 | 3 |
| A | B |
| 1 | 1 |
| 1 | 2 |
| 2 | 1 |
Par exemple, pour, le résultat est.
Réponse algèbre.R 1 ?AB7?BA(R). 2
Question 38. Considérez les tables :
PERSONNE(P#, Nom, Prenom, Adresse) PRIMARY KEY(P#)
VEHICULE(V#, Marque, Type) PRIMARY KEY(V#)
CONDUCTEUR(P#, V#, NInfractions)
PRIMARY KEY(P#, V#)
FOREIGN KEY(P#) REFERENCES PERSONNE
FOREIGN KEY(V#) REFERENCES VEHICULE
Un tuple hp,v,ni dans la relationau volant de la voitureCONDUCTEURv. La valeur poursignifie que n est le nombre d’infractions commisesNInfractions est un entier positif
par la personne p (? 1).
Donnez le nom et le prénom de chaque personne qui a commis des infractions au volant de deux ou plusieurs véhicules différents.
Par exemple, pour la bases de données suivante, le résultat se compose du nom et prénom de P1.
CONDUCTEUR P# V# NInfractions
P1 V1 1
P1 V3 1
P2 V1 2
Question 39. Considérez les tables suivantes avec les significations évidentes.
MANGE
| Personne | Aliment |
| Anne | pomme |
| Anne | steak |
| Anne | tomate |
| Bill | pomme |
| Bill | tomate |
| Ed | pomme |
| Ed | orange |
| Ed | salade |
| Ed | poulet |
| Aliment | Catégorie |
| pomme | fruit |
| steak | viande |
| tomate | légume |
| orange | fruit |
| salade | légume |
| poulet | viande |
| poire | fruit |
NOURRITURE
Qui est végétarien (c’est-à-dire, qui ne mange pas de viande)? ; Bill
Question 40. Base de données de la question 39.
Qui mange au moins deux fruits différents? ; Ed
Question 41. Considérez la base de données avec les tables :
FOURNISSEURS(F#, FNom, Ville)
PRIMARY KEY(F#)
PRODUITS(P#, PNom, Couleur) PRIMARY KEY(P#)
STOCK(F#, P#)
PRIMARY KEY(F#, P#)
FOREIGN KEY(F#) REFERENCES FOURNISSEURS
FOREIGN KEY(P#) REFERENCES PRODUITS
Les relations FOURNISSEURS et PRODUITS ont les significations évidentes. La relation STOCK contient un tuple {(F#,f), (P#,p)} si le fournisseur f garde le produit p en stock.
Donnez les numéros des fournisseurs qui gardent à la fois un produit rouge et un produit bleu en stock.
Question 42. Base de données de la question 41.
Donnez les numéros des fournisseurs qui ne gardent aucun produit rouge en stock.
Question 43. Considérez les tables :
S(S#, SNAME, STATUS, CITY)
P(P#, PNAME, COLOR, WEIGHT, CITY)
J(J#, JNAME, CITY)
1. Donnez les noms des fournisseurs qui fournissent à la fois un produit rouge et un produit vert au même projet à Londres.
2. Donnez les noms des produits qui sont fournis à un ou plusieurs projets en dehors de Londres.
Question 44. Soit R un ensemble fini d’entiers positifs. Pour tout i,j ?R, on dira que j est le successeur de i si i < j et il n’existe pas de k ?R tel que i < k < j.
Donnez tout couple (i,j) tel que i,j ? R et j est le successeur de i. Utilisez les extensions introduites dans la question 32.
Par exemple,
| A | B |
| 7 | 8 |
| 8 | 10 |
| 10 | 17 |
| 17 | 23 |
RA q(R)
10 ;
17
23
Question 45. Soit R un nom de relation avec sorte(R) = ABC. Écrivez une requête qui résulte en une réponse vide si et seulement si la relationdu résultat est sans importance. R satisfait la DF A ? B. Le nombre d’attributs
Réponse calcul.
{x | ?y1(?y2(?z1(?z2(R(x,y1,z1) ? R(x,y2,z2) ? ¬(y1 = y2)))))}
2
Question 46. La table Prix permet de comparer les prix des albums entre différents magasins.
| What’s Inside | Joan Armatrading | 18.99 | |
| What’s Inside | Joan Armatrading | Free Record Shop | 14.99 |
| What’s Inside | Joan Armatrading | Carrefour | 10.55 |
| à Tatons | Axelle Red | 9.99 | |
| à Tatons | Axelle Red | Free Record Shop | 8.99 |
Prix Album Artiste Magasin Prix
Affichez, pour chaque album, l’endroit [les endroits dans le cas d’un ex æquo] où on peut acheter cet album au meilleur prix. Utilisez les extensions de la questions 32.
What’s Inside Joan Armatrading Carrefour
à Tatons Axelle Red Free Record Shop
Question 47. On utilise un nom de relation R avec sorte(R) = AB pour stocker un graphe orienté : un tupleb {(A,a),AB(B,b(?B)7?}Cdénote une arête orienté (ou arc) du sommet(R) 1 ?A?7C(R)) ?R en français et en calcul relationnel.a vers le sommet
. Traduisez la requête ?
Question 48. Soit R,S deux noms de relation avec sorte(R) = sorte(S). Soit X ? sorte(R). Prouvez ou réfutez :
1. ?X(R ?S) v ?X(R) ? ?X(S)
2. ?X(R) ? ?X(S) v ?X(R ?S)
3. ?X(R 1 S)Xv ?X(R)X1 ?X(S)
4. ?X(R) 1 ? (S) v ? (R 1 S)
Question 49. Soit R et S des noms de relation tels que sorte(R) = X et sorte(S) = Y . Prouvez ou réfutez :
1. R ? ?X(R 1 S) X?Y
2. ?X(R 1 S) ? R 1 ? (S) I I
Réponse (partim).J?X(R 1 S)KI = ? et JRSoitKI I une base de données telle que, il est correct de conclure R ?6 R?X=6(R?1etSS). = ?. Sur la base de2
=6 ?
Question 50. Soit R un nom de relation. Soient X,Y des ensembles tels que sorte(R) = X ?Y . Prouvez ou réfutez :
1. ?X(R) 1 ?Y (R)Yv R 2. R v?X(R) 1 ? (R)
| A | B |
| 1 | 1 |
| 1 | 2 |
| 2 | 1 |
| 1 | 3 |
R
Question 51. Pour la base de données, donnez le résultat de :
?C7?B(?AC(?A7?C(R) 1 R)).
| A | B |
| 1 | 1 |
| 1 | 2 |
| 2 | 1 |
| 2 | 2 |
Réponse.2
?A(R 1 S) v ?A(?B=C(R 1 (?B7?C(?B(S))))).Réponse. Soit I une base de données dont le schéma contient R et S. Soit {(A,a)} n’importe quel tuple de ?A(R S) I.
Donc, il existe b,ctels que { ),(B,b)} ? R et { Donc, il existe b tel que {((A,aA,a),(B,b)} ?R tel que {
Donc, il existeDonc, il existeJb,cb tels que1 K {((A,aA,a)),,((B,bB,b))},(?C,cIIRet)I}{et?((C,bB,b{JR(B,b))1}}B???S),CKJ(JI?(C,c?.?BBB7?()(SC}S)())K??IB.SI(.IS.))KI.
Donc, il existeb tel queA B{=((CA,aA,a)),,((B,bB,bB?)),,C((C,bC,bB))}} )))))??JJR?BI1=.C?(R7 1 ?B7?C(?KB(S)))KI.
Donc, il existe b tel que { (R (? (? (S
Donc, {(A,a)} ? J? (? 1 7 K 2
Question 53. Soient
E1 := ?Cru,Qualité(VINS) ?Qualité7?Qual(?Cru,Qualité(VINS)) E2 := ?Cru(VINS) ? ?Cru1(E1 ? ?Qualité=Qual(E1)) Exprimez la requête E2 en français.
Réponse. Donnez tous les crus qui ont toujours été de la même qualité. 2
Question 54. Soient R et S des noms de relation tels que sorte(R) = sorte(S). Démontrez que R ? S ne peut pas être exprimée en algèbre SPJRD (i.e., l’algèbre sans Union).
Réponse.de donnéesPour deux expressions algébriquesI, |JE1KI| ? |JE2KI|. E1 et E2, on écrira |E1| ? |E2| si pour toute base Il est facile de prouver que pour toutes expressions E, E1, E2,
|?X(E)| ? |E| (10.5)
|? 7 (E)| ? |E| (10.7)
|E1? E2| ? |E1| (10.8)
Soient R et S deux noms de relation tels que sorte(R) = sorte(S) = {A}. Soit I la base de données suivante :
R A S A
0 1
Évidemment, JR ? SKI = {{(A,0)},{(A,1)}}, un ensemble avec deux tuples. SoitEI| ? 1. E une expression quelconque en algèbre SPJRD. On démontre que |J K
Preuve par induction sur la structure de E (i.e., la manière dont l’expression E est composée). La base d’induction est simple : si E ? R ou E ? S, alors |JEKI| = 1. Ensuite, l’étape d’induction :
CASE ? ?A=B(E1). Par hypothèse d’induction, |JE1KI| ? 1. Par (10.3), |JEKI| ?
1.
CASE ? ?A=“b”(E1). Analogue. CASE ? ?X(E1). Analogue.
CASE ? ?A7?B(E1). Analogue.
CAS|JEEKI?| ?E11.1 E2. Par hypothèse d’induction, |JE1KII| ? 1 et |JE2KI| ? 1. Par (10.6),I
CASI E ? E1? E2. Par hypothèse d’induction, |JE1K| ? 1. Par (10.8), |JEK| ? 1.
Question 55. Il se fait que l’on peut souvent éviter l’usage de la sélection de la forme “attribut égal attribut”. Par exemple, si{peut écrire cette même requête sans utiliserB}, alors la requête ?A(?A=BR,S(R 1sont des noms de relation avecS)) donne les tuples de?A=B(·), comme suit :S qui se trouvent aussi danssorteR 1(R?) =B7?A{(AS}).et sorteR(S. On) =
Prouvez que l’algèbre SPJRUD perd en expressivité si l’on interdit l’usage de la sélection “attribut égal attribut”, tout en permettant la sélection de type “attribut égal constante”.
Question 56. Comment peut-on exprimer la requête {x | ?y(R(x,“a”,y) ? ¬?z(R(x,“b”,z)))} en algèbre relationnelle?
Réponse. En supposant sorte(R) = ABC :
?A(?B=“a”R) ? ?A(?B=“b”R).
2
Question 57. Soit R un nom de relation avec sorte(R) = {A,B}. Traduisez la requête
{x | ?w(R(x,w)) ? ?w(?v(R(v,w)) ? ¬R(x,w))}
en algèbre relationnelle.
Question 58. Traduisez la requête E2 de la question 53 en calcul relationnel. Réponse.
{x | ?y(?z(VINS(x,y,z) ? ¬(?v(?w(VINS(x,v,w) ? ¬(z = w))))))} Si on prend la liberté d’alléger la syntaxe :
{x | ?y,z(VINS(x,y,z) ? ¬?v,w(VINS(x,v,w) ? z =6 w))}
En mots simples : donnez toutaucun autre tuple=6 z). hx,v,wi qui témoigne que le crux tel qu’il existe un tuplex a été d’une qualitéhx,y,zi en VINSwpourvu qu’il n’existeautre que z (donc2
w
Question 59. Soient R et S deux noms de relation d’arité 1. Quelle des deux requêtes suivantes est erronée, et pourquoi?
q q
Réponse. Si ?(x) dénote la formule R(x) ? ¬S(x), alors ?(a) est vraie pour toute constante a telle que S(a) est fausse. Il est évident que la requête q1 n’est pas indépendante du domaine d’interprétation.
Par contre, si l’on écrit la requête q2 comme
{x | ¬R(x) ?S(x)},
Question 60. Traduisez la requête suivante en français :
{x | DESTINATIONS(x) ? ¬(?u(?v(?w(TRIPS(u,v,“John”,x,w)))))}
La base de données est celle de la question 3.
Question 61. Comment peut-on exprimer la requête {x | R(x,“a”) ? ?y(R(“b”,y))} en algèbre relationnelle? Et en SQL?
Question 62. Pour la base de données de la question 5, donnez une requête en SQL pour la question suivante :
Quel pilote a gagné le plus de Grands Prix? ; M. Schumacher
Question 63. Pour la base de données de la question 8, écrivez une requête en SQL pour répondre à la question :
Quel est le nombre de femmes mariées qui habitent Mons? ; 2
Question 64. Pour la base de données de la question 8, écrivez une requête en SQL pour répondre à la question :
Quel est l’homme marié le plus âgé? ; Oncle Urbain
Question 65. Consider a suppliers-parts-projects database. Suppliers (S) and parts (P) are as in chapter 5. Projects (J) are uniquely identified by a project number (J#). Other attributes of projects are project name (JNAME) and city. The significance of an SPJ (shipment) tuple is that the specified supplier supplies the specified part to the specified project in the specified quantity (and the combination S#-P#-J# uniquely identifies such a tuple). Write a suitable data definition for this database. Réponse.
CREATE TABLE S
( ) ;
CREATE TABLE P
( ) ;
CREATE TABLE J
( J# J#,
JNAME NAME,
CITY CITY,
PRIMARY KEY ( J# ) ) ;
CREATE TABLE SPJ
( S# S#, P# P#,
J# J#,
QTY QTY,
PRIMARY KEY ( S#, P#, J# ),
FOREIGN KEY ( S# ) REFERENCES S,
FOREIGN KEY ( P# ) REFERENCES P,
2
Question 66. Get part number for parts supplied by a supplier in London. Réponse.
SELECT DISTINCT SPJ.P# FROM SPJ, S
WHERE SPJ.S# = S.S#
AND S.CITY = ‘London’ ;
2
Question 67. Get project numbers for projects supplied by at least one supplier not in the same city.
Réponse.
SELECT DISTINCT SPJ.J#
FROM SPJ, S, J
WHERE SPJ.S# = S.S# AND SPJ.J# = J.J#
AND S.CITY <> J.CITY ;
2
Question 68. Get part numbers of parts supplied to some project in an average quantity of more than 320. Réponse.
SELECT DISTINCT SPJ.P#
FROM SPJ
GROUP BY SPJ.P#, SPJ.J#
HAVING AVG ( ) > 320 ;
2
Question 69. Get project numbers for projects supplied entirely by S1. Réponse.
SELECT SPJX.J#
FROM SPJ AS SPJX
WHERE SPJX.S# = ‘S1’
AND NOT EXISTS
( SELECT *
FROM SPJ AS SPJY
WHERE SPJY.J# = SPJX.J#
AND SPJY.S# <> ‘S1’ ) ;
2
Question 70. Get all cities in which at least one supplier, part, or project is located. Réponse.
SELECT CITY
FROM S
UNION
SELECT CITY
FROM P
UNION
SELECT CITY
FROM J ;
2
Question 71. Get all pairs of supplier numbers, Sx and Sy say, such that Sx and Sy supply exactly the same set of parts each. Réponse.
SELECT SX.S#, SY.S#
FROM S AS SX, S AS SY
WHERE NOT EXISTS
( SELECT *
FROM SPJ AS SPJX
WHERE SPJX.S# = SX.S#
AND NOT EXISTS
( SELECT *
FROM SPJ AS SPJY
WHERE SPJY.S# = SY.S#
AND NOT EXISTS
( SELECT *
FROM SPJ AS SPJY
WHERE SPJY.S# = SY.S#
AND NOT EXISTS
( SELECT *
FROM SPJ AS SPJX
WHERE SPJX.S# = SX.S#
AND SPJX.P# = SPJY.P# ) ) ;
2
Question 72. Get supplier-number/part-number pairs such that the indicated supplier does not supply the indicated part. Réponse.
SELECT S.S#, P.P#
FROM S, P
WHERE NOT EXISTS ( SELECT *
FROM SPJ
WHERE SPJ.S# = S.S#
AND SPJ.P# = P.P# ) ;
2
Question 73. Get supplier numbers for suppliers supplying some project with part P1 in a quantity greater than the average shipment quantity of part P1 for that project. Réponse.
SELECT SPJX.S#
FROM SPJ AS SPJX
WHERE SPJX.P# = ‘P1’
AND >
( SELECT AVG ( ) FROM SPJ AS SPJY
WHERE SPJY.P# = ‘P1’
AND SPJY.J# = SPJX.J# ) ;
2
Question 74. Get project numbers for projects supplied with part P1 in an average quantity greater than the greatest quantity in which any part is supplied to project J1. Réponse.
SELECT SPJX.J#
FROM SPJ AS SPJX
WHERE SPJX.P# = ‘P1’
GROUP BY SPJX.J#
HAVING AVG ( ) >
( SELECT MAX ( ) FROM SPJ AS SPJY
WHERE SPJY.J# = ‘J1’ ) ;
2
Question 75. Pour la base de données de la question 4, écrivez une requête en SQL pour répondre à la question :
Combien de produits rouges sont stockés en dehors de Mons? ; 750
Quel est le résultat de votre requête si tous les produits en dehors de Mons sont non-rouges?
SELECT
FROM WAREHOUSES W1, STOCK S1
WHERE W1.W# = S1.W#
AND S1.COLOR <> ‘red’
GROUP BY
HAVING SUM() > ( SELECT SUM()
FROM WAREHOUSE W2, STOCK S2
WHERE W2.W# = S2.W#
AND =
AND S2.COLOR = ‘red’ );
La base de données est celle de la question 4.
Question 77. Pour la base de données de la question 9, donnez une requête SQL qui donne le nombre total de médailles par année et par pays, pourvu que ce nombre soit supérieur à zéro. La réponse est comme suit :
| 2004 | USA | 2 |
| 2004 | JAP | 1 |
| 2004 | GBR | 1 |
| 2000 | NED | 1 |
| 2000 | GBR | 1 |
Année Pays Nombre
Question 78. Pour la base de données de la question 10, donnez une requête SQL pour répondre à la question :
Quelle bière apparaît le plus grand nombre de fois comme bière favorite? ; Leffe
| Code | Titre | Enseignant | Sem | Jour | Heure | Local | Prérequis |
| S/3I/2 | Systèmes d’information | J. Wijsen | 2 | Jeudi | 13h15 | 3E11/P | S/2I/17 |
| S/3I/2 | Systèmes d’information | J. Wijsen | 2 | Jeudi | 13h15 | 3E11/P | S/3I/5 |
| S/2I/17 | Fichiers et Bases de Données | J. Wijsen | 1 | Vendredi | 10h15 | 3E11/P | S/1I/3 |
| S/3I/5 | Structure de l’information | V. Bruyère | 1 | Vendredi | 10h15 | 3E10/P | S/1I/3 |
| S/1I/3 | Informatique I | P. Dufour | 1 | Vendredi | 10h15 | 211/VI | — |
| S/1I/3 | Informatique I | P. Dufour | 1 | Mardi | 15h15 | 209/VI | — |
Quelles sont les DFs valables pour ces données? Remarquons que ces DF doivent exprimer, entre autres, que deux cours différents qui sont enseignés au même moment, doivent avoir des enseignants et des locaux différents.
Question 80. Considérons le schéma-DF {Code,Titre,Enseignant,Sem,Jour,Heure,Local,Prérequis} avec les DFs de la question 79. Quelles sont les clés de ce schéma-DF? Est-ce que ce schéma-DF est en 3NF? Expliquez.
Question 81. Supposons une table FILMS qui sert à enregistrer des informations sur des films. Les attributs ont les significations évidentes. Deux films peuvent porter le même Titre, mais la combinaison Titre plus Directeur constitue une identification unique d’un film. Supposons que la production de chaque film est assurée par une seule société. L’attribut Minutes donne la durée d’un film en minutes. L’attribut Première est la date de la première. Plusieurs premières peuvent avoir lieu à la même date pourvu que les films concernés n’aient pas de régisseurs ou acteurs en commun, afin de permettre aux directeurs et acteurs d’assister aux premières de leurs films.
Voici un exemple de cette table :
FILMS
| Titre | Directeur | Acteur | Société | Première | Minutes |
| The Birds | T. Hedren | Universal Pictures | 28/03/1963 | 113 | |
| The Birds | A. Hitchcock | R. Taylor | Universal Pictures | 28/03/1963 | 113 |
| Titanic | J. Cameron | K. Winslet | Twentieth Century Fox | 19/12/1997 | 195 |
| Titanic | J. Cameron | L. DiCaprio | Twentieth Century Fox | 19/12/1997 | 195 |
| The Birds | J. Cameron | K. Winslet | Paramount Pictures | 28/01/2001 | 182 |
| The Birds | J. Cameron | R. Taylor | Paramount Pictures | 28/01/2001 | 182 |
1. Pour simplifier la notation, désignons chaque attribut par sa première lettre (donc T pour Titre, D pour Directeur ). Donnez l’ensemble ? de dépendances fonctionnelles qui doivent être satisfaites par toute relation “valide” sur A := {T,D,A,S,P,M}. Donnez les clés du schéma-DF (A,?) obtenu.
2. Expliquez pourquoi le schéma-DF (A,?) qui résulte du point (1) n’est pas en 3NF. Donnez une décomposition en 3NF qui préserve les DFs.
3. Si la décomposition qui résulte du point (2) n’est pas en BCNF, donnez une décomposition en BCNF.
Réponse.
? = { TD ? SPM,
DP ? T,
AP ? TD }
Les clés sont TDA et AP. Cette relation n’est pas en 3NF parce que ? |= TD ?S, ? 6|= TD ? A et S n’est pas premier.
Le bon sens évoque une décomposition en deux composants : un premier composant pour stocker la société, la date de la première et la durée de tout film, un deuxième composant pour stocker les acteurs de tout film. Noter ? |=1 [TDSPM,TDA].
Composant Schéma DF Clé(s) BCNF?
Il est clair que cette décomposition ne préserve pas les DFs AP ? T et AP ? D.
Essayons ensuite d’ajouter au deuxième composant l’attribut: P afin de préserver AP ?
TD
Composant Schéma DF Clé(s) BCNF? 3NF?
12 TDSPMTDAP {{TDAP ?? TD,TDSPM,DP??P,DPT} ? T} AP,TDATD,DP nonoui ouioui
Notez que ? |= TDP ?SM, et donc ? |= [TDSPM,TDAP]. Ceci est une décomposition en
3NF qui préserve les DFs. 1
Remarquons que l’on peut supprimer l’attribut P du premier composant :
Composant Schéma DF Clé(s) BCNF? 3NF?
12 TDSMTDAP {{TDAP ?? TD,TDSM} ? P,DP ? T} TDAP,TDA nonoui ouioui
Notez que ? |= TD ?SM, et donc ? |=1 [TDSM,TDAP]. Ceci est une autre décomposition en 3NF qui préserve les DFs.
Pour l’exemple, la dernière décomposition donne les tables suivantes :
| Titre | Directeur | Société | Minutes | |||||
| The Birds | A. Hitchcock | Universal Pictures | 113 | |||||
| Titanic | J. Cameron | Twentieth Century Fox | 195 | |||||
| The Birds | J. Cameron | Paramount Pictures | 182 | |||||
| Titre | Directeur | Acteur | Première | |||||
| The Birds | A. Hitchcock | T. Hedren | 28/03/1963 | |||||
| The Birds | A. Hitchcock | R. Taylor | 28/03/1963 | |||||
| Titanic | J. Cameron | 19/12/1997 | ||||||
| Titanic | J. Cameron | L. DiCaprio | 19/12/1997 | |||||
| The Birds | J. Cameron | K. Winslet | 28/01/2001 | |||||
| The Birds | J. Cameron | R. Taylor | 28/01/2001 | |||||
2
Question 82. La Société Nationale des Cinémas Belges (SNCB) stocke des informations sur les cinémas et leur programmation actuelle dans la table montrée ci-dessous. Les premières deux lignes signifient que le film “Felice” de P. Delpeut est programmé à 19 :15 et à 21 :15 au cinéma Utopia à Alost. Ce film, avec une durée de 1 heure et 39 minutes, est aussi programmé au cinéma Rex à Alost, à 18 :00 (cinquième ligne). Il ne faut pas confondre ce film avec celui de S. Spielberg montré à l’Utopia à Namur (dernière ligne).
Bien sûr, il peut y avoir plusieurs cinémas dans la même ville, mais il est impossible d’avoir deux cinémas différents à la même adresse postale. De plus, tous les cinémas de la même ville auront des noms différents. Chaque cinéma ne dispose que d’une seule salle de projection. Dès lors, aucun cinéma ne peut programmer deux films différents au même moment. Un film est identifié de manière unique par son titre plus son régisseur. La durée d’un film est une donnée fixe. Notons que deux films différents peuvent avoir le même titre. Chaque cinéma possède un ou plusieurs numéros de téléphone, mais aucun numéro n’est partagé parmi plusieurs cinémas.
Utopia 6 Place du Parc Alost 053 66 33 33 Felice P. Delpeut 1 :39 19 :15
Utopia 6 Place du Parc Alost 053 88 44 44 Felice P. Delpeut 1 :39 19 :15
Utopia 6 Place du Parc Alost 053 88 44 44 Felice P. Delpeut 1 :39 21 :15 Rex 8 Rue du Marché Alost 053 44 22 22 Felice P. Delpeut 1 :39 18 :00 Utopia 5 Avenue Codd Namur 081 33 66 99 Little Sister T. Ravolta 1 :30 18 :15
Utopia 5 Avenue Codd Namur 081 33 66 99 Felice S. Spielberg 2 :05 19 :00
Quelles sont les DFs pour ce schéma-de-relation? Réponse.
— CinémaNom, Ville ? Rue — Rue, Ville ? CinémaNom
— Téléphone ? CinémaNom, Ville
— CinémaNom, Ville, Heure ? Titre, Régisseur
— Titre, Régisseur ? Durée
2
Question 83. Démontrez de manière précise que le schéma-DF présenté à la question 82 n’est pas en BCNF.
Question 84. Vous êtes engagé par la SNCB comme expert en BD. En effet, la société a
remarqué que la table de la question 82 est difficile à maintenir dû à des informations dupliquées. Ceci ne vous étonne pas, car la violation de BCNF est évidente (voir question 83). Donnez, en vous basant sur votre “bon sens”, une décomposition de cette table qui permet de stocker les mêmes informations et qui ne souffre pas des informations redondantes. Ajoutez les clés primaires et étrangères.
Réponse. En s’appuyant sur le “bon sens”, on trouve le schéma-de-base-de-données : CINEMAS (CinémaNom, Ville, Rue)
TELEPHONES (Téléphone, CinémaNom, Ville)
FILMS (Titre, Régisseur, Durée)
PROGRAMME (CinémaNom, Ville, Titre, Régisseur, Heure)
Cependant, ceci n’est pas une décomposition correcte, parce que la deuxième condition de la Définition 1 (i.e., la condition de lossless join) n’est pas vérifiée. En fait, considérez la relation R suivante qui satisfait toute DF :
| a1 | a2 | a3 | a4 | b5 | b6 | b7 | b8 |
| a1 | a2 | a3 | b4 | a5 | a6 | a7 | a8 |
R CinémaNom Rue Ville Téléphone Titre Régisseur Durée Heure
La décomposition donne :
| a1 | a2 | a3 |
CINEMAS CinémaNom Rue Ville
| a1 | a3 | a4 |
| a1 | a3 | b4 |
TELEPHONES CinémaNom Ville Téléphone
| b5 | b6 | b7 |
| a5 | a6 | a7 |
FILMS Titre Régisseur Durée
| a1 | a3 | b5 | b6 | b8 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| a1 | a3 | a5 | a6 | a8 La jointure des composants donne un tuple ha1,a2,a3, ,a8i qui ne fait pas partie de R. Pour arriver à une décomposition en BCNF qui est lossless join, il faut ajouter un composant TH(Téléphone, Heure). En quelque sorte, ce composant pourrait encoder quel téléphone est opérationnel à quelle heure. Cependant, il semble logique de supposer la DMV CinémaNom,Rue,Ville Téléphone, qui est équivalente à CinémaNom,Rue,Ville Titre,Régisseur,Durée,Heure. Intuitivement, pour chaque cinéma, les numéros de téléphone et la programmation sont indépendants. Ces DMVs ne peuvent pas être exprimées en tant que DF. Avec ces DMVs, notre solution “bon sens” est bien lossless join. 2 Question 85. La table suivante sert à stocker les podiums (médaille d’or, d’argent et de bronze) de la natation aux jeux Olympiques. On ne prend compte que des courses individuelles, pas les courses de relais. — Supposons que tout athlète est identifié par un nom unique et invariable. Par exemple, l’athlète nommé “M. Phelps” de 2004 est le même que celui de 2000. — Un athlète ne peut pas changer de sexe. Néanmoins, il peut changer de nationalité. Dans l’exemple, M. Phelps a changé de la Grande-Bretagne (GBR) aux états-Unis (USA) entre 2000 et 2004. évidemment, il est interdit de nager pour deux pays différents pendant les mêmes jeux Olympiques. — La finale d’une discipline a lieu à un jour déterminé. Par exemple, en 2004, la finale des — Les jeux Olympiques sont attribués à une seule ville : Athènes en 2004, Sydney en 2000 Certaines villes, telles que Paris et Athènes, ont déjà organisé les jeux plus qu’une fois. NATATION
Année Ville Nage Distance Sexe Date Athlète Pays Médaille Temps — Quelles sont les DFs pour ce schéma-de-relation? Écrivez les DFs en formatest minimal. évitez les DFs redondantes, i.e., les DFsX ? A avec A un seul attribut; assurez que X qui sont une conséquence logique des autres. — Donnez une clé pour ce schéma-DF. Question 86. Un club de tennis gère les réservations de ses terrains de tennis. Les dix terrains sont numérotés I, II, III, IV, , X. L’attribut Site indique si un terrain se trouve en salle (salle) ou en plein air (dehors); cette caractéristique d’un terrain ne change jamais. Les terrains peuvent être réservés en tranches d’une heure : la première tranche commence à 9h, la dernière à 19h. On stockera la personne (Nom) qui fait la réservation, le terrain (Terrain) et la tranche (Jdate et Par exemple, les deux premières rangées indiquent qu’à la date du 8 janvier, J. Henin a réservé le terrain IV pour le 22 janvier pendant deux tranches successives, à partir de 9h. Après vient K. Clijsters. Notons que le prix d’un terrain en salle est de 100 euros pour les membres et de 150 euros pour les non-membres. Apparemment, K. Clijsters est devenue membre du club à partir du 10 janvier; à cette date, elle introduit une réservation pour les terrains IV et II à l’heure du midi.
— Quelles sont les DFs pour ce schéma-de-relation? — Donnez une clé pour ce schéma-DF. Question 87. La table suivante sert à stocker les réservations des chambres dans un hôtel. RESERVATIONS
#Client NomClient Domicile NrChambre FaiteLe Séjour CartePaiement Une carte de paiement est indispensable pour garantir une réservation; toute carte de paiement est personnalisée et portera le nom de la personne qui a demandé la réservation. On n’enregistra jamais plus d’une carte de paiement par réservation. Bien sûr, une personne peut avoir plusieurs cartes de paiement. Tout numéro de carte est unique au cours du temps. La même personne peut être connue sous différents identifiants (#Client). Par exemple, les identifiants 111 et 333 identifient tous les deux le porteur de la carte 1111–1111. Néanmoins, les identifiants des clients, comme les cartes de paiements, sont personnalisés et ne seront jamais ré-utilisés pour d’autres clients. Donc, bien que deux personnes différentes puissent occasionnellement avoir le même nom et domicile, elles ne peuvent jamais partager la même carte de paiement ou le même #Client. Une personne ne peut être domiciliée en différents pays en même temps. Néanmoins, le domicile d’une personne peut varier dans le temps. Par exemple, Pierre Dupont habitait d’abord en France, puis en Espagne. — Quelles sont les DFs pour ce schéma-de-relation? — Donnez une clé pour ce schéma-DF. Question 88.Monsieur Bricolage est une entreprise qui loue des outils de bricolage (perceuses, bétonnières ) au grand public sur base journalière.
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
