Functional DependencyDefinitionIn other words….ExampleKeysClosureSlide 7AxiomsAxioms Cont.Derived Theorems from AxiomsBack to the ExampleToo Many FDsThe approachBack To Our ExampleNormal FormFunctional Functional DependencyDependencyRajhdeep JandirRajhdeep JandirDefinitionDefinitionA functional dependency is defined as a A functional dependency is defined as a constraint between two sets of constraint between two sets of attributes in a relation from a attributes in a relation from a database.database.Given a relation Given a relation RR, a set of , a set of attributesattributes XX in in RR is said to is said to functionally determinefunctionally determine another attribute another attribute YY, also in , also in RR, (written , (written XX → → YY) ) if and only ifif and only if each each XX value is value is associated with at most one associated with at most one YY value. value.In other words….In other words….XX is the is the determinant setdeterminant set and and YY is the is the dependent attributedependent attribute. Thus, given a . Thus, given a tupletuple and the values of the attributes and the values of the attributes in in XX, one can determine the , one can determine the corresponding value of the corresponding value of the YY attribute. attribute.ExampleExampleEmployee Employee SSNSSNNameNameJobTypeJobTypeDeptNameDeptName557-78-557-78-65876587Lance Lance SmithSmithAccountanAccountanttSalarySalary214-45-214-45-23982398Lance Lance SmithSmithEngineerEngineerProductProductNote: Name is functionally dependent on SSN because an employee’s name can be uniquely determined from their SSN. Name does not determine SSN, because more than one employee can have the same name..KeysKeysWhereas a key is a set of attributes that Whereas a key is a set of attributes that uniquely identifies an entire tuple, a uniquely identifies an entire tuple, a functional dependency allows us to functional dependency allows us to express constraints that uniquely identify express constraints that uniquely identify the values of certain attributes. the values of certain attributes. However, a candidate key is always a However, a candidate key is always a determinant, but a determinant doesn’t determinant, but a determinant doesn’t need to be a key. need to be a key.ClosureClosureLet a relation Let a relation RR have some functional have some functional dependencies dependencies FF specified. The specified. The closure of Fclosure of F (usually written as (usually written as F+F+) is the set of all functional ) is the set of all functional dependencies that may be logically derived from dependencies that may be logically derived from FF. Often . Often FF is the set of most obvious and is the set of most obvious and important functional dependencies and important functional dependencies and F+F+, the , the closure, is the set of all the functional closure, is the set of all the functional dependencies including dependencies including FF and those that can be and those that can be deduced from deduced from FF. The closure is important and . The closure is important and may, for example, be needed in finding one or may, for example, be needed in finding one or more candidate keys of the relation. more candidate keys of the relation.ExampleExample StudentStudentSNoSNoSNaSNamemeCNoCNoCNamCNameeAddrAddrInstr.Instr.OfficOfficee54255425SusaSusan n RossRoss102102Calc ICalc I……San San Jose, Jose, CACAP. P. SmitSmithhB42 B42 RooRoom m 11211278457845DaveDaveTurcTurcoo541541Bio Bio 1010......SaSan n DiegDiego, o, CACAL. L. TalipTalipB24 B24 RooRoom m 210 210 SNo -> SName CNo -> CName Instr -> OfficeSNo -> Addr CNo -> InstrAxiomsAxiomsBefore we can determine the closure Before we can determine the closure of the relation, Student, we need a of the relation, Student, we need a set of rules. set of rules. Developed by Armstrong in 1974, Developed by Armstrong in 1974, there are six rules (axioms) that all there are six rules (axioms) that all possible functional dependencies possible functional dependencies may be derived from them. may be derived from them.Axioms Cont.Axioms Cont.1. Reflexivity Rule1. Reflexivity Rule --- If --- If XX is a set of is a set of attributes and attributes and YY is a subset of is a subset of XX, then , then X X Y Y holds. holds. each subset of each subset of XX is functionally dependent on is functionally dependent on XX. . 2.2. Augmentation RuleAugmentation Rule --- If --- If X X Y Y holds holds and and WW is a set of attributes, then is a set of attributes, then WX WX WY WY holds. holds. 3. Transitivity Rule3. Transitivity Rule --- If --- If X X Y Y and and Y Y ZZ holds, then holds, then X X Z Z holds. holds.Derived Theorems from Derived Theorems from AxiomsAxioms4. 4. Union RuleUnion Rule --- If --- If X X Y Y and and X X Z Z holds, then holds, then X X YZ YZ holds. holds. 5. 5. Decomposition RuleDecomposition Rule --- If --- If X X YZ YZ holds, then so do holds, then so do X X Y Y and and X X Z Z. . 6. 6. Pseudotransitivity RulePseudotransitivity Rule --- If --- If X X Y Y and and WY WY Z Z hold then so does hold then so does WX WX Z Z. .Back to the ExampleBack to the ExampleSNoSNoSNaSNamemeCNoCNoCNaCNamemeAddrAddrInstr.Instr.OfficOfficeeBased on the rules provided, the following dependencies can be derived.(SNo, CNo) SNo (Rule 1) -- subset (SNo, CNo) CNo (Rule 1) (SNo, CNo) (SName, CName) (Rule 2) -- augmentationCNo office (Rule 3) -- transitivitySNo (SName, address) (Union Rule) etc.Too Many FDsToo Many FDsUsing the first rule alone, from our example Using the first rule alone, from our example we have 2^7 = 128 subsets. This will we have 2^7 = 128 subsets. This will further lead to many more functional further lead to many more functional dependencies. This defeats the purpose of dependencies. This defeats the purpose of normalizing relations. normalizing relations. So what now?So what now?One way is to deal with one attribute or a One way is to deal with one attribute or a set of attributes at a time and find its set of attributes at a time and find its closure (i.e. all functional dependencies closure (i.e. all functional dependencies relating to them). The aim of this exercise relating to them). The aim of this exercise is to find what attributes depend on a is to find what
View Full Document
Unlocking...