Affinement et Décomposition de Schéma

L'affinement de schéma est le processus de décomposition d'une relation en relations plus petites afin d'atteindre une forme normale désirée, sous réserve que la décomposition soit sans perte et, idéalement, qu'elle préserve les dépendances originales.

Definition

La décomposition remplace un schéma de relation R par un ensemble de schémas dont les attributs couvrent ensemble R, de sorte que la relation originale puisse être récupérée en joignant les parties (jointure sans perte) et, lorsque cela est possible, que chaque dépendance fonctionnelle originale puisse être appliquée sur les parties (préservation des dépendances).

Scope

Ce sujet couvre les algorithmes et les critères de décomposition des schémas relationnels : la propriété de jointure sans perte et la manière dont elle est testée, la préservation des dépendances et sa tension avec les formes normales supérieures, ainsi que les algorithmes standard de synthèse et de décomposition qui produisent une conception en 3FN (préservant les dépendances et sans perte) ou en BCNF (sans perte) à partir d'un ensemble de dépendances fonctionnelles. Il exclut les définitions des formes normales elles-mêmes et des dépendances qui régissent la décomposition.

Core questions

• Qu'est-ce qui rend une décomposition sans perte, et comment cette propriété est-elle testée ?
• Que signifie pour une décomposition de préserver les dépendances ?
• Pourquoi la décomposition en BCNF peut-elle échouer à préserver les dépendances alors que la synthèse en 3FN y parvient ?
• Comment fonctionnent les algorithmes standard de décomposition en BCNF et de synthèse en 3FN ?
• Comment le choix entre BCNF et 3FN est-il fait en pratique ?

Key concepts

• décomposition d'un schéma
• propriété de jointure sans perte
• préservation des dépendances
• tuples parasites
• algorithme de décomposition en BCNF
• algorithme de synthèse en 3FN
• couverture minimale
• compromis entre BCNF et 3FN

Key theories

Décomposition par jointure sans perte

Une décomposition binaire est sans perte si les attributs communs des deux parties forment une clé d'au moins l'une d'entre elles ; l'absence de perte garantit que la jointure des parties reconstitue exactement la relation originale sans tuples parasites.

Préservation des dépendances

Une décomposition préserve les dépendances si l'union des dépendances applicables sur les parties individuelles implique toutes les dépendances originales, de sorte que la cohérence puisse être vérifiée sans recalculer les jointures.

Décomposition en BCNF versus synthèse en 3FN

L'algorithme de décomposition en BCNF garantit l'absence de perte mais peut sacrifier la préservation des dépendances, tandis que l'algorithme de synthèse en 3FN à partir d'une couverture minimale garantit à la fois une jointure sans perte et la préservation des dépendances au prix de s'arrêter éventuellement à la 3FN.

Clinical relevance

Les algorithmes de décomposition sont la manière dont la théorie de la normalisation devient une procédure de conception actionnable : leur application produit des schémas qui évitent la redondance tout en pouvant être reconstruits et validés efficacement, ce qui affecte directement la justesse et la maintenabilité des bases de données de production.

History

La théorie de la décomposition sans perte et préservant les dépendances a été développée tout au long des années 1970, alors que les chercheurs formalisaient les conditions dans lesquelles la division d'une relation est sûre. Les algorithmes de synthèse produisant des conceptions en 3FN préservant les dépendances, et la reconnaissance que la BCNF peut entrer en conflit avec la préservation des dépendances, sont devenus des éléments standards dans les ouvrages sur les bases de données et restent centraux dans la conception de schémas.

Key figures

• Edgar F. Codd
• Jeffrey D. Ullman
• Philip Bernstein

Seminal works

• silberschatz2019
• ramakrishnan2003
• garciamolina2008

Frequently asked questions

Qu'est-ce qu'un tuple parasite et pourquoi est-ce important ?

Un tuple parasite est une ligne qui apparaît lorsque vous joignez les parties d'une décomposition mal choisie mais qui ne correspond à aucun tuple réel de la relation originale. Une décomposition par jointure sans perte est précisément celle qui ne produit pas de tuples parasites, c'est pourquoi l'absence de perte est une exigence non négociable.

Pourquoi pourrais-je choisir la 3FN plutôt que la BCNF ?

La décomposition en BCNF préserve toujours la propriété de jointure sans perte mais peut rompre la préservation des dépendances, ce qui signifie que certaines contraintes ne pourraient être vérifiées qu'en joignant des tables. L'algorithme de synthèse en 3FN garantit à la fois l'absence de perte et la préservation des dépendances, de sorte que les concepteurs acceptent la 3FN lorsqu'une conception en BCNF préservant les dépendances n'existe pas.