New version page

UTD CS 6360 - Database Design

Pages: 13
Documents in this Course

7 pages

24 pages

7 pages

4 pages

2 pages

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

View Full Document
Do you want full access? Go Premium and unlock all 13 pages.
Do you want full access? Go Premium and unlock all 13 pages.
Do you want full access? Go Premium and unlock all 13 pages.
Do you want full access? Go Premium and unlock all 13 pages.

Unformatted text preview:

!" #Chris Irwin Davis, Ph.D. Email: [email protected] Phone: (972) 883-3574 Oﬃce: ECSS 4.705Chapter 15.1CS-6360 Database Design!" #Notation■In the following discussion, we use an abbreviated notation when discussing functional dependencies. ■We concatenate attribute variables and drop the commas for convenience. ■Hence, ■the FD {X,Y} → {Z} is abbreviated to XY → Z, and ■the FD {X, Y, Z} → {U, V} is abbreviated to XYZ → UV.2!" #Inference Rules■IR1 (reflexive rule): ■If X ⊇ Y, then X →Y. ■IR2 (augmentation rule): ■{X → Y} ⊨ XZ → YZ. ■IR3 (transitive rule): ■{X → Y, Y → Z} ⊨ X → Z.3!" #Inference Rules■IR4 (decomposition, or projective, rule): ■{X → YZ} ⊨ X → Y and X → Z ■IR5 (union, or additive, rule): ■{X → Y, X → Z} ⊨ X → YZ. ■IR6 (pseudo-transitive rule): ■{X → Y, WY → Z} ⊨ WX → Z.4!" #Closure■Definition. For each such set of attributes X, we determine the set X+ of attributes that are functionally determined by X based on F; ■X+ is called the closure of X under F. ■Algorithm 16.1 can be used to calculate X+.5!" #Algorithm 15.16!" #Coverage■Definition. A set of functional dependencies F is said to cover another set of functional dependencies E if every FD in E is also in F+ ■That is, if every dependency in E can be inferred from F; ■Alternatively, we can say that E is covered by F. ■Definition. Two sets of functional dependencies E and F are equivalent if E+ = F+. Therefore, equivalence means that every FD in E can be inferred from F, and every FD in F can be inferred from E ■that is, E is equivalent to F if both the conditions—E covers F and F covers E—hold.7!" #Minimal Set of Functional Dependencies■Informally, a minimal cover of a set of functional dependencies E is a set of functional dependencies F that satisfies the property that every dependency in E is in the closure F+ of F. ■In addition, this property is lost if any dependency from the set F is removed ■F must have no redundancies in it, and the dependencies in F are in a standard form.8!" #Minimal Cover■To satisfy these properties, we can formally define a set of functional dependencies F to be minimal if it satisfies the following conditions: ■Every dependency in F has a single attribute for its right-hand side. ■We cannot replace any dependency X → A in F with a dependency Y → A, where Y is a proper subset of X, and still have a set of dependencies that is equivalent to F. ■We cannot remove any dependency from F and still have a set of dependencies that is equivalent to F. 9!" #Minimal Cover (cont’d)■We can think of a minimal set of dependencies as being a set of dependencies in a standard or canonical form and with no redundancies. ■Condition 1 just represents every dependency in a canonical form with a single attribute on the right-hand side. ■Conditions 2 and 3 ensure that there are no redundancies in the dependencies either by: ■having redundant attributes on the left-hand side of a dependency (Condition 2), or ■having a dependency that can be inferred from the remaining FDs in F (Condition 3).10!" #Minimal Cover■Definition. A minimal cover of a set of functional dependencies E is a minimal set of dependencies (in the standard canonical form and without redundancy) that is equivalent to E. We can always find at least one minimal cover F for any set of dependencies E using Algorithm 15.2.11!" #Algorithm 15.2■Let the given set of FDs be E : {B → A, D → A, AB → D}. ■We have to find the minimal cover of E. ■All above dependencies are in canonical form (that is, they have only one attribute on the right-hand side), so we have completed step 1 of Algorithm 16.2 and can proceed to step 2. ■In step 2 we need to determine if AB → D has any redundant attribute on the left-hand side; that is, can it be replaced by B → D or A → D?12!" #■Since B → A, by augmenting with B on both sides (IR2), we have BB → AB, or B → AB (i). However, AB → D as given (ii). ■Hence by the transitive rule (IR3), we get from (i) and (ii), B → D. Thus AB → D may be replaced by B → D. ■We now have a set equivalent to original E, say Eʹ:{B→A, D→A, B→D}. No further reduction is possible in step 2 since all FDs have a single attribute on the left-hand side. ■In step 3 we look for a redundant FD in Eʹ. By using the transitive rule on B → D and D → A, we derive B → A. Hence B → A is redundant in Eʹ and can be eliminated. ■Therefore, the minimal cover of E is {B → D, D →

View Full Document