Dependencias funcionales Flashcards
Definir informalmente dependencia funcional
Una dependencia funcional es un constraint que especifica una relacion entre dos conjuntos de atributos, tal que uno de los conjuntos puede determinar el valor del otro.
Definicion formal de dependencia funcional
Sea R un esquema de relacion y sean A y B subconjuntos de R, la dependencia funcional A -> B se cumple en R, si para cualquier instance r(R) se cumple que para todo par de tuplas t1, t2 \in r, si t1[A] = t2[A] entonces t1[B] = t2[B]
Definir superclave en terminos de dependencia funcional
Sea K \subset R, K es una superclave de R si y solo si K -> R
Definir clave candidata en terminos de dependencia funcional
Sea K \subset R, K es una clave candidata de R si:
- K -> R
- No existe ningun A \subset K, tal que A -> R
Que permiten expresar las dependencias funcionales?
Restricciones que no pueden ser expresadas a traves de superclaves
Definir dependencia funcional trivial
Una dependencia funcional se A -> B se dice trivial si B \subset A
Definir clausura de conjunto de dependencias funcionales
A partir de un conjunto de dependencias funcionales F se pueden probar que valen otras.
Sea F un conjunto de dependencias funcionales que valen en un esquema R, la clausura de F, denotado F+, es el conjunto de dependencias funcionales implicadas por F
Dar y definir los axiomas de Amstrong
(1) REFLEXIVIDAD: Si B \subseteq A, entonces A -> B
(2) AUMENTACION: Si A -> B, y C es un conjunto de atributos, entonces AC -> BC
(3) TRANSITIVIDAD: Si A -> B, y B -> C, entonces A -> C
Definir reglas derivadas de los axiomas de Amstrong
(1) UNION: Si se cumple que A -> B y A -> C, entonces A -> BC
(2) DESCOMPOSICION: Si se cumple que A -> BC, entonces se cumple que A -> B y A -> C
(3) PSEUDOTRANSITIVIDAD: Si se cumple que A -> B y BC -> D, entonces AC -> D
Demostraciones:
http://tinman.cs.gsu.edu/~raj/4710/sp08/fd-theory.pdf
Definir clausura de conjuntos de atributos
Dado un conjunto de atributos A, se define la clausura de A bajo F (denotado A+) como el conjunto de atributos que son determinados funcionalmente por A bajo F:
A -> B esta en F+ si y solo si B \subseteq A+
Dar el algoritmo para obtener la clausura de conjunto de atributos
result = A
while (result cambia) do:
for each dependencia B -> C in F do:
if B \subseteq result:
result = result + C
Dar el algoritmo para obtener la clausura de conjunto de atributos
result = A
while (result cambia) do:
for each dependencia B -> C in F do:
if B \subseteq result:
result = result + C
Para que sirve la clausura de conjunto de atributos?
(1) Para ver si un conjunto de atributos es superclave: si A es superclave, entonces A+ contiene todos los atributos de R
(2) Para probar la validez de una dependencia funcional: A -> B vale siempre que B este contenido en A+
(3) Computar clausura de conjunto de F: para cada C \subseteq R, definir la clasurura C+, y para cada S \subseteq C+, generar la dependencia funcional C -> S
Definir recubrimiento canonico
El recubrimiento canonico de un conjunto de dependencias funcionales F es el conjunto minimo de dependencias funcionales equivalente a F. EJEMPLO:
F = {A -> B, B -> C, A -> C}
Su recubrimiento canonico seria {A ->B, B -> C}, ya que A -> C se puede deducir por transitividad y no es necesario explicitarlo en F
Definir atributo extraño
Sea F un conjunto de dependencias funcionales, y A -> B una dependencia funcial en F.
(1) El atributo C es extraño en A si C \in A y F implica logicamente a (F - {A -> B}) U {(A - C) -> B}, es decir, que C no es necesario en A.
(2) El atributo C es extraño en B si si C \in B y F implica logicamente a (F - {A -> B}) U {A -> (B - C)}, es decir, que C no es necesario en B.
