确定关系是否为 BCNF 形式？

Question

如何判断下面的关系是否为BCNF形式？

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

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

我知道对于函数依赖 A->B A 必须是一个超级键。并且关系必须是 3NF 形式。但是我不确定如何应用这些概念。

Answer 1

要确定关系是否在 BCNF 中，对于定义，您应该检查 F+ 中的每个非平凡依赖项，即指定的所有依赖项 (F) 和从它们派生的那些，行列式应该是一个超级键。幸运的是，有一个定理表明仅对指定的依赖项执行此检查就足够了。

在您的情况下，这意味着您必须检查 UVW、VW 和 VWY 是否是超级密钥。

并且要查看在依赖项 X -> Y 中设置的属性 X 是否是一个超级键，您可以计算属性的闭包 (X+) 并检查它是否包含正确的手部分 Y.

所以你必须计算 UVW+ 并查看它是否包含 {U,V,W,X,Y,Z} 并且类似地用于其他两个依赖项。我把这个简单的练习留给你。

Answer 2

使用算法计算给定属性集的闭包和BCNF的定义如下图，

我们可以在python中实现上述算法来计算属性的闭包，然后判断给定的一组属性是否形成超键，如下代码片段所示：

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

现在检查关系 R 中每个给定的 FD A -> B，A 是否是超键，以确定 R 是否在 [=19= 中]与否：

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

要以标准形式处理给定的 FD，转换为合适的数据结构，我们可以使用以下函数：

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

现在，让我们测试几个关系：

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!

确定关系是否为 BCNF 形式？

Determine if relation is in BCNF form?

algorithm

rdbms

database-normalization

bcnf