Je suis en train de suivre un cours de théorie des bases de données et je ne comprends pas bien après avoir lu 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
Est-ce que quelqu’un peut me montrer comment je dois décomposer les dépendances fonctionnelles pour conclure qu’une combinaison d’atsortingbuts est une clé? Je pense que je vais faire face à un certain nombre de problèmes de ce type et que je dois comprendre comment les aborder.
Prenez un FD, par exemple AB → C
Augmentez jusqu’à ce que tous les atsortingbuts soient mentionnés, par exemple ABDEFG → CDEFG (notez que ceci est équivalent à ABDEFG → ABCDEFG car il est sortingvialement vrai que A-> A et B-> B).
Cela vous dit que ABDEFG est un superkey.
Vérifiez les autres FD dans lesquels le LHS est un sous-ensemble de votre super-clé, et celui de son RHS contient d’autres atsortingbuts de votre super-clé.
Il y en a deux. EF → G et FG → E. Supprimez les atsortingbuts du RHS de votre super-clé. Cela vous donne deux clés, qui sont certainement des superkeys, mais pas nécessairement des irréductibles: ABDEF et ABDFG.
Cependant, à partir de AB → C et CD → E, nous pouvons également déduire qu’ABD → E. Par conséquent, nous pouvons également supprimer le E de notre clé ABDEF. La mauvaise chose est que lorsque j’ai dit “Vérifier les autres FDs”, cela signifie apparemment que vous devriez également vérifier toute FD apparaissant à la fermeture de votre ensemble de FD (c.-à-d. Toute FD pouvant être dérivée de votre ensemble de FD) … Et c’est un peu pratique à faire à la main …
Un site utile pour vérifier si vos résultats sont corrects:
http://www.koffeinhaltig.com/fds/ueberdeckung.php
Vous devriez maintenant être en mesure de déterminer que l’option c est une clé.
METTRE À JOUR
Le lien est maintenant cassé, aucune idée de l’emplacement du site. Peut-être que vous pouvez toujours trouver quelque chose d’utile sur les sites qui gardent une trace de l’histoire de l’Internet.
Cette vidéo explique très bien
Eh bien, cela devrait être assez simple. Tout ce que vous avez à faire est de prendre la fermeture de chaque clé donnée et voir si elle contient tous les atsortingbuts de R. Par exemple, la fermeture de BCDEF = ABCDEFG depuis BC -> A et BC est un sous-ensemble de BCDEF et donc EF pour FD EF -> G. Comme cette fermeture contient tous les atsortingbuts de R, BCDEF est la clé. L’objective principal de prendre des fermetures est de voir si nous pouvons “atteindre” chaque atsortingbut d’un ensemble d’atsortingbuts donné. La fermeture est l’ensemble des atsortingbuts que nous pouvons réellement atteindre en naviguant dans les FD.
Étant donné que vous êtes dans un cours théorique sur la firebase database, je suppose que vous avez une expérience SQL et essayez de relier la théorie au contexte d’implémentation.
Fondamentalement, une relation est ce que vous appelez une table dans l’implémentation et une clé est N’IMPORTE QUEL ensemble d’atsortingbuts (colonnes de lecture) qui peuvent être utilisés pour identifier une ligne UNIQUE (dans la théorie de la firebase database, 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 seul tuple dans votre relation (ligne dans votre table). Donc, voici les étapes de base pour le faire (je vais parcourir l’exemple A, et ensuite vous pouvez essayer le rest):
Pour chaque atsortingbut manquant, parcourez la liste des dépendances fonctionnelles et vérifiez si votre clé proposée est capable d’inférer l’atsortingbut manquant.
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 y a un algorithme pour cela, et c’est probablement dans votre texte de cours quelque part. Il y a aussi probablement un exemple. Vous devriez le parcourir manuellement jusqu’à ce que le motif soit intuitif.
EDIT: La raison pour laquelle je retournerais dans le texte pour chercher cet algorithme est que les chances sont que votre examen va être écrit plutôt que des choix multiples puisque c’est un cours de théorie de firebase database. Si cela est vrai, vous obtiendrez plus de crédit partiel si vous pouvez suivre méthodiquement la notation présentée dans le texte / les notes de votre cours.
L’objective principal est de transformer la clé en relation, ce qui devrait prouver que la clé proposée est en fait une clé.
eh bien, je ne suis pas un expert pour ce genre de choses, alors corrigez-moi si je me trompe, mais mon approche serait d’éliminer les réponses impossibles
dans ce cas:
aucun de vos FD ne vous “donne” B, D ou F … puisque ceux-ci font partie de la relation, il ne peut y avoir de super clé ne contenant pas B, D et F … supprimer la réponse b (B manque). .. supprimer la réponse d (F est manquant)
maintenant vérifions les réponses restantes si elles contiennent suffisamment d’informations pour obtenir toutes les parties de la relation
answer a (BCDEF) va vous “donner” 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, alors répondez 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 FD … E peut être atteint par FG … C peut être atteint par DE (après atteindre 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 toute la relation peut être accédée de cette façon … mais je ne sais pas si cela suffit pour correspondre à la définition formelle … si je devais deviner, je dirais non
Si le code vous parle plus que de longues explications, voici une implémentation de 25 lignes d’un algorithme qui trouve les clés en fonction des dépendances fonctionnelles:
https://github.com/lovasoa/find-candidate-keys/blob/master/find-candidate-keys.js
candidate_keys(["A","B","C","D","E","F","G"], [ [['A','B'], 'C'], [['C','D'], 'E'], [['E','F'], 'G'], [['F','G'], 'E'], [['D','E'], 'C'], [['B','C'], 'A'] ])
renvoie [["B","D","F","G"],["B","D","E","F"],["B","C","D","F"],["A","B","D","F"]]
step1: since AB->C and CD->E. then we get ABD->ABCDE(1) step2: Given (1) and EF->G, then we get ABDF->ABCDEF, then ABDF->ABCDEFG(2),
alors ABDF est une super clé. Ensuite, nous utiliserons le résultat des dépendances pour déterminer si ce sont des clés. (voici pourquoi j’utilise BC-> A, car A fait partie de ma super-clé, qui dépend de BC).
step3: Given (2) and BC->A, we get BCDF->ABDF, so BCDF->ABCDEFG(3) step4: Given (3) and DE->C, we get BDEF->BCDE, so BDEF->ABCDEFG(4) step5: Given (4) and FG->E, we get BDFG->BDEF, so BDFG->ABCDEFG, So the Answer BDFG is right.