Determine if relation is in BCNF form?

Question

How do I determine if the following relation is in BCNF form?

R(U,V,W,X,Y,Z)

UVW ->X
VW -> YU
VWY ->Z

I understand that for a functional dependency A->B A must be a superkey. And the relation must be in 3NF form. But I am unsure how to apply the concepts.

Answer 1

To determine if a relation is in BCNF, for the definition you should check that for each non-trivial dependency in F+, that is, for all the dependencies specified (F) and those derived from them, the determinant should be a superkey. Fortunately, there is a theorem that says that it is sufficient perform this check only for the specified dependencies.

In your case this means that you must check if UVW, VW and VWY are superkeys.

And to see if in a dependency X -> Y the set attributes X is a superkey you can compute the closure of the attributes (X+) and check if it contains the right hand part Y.

So you have to compute UVW+ and see if it contains {U,V,W,X,Y,Z} and similarly for the other two dependencies. I leave to you this simple exercise.

Answer 2

Using the algorithm to compute the closure of a given set of attributes and the definition of BCNF as shown in the following figure,

we can implement the above algorithm in python to compute closure of attributes and then determine whether a given set of attributes forms a superkey or not, as shown in the following code snippet:

def closure(s, fds):
    c = s
    for f in fds:
        l, r = f[0], f[1]
        if l.issubset(c):
            c = c.union(r)
    if s != c:
        c = closure(c, fds)
    return c

def is_superkey(s, rel, fds):
    c = closure(s, fds)
    print(f'({"".join(sorted(s))})+ = {"".join(sorted(c))}')
    return c == rel

Now check if for each given FD A -> B from relation R, A is a superkey or not, to determine whether R is in BCNF or not:

def is_in_BCNF(rel, fds):
   for fd in fds:
      l, r = fd[0], fd[1]
      isk = is_superkey(l, rel, fds)
      print(f'For the Functional Dependency {"".join(sorted(l))} -> {"".join(sorted(r))}, ' +\
                  f'{"".join(sorted(l))} {"is" if isk else "is not"} a superkey')
      if not isk:
         print('=> R not in BCNF!')
         return False
   print('=> R in BCNF!')  
   return True 

To process the given FDs in standard form, to convert to suitable data structure, we can use the following function:

import re

def process_fds(fds):
    pfds = []
    for fd in fds:
        fd = re.sub('\s+', '', fd)
        l, r = fd.split('->')
        pfds.append([set(list(l)), set(list(r))])
    return pfds

Now, let's test with a couple of relations:

relation = {'U','V','W','X','Y','Z'}
fds = process_fds(['UVW->X', 'VW->YU', 'VWY->Z'])
is_in_BCNF(relation, fds)

# (UVW)+ = UVWXYZ
# For the Functional Dependency UVW -> X, UVW is a superkey
# (VW)+ = UVWXYZ
# For the Functional Dependency VW -> UY, VW is a superkey
# (VWY)+ = UVWXYZ
# For the Functional Dependency VWY -> Z, VWY is a superkey
# => R in BCNF!

relation = {'A','B','C'}
fds = process_fds(['A -> BC', 'B -> A'])
is_in_BCNF(relation, fds)

# (A)+ = ABC
# For the Functional Dependency A -> BC, A is a superkey
# (B)+ = ABC
# For the Functional Dependency B -> A, B is a superkey
# => R in BCNF!