Functional dependencies
The functional dependency X → Y, what data can refute, Armstrong's axioms, the closure of a set of attributes, the superkeys and candidate keys it gives, and the minimal cover.
- 25 cards
- 4 topics
- Free
The outline, topic by topic
Each topic is weighted the way the exam weighs it.
- Concepts
- Questions
- Sort and link
- Understand
A few cards from the deck
Functional dependency: what is it?
Show the answer
A constraint X → Y on a relation: two rows that share the same value of X must share the same value of Y.
It is a rule of the domain, not a fact observed in the data:
id_client → villeholds if a customer has only one city, whatever rows are present today.Let R(A, B, C, D, E) have the dependencies A → B, B → C and CD → E. What is the closure of {A, D}?
{A, B, C, D, E}{A, B, D}{A, D, E}{A, B, C, D}
Show the answer
{A, B, C, D, E}A → B adds B, then B → C adds C, and since C and D are both present, CD → E adds E. Forgetting the last round gives
{A, B, C, D}.A dependency X → Y is … when Y is included in X; it is then always true, by the axiom of ….
Show the answer
A dependency X → Y is trivial when Y is included in X; it is then always true, by the axiom of reflexivity.
{A, B} → Asays nothing: two rows that share A and B obviously share A.Armstrong's axioms: what is it?
Show the answer
Three inference rules (reflexivity, augmentation, transitivity) that let you derive every dependency implied by a given set.
They are sound (they only produce true dependencies) and complete (they produce all of them): every other rule, such as union, follows from them.
Why is computing the closure of X enough to know whether X is a superkey?
- If X⁺ contains every attribute, X determines the whole row, so two rows that agree on X are the same row
- The closure counts the table's rows and checks that X has no duplicates
- The closure is the list of every candidate key that contains X
- A closure larger than X proves that X is minimal
Show the answer
If X⁺ contains every attribute, X determines the whole row, so two rows that agree on X are the same row
The closure only looks at the dependencies, never at the rows. It says what X determines; minimality is tested separately, by removing one attribute at a time.