Functional Dependencies PDF

Functional Dependencies: A functional dependency (FD) is a constraint that requires that the value for a set of attributes uniquely determines the value for another set of attributes. If a functional dependency α → β holds on a relation schema R, then for any legal r...

Functional Dependencies: A functional dependency (FD) is a constraint that requires that the value for a set of attributes uniquely determines the value for another set of attributes. If a functional dependency α → β holds on a relation schema R, then for any legal relations r(R), if two tuples t1 and t2 agree on the attributes α, they also agree on the attributes β. A functional dependency is a generalization of the concept of a key. A specific instance of a relation may satisfy an FD even if the FD does not hold on all legal instances. A functional dependency α → β is trivial if β is a subset of α. o For example, ID, name → ID or name → name. Keys: A superkey K for a relation schema R is such that K → R, meaning that the values of attributes in K determine the values of all attributes in R. A candidate key K for R is a superkey, and no subset of K is also a superkey. Closure of Functional Dependencies: Given a set of FDs, there are other FDs that are logically implied by F. The closure of F, denoted F+, is the set of all FDs logically implied by F. F+ is a superset of F. Armstrong's Axioms can be used to find F+: o Reflexivity: If β is a subset of α, then α → β. o Augmentation: If α → β, then γα → γβ. o Transitivity: If α → β, and β → γ, then α → γ. Additional rules can be inferred from Armstrong’s axioms: o Union: If α → β and α → γ, then α → βγ. o Decomposition: If α → βγ, then α → β and α → γ. o Pseudotransitivity: If α → β and γβ → δ, then αγ → δ. Attribute Set Closure: The closure of a set of attributes α under F, denoted by α+, is the set of attributes that are functionally determined by α under F. An algorithm to compute α+ involves initializing the result to α, and then iteratively adding attributes to the result based on the given FDs until no changes occur. Uses of Attribute Closure: Testing for superkey: To test if α is a superkey, compute α+ and check if it contains all attributes of R. Testing functional dependencies: To check if α → β holds, check if β is a subset of α+. Canonical Cover: A canonical cover Fc for F is a set of dependencies such that: F logically implies all dependencies in Fc, Fc logically implies all dependencies in F, no FD in Fc contains an extraneous attribute, and each left side of the FD in Fc is unique. A canonical cover is a minimal set of FDs equivalent to F, having no redundant dependencies or redundant parts of dependencies. To compute a canonical cover for F, repeatedly apply the union rule to replace dependencies with a single dependency, and find and delete extraneous attributes. Extraneous Attributes: An attribute A is extraneous in α of an FD α → β if A is in α, and F logically implies (F – {α → β}) ∪ {(α – A) → β}. An attribute A is extraneous in β of an FD α → β if A is in β, and (F – {α → β}) ∪ {α → (β – A)} logically implies F. To test if A is extraneous in α, compute (α – A)+ using dependencies in F, and check if (α – A)+ contains β. To test if A is extraneous in β, compute α+ using only the dependencies in F' = (F - {α → β}) ∪ {α → (β - A)}, and check if α+ contains A. Lossless-Join Decomposition: A decomposition of R into R1 and R2 is lossless if at least one of the following dependencies is in F+: R1 ∩ R2 → R1 or R1 ∩ R2 → R2. Dependency Preservation: A decomposition is dependency preserving if (F1 ∪ F2 ∪ … ∪ Fn)+ = F+, where Fi is the set of dependencies in F+ that include only attributes in Ri. If a decomposition is not dependency preserving, checking for FD violations may require expensive joins. Boyce-Codd Normal Form (BCNF): A relation schema R is in BCNF if, for all FDs in F+ of the form α → β, where α is a subset of R and β is a subset of R, at least one of the following holds: o α → β is trivial, or o α is a superkey for R. If a schema is not in BCNF, it can be decomposed into BCNF by creating two new schemas: R1 = (α ∪ β) and R2 = (R - (β - α)). It is not always possible to achieve both BCNF and dependency preservation. Third Normal Form (3NF):  A relation schema R is in 3NF if, for all FDs in F+ of the form α → β, at least one of the following holds: o α → β is trivial, o α is a superkey for R, or o Each attribute A in β - α is contained in a candidate key for R. If a relation is in BCNF, it is also in 3NF. 3NF allows some redundancy but ensures dependency preservation. A decomposition into 3NF is always lossless-join and dependency-preserving. 3NF Decomposition Algorithm: Compute a canonical cover Fc for F. For each FD α → β in Fc, create a schema Ri = αβ if no existing schema Rj contains αβ. If none of the schemas contains a candidate key for R, add a schema with any candidate key for R. Optionally remove redundant schemas. Design Goals: The goal for a relational database design is to achieve BCNF, lossless join, and dependency preservation. If BCNF cannot be achieved while preserving dependencies, accept redundancy using 3NF. SQL does not provide a direct way of specifying functional dependencies other than superkeys.