Functional DependancyCharacteristicsKeysUses for Functional DependancyTermsFunctional Dependency Theory: ClosureClosure Rules of InferenceClosure Rules of Inference Cont.Boyce Codd Normal FormDecomposition into BCNFExampleThird Normal FormDecomposition into 3NFSlide 14Fourth Normal FormDecomposition into 4NFSlide 17Resources:Functional DependancyDefinition:–constraints on relations–characteristic of an attribute where values are determined by another attribute’s valuesNotation:–α→β (α determines β)–(α→β may take the form AB→C, A→BC, etc.)CharacteristicsFunctional dependency holds if:–t1[β] = t2[β] where t1[α] = t2[α];β is functionally dependent on α if value of α in tuples t1 and t2 determines value of β in tuples t1 and t2.–Or, for each value of α, there is only 1 corresponding value of β.KeysKeys:–consist of single or multiple attributes that determine the values of non-key attributes.Superkey:–A chosen set of attributes that has closure over relation R.Candidate key:–A possible set of attributes that has closure over relation R.Uses for Functional Dependancy•To determine if a relation is in a Normal Form.•To specify constraints on the set of legal relations (functional dependencies to focus on)•To determine if a decomposition would cause data loss (R decomposed to R1 and R2 but, R1 |X| R2 ≠ R)TermsTrivial:–A→A and AB→A are trivial because A is a subset of A and ABSatisfy/Hold:–Relation R satisfies functional dependency α→β if t1[β] = t2[β] wherever t1[α] = t2[α]; conversely functional dependency α→β holds on relation R.Functional Dependency Theory: ClosureDefinition:–the set of all functional dependencies that logically implied by those in a set F.Notation:–F+ (closure in functional dependency set F)–α+ (closure of the attribute set α under F; used to determine if α is a superkey)–Fc (canonical cover implied by F that excludes extraneous attributes)Closure Rules of Inference•Armstrong’s Axioms:–Reflexivity rule:•if α is a set of attributes and β is contained in α then α→β•i.e. given AB→C, then A→B–Augmentation rule:•given α→β and another set of attributes γ, then γα→γβ–Transitivity rule:•if α→β and β→γ , then α→γClosure Rules of Inference Cont.•Other Rules:–Union rule:•if α→β and α→γ , then α→βγ–Decomposition rule:•if α→βγ , then α→β and α→γ–Pseudotransitivity rule:•if α→β and γβ→δ , then γα→δBoyce Codd Normal Form•Eliminates all redundancy based on functional dependancy α→β in closure F+.•Conditions (at least one):–β is a subset of α–α is a superkey for relation R (α+ has closure over R or all attributes of R)Decomposition into BCNF•If α→β and relation R is not in BCNF,decompose R into two relations (α U β) and (R - (β - α))•if decompositions are not in BCNF, repeatExample•Given relation R(A, B, C)–AB is the Superkey, B alone is not–if F = {(B→C)} required to hold, then R is not in BCNF; R decomposes to (B,C) and (A,B)–if F = {(A→B), (B→C)} required to hold, thenF+ = {(A→B), (B→C), (A→C), (AB→C)}, andFc = {(AB→C)}; R is in BCNFThird Normal Form•Preserves functional dependency•Conditions (at least one):–In BCNF•β is a subset of α•α is a superkey for relation R–each attribute in (β - α) is contained in a candidate keyDecomposition into 3NF•Same as with BCNF•does not require decomposition if each attribute in β, but not in α, is contained in a candidate keyExample•Given relation R(A, B, C, D)–AB is the Superkey, BC is a candidate key–if F = {(A→C)} required to hold, R is in 3NF since C - A exists in BC; no decomposition requiredFourth Normal Form•Conditions:–In BCNF•β is a subset of α•α is a superkey for relation R–Decomposition also based on functional dependencies involving multivalued attributesDecomposition into 4NF•Same as with BCNF•treat dependencies involving multivalued attributes as part of the constraints(text says the opposite - treat functional dependencies as multivalued dependencies, then use all multivalued dependencies as contraints)Example•Given relation R(A, B, C, D)–AB is the Superkey, D is multivalued and B→D–if F = {(A→C)} required to hold, then treat as F = {(A→C), (B→D)}–R is not in 4NF; R decomposes to (A,C) and (A,B,D); (A,B,D) is not in 4NF, so decompose again to (B,D) and (A,B).Result: {(A,C), (B,D), (A,B)}Resources:•Silberschatz, A. Korth, H. Sudarshan, S. (2006). Database System concepts. New York: New
View Full Document
Unlocking...