Exam1_corriges.pdf

Loading ...
Global Do...
News & Politics
INF7115 BASES DE DONNEES 
EXAMEN 
Automne 2000 
 
B. Kerhervé, 6 Novembre 2000 
 
 
PARTIE 1 : QUESTIONS DE COURS 
 
Répondez par vrai ou faux aux affirmations suivantes : 
 
Question 1)  
- La vérification des contraintes d’intégrité ensemblistes doit se faire en utilisant le mécanisme de 
triggers . 
VRAI 
 
Question 2)  
-  Dans l’optimisation de requêtes, un système de gestion de bases de données (SGBD) relationnel 
réalise la phase d’ordonnancement des jointures afin d’introduire des projections supplémentaires dans 
l’exécution de la requête. 
FAUX 
 
Question 3)  
-  Le concept d’identifiant d’objet n’existe pas dans les systèmes de gestion de bases de données (SGBD) 
relationnels-objet. 
FAUX 
 
PARTIE 2 : EXERCICES 
Exercice 1 : Intégrité sémantique  
 
Soit la base de données relationnelle suivante, modélisant les employés et les départements d’une 
compagnie québécoise  (les clés des relations sont soulignées): 
 
EMPLOYÉ  
(NumEmp, Nom, Prénom, Date-Naissance, Grade, Salaire) 
où l'attribut Grade représente le grade de l’employé et peut prendre les valeurs: 1, 2, 3 ou 4, et où 
l’attribut Salaire représente le salaire annuel de l’employé. 
SERVICE  
(NumService, NomServ, Directeur, Secrétaire) 
où Directeur est le numéro d’employé du directeur, et secrétaire le numéro d’employé de la 
secrétaire de direction du service.   
AFFECTATION  (NumEmp, NumService, DateDebAffect, DateFinAffect,TypeAffect) 
modélisant les affectations des employés dans des services. DateDebAffect représente la date de 
début de l’affectation, DateFinAffect, la date de fin de l’affectation et TypeAffect le type 
d’affectation représentée par un entier compris entre 0 et 100 correspondant au pourcentage de 
temps de l’employé dans ce service . 
 
Question 4)  
Sur ces 3 relations des contraintes de domaine et des contraintes référentielles doivent être définies. Pour 
chaque relation listez ces différentes contraintes, vous les exprimerez en français. 
Table EMPLOYE 
Contrainte de domaine : Grade IN {1,2,3,4} 
Table SERVICE 
Contrainte référentielle : Directeur référence NumEmp de la relation 
Employé, Secrétaire référence NumEmp de Employé 
Table AFFECTATION 
Contrainte de domaine sur l’attribut TypeAffect (entier compris entre 0 
et 100) 
Contrainte référentielle avec NumEmp de la table Employé 
Contrainte référentielle avec NumService de la table Service 
Contrainte de domaine sur DateFinAffect qui doit être >= à 
DateDebAffect 
 
Question 5)  
Nous souhaitons définir une nouvelle contrainte sur cette base de données qui stipule que 
 
la durée d’affectation d’un employé dans un service ne peut être inférieure à deux semaines. 
 
Comment pouvez-vous exprimer cette contrainte ? Quelles hypothèses devez-vous faire ? 
 
Table AFFECTATION 
Contrainte de plage de valeur exprimée sur la différence entre les 
valeurs des attributs DateDebAffect et DateFinAffect. 
DateFinAffect – DateDebAffect >= 12. On fait l’hypothèse que la date de 
début de l’affectation est un lundi et la date de fin d’affectation est un 
vendredi.  
 
Exercice 2 : Optimisation de requêtes 
 
Sur la base de données suivante: 
PERSONNE  
(NumPer, Nom, Prénom, Age) 
 
décrivant des personnes en donnant leur numéro, nom, prénom et âge 
COSTUME  
(NumCostume, NomCostume, Taille) 
 
décrivant des costumes d’Halloween à louer, en donnant leur numéro, leur nom, et la taille qui  
 
peut prendre les valeurs :  4-6, 8-10, 12-14, S, M, L 
LOCATION  
(NumCostume, NumPer, DateLocation, DuréeLocation) 
 
Nous voulons exprimer la requête suivante : 
Rechercher le nom et le prénom des personnes de plus de 50 ans qui ont loué un costume de  
Batman (nom du costume) au mois d’octobre 2000 
 
Question 6)  
Proposez un premier arbre d’opérateurs de l’algèbre relationnelle pour l’exécution de cette requête. 
Arbre simple avec les restrictions et les jointures minimales 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
NomCostume=
« Batman »
C
Nom
W
P
L
Age>50
P.NumPer = L.NumPer
L.NumCostume=C.NumCostume
Date>=1-10-2000
And
Date <= 31-10-2000
 
 
 
 
Question 7)  
Vous devez maintenant améliorer cet arbre d’opérateurs. 
Proposez des améliorations : 
 
1) en ajoutant des projections ; 
 
2) en proposant un ordre d’exécution des jointures ; 
 
