8. Functional Dependencies

Question 1

Functional Dependency (FD):

Answer 1

A constraint denoted by X → Y, where X (LHS) and Y (RHS) are sets of attributes in a relation R. It specifies that for any two tuples, if they have the same values for attributes in X, they must have the same values for attributes in Y. X determines Y, or Y is functionally dependent on X.

Question 2

Inference Rules (Armstrong’s Axioms):

Answer 2

A set of rules used to infer additional FDs implied by a given set F.
◦ Reflexive: If Y ⊆ X, then X → Y.
◦ Augmentation: If X → Y, then XZ → YZ and XZ → Y (for any Z).
◦ Transitive: If {X → Y, Y → Z}, then X → Z.
◦ Decomposition (Projective): If X → YZ, then X → Y and X → Z.
◦ Union (Additive): If {X → Y, X → Z}, then X → YZ.
◦ Pseudotransitive: If {X → Y, WY → Z}, then WX → Z.

Question 3

Closure of FDs (F+):

Answer 3

The set of all FDs that can be inferred from a given set F using the inference rules.

Question 4

Closure of Attributes (X+):

Answer 4

Given a set of FDs F and a set of attributes X, X+ is the maximal set of attributes determined by X. Algorithm: Start with X, repeatedly add attributes determined by any set of attributes currently in X+ based on the FDs in F.

Question 5

Redundant FD:

Answer 5

An FD X → Y in a set F is redundant if it can be inferred from the other FDs in F (i.e., F+ = (F - {X → Y})+).

Question 6

Minimal Cover:

Answer 6

A set of FDs F is minimal (irreducible) if every RHS is a single attribute, every LHS is irreducible (no redundant attributes), and no FD in F is redundant. An algorithm exists to compute a minimal cover for any set of FDs.