# 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`

.

In all legal tables involving `A`

and `B`

, whenever two rows take the same values on attribute `A`

, they also take the same values on attribute `B`

.

#### 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.

#### 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`

.

#### Transitivity Rule

If `A -> B`

and `B -> C`

hold, then `A -> C`

holds.

## No Comments