DOC PREVIEW
Berkeley COMPSCI 186 - Functional Dependencies

This preview shows page 1-2-3-4-5 out of 16 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 16 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 16 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 16 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 16 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 16 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 16 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Functional DependenciesReview: Database DesignThe Evils of RedundancyFunctional Dependencies (FDs)FD’s ContinuedExample: Constraints on Entity SetProblems Due to R  WDetecting ReduncancyDecomposing a RelationRefining an ER DiagramReasoning About FDsRules of InferenceExampleAttribute ClosureAttribute Closure (example)Next Class…Functional DependenciesR&G Chapter 19Lecture 13Science is the knowledge of consequences, and dependence of one fact upon another. Thomas Hobbes (1588-1679)Review: Database Design•Requirements Analysis– user needs; what must database do?•Conceptual Design– high level descr (often done w/ER model)•Logical Design– translate ER into DBMS data model•Schema Refinement – consistency,normalization•Physical Design - indexes, disk layout•Security Design - who accesses whatThe Evils of Redundancy•Redundancy is at the root of several problems associated with relational schemas:–redundant storage, insert/delete/update anomalies•Integrity constraints, in particular functional dependencies, can be used to identify schemas with such problems and to suggest refinements.•Main refinement technique: decomposition –replacing ABCD with, say, AB and BCD, or ACD and ABD.•Decomposition should be used judiciously:–Is there reason to decompose a relation?–What problems (if any) does the decomposition cause?Functional Dependencies (FDs)•A functional dependency X  Y holds over relation schema R if, for every allowable instance r of R: t1  r, t2  r, X (t1) = X (t2) implies Y (t1) = Y (t2)(where t1 and t2 are tuples;X and Y are sets of attributes)•In other words: X  Y means Given any two tuples in r, if the X values are the same, then the Y values must also be the same. (but not vice versa)•Can read “” as “determines”FD’s Continued•An FD is a statement about all allowable relations.–Must be identified based on semantics of application.–Given some instance r1 of R, we can check if r1 violates some FD f, but we cannot determine if f holds over R.•Question: How related to keys?•if “K  all attributes of R” then K is a superkey for R(does not require K to be minimal.)•FDs are a generalization of keys.Example: Constraints on Entity Set•Consider relation obtained from Hourly_Emps: Hourly_Emps (ssn, name, lot, rating, wage_per_hr, hrs_per_wk)•We sometimes denote a relation schema by listing the attributes: e.g., SNLRWH•This is really the set of attributes {S,N,L,R,W,H}.•Sometimes, we refer to the set of all attributes of a relation by using the relation name. e.g., “Hourly_Emps” for SNLRWHWhat are some FDs on Hourly_Emps?ssn is the key: S  SNLRWH rating determines wage_per_hr: R  Wlot determines lot: L  L (“trivial” dependnency)Problems Due to R  W•Update anomaly: Can we modify W in only the 1st tuple of SNLRWH?•Insertion anomaly: What if we want to insert an employee and don’t know the hourly wage for his or her rating? (or we get it wrong?)•Deletion anomaly: If we delete all employees with rating 5, we lose the information about the wage for rating 5! S N L R W H123-22-3666 Attishoo 48 8 10 40231-31-5368 Smiley 22 8 10 30131-24-3650 Smethurst 35 5 7 30434-26-3751 Guldu 35 5 7 32612-67-4134 Madayan 35 8 10 40Hourly_EmpsDetecting ReduncancyS N L R W H123-22-3666 Attishoo 48 8 10 40231-31-5368 Smiley 22 8 10 30131-24-3650 Smethurst 35 5 7 30434-26-3751 Guldu 35 5 7 32612-67-4134 Madayan 35 8 10 40Hourly_EmpsQ: Why was R  W problematic, but S W not?Decomposing a Relation•Redundancy can be removed by “chopping” the relation into pieces.•FD’s are used to drive this process.R  W is causing the problems, so decompose SNLRWH into what relations?S N L R H123-22-3666 Attishoo 48 8 40231-31-5368 Smiley 22 8 30131-24-3650 Smethurst 35 5 30434-26-3751 Guldu 35 5 32612-67-4134 Madayan 35 8 40R W8 105 7Hourly_Emps2WagesRefining an ER Diagram•1st diagram becomes: Workers(S,N,L,D,Si) Departments(D,M,B)–Lots associated with workers.•Suppose all workers in a dept are assigned the same lot: D  L•Redundancy; fixed by: Workers2(S,N,D,Si) Dept_Lots(D,L) Departments(D,M,B)•Can fine-tune this: Workers2(S,N,D,Si) Departments(D,M,B,L) lotdnamebudgetdidsincenameWorks_InDepartmentsEmployeesssnlotdnamebudgetdidsincenameWorks_InDepartmentsEmployeesssnBefore:After:Reasoning About FDs•Given some FDs, we can usually infer additional FDs:title  studio, star implies title  studio and title  star title  studio and title  star implies title  studio, startitle  studio, studio  star implies title  starBut, title, star  studio does NOT necessarily imply that title  studio or that star  studio•An FD f is implied by a set of FDs F if f holds whenever all FDs in F hold.•F+ = closure of F is the set of all FDs that are implied by F. (includes “trivial dependencies”)Rules of Inference•Armstrong’s Axioms (X, Y, Z are sets of attributes):–Reflexivity: If X  Y, then X  Y –Augmentation: If X  Y, then XZ  YZ for any Z–Transitivity: If X  Y and Y  Z, then X  Z•These are sound and complete inference rules for FDs!–i.e., using AA you can compute all the FDs in F+ and only these FDs.•Some additional rules (that follow from AA):–Union: If X  Y and X  Z, then X  YZ–Decomposition: If X  YZ, then X  Y and X  ZExample•Contracts(cid,sid,jid,did,pid,qty,value), and:–C is the key: C  CSJDPQV–Proj purchases each part using single contract: JP  C–Dept purchases at most 1 part from a supplier: SD  P•Problem: Prove that SDJ is a key for Contracts•JP  C, C  CSJDPQV imply JP  CSJDPQV(by transitivity) (shows that JP is a key)•SD  P implies SDJ  JP (by augmentation)•SDJ  JP, JP  CSJDPQV imply SDJ  CSJDPQV (by transitivity) thus SDJ is a key.Q: can you now infer that SD  CSDPQV (i.e., drop J on both sides)?No! FD inference is not like arithmetic multiplication.Attribute Closure•Computing the closure of a set of FDs can be expensive. (Size of closure is exponential in # attrs!)•Typically, we just want to check if a given FD X  Y is in the closure of a set of FDs F. An efficient check:–Compute attribute closure of X (denoted X+) wrt F. X+ = Set of all attributes A such that X  A is in F+•X+ := X•Repeat


View Full Document

Berkeley COMPSCI 186 - Functional Dependencies

Documents in this Course
Load more
Download Functional Dependencies
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Functional Dependencies and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Functional Dependencies 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?