:: Enseignements :: Licence :: L3 :: 2008-2009 :: Bases de données ::

---

Conception et intégrité

---

Le but de cette série d'exercices est d'apprendre à construire un Schéma Relationnel (SR) sans redondances de données, n'entraînant pas d'anomalies lors des opérations de mise à jour.

---

Exercice 1 - Introduction aux dépendances fonctionnelles

Exercice 2 - Equivalences d'ensembles de dépendances fonctionnelles

1. Soit R (A, B, C) un schéma de relations, et soit F = {A B --> C} un ensemble de dépendances fonctionnelles pour R. Prouver que : F = {A B --> C} |= AB --> BC en utilisant :
   • Les axiomes de dérivation des dépendances fonctionnelles
   • La notion de fermeture d'un constituant
    
2. Soit R (A, B, C, D, E, J) un schéma relationnel, muni de F= {A-->B, BC-->D, BDE-->J}. Pouvez- vous affirmer que : ACE --> J dérive de F ? Justifier votre affirmation. 
3. Soit R (A, B, C, D, E), muni de l'ensemble F = {A --> B, BC --> D, DE --> A, E --> D}. Pouvez- vous affirmer que CE --> A dérive de F ? Justifier votre affirmation.
4. Soit R (A, B, C, D, E, G) un schéma de relations. Soit F= {A B --> C, C --> A, B C --> D, A C D --> B, D -->E G, B E --> C, C G --> BD, C E --> A G} un ensemble de dépendances fonctionnelles pour R.
   • Indiquer l'ensemble des constituants de R.
   • Calculer (CE) + = Fermeture (CE, F)
   • Si (CE) + = {Y1, Y2, ..., Yn}, prouver, en utilisant les axiomes de dérivation des dépendances fonctionnelles, que F |= CE --> Yi
   • Calculer C+ = Fermeture (C, F).
5. Soit le schéma R (P, M, C, S, J, H), régissant les emplois du temps dans un lycée, et r, une relation de schéma R. Un tuple t (p, m, c, s, j, h) de r représente que : le prof p enseigne la matière m à la classe c dans la salle s à l'heure h du jour j. Soit F = {P --> M, PHJ --> C, HJS --> P, HJC --> S} un ensemble de dépendances fonctionnelles pour R.
   En utilisant la notion de fermeture, montrer que F n'est pas équivalent à G = F - {HJC-->S}
6. Pour un schéma R (A, B, C, D), les deux ensembles de dépendances fonctionnelles F = {AD --> B, A--> C} et G = {A--> B, AD --> C} sont-ils équivalents ?
7. Pour un schéma R (A, B, C), les deux ensembles de dépendances fonctionnelles F = {AB --> C, A--> B} et G = {B --> C, A--> B} ne sont pas équivalents.
   Trouver une relation r de schéma R qui vérifie F et qui ne vérifie pas G.
8. Soit R (A, B, C, D, E) un schéma et F et G deux ensembles de dépendances fonctionnelles sur R, avec :
   F = {AC --> D, E --> DA, C --> ED} et G = {A --> D, E --> DA, C --> E}.
   • Quand deux ensembles de dépendances fonctionnelles sont- ils équivalents ?
   • F et G sont-ils équivalents ? Si ils ne sont pas équivalents, donner une relation r de schéma R qui vérifie un des deux ensembles de dépendances fonctionnelles et pas l'autre.
   • Donner la clé (ou les clés) de R muni de l'ensemble des dépendances fonctionnelles F.

Exercice 3 - Couverture minimale

1. Soit R (TITRE, DATE, MS, FEST, PRIX, ACT, NAT) un schéma relationnel et F = {TITRE --> (DATE, MS), (TITRE, FEST) --> PRIX, ACT --> NAT} un ensemble de dépendances fonctionnelles pour R. Si r est une relation de schéma R, et u(t, d, m, f, p, a, n) est un tuple de r, alors : le film de titre t, sorti à la date d, du metteur en scène m, a obtenu, au festival f, le prix p, pour l'acteur a, de nationalité n.
   Trouver une couverture minimale pour F. 