3) en choisissant une stratégie d’exécution pour chacun des opérateurs. 
Vous listerez chacune des améliorations et pour les  points 2) et 3) vous formulerez vos propres 
hypothèse sur la taille des relations, les coefficients de sélectivité et l’existence d’organisations 
physiques. 
Hypothèse : le nombre de costumes de Batman est inférieur au nombre de 
personnes de plus de 50 ans 
Des projections sont ajoutées pour éliminer les attributs inutiles 
On peut utiliser différentes stratégies d’exécution pour les opérateurs. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Exercice 3 : Bases de données actives 
 
Nous utilisons à nouveau la base de données: 
PERSONNE  
(NumPer, Nom, Prénom, Age) 
COSTUME  
(NumCostume, NomCostume, Taille) 
LOCATION  
(NumCostume, NumPer, DateLocation, DuréeLocation) 
 
Nous souhaitons formuler la contrainte d’intégrité suivante : ‘la durée moyenne de location des costumes 
ne peut excéder 30 jours ’. 
 
Question 8)  
Définissez le ou les triggers nécessaires pour contrôler cette contrainte d’intégrité. Vous définirez 
obligatoirement les triggers sous la forme (Evènement, Condition, Action). 
 
NomCostume=
« Batman »
C
Nom
W
P
L
L.NumCostume=C.NumCostume
Date>=1-10-2000
And
Date <= 31-10-2000
NumCostume
NumPer, Nom
P.NumPer = L.NumPer
NumCostume,
NumPer
NumPer
 Evénement : après Insertion dans Location 
 Condition :  
 Action : si (Moyenne (DuréeLocation) <= 30) 
  
    Accepter la mise à jour 
  
    Sinon rejeter la mise à jour 
 
 Evénement : après Suppression dans Location 
 Condition :  
 Action : si (Moyenne (DuréeLocation) <= 30) 
  
    Accepter la mise à jour 
  
    Sinon rejeter la mise à jour 
 
 Evénement : après Modification (DuréeLocation) dans Location 
 Condition :  
 Action : si (Moyenne (DuréeLocation) <= 30) 
  
    Accepter la mise à jour 
  
    Sinon rejeter la mise à jour 
  
 
 
Question 9)  
Cette contrainte d’intégrité est-elle coûteuse à vérifier ? Expliquez pourquoi.  
Y a-t-il un moyen de réduire les coûts de vérification ? Proposez une solution. 
 
Oui cette contrainte est coûteuse à vérifier car à chaque requête de mise 
à jour, il faut recalculer la moyenne de la durée des locations. Pour 
éviter ce recalcul, on peut utilir une vue concrête de schéma (Nb-
Locations, DuréeMoyenne) qui conserve la durée moyenne des locations. 
Il suffit alors de calculer la nouvelle durée moyenne à partir de cette 
relation (un seul tuple) sans avoir à tout recalculer. 
 
Exercice 4 : Bases de données déductives 
 
Nous utilisons le langage Datalog pour la définition et la manipulation de bases de données déductives.  
Soit la base de données suivante: 
LIEN (NoLien, VilleUn, VilleDeux, NoRoute, Distance) 
Cette table décrit les liens directs entre deux villes avec la distance les séparant et le numéro 
de la route qui les relie. 
On notera que les liens sont orientés, une route entre deux villes sera donc représentée par deux  
liens (un dans chaque sens : Montréal-Sherbrooke et Sherbrooke-Montréal). 
Question 10)  
En utilisant le langage DATALOG, donnez quelques axiomes correspondant à des instanciations de la 
relation Lien.   
LIEN (34, Montréal, Sherbrooke, 10, 115) <-- 
LIEN (35, Sherbrooke, Montréal, 10, 117) <-- 
  
Question 11)  
Exprimez les requêtes d'interrogation suivantes à l'aide d'un programme de règles DATALOG  
 
Quel est le numéro de la route reliant directement Montréal à Sherbrooke ? 
R(x) <--LIEN (-, Montréal, Sherbrooke, x, -) 
 
 
Quelles sont les villes situées à une distance de 50 km de Montréal par une route directe ? 
R(x) <--LIEN (-, Montréal, x, -, 50) 
R(x) <--LIEN (-, x, Montréal, -, 50) 
Question 12)   
Nous aimerions maintenant construire une table CHEMIN (VilleDépart, Ville Arrivée) qui nous permet 
de représenter le fait qu’il y a un chemin entre deux villes, même si ce n’est pas une route directe.   
Donnez le programme de règles DATALOG permettant de définir la relation CHEMIN. 
CHEMIN(x, y)  <-- LIEN (-, x, y, -, -) 
CHEMIN(x, z)  <-- CHEMIN(x, y)  AND LIEN (-, y, z, -, -) 
 
 
BAREME INDICATIF 
 
Le système de notation adopté est une note sur 20 points. Il y a donc 1 point de bonus…  
Partie 1 : au total 3  points: 
chaque question sur 1 point 
 
 
Partie 2 : au total 18 points 
exercice 1 : 4 points (  
question 4 : 2 pts  
question 5 : 2 pts) 
exercice 2 : 4  points ( 
question 6 : 2 pts  
question 7 : 2 pts) 
exercice 3 : 4 points (  
question 8 : 2 pts  
question 9 : 2 pts) 
exercice 4 : 6 points (  
question 10 : 2 pts 
question 1 : 2 pts  
question 12 : 2 pts)