COLUMBIA UNIVERSITY COMS W4111.002

This document clarifies decomposition for functional dependencies.

In BCNF, you perform decomposition based on FDs implied by armstrongâ€™s axioms.

```
DecomposedRelations = { R }
while DecomposedRelations is not empty
R = pop a relation from DecomposedRelations
FR = subset of FDs in R's projection
Does there exist an fd X->Y in FR's closure that violates BCNF?
if yes:
NewRs = decompose R using X->Y
add NewRs to DecomposedRelations
continue while loop
```

Thus, you continue until all fds implied by your set of functional dependencies do not violate BCNF for the decomposition.

```
R: ABCDE
FDS: A->BCDE, BC->A, D->B, C->D
# suppose we first check D->B:
D doesn't determine R, thus we decompose into: BD, ACDE
Let's check BD:
Only D->B is in its projection, thus its in BCNF.
EDIT:
Let's check ACDE:
C determines ACDE, thus is a key
D determines D, and is a trivial fd
BC does not apply
A determines CDE, thus is a key
Thus it's in BCNF
Decomposition: BD, ACDE
```

Here is another way to think about it, in terms of a procedure:

```
For each attribute or combination of attributes in R. Call it _attrs_
Does the closure of _attrs_ contain all attributes in R?
If yes:
continue
Else:
decompose relation wrt _attrs_ and its closure
Recall that _attrs_ --> _attrs_ is trivially true.
```

For instance:

```
Given A->B, B->C, and relation ABCD
Consider A: it determines B, and C, but not D
Decompose using A->B: AB, ACD
Consider A for ACD: it determines C, but not D
Decompose using A->C: AB, AC, AD
```

In 3NF, you first compute the minimal cover of the FDs. Note that the minimal cover may not always be unique. Once you have the minimal cover, the procedure is similar to BCNF, with two key differences

- checking violation of
`X->Y`

in 3NF also allows Y to be part of a key (minimal key). - once you have performed BCNF decomposition, any lost dependencies are added as new relations.