Loading ...
Global Do...
News & Politics
4
0
Try Now
Log In
Pricing
NUMÉRO D’ANONYMAT: Université Bordeaux 1 — Master d’informatique UE Bases de Données INF 305 (Clément/Retoré) Examen du vendredi 16 décembre 2005, 8h30–10h Pour les deux premiers exercices, on considère la de données base ”avions” utilisée en TD: PILOTE (NUMPIL, NOMPIL, ADR, SAL) AVION (NUMAV, NOMAV, CAPACITE, LOC) VOL (NUMVOL, NUMPIL, NUMAV, VILLE_DEP, VILLE_ARR, H_DEP, H_ARR) NUMPIL: clé de PILOTE, nombre entier NOMPIL: nom du pilote, chaı̂ne de caractères ADR: ville de la résidence du pilote, chaı̂ne de caractères SAL: salaire du pilote, nombre entier NUMAV: clé de AVION, nombre entier CAPACITE: nombre de places d’un avion, nombre entier LOC: ville de l’aéroport d’attache de l’avion, chaı̂ne de caractères NUMVOL: clé de VOL, nombre entier VILLE_DEP: ville de départ du vol, chaı̂ne de caractères VILLE_ARR: ville d’arrivée du vol, chaı̂ne de caractères H_DEP: heure de départ du vol, nombre entier entre 0 et 23 H_ARR: heure d’arrivée du vol, nombre entier entre 0 et 23 Exercice A Requêtes en SQL (A.i) Quels sont les avions (NUMAV,NOM) localisés à Nice? (A.ii) Quels sont les pilotes (NUMPIL,NOMPIL) ne conduisant que des avions localisés à Nice? 1 (A.iii) Quels sont les pilotes (NUMPIL,NOMPIL) conduisant tous les avions localisés à Nice? (A.iv) Quelle est la moyenne des heures de départ des vols effectuant un trajet donné (VILLE DEP, VILLE ARR,TEMPS MOYEN)? (A.v) Quels sont les pilotes toulousains (NOM,SAL) les mieux payés? Exercice B Requêtes en Datalog (B.i) Quelles sont les villes accessibles depuis Bordeaux sans jamais prendre un vol conduit par un pilote nommé Skywalker. 2 (B.ii) Quelles sont les villes accessibles depuis Bordeaux en empruntant au plus un vol conduit par un pilote nommé Skywalker. (B.iii) Quels sont les pilotes (NUMPIL) conduisant tous les avions? Exercice C Conception de schémas relationnels On décompose R(A,B,C,D) muni des dépendances fonctionnelles A→ B et C → D en S(A,B) et T (C,D). (C.i) Les dépendances fonctionnelles sont elle préservées? (C.ii) Y a-t-il perte d’information? Si oui donner un exemple de table R, ses projections πA,BR et πC,DR, leur jointure πA,BR ⊲⊳ πC,DR ainsi qu’un n-uplet ~u tel que ~u ∈ (πA,BR ⊲⊳ πC,DR) et ~u 6∈ R. 3 Exercice D Conception de schémas relationnels (D.i) Donner un exemple de schéma qui soit 3NF mais pas BCNF, en expliquant pourquoi le schéma est 3NF et pourquoi il n’est pas BCNF. (D.ii) Pourquoi est-il parfois préférable d’utiliser un schéma en 3NF plutôt qu’un schéma BCNF? 4 Exercice E Conception de schémas relationnels (E.i) Qu’est-ce qu’une dépendance fonctionnelle non-triviale? (E.ii) On suppose qu’on a a la dépendance fonctionnelle X → Y . Montrer que si X n’est pas une clé, alors Y n’est pas une clé non plus. (On pourra montrer la contraposée: Si Y est une clé, alors X est aussi une clé.) (E.iii) Soit F un ensemble de dépendances fonctionnelles avec un seul attribut à droite. On considère la propriété P: si une dépendance fonctionnelle X → A qui est une conséquence de F (c.-à-d. X → A ∈ Cl(F)) empêche un schéma relationnel R d’être en BCNF alors il existe une dépendance fonctionnelle Y → B de F qui empêche R d’être en BCNF. (E.iv) Que signifie la propriété P? (E.v) Démontrer la propriété P. (Indication: on pourra procéder par récurrence sur le nom- bre d’axiomes d’Armstrong utilisés pour dériver X → A ∈ Cl(F).) 5 6 Exercice F Table de hachage 1. Quelles doivent être les propriétés d’une fonction de hachage ? 2. Proposer une fonction de hachage portant sur des clefs de type chaı̂ne de caractères pour une table de 101 blocs Exercice G B-Tree 1. Quelles sont les propriétés qu’un B-Arbre de rang k doit respecter pour être bien-formé ? 2. Quel est le nombre maximal de clefs que peut contenir un B-Tree de rang k et dont le niveau est N ? 3. Soit le B-Tree I de rang 3 suivant : 5 11 17 2 3 N2 N3 5 8 N5 N8 11 13 N11 N13 17 19 23 N17 N19 N23 NIL 7 (a) Ajouter l’information (4,N4), où 4 est la clef et N4 l’enregistrement correspondant à cette clef. (b) Sur le nouveau B-Tree obtenu, ajouter l’information (7,N7) (c) Sur le nouveau B-Tree obtenu, ajouter l’information (18,N18) (d) Supprimer du B-Tree original I l’information (8,N8) 8