2. Soit R (A, B, C) un schéma de relation, et soit F = {AB --> C, A--> B} un ensemble de dépendances fonctionnelles pour R. Calculer une couverture minimale de F
3. Soit R (A, B, C, D) un schéma relationnel muni de
   F = {A --> CD, BC --> D, B --> A}.
   
   Quelle est une couverture minimale de F ?

Exercice 4 - Décompositions de schémas relationnels, sans perte d'informations

1. Le schéma relationnel R (Agence, Prêt, Montant, Client, Compte, Solde), muni de l'ensemble
   F = {Prêt -->Montant, Prêt -->Agence, Compte --> Solde}, représente les agences, avec les clients, leurs comptes, de solde Solde, et leurs prêts, de montant Montant.
   
   Quels sont les inconvénients de ce schéma ? 
2. Soit CRÉDIT (Agence, Prêt, Client, Montant) un schéma relationnel, représentant qu'un dossier de prêt Prêt a été ouvert à l'agence Agence ; le montant de ce prêt est Montant et le bénéficiaire est Client. Soit F = {Prêt ---> (Agence, Client, Montant)} un ensemble de dépendances fonctionnelles pour CRÉDIT. Soit r une relation de schéma CRÉDIT, vérifiant l'ensemble de ces dépendances fonctionnelles.

   r	Agence	Prêt	Client	Montant
   	a1	p1	c1	10
   	a2	p2	c2	20
   	a1	p3	c3	10

   • Vérifier sur r que la décomposition de CRÉDIT avec : CM (Client, Montant), APM (Agence, Prêt, Montant) est avec perte.
   • Vérifier sur r que la décomposition de CRÉDIT avec : AP (Agence, Prêt) et PCM (Prêt, Client, Montant) est sans perte.
3. Le schéma CRÉDIT a les dépendances fonctionnelles suivantes :
   F = {Prêt ---> Client, Prêt ---> Agence, Prêt ---> Montant}
   
   Prouver par rapport à F
   • que la décomposition AP (Agence, Prêt) et PCM (Prêt, Client, Montant) est sans perte
   • que la décomposition CM (Client, Montant), APM (Agence, Prêt, Montant) est avec perte
   En utilisant :
   • L'algorithme de test de décomposition sans perte (basé sur les tableaux).
   • Le théorème donnant des conditions de décomposition sans perte.
4. Soit le schéma relationnel R (Film, Festival, Metteur en scène), représentant des films ayant obtenu des premiers prix à des festivals. Les dépendances fonctionnelles de R sont :
   F = {Film ---> Metteur en scène, Festival --->Film}
   • La décomposition R1, R2, avec R1 = (Festival, Film) et R2 = (Film, Metteur en scène) est-elle sans perte ?
   • La décomposition R1, R2, avec R1 = (Festival, Metteur en Scène) et R2 = (Film, Metteur en scène) est-elle sans perte ?
5. Donner une décomposition sans perte du schéma R (Cours, Étudiant, Note, Prof), muni de
   F = {(Cours, Étudiant) ---> Note, Cours --->Prof}

Exercice 5 - Formes normales

1. Le schéma relationnel LIVRE (titre, auteurs, date, mots-clés) est-il en 1ère Forme Normale ? Si non, le transformer en schéma en 1ère Forme Normale.

   Exemple	Titre	Auteurs	Année	Mots-clés
   	Systèmes de Gestion de Bases de Données	{Korth, Silberschatz}	1991	{informatique, bases de données}
   	Algorithmes et structures de données	Wirth	1989	{informatique, structures de données, indexation}

