Décomposition d’une relation

Décomposition d’instances de relations

La décomposition de la relation \(R(A,B,C,D)\) :

En deux relations \(R_1(A,B)\) et \(R_2(B,C,D)\) :

ne sera pas sans perte d’informations du fait que la jointure naturelle entre les deux relations

• \(\Join_{[R_1.B=R_2.B]}(R_1, R_2)\) :

ne permet pas de reconstituer la relation de départ.

En effet, l’attribut de jointure (B) ne permet pas de reconstituer la table d’origine puisqu’une valeur de cet attribut ne permet pas de déterminer une seule valeur pour les attributs (C,D)

Avant d’éxécuter la requête de jointure naturelle ci-dessous, combien d’éléments pensez-vous qu’elle donnera comme résultat ?

Par contre la décomposition en deux relations \(R_1(A,B,C)\) et \(R_2(A,D)\) :

• \(\Join_{[R_1.A=R_2.A]}(R_1, R_2)\) :

permettra de reconstituer la relation de départ par jointure naturelle puisque à chaque valeur de l’attribut A correspond une seule valeur des attributs B,C et de l’attribut D.

Autrement dit :

• \(A \rightarrow (B,C)\)
• \(A \rightarrow D\)

Décomposition et dépendances fonctionnelles

Dans la relation \(R(A,B,C,D)\) :

Où l’on identifie les dépendances fonctionnelles :

• \(A \rightarrow (B,C)\)
• \(C \rightarrow D\)
• \(D \rightarrow B\)

La décomposition précédente en deux relations \(R_1(A,B,C)\) et \(R_2(A,D)\) :

ne préservera pas correctement les dépendances entre les informations.

Par contre la décomposition suivante en trois relations :

• \(R_1(A,B,C)\)
• \(R_2(C,D)\)
• \(R_3(D,B)\)

permettra de préserver les dépendances fonctionnelles du schéma relationnel (les attributs de chaque relation est constitué de l’ensemble des attributs des DF).

Dans la création du modèle de données en SQL, les attributs « source » des DF constitueront la clé primaire de la relation et certains attributs de jointure qui apparaissent comme clé primaire dans une autre table pourront être définies comme clé étrangère référençant la clé primaire de la table en question.

Dans le cas précédent on pourra représenter notre modèle de données de la manière suivante :

• \(R_1(\underline{A},B,\#C)\)
• \(R_2(\underline{C},\#D)\)
• \(R_3(\underline{D},B)\)

Où, par convention les clés primaires de tables sont représentés par des attributs soulignés et les clés étrangères sont préfixés par un “hashtag” (#).

Avant d’éxécuter les requêtes suivantes, laquelle d’après vous ne permettra pas de retrouver les informations de la table d’origine \(R(A,B,C,D)\) :

SELECT A,B,C,D  FROM R1 NATURAL JOIN R2;
SELECT A,B,C,D  FROM R1 NATURAL JOIN R3;

A votre avis pour quelle raison ?

Décomposition SPI

Un schéma relationnel \(R(U,F)\) constitué :

• d’un ensemble d’attributs : \(U=(X,Y,Z)\)
• d’un ensemble de DF : \(F=\{X \rightarrow Y \}\)

pourra être décomposé sans perte d’informations (SPI) en deux relations :

• \(R_1(X,Y),R_2(X,Z)\)

en appliquant le théorème de Heath ou théorème de décomposition SPI.

Dans le contexte du schéma relationnel ci-dessus la décomposition en deux relations :

• \(R_1(X,Y),R_2(X,Z)\)

permettra par jointure naturelle sur le groupe d’attributs \(X\) de retrouver les informations de la table d’origine \(R(X,Y,Z)\)

• \(R(X,Y,Z)= \Join_{[R_1.X=R_2.X]}(R_1(X,Y),R_2(X,Z))\)

puisque l’intersection des groupes d’attributs des deux relations \(R_1,R_2\) :

• \(X=\cap((X,Y),(X,Z))\)

est le groupe d’attributs source de la dépendance fonctionnelle (\(X \rightarrow Y\))

et la différence des groupes d’attributs des deux relations \(R_1,R_2\) :

• \(Y=\setminus((X,Y),(X,Z))\)

représente le groupe d’attributs cible de la dépendance fonctionnelle (\(X \rightarrow Y\))

Par contre les décompositions suivantes :

• \(R_1(X,Y),R_2(Y,Z)\)
• \(R_1(X,Z),R_2(Y,Z)\)

ne permettront pas de :

• satisfaire le théorème de décomposition sans perte
• préserver la DF : \(X \rightarrow Y\)
• retrouver les informations de la relation initiale \(R\) en effectuant une jointure entre les tables \(R_1,R_2\).

Exercices

CREATE TABLE R (
                X  char(2),
                Y  char(2),
                Z  char(2)
               );

INSERT INTO R VALUES('x1','y1','z1');
INSERT INTO R VALUES('x2','y1','z1');
INSERT INTO R VALUES('x2','y2','z2');
INSERT INTO R VALUES('x3','y3','z2');
INSERT INTO R VALUES('x3','y2','z2');

CREATE TABLE R1 (
                 X  char(2),
                 Y  char(2)
                );

INSERT INTO R1 VALUES('x1','y1');
INSERT INTO R1 VALUES('x2','y1');
INSERT INTO R1 VALUES('x2','y2');
INSERT INTO R1 VALUES('x3','y3');
INSERT INTO R1 VALUES('x3','y2');

CREATE TABLE R2 (
                 Y  char(2),
                 Z  char(2)
                );

INSERT INTO R2 VALUES('y1','z1');
INSERT INTO R2 VALUES('y2','z2');
INSERT INTO R2 VALUES('y3','z2');

CREATE TABLE R3 (
                 X  char(2),
                 Z  char(2)
                );

INSERT INTO R3 VALUES('x1','z1');
INSERT INTO R3 VALUES('x2','z1');
INSERT INTO R3 VALUES('x2','z2');
INSERT INTO R3 VALUES('x3','z2');

SELECT X,Y,Z FROM R1 NATURAL JOIN R2;
SELECT X,Y,Z FROM R1 NATURAL JOIN R3;
SELECT X,Y,Z FROM R2 NATURAL JOIN R3;

SELECT X,Y,Z FROM R1 NATURAL JOIN R2;