Année Universitaire 2010/2011

Session 1 de Printemps

PARCOURS : CSB4 & CSB6

UE : INF 159, Bases de données
Épreuve : INF 159 EX
Date : Mardi 3 mai 2010
Heure : 11 heures Durée : 1 heure 30
Documents : non autorisés
DISVE
Épreuve de M. Alain Griffault
Licence

SUJET + CORRIGE

Avertissement
 La plupart des questions sont indépendantes.
 Le barème total est de 23 points car le sujet est assez long.
 Le barème de chaque question est (approximativement) proportionnel à sa diculté.
 L'espace pour répondre est susant (sauf si vous l'utilisez comme brouillon, ce qui est fortement déconseillé).

Exercice 1 (Conception et SQL (12 points))

L'exercice porte sur une gestion simpliée d'arbres généalogiques. Le concepteur de la base a conçu un schéma re-
lationnel composé des trois relations Personnes, Parents et Mariages. La première partie de l'exercice consiste
à comprendre et à expliquer ce schéma. La seconde partie sera composée de requêtes, et la troisième de variantes.
Les sources sont au format PostGreSQL, et toutes les relations sont préxées par le nom du schéma Genealogie.
CREATE SCHEMA G e n e a l o g i e ;

CREATE TABLE Genealogie . Personnes (

−− T y p a g e d e s a t t r i b u t s
I d s e r i a l NOT NULL , −− s e r i a l = s e q u e n c e d ' e n t i e r 1, 2, 3, . . .

Nom t e x t NOT NULL ,

Prenom t e x t NOT NULL ,
Sexe char NOT NULL CHECK ( Sexe = ' F ' or Sexe = 'M' ) ,
D a t e N a i s s a n c e date NOT NULL ,
DateDeces date NOT NULL DEFAULT ' i n f i n i t y ' ,
−− C l e f s c a n d i d a t e s
PRIMARY KEY ( i d ) ,
−− C o n t r a i n t e s d ' i n t e g r i t e e l e m e n t a i r e
CHECK ( D a t e N a i s s a n c e < DateDeces )
);

Question 1.1 (1 point) Pour la relation Personnes, donnez la seule dépendance fonctionnelle déclarée, puis
expliquez à quoi correspond la contrainte d'intégrité.

Réponse :

Id → (N om, P renom, Sexe, DateN aissance, DateDeces)

La date de décès ne peut être antérieure à la date de naissance.

CREATE TABLE Genealogie . Parents (
−− T y p a g e d e s a t t r i b u t s
E n f a n t integer NOT NULL ,
Mere integer NOT NULL ,
P e r e integer NOT NULL ,
−− C l e f s c a n d i d a t e s
PRIMARY KEY ( E n f a n t ) ,

1/ 7
INF 159 : Bases de données Session 1, Année 2010/2011

−− Clefs etrangeres

FOREIGN KEY ( E n f a n t ) REFERENCES G e n e a l o g i e . P e r s o n n e s ( I d ) ,

FOREIGN KEY ( Mere ) REFERENCES G e n e a l o g i e . P e r s o n n e s ( I d ) ,
FOREIGN KEY ( P e r e ) REFERENCES G e n e a l o g i e . P e r s o n n e s ( I d ) ,
−− Contraintes d' integrite elementaire

CHECK ( E n f a n t <> Mere AND E n f a n t <> P e r e AND Mere <> P e r e )

);

−− PostgreSQL exige une fonction pour les contraintes d' integrite avec SELECT

CREATE FUNCTION G e n e a l o g i e . A g e M e r e P e r e C o r r e c t s ( integer , integer , integer )

