University Database Relation Schema
inst_dept ( id, name, salary , dept_name, building, budget )
should be :
instructor ( id, name, salary , dept_name )
department (dept_name, building, budget )
Lossless Decomposition
Testing for Lossless Decomposition
R1 and R2 form a lossless decomposition on R if at least one of the following FDs appear in F+
R1 ∩ R2 ® R1
R1 ∩ R2 ® R2
· In other words:
o Which attributes appear in BOTH relations ?
o Are those attributes a superkey of either one of the relations?
Functional Dependencies
* A Functional Dependency describes a relationship between attributes in a relation.
* A set of attributes is functionally dependant on another if
We can use the values of one set of attributes in a tuple (the key) to determine (ie, uniquely identify)
the values of another set of attributes in the same tuple
Each set of values for ALPHA uniquely determines precisely one set of values for BETA.
* determinant - the attributes on the left hand side of the functional dependency ( a )
* dependent - the attribute on the right side of the functional dependency ( b )
* a determinant is an attribute or a group of attributes that establish the value of other attributes
* dependent attributes are uniquely identified by the attributes of the determinant
· A functional dependency is a generalization of the notion of a key.
· Given a functional dependency, a → b ,
o If the determinate a, determines ALL the other attributes defined in the relation
§ a is a superkey
o If determinate a is a superkey
o Key fields are all the individual attributes is a
o Non-key field is defined to be (b - a)
§ Attributes in b that are not also in a
Normal Forms:
· 1NF - First Normal Form
o A relation R is in 1NF if the DOMAINS of all attributes of R are ATOMIC (simple values)
o 1NF is violated when there are composite or multi-valued attributes
o Remove repeating values into new relation and flatten composite attributes
· 2NF - Second Normal Form
o No functional dependencies on part of the key; must depend on ALL attributes in the a
o 2NF is violated when a non-key field depends on part of a instead of ALL of a.
o Move non-key field into a new relation and add its candidate key
· 3NF – Third Normal Form
o All non-key attributes must be mutually independent
§ ALL attributes in b are contained in a (trivial dependency)
§ a is a superkey
§ All attributes in b - that are not in a - must be contained in SOME candidate key.
o Non-key attributes may not be functionally dependent on other non-key attributes
§ 3NF is violated when a non-key field is a fact about another non-key field
o Move transitively dependent non-key fields into a new relation with its candidate key
· BCNF – Boyce-Codd Normal Form
o Every non-trivial functional dependency in the table is a dependency on a superkey
§ Attributes in b are contained in the key (trivial dependency)
§ a is a superkey
o BCNF is violated when a determinate is not a candidate key
o Create new relation with the old non-key determinate as the new key
Armstrong’s Axioms:
if b ⊆ a then a → b (reflexivity)
if a → b then g a → g b (augmentation)
if a → b and B → C then a → g (transitivity)
Derived Axioms:
if a → b and a → g then a → b g (union)
if a → b C then a → b and a → g (decomposition)
if a → b and g b → d then a g → d (pseudotransitivity)
These Axioms are :
· sound – If used correctly, inferences are guaranteed to give a correct result
· complete – will generate ALL other possible functional dependencies
Closure on a Set of Functional Dependencies – F+:
The set of ALL functional dependencies that may be implied given the set of functional dependencies in F.
Implied functional dependencies are inferred using Armstrong’s Axioms and their derivatives.
F+ is a super set of F.
a+ : The Closure of a under F
The set of all attributes functionally determined by a in the set of functional dependencies F.
Algorithm for Computing Closure of A under F
result := A
repeat for each B → C in F
if B ⊆ result then
result := result + C
end loop
Uses for Computing the Closure of A under F
· Test if a a super key for R
o if a+ on F contains ALL the attributes of R, it is a super key
· Test if Is a → b in F+
o if b is in a+, then a → b is in F+
· Find F+ (ie, an easier way to computer F+ not using Axioms)
o for every set of attributes g in R
§ compute closure on g
o output a functional dependency g → S for every attribute in g+
Finding Extraneous Attributes in F
F – original set of Functional Dependencies
a → b – a particular functional dependency in F that may contain an extraneous attribute
F’ – revised set of Functional Dependencies with A removed from a or b
|
If extraneous attribute A is in : |
|
|
a |
b |
|
Remove attribute from a |
Remove attribute from b |
|
F’ is revised set of FDs with A removed |
F’ is revised set of FDs with A removed |
|
Prove F → F ’ using Axioms |
Prove F |
|
OR Compute (revised) a+ under F |
OR Compute (original) a+ under F ‘ |
If the removed attribute still appears in the result set, the attribute is extraneous.
Canonical Cover Fc for F
· Fc → F and F → Fc They are logically equivalent
· Fc has the following properties for each a → b
o No extraneous attributes in a
o No extraneous attributes in b
o Each a is unique
Computing Cover Fc for F
Fc := F
repeat
union - Replace a1 → b1 and a1 → b2 with a1 → b1 b2
Remove - all extraneous attributes from a and b using current Fc
until Fc does not change
Example of Computing Cover Fc for F using Axioms
R = ( A, B, C )
Fc = { A->BC, B->C, A->B, AB->C } Fc = F
repeat
union
Replace A → B and A → BC with A → BC
Fc is now { A->BC, B->C, AB->C }
Remove
A from AB -> C. Becomes B -> C (LHS)
Prove that old Fc = { A->BC, B->C, AB->C } infers B->C
B->C is already in the set and is entirely redundant – OK
Fc is now { A->BC, B->C }
C from A->BC. Becomes A->B (RHS)
Prove that new F’ = { A->B, B->C } infers A->BC
Since A->B and B->C then A->BC; - OK
Fc = { A->C, B->C }
until Fc does not change
Computing Cover Fc for F using Closure of Attributes
1. Make sure ALL dependencies have singleton right hand sides
a. Using decomposition, split all FDs so that there is only one attribute on the right hand side
2. Remove extraneous attributes on the left hand side
a. Look for FDs that have 2 or more attributes on the LHS
b. Compute closure of attributes for EACH of those attributes
c. If any one of the attributes appears in the closure of the other attributes, it is extraneous
i. It can be removed from that FD
d. Do ONE FD at a time
3. Remove redundant FDs from those that are remaining
a. Compute the closure on all the attributes on the left hand side
i. Do NOT include that FD when you compute the closure for those attributes
b. If the attribute on the right hand side of that FD appears in the closure, that FD is redundant
i. Remove it from the FD
c. Do ONE FD at a time
Dependency Preservation
Testing for Dependency Preservation
1. Decompose relations into BCNF
2. Are there any FDs in F for which ALL of the attributes in a and b do not appear in a single relation?
a. Yes – decomposition is NOT dependency preserving
For each a → b in F
result := a
repeat for each Ri ( i.e., relation) in the decomposition
t = Ri ∩ result get attributes in Ri that are already in the result set
t = t+ compute the closure of those attributes on F
t = t ∩ Ri get attributes from the closure that are in Ri
result := result U t add those attributes to the result
until result does not change
If result contains ALL attributes in , the dependency is preserved
BCNF
Testing for BCNF in R
1. Compute a+ for each FD in F
2. FD passes the test if ONE of the following is true
a. FD is trivial - All b attributes are also in a
b. a is a superkey for R - a+ contains ALL the attributes in R
Testing for BCNF in Ri
1. Find all FDs whose attributes ALL appear in Ri, which we call Fi
2. For each in Fi compute a+ using the original set F
3. The FD passes the test if ONE of the following holds
a. If a+ contains ALL the attributes in Ri
b. a+ does NOT contain any attributes that are in Ri but not in a
Decomposition into BCNF - Algorithm
1. Compute F+
2. For every relation in the decomposition Ri
a. For any a ® b that is in Fi
i. Test the FD for the following
1. a is NOT a superkey of Ri based on F+
2. a does not share any attributes with b
ii. Decompose Ri by
1. Removing b attributes from Ri
2. Create new relation using (a, b)
3NF
Testing for 3NF in R
1. Compute a+ for each FD in F
2. FD passes the test if ONE of the following is true
a. FD is trivial - All b attributes are also in a
b. a is a superkey for R - a+ contains ALL the attributes in R
c. b - a is contained in a candidate key for R - attributes in b but not in a appear in some candidate key
Decomposition into 3NF - Algorithm
1. Compute Fc
2. For every relation in the decomposition Ri
a. For any a ® b that is in Fc
i. If no Ri exists that contains ALL a attributes and ALL b attributes
1. Create a new Ri consisting of (a , b)
ii. If none of the Ri’s contains a candidate key for the original relation
1. Create a new relation consisting of a candidate key
iii. If there are any redundant schemas whose attributes all appear in other relations
1. Delete that schema