Week 6 Lecture 2

Non-intersecting decompositions

When there is no intersection, decomposition tends to be lossy. This is because there are no common attributes to impose constraints on combinations.

Lossless decompositions

Natural Join is a special case of the Cartesian Product with constraints.

Natural join algorithm:

  • Take a pair of tuples [t1, t2] from the respective tables
  • Add their combination to the result if they match on the common attributes.

If there are no common attributes, all combinations across decomposed tables will be included in the result. Even if there are common attributes, there may be incorrect combinations in the result. A lossless join decomposition is achieve if the correct set of common attributes is selected.

Functional dependencies

A functional dependency A -> B is said to exist when each value (combination) of A is associated with one value (combination) of B

The functional dependency A -> B is said to exist when each value of A is associated with a unique value of B.

Screenshot-2017-11-2-week6-02-pptx.png

Heath's theorem

A take [U, X, Y] that satisfies a functional dependency X -> Y can always be losslessly decomposed into [U, X] and [X, Y].

Functional dependencies and keys

A -> B: Each value of A is associated with a unique value of B. Each attribute is functionally dependent on the key of the table, by definition.

Union rule

A -> B C holds if and only if A -> B and A -> C hold.

Screenshot-2017-11-2-week6-02-pptx(1).png

Sets on the left side

The left hand side of a functional dependency could be a set: A B -> C. Each combination of values of A and B, is associated with one value of C.

A B -> C does not mean A -> C and B -> C hold. X -> Y Z on the other hand, does mean that X -> Y and X -> Z holds.

Trivial functional dependencies

A functional dependency A -> B is trivial if B is a subset of A.

  • A B -> A
  • A B -> B
  • A B -> A B
  • A -> A

Augmentation rule

If A -> B holds, A C -> B C also holds for any attribute C.

Screenshot-2017-11-2-week6-02-pptx(2).png

Transitivity Rule

If A -> B and B -> C hold, then A -> C holds.