2. On considère les schémas relationnels PERSONNE (n°SS, nom, prénoms, numéros-téléphone) et EMPLOYÉ (n°employé, date-embauche, projets). Ces schémas sont-ils en 1ère Forme Normale ? Si non, comment les transformer en schémas qui soient en 1ère Forme Normale ?
3. Le schéma relationnel Client-Compte-Agence (client, compte, agence, s, cladr, agadr) indique que le client numéro client, habitant à l'adresse cladr, a, auprès de l'agence agence, située à l'adresse agadr, un compte compte, de solde s. Par rapport à F = {compte ---> s, client ---> cladr, agence ---> agadr}, ce schéma est- il en 2ème Forme Normale ? Si non, le transformer en schémas en 2ème Forme Normale. 
4. On considère le schéma relationnel CV (n°SS, nom, entreprise, date-embauche) muni de F = {n°SS --> nom, (n°SS, entreprise) --> date-embauche}. Quelles sont les anomalies de ce schéma ? Est-il en 2ème Forme Normale ? Si non, le décomposer en schémas qui soient en 2ème Forme Normale.
5. Le schéma Dossier-Credit (agence, prêt, montant, client, compte, s) indique que le dossier de prêt numéro prêt, pour un certain montant, est ouvert auprès de l'agence agence ; un numéro de bénéficiaire est client. Ce bénéficiaire rembourse le prêt avec un compte de numéro compte, de solde s. Un ensemble de dépendances fonctionnelles est : F = {prêt ---> montant, prêt ---> agence, compte ---> s, compte ---> agence}
   • Quelle est la clé de ce schéma ? L'attribut Prêt constitue une clé pour ce schéma ?
   • Ce schéma est en 3ème Forme Normale par rapport à F ? En quelle forme normale sont les schémas suivants ?
     • Prêt (agence, prêt, montant) avec F1 = {prêt -->montant, prêt -->agence}
     • Compte-Solde (compte, s) avec F2 = {compte --> s}
     • Compte-Agence (compte, agence) avec F3 = {compte --> agence}
     • Prêt-Client-Compte (prêt, client, compte) avec F4 = Ø
6. R (n°employé, spécialisation, prime) est un schéma relationnel muni de l'ensemble des dépendances fonctionnelles :
   F = {n°employé --> spécialisation, n°employé --> prime, spécialisation --> prime}
   
   Quelles sont les anomalies de ce schéma ? Est-il en 2ème Forme Normale ? Et en 3ème Forme Normale ?

   Exemple de relation r de schéma R	n°employé	spécialisation	prime
   	1235	électricité	3,5%
   	1412	plomberie	3%
   	1311	électricité	3,5%
   	1270	menuiserie	3,5%

7. On considère le schéma relationnel Voiture (nv, marque, type, puissance, couleur) muni de l’ensemble : F = {nv ---> marque, nv ---> type, nv ---> puissance, nv ---> couleur, type ---> puissance}. Ce schéma est- il en 3ème Forme Normale ?
8. Dans le contexte bancaire décrit ci-dessus, considérons le schéma Crédit (agence, prêt, client, montant) avec F = {prêt ---> montant, prêt ---> agence}. Quelle est la clé de Crédit ? Ce schéma est en BCNF ?
9. Prouver que le schéma (Rue, Ville, Code) avec F = {Rue, Ville --> Code, Code -->Ville} est en 3ème Forme Normale mais pas en BCNF.

Exercice 6 - Formes normales et décompositions

1. Soit R (A, B, C, D) un schéma relationnel muni de l'ensemble des dépendances fonctionnelles : F = {A --> B, B --> C, B --> D}.
   • Ce schéma est-il en BCNF ? Si non, proposer une décomposition en sous-schémas BCNF, sans perte d'information.
   • Ce schéma est-il en 3ème Forme Normale ? Si non, proposer une décomposition en sous-schémas en 3ème Forme Normale, sans perte d'information et préservant les dépendances fonctionnelles.
2. Soit R (agence, prêt, montant, client, compte, solde), muni de
   F = {prêt-->montant, prêt-->agence, compte --> solde, compte --> agence}
   
   Est-ce R en BCNF ? Si non, le décomposer en sous-schémas en BCNF. Cette décomposition conserve les dépendances fonctionnelles ?
