|< < 34 > >|

BCNF Decomposition — Details

Closure of a set of columns


closure(R: relation, S: set of columns):
    assert S ⊆ R.columns
    C = S
    for each FD X → Y of R:
        if X ⊆ C and not(Y ⊆ C):
            C = C ∪ Y
    return C

Intuition

Start with the given set of columns.
Keep adding columns by using FDs pointing to columns not yet included.

|< < 34 > >|