6. Functional Dependencies

Werner Van Belle¹ - werner@yellowcouch.org, werner.van.belle@gmail.com

1- Programming Technology Lab (PROG) Department of Computer Science (DINF) Vrije Universiteit Brussel (VUB); Pleinlaan 2; 1050 Brussel; Belgium

Abstract : Some proofs in functional dependencies.

Reference: Werner Van Belle; Functional Dependencies;

Functioneel afhankelijk:

U={A,B,C,D,E}

waarbij

Als R een relatie is over U dan voldoet R aan als en slechts als

[Wanneer s,t in R zodat s.X=t.X dan s.Y=t.Y]

Notatie: R =

Logische Implicatie

Laat een verzameling functionele afhankelijkheden over U zijn,

impliceert logisch als en slechts als

elke relatie (over U) die beantwoord aan elke FA binnen ook elke FA binnenbeantwoord.

Notatie: =

Axiomas

Reflexiviteit: if then
Augmentatie: if then
Transitiviteit: if & then 1

Door deze regels te hanteren kunnen we nieuwe verzamelingen functionele afhankelijkheden creeeren, genoteerd als -

Armstrong heeft nu bewezen dat - als en slechts als =

Oef1: Let R be a relation of degree n. What is the maximum amount of functional dependencies R can possibly satisfy (trivial as well as nontrivial) ?

Oef2: Define (a) the closure of a set of FD’s; (b) the closure of a set of attributes under a set of FD’s.

Oef3: Onderstaand een set van functionele afhankelijkheden voor de relatie R{A,B,C,D,E,F,G}.

A -> B
BC -> DE
AEF -> G

Bepaal de closure {A,C}* met deze verzameling in gedachten. Is de functionele afhankelijkheid ACF -> DG afleidbaar uit deze verzameling ?

Oef4: Wat betekent het te zeggen dat twee verzamelingen functionele afhankelijkheden F1 en F2 equivalent zijn ? Zijn de onderstaande verzamelingen equivalent ?

1. A-> B AB -> C D -> AC D -> E
2. A -> BC D -> AE

Oef5: wat betekent het om te zeggen dat een verzameling FD’s irreducible is ? Onderstaand is een set FD’s over relatie R{A,B,C,D,E,F}. Vind hiervoor een irreducible set.

AB -> CC -> A

BC -> D
ACD -> B
BE -> C
CE -> FA
CF -> BD
D -> EF

1 Merk op dat deze basis functionele afhankelijkheden verschillend zijn van de drie gegeven in de cursus. Desalnietemin zijn ze hetzelfde.

http://werner.yellowcouch.org/
werner@yellowcouch.org