Décomposition de jointure sans perte

Dans le domaine de la conception de bases de données, une décomposition de jointure sans perte est une décomposition d'une relation $R$ dans des sous-relations $R_{1},R_{2}$ de telle sorte qu'une jointure naturelle des deux sous-relations renvoie la relation originale. Il s'agit d'un moyen central pour supprimer en toute sécurité la redondance dans les bases de données tout en préservant les données d’origine. La jointure sans perte peut également être appelée jointure non-additive.

Critères

Soit $(R_{1},R_{2})$ une décomposition d'une relation $R$.

La décomposition est sans perte si et seulement si la jointure naturelle de $R_{1}$ et $R_{2}$ aboutit à la relation originale $R$ (c'est à dire, si $R_{1}\bowtie R_{2}=R$ ).

De manière équivalente, la décomposition est sans perte si et seulement si l'une des sous-relations (c'est-à-dire $R_{1}$ ou $R_{2}$ ) est un sous-ensemble de la clôture de leur intersection. Autrement dit, la décomposition de $R$ est sans perte si $R_{1}\subseteq [R_{1}\cap R_{2}]^{+}$ ou $R_{2}\subseteq [R_{1}\cap R_{2}]^{+}$ est vrai.

Critères pour plusieurs sous-relations

Plusieurs sous-relations $R_{1},R_{2},...,R_{n}$ ont une jointure sans perte s'il existe un moyen par lequel on peut effectuer à plusieurs reprises des jointures sans perte jusqu'à ce que toutes les relations aient été jointes en une seule relation. Une fois que l'on a une nouvelle sous-relation créée à partir d’une jointure sans perte, on ne peut plus utiliser une de ses sous-relations isolées pour se joindre à l’une des autres relations. Par exemple, si on peut effectuer une jointure sans perte sur une paire de relations $R_{i},R_{j}$ pour construire une nouvelle relation $R_{i,j}$, on utilisera alors cette nouvelle relation (plutôt que $R_{i}$ ou $R_{j}$) pour former une jointure sans perte avec une autre relation $R_{k}$ (qui peut avoir déjà été jointe (par exemple, $R_{k,l}$)).

Exemples

• Soit $R=(A,B,C,D)$ être un schéma relationnel, avec les attributs A, B, C et D .
• Soit $F=\{A\rightarrow BC\}$ être l’ensemble des dépendances fonctionnelles.
• La décomposition en $R_{1}=(A,B,C)$ et $R_{2}=(A,D)$ est sans perte sous F car $R_{1}\cap R_{2}=A$. A est une super-clé dans $R_{1}$, ce qui signifie que nous avons une dépendance fonctionnelle $\{A\rightarrow BC\}$. En d’autres termes, nous avons maintenant prouvé que $(R_{1}\cap R_{2}\rightarrow R_{1})\in F^{+}$.