transitivas transitiva total resueltos funcionales funcional ejercicios dependencias dependencia definicion datos database functional-dependencies

database - transitiva - dependencias funcionales ejercicios resueltos



Determinar claves a partir de dependencias funcionales (7)

Código

Si el código le habla más que explicaciones largas, aquí hay una implementación de 25 líneas de un algoritmo que encuentra claves basadas en dependencias funcionales:

https://github.com/lovasoa/find-candidate-keys/blob/master/find-candidate-keys.js

Ejemplo

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''] ]) devuelve [["B","D","F","G"],["B","D","E","F"],["B","C","D","F"],["A","B","D","F"]]

Estoy tomando un curso de teoría de bases de datos, y no me queda claro después de leer cómo puedo inferir claves, dado un conjunto de dependencias funcionales.

Tengo un problema de ejemplo:

Encuentre todas las claves de la relación R (ABCDEFG) con dependencias funcionales.

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

Demuestre su conocimiento identificando cuál de las siguientes es una clave.

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

¿Puede alguien explicarme cómo debo descomponer las dependencias funcionales para concluir que una combinación de atributos es una clave? Espero que me enfrente a varios de estos tipos de problemas y necesito entender cómo abordarlos.

Bueno, esto debería ser bastante sencillo. Todo lo que necesita hacer es tomar el cierre de cada clave dada y ver si contiene todos los atributos de R. Por ejemplo, el cierre de BCDEF = ABCDEFG ya que BC -> A y BC es un subconjunto de BCDEF y, por lo tanto, si EF para FD EF -> G. Dado que este cierre contiene todos los atributos de R, BCDEF es la clave. El objetivo principal de tomar cierres es ver si podemos "alcanzar" cada atributo de un conjunto dado de atributos. El cierre es el conjunto de atributos que realmente podemos alcanzar al navegar los FD.

Bueno, no soy un experto en esto, así que corrígeme si me equivoco, pero mi enfoque sería eliminar respuestas imposibles.

en este caso:

ninguno de sus FD "le da" B, D o F ... ya que son parte de la relación, no puede haber una super clave que no contenga B, D y F ... eliminar respuesta b (falta B). .. eliminar respuesta d (falta F)

ahora, verifiquemos las respuestas restantes si contienen suficiente información para obtener todas las partes de la relación

contestar a (BCDEF) le "dará" B, C, D, E y F, por lo que deberá encontrar A y G utilizando los FD ... A puede ser alcanzado por BC y G puede llegar por G, así que responda a es una clave

La respuesta c (BDFG) le "dará" B, D, F y G, por lo que deberá encontrar A, C y E utilizando los FD ... Se puede llegar a E con FG ... Se puede llegar a C mediante DE (después de alcanzando E por FG) ... y finalmente A puede ser alcanzado por BC (después de alcanzar C) ...

así que la respuesta c es algún tipo de clave, ya que se puede acceder a toda la relación de esta manera ... pero no sé si esto es suficiente para ajustarse a la definición formal ... si tuviera que adivinar, diría no

Tome un FD, por ejemplo, AB → C

Aumente hasta que se mencionen todos los atributos, por ejemplo, ABDEFG → CDEFG (tenga en cuenta que esto es equivalente a ABDEFG → ABCDEFG porque es trivialmente cierto que A-> A y B-> B).

Esto te dice que ABDEFG es una superclave.

Verifique las otras FD en las que el LHS es un subconjunto de su superclave, y que en su RHS contiene algún otro atributo de su superclave.

Hay dos. EF → G y FG → E. Elimine los atributos de la RHS de estos de su superclave. Hacerlo te da dos claves, que son ciertamente superclaves, pero no necesariamente irreductibles: ABDEF y ABDFG.

Sin embargo, de AB → C y CD → E también podemos derivar que ABD → E. Por lo tanto, también podemos eliminar la E de nuestra clave ABDEF. Lo desagradable aquí es que cuando dije "Revisar las otras FD", eso aparentemente significa que también debes verificar cualquier FD que aparezca en el cierre de tu conjunto de FD (es decir, cualquier FD que sea derivable de tu conjunto dado de FD) ... y eso es un poco impráctico de hacer a mano ...

Un sitio útil para verificar si sus resultados son correctos:

http://www.koffeinhaltig.com/fds/ueberdeckung.php

Ahora deberías poder determinar que la opción c es una clave.

ACTUALIZAR

El enlace ahora está roto, ni idea de dónde ha ido el sitio. Quizás aún pueda encontrar algo útil en los sitios que hacen un seguimiento de la historia de Internet.

Ya que estás en un curso de teoría de db, voy a asumir que tienes experiencia en SQL e intentaré relacionar la teoría con el contexto de la implementación.

Básicamente, una relación es lo que usted denominaría una tabla en la implementación y una clave es CUALQUIER conjunto de atributos (columnas de lectura) que se pueden usar para identificar una fila ÚNICA (en teoría de DB, esto sería una tupla). La analogía más simple aquí es que una clave es su clave principal, así como cualquier otro conjunto posible de columnas que pueda usar para identificar una sola tupla en su relación (fila en su tabla). Entonces, aquí están los pasos básicos para hacer esto (veré el ejemplo A, y luego puedes probar el resto):

  1. Enumere todos los atributos que NO están en su clave propuesta (por lo tanto, BCDEF no incluye A y G).

  2. Para cada atributo que le falte, revise la lista de dependencias funcionales y vea si la clave propuesta es capaz de inferir el atributo que falta.

    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.

Debido a que pudo inferir tanto A como G de BCDEF, la opción a es una clave de la relación ABCDEFG. Sé que hay un algoritmo para esto, y probablemente esté en el texto del curso en alguna parte. Probablemente también hay un ejemplo. Debes recorrerlo manualmente hasta que el patrón sea intuitivo.

EDITAR: La razón por la que volvería a revisar el texto para buscar este algoritmo es que es probable que su examen sea escrito en lugar de una opción múltiple, ya que es un curso de teoría de la DB. Si esto es cierto, entonces obtendría un crédito más parcial si pudiera seguir la notación demostrada metódicamente en el texto / notas de su curso.

El objetivo principal es convertir la clave en la relación, lo que debería probar que la clave propuesta es, de hecho, una clave.

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),

entonces ABDF es una super clave. Luego usaremos el resultado de las dependencias para determinar si son claves. (aquí por qué uso BC-> A, porque A es parte de mi superclave, que depende 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.