RETURNS b o o l e a n AS $$
SELECT EXISTS (
SELECT ∗
FROM
( SELECT D a t e N a i s s a n c e FROM G e n e a l o g i e . P e r s o n n e s WHERE $1 = I d ) AS DateEnfant ,
( SELECT D a t e N a i s s a n c e FROM G e n e a l o g i e . P e r s o n n e s WHERE $2 = I d ) AS DateMere ,
( SELECT D a t e N a i s s a n c e FROM G e n e a l o g i e . P e r s o n n e s WHERE $3 = I d ) AS DatePere
WHERE Extract ( year FROM D a t e E n f a n t . D a t e N a i s s a n c e ) >
Extract ( year FROM DateMere . D a t e N a i s s a n c e ) + 10
AND Extract ( year FROM D a t e E n f a n t . D a t e N a i s s a n c e ) >
Extract ( year FROM D a t e P e r e . D a t e N a i s s a n c e ) + 1 0 )
$$ LANGUAGE SQL ;
−− A j o u t d e l a c o n t r a i n t e p a r a p p e l d e l a f o n c t i o n
ALTER TABLE G e n e a l o g i e . P a r e n t s ADD CONSTRAINT A g e s P a r e n t s P o s s i b l e s
CHECK( G e n e a l o g i e . A g e M e r e P e r e C o r r e c t s ( E n f a n t , Mere , P e r e ) = TRUE ) ;
−− PostgreSQL exige une fonction pour les contraintes d' integrite avec SELECT

CREATE FUNCTION G e n e a l o g i e . S e x e M e r e P e r e C o r r e c t s ( integer , integer )

RETURNS b o o l e a n AS $$
SELECT NOT EXISTS (
SELECT ∗
FROM G e n e a l o g i e . P e r s o n n e s
WHERE ( $1 = I d AND Sexe = 'M' ) OR ( $2 = I d AND Sexe = ' F ' ) )
$$ LANGUAGE SQL ;
−− A j o u t d e l a c o n t r a i n t e p a r a p p e l d e l a f o n c t i o n
ALTER TABLE G e n e a l o g i e . P a r e n t s ADD CONSTRAINT S e x e s P a r e n t s P o s s i b l e s
CHECK( G e n e a l o g i e . S e x e M e r e P e r e C o r r e c t s ( Mere , P e r e ) = TRUE ) ;
Question 1.2 (1 point) Pour la relation Parents, donnez la seule dépendance fonctionnelle déclarée, puis
expliquez à quoi correspondent les trois contraintes d'intégrité.

Réponse :

Enf ant → (M ere, P ere)

 Pour chaque triplet, les identités de l'enfant, de la mère et du père sont toutes diérentes.
 Les parents doivent avoir 10 ans au moment de la naissance de leurs enfants.
 Le père doit être de sexe masculin, et la mère de sexe féminin.
CREATE TABLE Genealogie . Mariages (
−− T y p a g e d e s a t t r i b u t s
Femme s e r i a l NOT NULL ,
Mari s e r i a l NOT NULL ,
D a t e M a r i a g e date NOT NULL ,
D a t e D i v o r c e date NOT NULL DEFAULT ' i n f i n i t y ' ,
−− C l e f s c a n d i d a t e s
PRIMARY KEY (Femme , Mari , D a t e M a r i a g e ) ,
UNIQUE (Femme , Mari , D a t e D i v o r c e ) ,
−− C l e f s e t r a n g e r e s
FOREIGN KEY (Femme) REFERENCES G e n e a l o g i e . P e r s o n n e s ( I d ) ,
FOREIGN KEY ( Mari ) REFERENCES G e n e a l o g i e . P e r s o n n e s ( I d ) ,
−− C o n t r a i n t e s d ' i n t e g r i t e e l e m e n t a i r e

2/ 7
INF 159 : Bases de données Session 1, Année 2010/2011

CHECK (Femme <> Mari ) ,

CHECK ( DateMariage < DateDivorce )
);

−− PostgreSQL exige une fonction pour les contraintes d' integrite avec SELECT

CREATE FUNCTION G e n e a l o g i e . D a t e s M a r i a g e C o r r e c t e s ( integer , integer , date , date )

