44 votes

Déterminer les clés à partir des dépendances fonctionnelles

Je suis un cours sur la théorie des bases de données et je ne vois pas très bien, après avoir lu le cours, comment je peux déduire des clés, étant donné un ensemble de dépendances fonctionnelles.

J'ai un exemple de problème :

Trouver toutes les clés de la relation R(ABCDEFG) avec des dépendances fonctionnelles

AB  C
CD  E
EF  G
FG  E
DE  C
BC  A

Démontrez vos connaissances en identifiant lequel des éléments suivants est une clé.

a. BCDEF             
b. ADFG           
c. BDFG           
d. BCDE 

Quelqu'un peut-il m'expliquer comment je dois décomposer les dépendances fonctionnelles pour conclure qu'une combinaison d'attributs est une clé ? Je m'attends à être confronté à un certain nombre de problèmes de ce type et j'ai besoin de comprendre comment les aborder.

0 votes

La vidéo en La réponse de yrazlik utilise en fait l'approche introduite dans [1], si vous souhaitez savoir pourquoi elle fonctionne. (Les preuves sont courtes et directes) [1] H. Saiedian et T. Spencer, "An Efficient Algorithm to Compute the Candidate Keys of a Relational Database Schema" (Un algorithme efficace pour calculer les clés candidates d'un schéma de base de données relationnelle). Le Journal de l'informatique vol. 39, n° 2, février 1996 [En ligne]. Disponible : pdfs.semanticscholar.org/ab3f/ . [consulté le 31 juillet 2019].

1 votes

@Leponzo L'introduction de l'algorithme à puces que vous avez donné dans certaines réponses supprimées similaires à votre réponse supprimée ici est incorrecte. L'algorithme exige que F soit une couverture pour les DF qui tiennent, et pas seulement un ensemble de DF qui tiennent. PS S'il vous plaît utilisez du texte, et non des images/liens, pour le texte - y compris les tableaux et les ERD. Paraphrase ou citation d'un autre texte. N'utilisez les images que pour ce qui ne peut être exprimé sous forme de texte ou pour compléter le texte. Les images ne peuvent pas être recherchées ou copiées et collées. Incluez une légende/clé et une explication avec une image.

33voto

Erwin Smout Points 7499

Prenez un FD, par exemple ABC

Augmentez jusqu'à ce que tous les attributs soient mentionnés, par exemple ABDEFG CDEFG (notez que cela est équivalent à ABDEFG ABCDEFG car il est trivialement vrai que A->A et B->B).

Cela vous indique que ABDEFG est une super clé.

Vérifiez les autres FD dont le LHS est un sous-ensemble de votre superclé, et dont le RHS contient un autre attribut de votre superclé.

Il y en a deux. EFG et FGE. Enlevez les attributs de la RHS de celles-ci de votre superclé. Vous obtiendrez ainsi deux clés, qui sont certes des superclés, mais pas nécessairement irréductibles : ABDEF et ABDFG.

