Fichier de rejeu Close
Indication Close
A propos de... Close
Commentaire Close
Systèmes d'Information
- Notions mathématiques
- Calcul relationnel
- Algèbre relationnelle
- Langage de requêtes
- Arbre de requêtes
- Exercices
- Introduction
- Commandes de bases
- Langage de définition de données (LDD)
- Langage de manipulation de données (LMD)
- Types de données
- Exercice
- Dépendances fonctionnelles
- Décomposition de relations
- Inférence logique
- Normalisation
- Aux pays des bières
- Modélisation
- Exercices
© Your Copyright
Aide
Dépendances Fonctionnelles
Définition
Soit le schéma relationnel \(R(X,Y,Z)\), où \((X,Y,Z)\) représente des groupes d’attributs.
Il existe une dépendance fonctionnelle (DF) entre les groupes d’attributs \((X,Y)\) notée :
- \(X \rightarrow Y\)
si et seulement si : \(\forall (x,y,y',z,z')\)
\(\left. \begin{array}{l} (x,y,z) \in R(X,Y,Z) \\ (x,y',z') \in R (X,Y,Z) \end{array} \right \rbrace \Rightarrow y = y'\)
Autrement dit :
- SI on connaît les valeurs du groupe d’attributs \(X\) ALORS on connaît celles du groupe d’attributs \(Y\).
On dit aussi que :
- les attributs \(Y\) dépendent fonctionnellement de ceux de \(X\)
- les valeurs des attributs \(X\) déterminent celles de \(Y\).
On appelle :
- source de la DF : l’ensemble des attributs \(X\) qui détermine les attributs \(Y\)
- cible de la DF : l’ensemble des attributs \(Y\) qui dépendent fonctionnellement de \(X\)
Une dépendance fonctionnelle :
- \(X \rightarrow Y\)
devra vérifier que l’expression suivante :
- \(\forall x \in X \ , \Pi_Y(\sigma_{X = x}(r))\)
ou :
- \(\forall x \in X \ , R[X=x|Y]\)
ne donnera qu’un seul élément (ensemble de valeurs du groupe d’attributs Y) correspondant à celles de l’élément \(x\) du groupe d’attributs \(X\)
Dépendance Fonctionnelle Elémentaire
Une Dépendance Fonctionnelle Elémentaire (DFE) notée :
- \(X \rightarrow A\)
est une DF où :
- \(A\) : attribut unique tel que \(A \notin X\)
- \(\nexists \; X' \subset X \; , \; X' \rightarrow A\)
Remarques sur les DFE :
- la cible (\(A\)) est un attribut unique
- la source (\(X\)) ne comporte pas d’attributs superflus
Regroupement de DFE
Lorsqu’il existe plusieurs DFE qui ont un même groupe d’attributs source on peut regrouper les attributs cible qui dépendent de la même source en une seule DF en vertu d’un des six axiomes d’Armstrong. Ces axiomes seront étudiés plus loin dans la section « Inférences logiques » :
- Additivité : \(X \rightarrow Y , X \rightarrow Z \Longrightarrow X \rightarrow YZ\)
Réciproquement, lorsqu’une DF a plusieurs attributs cibles on peut décomposer la DF en autant de DF ayant le même groupe d’attributs source avec un seul attribut cible en vertu d’un autre des six axiomes d’Armstrong :
- Décomposition : \(X \rightarrow Y , Z \subset Y \Longrightarrow X \rightarrow Z\)
Exercices
A partir de l’instance de relation \(R(A,B,C,D,E)\) suivante :
| R | ||||
|---|---|---|---|---|
| A | B | C | D | E |
| a1 | b1 | c1 | d1 | e1 |
| a1 | b2 | c2 | d2 | e1 |
| a2 | b1 | c3 | d3 | e1 |
| a2 | b1 | c4 | d3 | e1 |
| a3 | b2 | c5 | d1 | e1 |
Répondre aux exercices suivants concernant les Dépendances Fonctionnelles Elementaires (DFE)
Expliquer pour quelle raison la DF suivante :
- \(C \rightarrow (A,B,D,E)\)
peut être retenue dans l’ensemble des DFE
Votre réponse :
Zone de saisie de texte
| Clavier | Action |
|---|---|
| F1 | Afficher une aide technique |
| F2 | Afficher une aide pédagogique |
| Ctrl-A | Tout sélectionner |
| Ctrl-C | Copier la sélection dans le presse-papier |
| Ctrl-V | Copier le presse-papier dans la sélection |
| Ctrl-X | Couper la sélection et la copier dans le presse-papier |
| Ctrl-Z | Annuler la modification |
| Maj-Ctrl-Z | Rétablir la modification |
| Menu | Action |
|---|---|
| Ré-initialiser les sorties | |
| Faire apparaître le menu d'aide | |
| Valider la zone de saisie | |
| Initialiser la zone de saisie | |
| Charger le contenu d'un fichier dans la zone de saisie | |
| Sauvegarder le contenu de la zone de saisie dans un fichier | |
| Imprimer le contenu de la zone de saisie |
Une solution possible :
En utilisant l’axiome de décomposition on peut décomposer la DF en faisant apparaître un seul attribut cible :
- \(C \rightarrow A\)
- \(C \rightarrow B\)
- \(C \rightarrow D\)
- \(C \rightarrow E\)
Comme il n’y a qu’un seul attribut source, il ne peut donc y avoir de sous-ensemble qui soit une DF sur l’attribut cible.
Expliquer pour quelle raison la DF suivante :
- \((A,B,C) \rightarrow (D,E)\)
ne peut être retenue dans l’ensembles des DFE
Votre réponse :
Zone de saisie de texte
| Clavier | Action |
|---|---|
| F1 | Afficher une aide technique |
| F2 | Afficher une aide pédagogique |
| Ctrl-A | Tout sélectionner |
| Ctrl-C | Copier la sélection dans le presse-papier |
| Ctrl-V | Copier le presse-papier dans la sélection |
| Ctrl-X | Couper la sélection et la copier dans le presse-papier |
| Ctrl-Z | Annuler la modification |
| Maj-Ctrl-Z | Rétablir la modification |
| Menu | Action |
|---|---|
| Ré-initialiser les sorties | |
| Faire apparaître le menu d'aide | |
| Valider la zone de saisie | |
| Initialiser la zone de saisie | |
| Charger le contenu d'un fichier dans la zone de saisie | |
| Sauvegarder le contenu de la zone de saisie dans un fichier | |
| Imprimer le contenu de la zone de saisie |
Une solution possible :
Un sous-ensemble de l’ensemble des attributs \((A,B,C)\) suffit pour déterminer les valeurs des attributs \((D,E)\)
Les DF \((A,B,C) \rightarrow D\) et \((A,B,C) \rightarrow E\) ne peuvent donc pas être retenues dans l’ensemble des DFE.
Trouver les Dépendances Fonctionnelles Elémentaires (DFE) existantes entre les attributs \((A,B,C,D,E)\).
On représentera les DF sous la forme \(X \rightarrow A\).
Votre réponse :
Zone de saisie de texte
| Clavier | Action |
|---|---|
| F1 | Afficher une aide technique |
| F2 | Afficher une aide pédagogique |
| Ctrl-A | Tout sélectionner |
| Ctrl-C | Copier la sélection dans le presse-papier |
| Ctrl-V | Copier le presse-papier dans la sélection |
| Ctrl-X | Couper la sélection et la copier dans le presse-papier |
| Ctrl-Z | Annuler la modification |
| Maj-Ctrl-Z | Rétablir la modification |
| Menu | Action |
|---|---|
| Ré-initialiser les sorties | |
| Faire apparaître le menu d'aide | |
| Valider la zone de saisie | |
| Initialiser la zone de saisie | |
| Charger le contenu d'un fichier dans la zone de saisie | |
| Sauvegarder le contenu de la zone de saisie dans un fichier | |
| Imprimer le contenu de la zone de saisie |
Une solution possible :
- \(A \rightarrow E\)
- \(B \rightarrow E\)
- \(C \rightarrow (A,B,D,E)\)
- \(D \rightarrow E\)
- \((A,B) \rightarrow D\)
- \((A,B) \rightarrow B\)
- \((B,D) \rightarrow A\)
Les quatre premières DF s’expliquent du fait qu’il n’y a qu’un seul élément (une seule valeur) dans l’ensemble \(E\) sur tous les enregistrements, l’attribut E dépend donc fonctionnellement de chaque attribut de la relation \((A,B,C,D)\). Ce sont des DFE car il n’y a qu’un attribut cible et, du fait que la source de la DF n’est constitué que d’un seul attribut, il n’existe pas de sous-ensemble des attributs source qui pourraient représenter une DF sur l’attribut \(E\) .
Comme les valeurs de l’attribut \(C\) sont toutes différentes, chacun des autres attributs dépend fonctionnellement de l’ensemble \(C\). En utilisant des axiomes d’additivité et de décomposition on peut donc grouper les DFE en une seule DF \(C \rightarrow (A,B,D,E)\) puis les dégrouper pour obtenir les DFE.
Il ne pourra y avoir de combinaison des attributs \((A,B,C,D)\) en tant qu’attributs source pour déterminer l’attribut cible \(E\) puisqu’avec les DFE précédentes il y aura toujours un sous-ensemble de ces combinaisons qui suffira à déterminer les valeurs de \(E\).
La cinquième DF peut-être retenue en tant que DFE car pour chaque valeur combinée des attributs \((A,B)\), il n’y a qu’une seule valeur associée de l’attribut \(D\). Ce ne sera pas le cas pour les 2 sous-ensembles possibles de ces 2 attributs source. Par contre \((A,B) \rightarrow C\) ne sera pas une DF car il peut correspondre des valeurs différentes de l’attribut cible pour un même combinaison des valeurs des attributs sources \(A,B\).
De même, la sixième DF peut-être retenue en tant que DFE car pour chaque valeur combinée des attributs \((A,D)\), il n’y a qu’une seule valeur associée de l’attribut \(B\). Par contre il n’y a pas une seule valeur correspondante de l’attribut \(C\).
La dernière DF peut aussi être retenue en tant que DFE car pour chaque valeur combinée des attributs \((B,D)\), il n’y a qu’une seule valeur associée de l’attribut \(A\). Par contre il n’y a pas une seule valeur correspondante de l’attribut \(C\).
Schéma relationnel
Un schéma relationnel (\(R\)) sera défini par :
- l’ensemble des attributs (
U) qui le constituent- l’ensemble des dépendances fonctionnelles (
F) entre les attributs
Notation d’un schéma relationnel : \(R(U,F)\)
Dans le schéma relationnel suivant :
Cours(matiere, jour, heure, salle)
On peut identifier la dépendance fonctionnelle entre les attributs :
- \((salle, jour, heure) \rightarrow matiere\)
qui signifie que dans une salle à un moment donné (heure) de la journée (jour ) ne peut être enseigné qu’une seule matiere.