RETURNS b o o l e a n AS $$
SELECT NOT EXISTS (
SELECT ∗
FROM G e n e a l o g i e . M a r i a g e s
WHERE ( $1 = Femme AND $3 <= D a t e M a r i a g e AND $4 >= D a t e D i v o r c e )
OR ( $2 = Mari AND $3 <= D a t e M a r i a g e AND $4 >= D a t e D i v o r c e ) )
$$ LANGUAGE SQL ;
−− A j o u t d e l a c o n t r a i n t e p a r a p p e l d e l a f o n c t i o n
ALTER TABLE G e n e a l o g i e . M a r i a g e s ADD CONSTRAINT D a t e s P o s s i b l e s
CHECK( G e n e a l o g i e . D a t e s M a r i a g e C o r r e c t e s (Femme , Mari , DateMariage , D a t e D i v o r c e ) = TRUE ) ;
−− PostgreSQL exige une fonction pour les contraintes d' integrite avec SELECT

CREATE FUNCTION G e n e a l o g i e . S e x e F e m m e M a r i C o r r e c t s ( integer , integer )

RETURNS b o o l e a n AS $$
SELECT NOT EXISTS (
SELECT ∗
FROM G e n e a l o g i e . P e r s o n n e s
WHERE ( $1 = I d AND Sexe = 'M' ) OR ( $2 = I d AND Sexe = ' F ' ) )
$$ LANGUAGE SQL ;
−− A j o u t d e l a c o n t r a i n t e p a r a p p e l d e l a f o n c t i o n
ALTER TABLE G e n e a l o g i e . M a r i a g e s ADD CONSTRAINT S e x e s C o u p l e P o s s i b l e s
CHECK( G e n e a l o g i e . S e x e F e m m e M a r i C o r r e c t s (Femme , Mari ) = TRUE ) ;
Question 1.3 (1 point) Pour la relation Mariages, donnez les seules dépendances fonctionnelles déclarées,
puis expliquez à quoi correspondent les quatre contraintes d'intégrité.

Réponse :

(F emme, M ari, DateM ariage) → DateDivorce

(F emme, M ari, DateDivorce) → DateM ariage

La femme et le mari ne font pas qu'un.

Ils doivent se marier avant de divorcer.
Une femme ne peut pas être mariée à deux hommes en même temps.
Un homme ne peut pas être marié à deux femmes en même temps.
Le mari est de sexe masculin et la femme de sexe féminin.
Remarque complémentaire non demandée : Les contraintes sur la monogamie ajaoute en fait 4 nouvelles
DFs.

(F emme, DateM ariage) → (M ari, DateDivorce)

(F emme, DateDivorce) → (M ari, DateM ariage)
(M ari, DateM ariage) → (F emme, DateDivorce)
(M ari, DateDivorce) → (F emme, DateM ariage)

Question 1.4 (1 point) En tenant compte uniquement des dépendances fonctionnelles que vous avez listées
dans les réponses précédentes, dites si les relations Personnes, Parents et Mariages sont 3NF et/ou BCNF.

Réponse :

3/ 7
INF 159 : Bases de données Session 1, Année 2010/2011

3NF BCNF Justication

Personnes OUI OUI Id → (N om, P renom, Sexe, DateN aissance, DateDeces) est la seule
DF irréductible à gauche, donc BCNF
BNCF ⇒ 3NF
Parents OUI OUI Enf ant → (M ere, P ere) est la seule DF irréductible à gauche, donc
BCNF
BNCF ⇒ 3NF
Mariages OUI OUI Cas 1 : Les 2 DFs déclarées seules
Les 2 clefs candidates sont les membres gauches des 2 DFs, donc BCNF
Cas 2 : Les 2 DFs plus les 4 DFs
Les 2 premières ne sont pas irréductibles, donc 4 DFs
Les 4 clefs candidates sont les membres gauches des 4 DFs, donc BCNF
BNCF ⇒ 3NF

Question 1.5 (1 point) Après en avoir donné une écriture algébrique, écrire une requête SQL qui caractérise
les identiants des Enfant ayant pour mère 7 et pour père 4.

Réponse : R = π[Enfant](σ[M ere = 7 ∧ P ere = 4](P arents))