Cependant, à partir de ABC et CDE, nous pouvons également déduire que ABDE. Par conséquent, nous pouvons également supprimer le E de notre clé ABDEF. Ce qui est désagréable ici, c'est que lorsque j'ai dit "Vérifier les autres DF", cela signifie apparemment que vous devriez également vérifier tout DF qui apparaît dans la fermeture de votre ensemble de DF (c'est-à-dire tout DF qui est dérivable de votre ensemble donné de DF)... Et c'est un peu difficile à faire à la main...

Un site utile pour vérifier si vos résultats sont corrects :

http://raymondcho.net/RelationalDatabaseTools/RelationalDatabaseTools

Vous devriez maintenant être en mesure de déterminer que l'option c est une clé.

0 votes

BDF n'est-il pas la clé candidate ? Puisque DF->C, EF->G, CD->E nous avons G de BDF.

0 votes

NickRosencrantz : Il y a quatre clés pour les candidats. BDF n'en fait pas partie ; elles ont toutes quatre attributs. Je ne suis pas du tout votre logique déductive ; aucune des FD que vous mentionnez ne contient B.

0 votes

Il a mentionné DF->C mais cela n'a pas été précisé. Peut-être a-t-il mal lu DE->C.

13voto

bigO Points 1371

Cette vidéo l'explique très bien

http://www.youtube.com/watch?v=s1DNVWKeQ_w

3voto

Parth Mehta Points 31

Cela devrait être assez simple. Tout ce que vous devez faire est de prendre la fermeture de chaque clé donnée et de voir si elle contient tous les attributs de R. Par exemple, la fermeture de BCDEF = ABCDEFG puisque BC -> A et BC est un sous-ensemble de BCDEF et donc si EF pour FD EF -> G. Puisque cette fermeture contient tous les attributs de R, BCDEF est la clé. L'objectif principal de la prise en compte des fermetures est de voir si nous pouvons "atteindre" chaque attribut à partir d'un ensemble donné d'attributs. La fermeture est l'ensemble des attributs que nous pouvons effectivement atteindre en naviguant dans les FD.

0 votes

BCDEF n'est pas une clé candidate, car elle est réductible. (BC->E) Mais BCDF est un des clés candidates.

2voto

Dave Points 3747

Puisque vous suivez un cours de théorie de la base de données, je vais supposer que vous avez de l'expérience en SQL et que vous essayez de relier la théorie au contexte de mise en œuvre.

Fondamentalement, une relation est ce que vous appelleriez une table dans la mise en œuvre et une clé est N'IMPORTE QUEL ensemble d'attributs (lire colonnes) qui peut être utilisé pour identifier une ligne UNIQUE (en théorie de la BD, ce serait un tuple). L'analogie la plus simple ici est qu'une clé est votre clé primaire, ainsi que tout autre ensemble possible de colonnes que vous pouvez utiliser pour identifier un tuple unique dans votre relation (ligne dans votre table). Voici donc les étapes de base à suivre (je vais vous présenter l'exemple A, puis vous pourrez essayer les autres) :

  1. Énumérez tous les attributs qui ne figurent PAS dans votre clé proposée (ainsi, BCDEF ne comprend pas A et G).
  2. Pour chaque attribut qui vous manque, parcourez la liste des dépendances fonctionnelles et voyez si la clé que vous proposez est capable de déduire l'attribut qui vous manque.

                 a. So for A, you have BC -> A.  Since both B and C are in the proposed
                    key BCDEF, you can infer that BCDEF -> A.  Your set now becomes
                    BCDEFA.
                 b. For G, again going through your FDs you find EF -> G.  Since both
                    E and F are in BCDEFA, you can infer BCDEFA -> G.

Comme vous avez pu déduire A et G de BCDEF, l'option a est une clé de la relation ABCDEFG. Je sais qu'il existe un algorithme pour cela, et il est probablement quelque part dans votre manuel de cours. Il existe probablement aussi un exemple. Vous devriez le parcourir manuellement jusqu'à ce que le modèle soit intuitif.

EDIT : La raison pour laquelle je chercherais cet algorithme dans le texte est qu'il y a de fortes chances que votre examen soit écrit plutôt qu'à choix multiple, puisqu'il s'agit d'un cours de théorie de la DB. Si c'est vrai, vous obtiendrez plus de crédits partiels si vous pouvez suivre méthodiquement la notation démontrée dans le texte/notes de votre cours.

L'objectif principal est de transformer la clé en relation, ce qui devrait prouver que la clé proposée est en fait une clé.

1 votes

L'option a est effectivement une clé, mais pas une clé irréductible. L'irréductible est l'option c.

0 votes

Oui, j'ai juste regardé l'option a. Je n'ai pas vraiment pensé à spécifier/figurer quelles clés étaient des clés minimales parce que ça ne faisait pas partie de la question. Je me souviens de mes cours de théorie de la DB que l'identification des clés minimales était un sujet différent de l'identification de toute clé. J'ai donc choisi de ne pas le mentionner dans ma réponse pour éviter toute confusion.

1 votes

@Erwin, après avoir examiné la question de plus près, je comprends votre point de vue. Je pense que l'utilisation du mot "clé" dans la question est vague. La réponse à cette question varie selon que l'on entend par "clé" une clé candidate. Dans ce cas, vous auriez raison et l'option a ne serait pas une clé, car il existe un sous-ensemble de l'option a qui est toujours une superclé valide.

1voto

DarkSquirrel42 Points 4090

Je ne suis pas un expert dans ce domaine, alors corrigez-moi si je me trompe, mais mon approche consisterait à éliminer les réponses impossibles.

dans ce cas :

aucun de vos DF ne vous "donne" B, D ou F ... puisque ceux-ci font partie de la relation, il ne peut y avoir de super clé qui ne contienne pas B, D et F ... supprimez la réponse b (B est manquant) ... supprimez la réponse d (F est manquant)

maintenant vérifions les réponses restantes si elles contiennent assez d'informations pour obtenir toutes les parties de la relation

La réponse a (BCDEF) vous "donnera" B, C, D, E et F. Vous devez donc trouver A et G en utilisant les FD ... A peut être atteint par BC et G peut être atteint par EF, donc la réponse a est une clé.

La réponse c (BDFG) vous "donnera" B, D, F et G. Vous devez donc trouver A, C et E en utilisant les FDs ... E peut être atteint par FG ... C peut être atteint par DE (après avoir atteint E par FG) ... et enfin A peut être atteint par BC (après avoir atteint C) ...

donc la réponse c est une sorte de clé puisque l'ensemble de la relation est accessible de cette façon ... mais je ne sais pas si cela est suffisant pour correspondre à la définition formelle ... si je devais deviner, je dirais non

2 votes

La réponse a est une superclé appropriée, ce qui signifie qu'il existe un sous-ensemble approprié de celle-ci qui est également une clé. Souvent, le terme "clé" signifie "irréductible", ce qui n'est pas le cas de a. Mais ces détails peuvent varier d'un cours à l'autre...

Prograide.com

Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.

Powered by:

X