3. Vins (cru, pays, région) est un schéma relationnel muni de l'ensemble des dépendances fonctionnelles F = {région --> pays, (cru, pays) --> région}. Ce schéma est-il en 3ème Forme Normale ? Est-il en BCNF ?

   Exemple de	cru	pays	région
   	Chenas	France	Beaujolais
   	Juliénas	France	Beaujolais
   	Morgon	France	Beaujolais
   	Brouilly	France	Beaujolais
   	Chablis	États-Unis	Californie

   La décomposition de Vins en sous-schémas :
   Cru (cru, région)
   Région (région, pays) muni de F1 = {région --> pays}
   • Est en BCNF, sans perte d'information et préservant les dépendances fonctionnelles ?
   • Les tuples (vin1, Beaujolais) et (vin1, Bordelais) sont-ils admissibles pour une relation r de schéma Cru ?
4. Soit R (titre, date, ms, fest, prix, act, nat) un schéma relationnel, muni de l'ensemble des dépendances fonctionnelles F= {titre-->date, titre--> ms, (titre, fest) --> prix, act --> nat}. R est-il en 3ème Forme Normale ? Si non, décomposer R en 3ème Forme Normale, sans perte d'information et en préservant les dépendances fonctionnelles.
5. Soit R (A, B, C, D) un schéma relationnel muni de F = {AB --> C, C --> A, B --> D}. R est-il en 3ème Forme Normale ? Si non, donner une décomposition préservant les dépendances fonctionnelles et sans perte d'information.
6. Soit donné le schéma relationnel : R (N°Contrat, N°Matériel, NomMatériel, N°Client, NomClient, CoûtAnnuel, N°Vend, NomVend)
   Muni de l'ensemble de dépendances fonctionnelles : F = {N°Contrat --> (N°Client, CoûtAnnuel), N°Client --> NomClient, N°Vend --> NomVend, N°Matériel --> NomMatériel, N°Contrat --> (N°Vend, NomVend)}.
   
   Un tuple de valeurs (nco, nmat, nommat, ncl, nomcl, ca, nv, nomv) indique que le contrat d'assurance numéro nco couvre le matériel numéro nmat, dont le nom est nommat. Ce contrat a été stipulé entre le client de numéro ncl et nom nomcl et le vendeur de numéro nv et nom nomv. Le coût annuel de l'assurance est ca.
   • Cette relation est-elle en forme normale ? Laquelle ?
   • Donner une décomposition en 3ème Forme Normale de ce schéma, qui conserve les dépendances fonctionnelles et soit sans perte d'information.
7. Soit S (J, K, L) un schéma relationnel, avec F = {J K --> L, L -->K}.
   • Indiquer toutes les clés de S.
   • Est-ce S en BCNF ? Si non, donner une décomposition en BCNF, sans perte d'information.
   • Cette décomposition préserve-t-elle les dépendances fonctionnelles ?
8. Pour suivre les élections présidentielles et les scores des candidats, par département, on a conçu le schéma relationnel suivant :
   Élection (n°c, nom_c, prénom_c, n°f, nom_f, n°dept, nom_dept, score)
   Avec :
   • n°c, nom_c, prénom_c numéro, nom et prénom d'un candidat
   • n°f, nom_f numéro et nom d'une formation politique
   • n°dept, nom_dept numéro et nom d'un département
   • score nombre de voix obtenus par le candidat sur le département.
   [Convention : Parmi les formations politiques, on introduit une formation fictive (avec n°f = 0 et nom_f = "Indépendants") servant à attacher les candidats indépendants de toute formation politique réelle]
   
   On a trouvé sur Élection les dépendances fonctionnelles suivantes :
   F = {n°c -> (nom_c, prénom_c, n°f), n°f -> nom_f, n°dept -> nom_dept, (n°c, n°dept) -> score, nom_dept -> n°dept, (n°c, nom_dept, nom_f) -> score}
   
   Quelle est la clé de ce schéma ? Est-il en 3FN ? Si non, donner une décomposition en 3 FN, sans perte d'information.  