SELECT Enfant
FROM Genealogie . Parents
WHERE G e n e a l o g i e . P a r e n t s . Mere = 7
AND G e n e a l o g i e . Parents . Pere = 4;

Question 1.6 (1,5 point) Après en avoir donné une écriture algébrique, écrire une requête SQL qui caracté-
rise les noms, prénoms et date de naissance des enfants de 4. La requête listera les réponses par ordre croissant
des dates de naissance.

Réponse : Réponse non unique.

R = π[Nom,Prenom,DateNaissance ](σ[Id = Enf ant](P ersonnes×π[Enf ant](σ[M ere = 4∨P ere = 4](P arents))))
SELECT Nom, Prenom , D a t e N a i s s a n c e
FROM Genealogie . Personnes ,
( SELECT E n f a n t
FROM G e n e a l o g i e . P a r e n t s
WHERE ( G e n e a l o g i e . P a r e n t s . Mere = 4 OR G e n e a l o g i e . Parents . Pere = 4))
AS E n f a n t s
WHERE Id = Enfant
ORDER BY D a t e N a i s s a n c e ;
Question 1.7 (1,5 point) Après en avoir donné une écriture algébrique, écrire une requête SQL qui carac-
térise les noms, prénoms et date de naissance des demi-frères et des demi-soeurs de 4. La requête listera les
réponses par ordre croissant des dates de naissance.

Réponse : Réponse non unique.

