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.

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.

I'm currently looking for interesting work in the Basel area. If you have a challenging task with regard to data analysis and/or bioinformatics, please drop me a line.
Momentan suche ich Arbeit in der Basler Umgebung. Nehmen Sie bitte kontakt auf falls Sie ein interessantes Problem im zusammenhang mit Bioinformatik und/oder Datenanalyse haben.

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