9. Soit donné le schéma R (n°e, grade, date, salaire, nome). Un tuple (e, g, d, s, n) d'une relation r de schéma R, représente le fait que l'employé de n° e et nom n a le grade g à la date d et perçoit le salaire s.
   Indiquer en quelle forme normale est ce schéma. S'il n'est pas en 3FN, donner une décomposition en 3FN, sans perte d'information et avec conservation des dépendances fonctionnelles.

Exercice 7 - Dépendances multivaluées

1. Pour un schéma relationnel R(X, Y, Z), qu'exprime la dépendance multivaluée
   X -->--> Y/Z, avec X, Y, Z ensembles d'attributs de R ?
   Le schéma relationnel R (Étudiant, Sport, Matière, Note) exprime une relation parmi un étudiant, les sports qu'il pratique, les examens soutenus et les notes obtenues à ces examens. Par exemple, la relation suivante est de schéma R.

   Étudiant	Sport	Matière	Note
   DUPONT	foot	Bases de Données	20
   DUPONT	tennis	Algorithmique	18
   DURANT	natation	Systèmes	19
   DUPONT	tennis	Bases de Données	20
   DUPONT	foot	Algorithmique	18

   • Les dépendances multivaluées D = {étudiant-->-->sport, étudiant-->--> (matière, note)} sont admissibles pour R ?
   • Est-ce ce schéma en 4ème Forme Normale ?
2. Quelles sont les dépendances (fonctionnelles et multivaluées) pour le schéma
   R1 (Personne, Compte, Localité), exprimant qu'une personne possède un compte bancaire et a une habitation dans une localité.
   • R1 est en 4ème Forme Normale ?
   • Mêmes questions pour R2 (Personne, PEL, resprinc), décrivant les clients de la banque ayant un Plan Épargne Logement. Pour ces personnes ont connaît leur résidence principale.
3. On considère le schéma relationnel R (personne, compte, solde, activité). Si r est une relation de schéma R, alors un tuple t (p, c, s, a) de r signifie que : « La personne p possède un compte bancaire numéro c, de solde s, et exerce une activité codée a ».
   Quelles sont les dépendances fonctionnelles et multivaluées de R ?

   ? personne --> compte personne --> solde personne --> activité compte --> solde compte --> activité compte --> personne

   ? solde --> personne solde --> compte solde --> activité activité--> personne activité--> compte activité--> solde

   ? personne -->--> compte personne -->--> (activité, solde) personne -->--> activité personne -->--> (compte, solde) personne -->--> solde personne -->--> (activité, compte)

   Si dans r existent les tuples :
   • t1 (p1, c1, s1, a1)
   • t2 (p1, c2, s2, a2)
   • t3 (p2, c3, s3, a3)
   Quelles autres tuples existent également dans r ?
4. Soit le schéma : Zoos (Nzoo, Nespèce, Quantité, Jour), pour représenter des grands parcs animaliers, contenant plusieurs espèces d'animaux. Un tuple t (nz, nesp, qté, j) est dans la relation Zoos, si le zoo numéro nz possède l'espèce numéro nesp en quantité qté et il est ouvert le jour j de la semaine.
   Indiquer, parmi les dépendances fonctionnelles et multivaluées suivantes, lesquelles sont valables sur Zoos, et pourquoi. Quelle est la clé de Zoos ?
   • a) Nzoo --> Nespèce
   • b) Nzoo --> Quantité
   • c) Nzoo --> Jour
   • d) Nespèce --> Nzoo
   • e) Nzoo -->-> Nespèce
   • f) Nzoo -->--> Jour
   • g) (Nzoo, Nespèce) --> Quantité
   • h) (Nzoo, Quantité) --> Nespèce
   • i) Nzoo -->--> (Nespèce, Quantité)

---