Discussion :

[Blacko952]

Bonjour, je m'excuse d'avance si ma question manque de pertinence, je suis un novice en informatique : )
J'ai un cours visant à m'apprendre la normalisation d'un modèle relationnel et j'en suis au stade de la production des clés candidates. J'ai lu un post qui m'a enfin permis de comprendre la démarche à suivre, mais me voila maintenant frappé d'une interrogation.
Par exemple dans le cadre d'une relation R(A,B,C,D,E,F) avec
DF1 : {A} → {B}
DF2 : {C} → {A}
DF3 : {C} → {D}
DF4 : {A,F} → {C}
DF5 : {A,F} → {E}

je sais que dans ce cas, comme {F} n'est jamais un dépendant parmi les DF, il est forcément constituant des clé candidates. Ma question est la suivante, peut on pour gagner du temps partir également du principe que si un élément n'est jamais un déterminant dans aucune des DF , il peut etre exclu des recherches comme il ne déterminerait aucun autre élément? Par exemple dans ce cas, on ne ferait pas la fermeture de {B} ni d'aucun autre sous-ensemble de R contenant {B}.

Merci pour votre indulgence et vos réponses,

Cordialement,

Blacko952.

[Oishiiii]

Bonjour,

peut on pour gagner du temps partir également du principe que si un élément n'est jamais un déterminant dans aucune des DF , il peut etre exclu des recherches comme il ne déterminerait aucun autre élément?

Je pense que la réponse est oui.
Cette propriété est utilisée dans une méthode de recherche des clés qui est à ma connaissance la plus simple et la plus rapide. Elle est décrite dans un papier intitulé An Efficient Algorithm to Compute the Candidate Keys of a Relational Database Schema.

On part d'un ensemble de DF irréductible, et on procède en trois étapes.

Première étape

On crée trois ensembles de DF, trois variables, que l'on va alimenter.

Dans le premier, disons L, on place tous les attributs qui appartiennent uniquement aux déterminants des DF.

C'est, facile, en partant de votre ensemble de DF, il n'y a qu'un attribut qui satisfait cette propriété.

L = {F}

Un deuxième ensemble R va contenir tous les attributs qui apparaissent uniquement dans les dépendants.

R = {B, D, E}

Un dernier ensemble, disons Z va contenir les attributs qui apparaissent des deux côtés des DF, à la fois dans les dépendants et les déterminants.

Z = {A, C}

Pour s'assurer de ne pas s'être trompé on vérifie que :

• L ∩ R = Ø
• L ∩ Z = Ø
• R ∩ Z = Ø

On vérifie donc également que:

• L ∪ R ∪ Z = R

Deuxième étape

On sait directement que l'ensemble d'attributs L appartient forcément à chaque clé candidate.

Si la fermeture L+ de L est égale à R, L est la seule clé de R. Le travail est terminé. Si ce n'est pas le cas on passe à la dernière étape.

Troisième étape

On ajoute un à un les attributs de Z à L et on recalcule la fermeture de ce nouvel ensemble.

Z ne contient que deux attributs; A et C. Il suffit de calculer {A,F}+ et {C,F}+.

Seul {A, F}+ = R. {A, F} est la seule clé de R.

Cette méthode est simple, très rapide à réaliser sur papier et réduit au minimum le nombre de fermetures à calculer.

[Blacko952]

Merci beaucoup pour cette réponse : )