Functional Dependencies (Part 3)AgendaQuick ReviewFunctional Dependency TheorySlide 5The Closure of a SetDecompositionSlide 8Slide 9Slide 10Multivalued DependenciesThe EndFunctional Dependencies(Part 3)Presented by Nash RaghavanAll page numbers are in reference toDatabase System Concepts (5th Edition)AgendaQuick ReviewWhat is a functional dependencyDifferent normal formsFunctional Dependency TheoryClosure of a Set of DependenciesDecomposition using F.D.Multivalued dependenciesQuick ReviewWhat is a functional dependency?SSN → Name “Name is functionally dependent on SSN”Given a relation R, if , then must be the same whenever is the same for all tuples in RFirst Normal FormDomains of all attributes in relation R are atomicPage 269Boyce-Codd Normal FormFor all functional dependencies , is a superkeyPage 272Functional Dependency TheoryArmstrong’s axioms (page 279)Reflexivity rule: If , then holdsExample: A A , BCD BCAugmentation rule: If , then Example: A B, therefore AC BCTransitivity: If and then Example: A B and B C then A CFunctional Dependency TheoryAdditional rules (page 280)Union rule: If and then Example: If A B and A C then A BCDecomposition rule: If , then and Example: A BC, then A B and A CPseudo-transitivity: If and then Example: A B and BD C then AD CThe Closure of a SetWhy do we care about the axioms?Given a set of functional dependencies denoted by F{ A B, A C, CG H, CG I, B H }We can now determine logically implied functional dependencies such as A HThe set of all functional dependencies implied by F is denoted by F+ and is called the closure of FSee page 279 for more detailsDecompositionThe ability to compute F+ enables us to convert a relation R into any normal formExample: BCNF DecompositionSee pages 289 – 290lending = ( branch_name, branch_city, assets, customer_name, loan_number, amount )Candidate Key: { loan_number, customer_name }Functional Dependencies:branch_name assets branch_cityloan_number amount branch_nameDecompositionThe problembranch_name assets branch_cityValid but branch_name is not a superkey, therefore it is not in BCNF!The solution – decomposition!lending = ( branch_name, branch_city, assets, customer_name, loan_number, amount )Decomposes to multiple relations:branch = ( branch_name, branch_city, assets )loan_info = ( branch_name, customer_name, loan_number, amount )Decompositionbranch relation is now in BCNF but loan_info is not because loan_number is not a superkey given the following dependency:loan_number amount branch_nameSolution is to iteratively decompose relations until all relations are in desired form.To complete solution, decompose loan_info to:loanb = ( loan_number, branch_name, amount )borrower = ( customer_name, loan_number )DecompositionThe beginning:lending = ( branch_name, branch_city, assets, customer_name, loan_number, amount )The end result:branch = ( branch_name, branch_city, assets )loanb = ( loan_number, branch_name, amount )borrower = ( customer_name, loan_number )The Original Functional Dependencies:branch_name assets branch_cityloan_number amount branch_nameEverything is now in BCNF!Multivalued DependenciesA multivalued dependency, denoted: Means a tuple must exist for every value in Example: class booksClass = { CS 157, CS 46 }Books = { Manual, Solution }CID class books10 CS 46 Manual10 CS 46 Solution20 CS 157 Manual20 CS 157 SolutionMultivalued dependencies result in duplicate data and are considered “tuple-generating dependencies”.Formal definition – see page 295The EndThis information will become relevant … eventually.Makes more sense when we study:Database design/creationNormalizationBCNF, 1NF, 2NF, 3NF,
View Full Document
Unlocking...