R = π[Nom, Prenom, DateNaissance ](σ[Id = Enf ant](P ersonnes × (

π[Mere.Enfant](σ[P arents.Enf ant = 4 ∧ P arents.M ere = M ere.M ere](P arents × α(P arents : M ere)))
∪
π[Pere.Enfant](σ[P arents.Enf ant = 4 ∧ P arents.P ere = P ere.P ere](P arents × α(P arents : P ere))))

SELECT Nom, Prenom , D a t e N a i s s a n c e

FROM Genealogie . Personnes ,
( SELECT Mere . E n f a n t
FROM G e n e a l o g i e . P a r e n t s AS EnfantsM , G e n e a l o g i e . P a r e n t s AS Mere
WHERE EnfantsM . E n f a n t = 4
AND EnfantsM . Mere = Mere . Mere
UNION
SELECT Pere . Enfant
FROM G e n e a l o g i e . P a r e n t s AS E n f a n t s P , G e n e a l o g i e . P a r e n t s AS Pere
WHERE EnfantsP . Enfant = 4

4/ 7
INF 159 : Bases de données Session 1, Année 2010/2011

AND EnfantsP . Pere = Pere . Pere )

ASEnfants
WHERE Id = Enfant
ORDER BY D a t e N a i s s a n c e ;
Question 1.8 (1,5 point) Écrire une requête SQL qui liste les noms et les prénoms des personnes qui se sont
mariés plus de 4 fois.

Réponse : Réponse non unique.

SELECT Nom, Prenom , Nombre

FROM Genealogie . Personnes ,
( SELECT Femme AS Humain , Count ( ∗ ) AS Nombre
FROM G e n e a l o g i e . M a r i a g e s
GROUP BY Femme
HAVING Count ( ∗ ) > 4
UNION
SELECT Mari AS Humain , Count ( ∗ ) AS Nombre
FROM G e n e a l o g i e . M a r i a g e s
GROUP BY Mari
HAVING Count ( ∗ ) > 4
) AS R e c i d i v i s t e
WHERE P e r s o n n e s . I d = R e c i d i v i s t e . Humain ;

Question 1.9 (1 point) Lister les problèmes posés par la fusion des relations Personnes et Parents en une
seule relation qui contiendrait l'union des attributs.

Réponse :
C'est le problème de l'oeuf et de la poule. On ne peut pas ajouter une personne sans connaître ses parents.
Une solution consiste à accepter des attributs à valeurs indénies. Deux inconvénients : on sort du cadre rela-
tionnel, et les contraintes d'intégrité sont très diciles à écrire.

Question 1.10 (1,5 point) Une personne propose de scinder la relations Personnes en deux relations Hommes
et Femmes ayant les mêmes listes d'attributs (Id, Nom, Prenom, DateNaissance, DateDeces) . Donnez les
avantages et les inconvénients de ce nouveau schéma par rapport au précédent.

Réponse :
Avantages : Certaines contraintes s'écrivent plus facilement car il n'est pas nécessaire de faire les tests sur le
sexe d'une personne.
Inconvénients : Un homme et une femme peuvent avoir les mêmes identiants, ce qui demande d'ajouter
un attribut (lequel ?) dans la table parents qui n'est plus une relation, car il n'y a plus de clefs candidate
possible. Une solution consiste à imposer que les identiants soient diérents (positifs pour les uns et
négatifs pour les autres, ou bien pairs et impairs), ce qui revient à encoder l'information du sexe. Une
autre solution consiste à faire deux relations parents : parents des garçons et parents des lles. Les requêtes
deviennent compliquées à écrire.

Exercice 2 (Normalisation (7 points))

Soit la relation Concerts (Salle, Categorie, NbPlaces, Jour, Orchestre, TypeMusique, Soliste) , vi-
sion simpliée d'une gestion de concerts, et un ensemble irréductible de dépendances fonctionnelles :
 {Salle} −→ {Categorie} : une salle détermine sa catégorie.
 {Categorie} −→ {NbPlaces} : la catégorie d'une salle détermine son nombre de places.
 {Soliste} −→ {TypeMusique} : un soliste ne joue que d'un seul type de musique.
 {Salle, Jour} −→ {Orchestre} : par jour, une salle n'est occupée que par un seul orchestre.
 {Salle, Jour} −→ {Soliste} : par jour, une salle n'est occupée que par un seul soliste.
 {Orchestre, TypeMusique } −→ {Soliste} : pour chaque type de musique, un orchestre possède son soliste.
 {Orchestre, Jour} −→ {Salle} : un orchestre ne joue pas dans deux salles diérentes le même jour.
 {Soliste, Jour} −→ {Salle} : un soliste ne joue pas dans deux salles diérentes le même jour.
Salle Categorie NbPlaces Jour Orchestre TypeMusique Soliste
Playel Theatre 1000 27-03-2008 Velvet Rock Lou Reed
Parc des Princes stade 40000 26-03-2008 E Street Band Rock Bruce Springsteen

5/ 7
INF 159 : Bases de données Session 1, Année 2010/2011

Question 2.1 (1 point) Donnez toutes les clefs candidates de la relation Concerts.

Réponse : Les dépendances fonctionnelles donnent :

 C1 = {Salle, Jour}
 C2 = {Soliste, Jour}
 C3 = {Orchestre, Jour}

Question 2.2 (1 point) Même si l'on suppose qu'il n'y a aucun doublon dans Concerts, justiez pourquoi la
relation Concerts n'est pas en troisième forme normale.

Réponse : Une seule des explications suivantes est susante (liste non exhaustive).
Non 2NF : La clef {Salle, Jour} contient {Salle} qui détermine {Categorie}.
Non 3NF : La clef {Salle, Jour} et {Categorie} −→ {NbPlaces}.
Non 3NF : La clef {Salle, Jour} et {Soliste} −→ {TypeMusique}.

Question 2.3 (2 points) Appliquez un algorithme (ou une technique) de normalisation pour obtenir une dé-
composition, sans perte d'information, de la relation Concerts en un ensemble de relations au moins en troi-
sième forme normale. Vous n'écrirez sur la copie que les nouvelles relations et les dépendances fonctionnelles
qui sont à la base des projections eectuées.

Réponse : Décomposition en BCNF :

1. Categories (Categorie, NbPlaces) qui provient de {Categorie} −→ {NbPlaces} (BCNF)
2. Salles (Salle, Categorie) qui provient de {Salle} −→ {Categorie} (BCNF)
3. Solistes (Soliste, TypeMusique) qui provient de {Soliste} −→ {TypeMusique} (BCNF) mais la
dépendance {Orchestre, TypeMusique } −→ {Soliste} devient une contrainte inter relations.
4. JoursConcerts (Salle, Jour, Orchestre, Soliste) (BCNF)
Décomposition en 3NF :
1. Categories (Categorie, NbPlaces) qui provient de {Categorie} −→ {NbPlaces} (BCNF)
2. Salles (Salle, Categorie) qui provient de {Salle} −→ {Categorie} (BCNF)
3. JoursConcerts (Salle, Jour, Orchestre, Soliste) qui provient de {Salle, Jour} −→ {Orchestre, Soliste}
(BCNF)
4. TypesConcerts (Orchestre, TypeMusique, Soliste) qui provient de {Orchestre, TypeMusique } −→
{Soliste} et qui contient {Soliste} −→ {TypeMusique}. (3NF et non BCNF)

Question 2.4 (3 points) Après avoir précisé si votre décomposition est en BCNF ou bien seulement en 3NF,
répondez aux questions qui vous concernent.
Votre décomposition est en BCNF :
1. Indiquez la dépendance fonctionnelle que vous avez perdue.
2. En supposant que cette dépendance ne soit pas écrite sous forme d'une contrainte, donnez un ensemble
de requêtes d'insertion pour vos relations, qui viole cette dépendance fonctionnelle.
Votre décomposition est seulement en 3NF :
1. Indiquez le problème de redondance qui subsiste.
2. Donnez un ensemble de requêtes d'insertion pour vos relations, suivi d'une requête de mise à jour
qui nécessite que le SGBD modie eventuellement plusieurs tuples, du fait de la redondance.

Réponse :
Décomposition en BCNF :
1. {Orchestre, TypeMusique } −→ {Soliste}.
2. Les insertions suivantes sont possibles :
INSERT INTO S o l i s t e s VALUES ( s1 , t1 ) ;
INSERT INTO S o l i s t e s VALUES ( s2 , t1 ) ;
INSERT INTO J o u r s C o n c e r t s VALUES ( s a l l e 1 , ' 01 − 01 − 2011 ' , o r c 1 , s 1 ) ;
INSERT INTO J o u r s C o n c e r t s VALUES ( s a l l e 1 , ' 02 − 01 − 2011 ' , o r c 1 , s 2 ) ;

Votre décomposition est seulement en 3NF :

1. L'information (Soliste, TypeMusique) est dupliquée.

6/ 7
INF 159 : Bases de données Session 1, Année 2010/2011

2. La mise à jour suivante modie plusieurs tuples.

INSERT INTO T y p e s C o n c e r t s VALUES ( o r c 1 , t1 , s 1 ) ;
INSERT INTO T y p e s C o n c e r t s VALUES ( o r c 2 , t1 , s 1 ) ;
UPDATE T y p e s C o n c e r t s SET ( TypeMusique = t 2 ) WHERE S o l i s t e = s 1 ;

Exercice 3 (Reprise après une panne (4 points))

Nous supposons que le SGBD écrit dans un journal le début, les opérations et la n de chaque transaction, et que
chaque écriture est aussitôt sauvegardée sur disque. Nous supposons également que le SGBD utilise la technique
des points de synchronisation : à intervalles réguliers le SGBD écrit dans le journal la liste des transactions en
cours, puis aussitôt sauvegarde le journal et la base de données sur le disque dur.
Soit pc le dernier point de synchronisation réalisé à une date tc, et une panne du SGDB à la date tf > tc.

Question 3.1 (1 point) Donner les objectifs de l'algorithme de reprise après la panne.

Réponse : L'objectif principal est la reprise du service. Cette reprise doit pénaliser le moins possible les ap-
plications clientes. Elle doit donc remettre la base dans un état cohérent vis à vis de l'information connue des
clients, ainsi :
 Un client ne doit pas avoir à refaire une transaction terminée avant la panne.
 Un client doit avoir à refaire une transaction non terminée avant la panne.

Question 3.2 (3 points) Donner l'algorithme de reprise après la panne.

Réponse : (cf pages 53 et 54 du polycopie)

7/ 7