Bernstein 3NF合成算法分解特殊表时的异常问题问询

问题描述 #

在编写自动数据表分解工具库时，应用用于3NF规范化的Bernstein合成算法（ACM 1976）时遇到异常：初始步骤输出不符合预期。

测试数据表 #

测试表的结构与数据如下：

a b
---
1 1
2 1
1 2
2 2

错误的函数依赖集推导 #

我认为该表的完整函数依赖集为：

{} -> {}
a -> {}
a -> a
b -> {}
b -> b
ab -> {}
ab -> a
ab -> b
ab -> ab

直观判断与算法执行异常 #

从数据来看，a和b共同构成候选键，原表无需规范化。但应用Bernstein算法时出现问题：

1. 消除无关属性后，得到简化依赖集：

   {} -> {} (repeated)
   a -> a (repeated)
   b -> b (repeated)
   ab -> ab
   

2. 寻找非冗余覆盖时，通过增广律判定ab -> ab冗余，最终得到：

   {} -> {}
   a -> a
   b -> b
   

   若保留这些依赖，后续步骤会生成两个独立关系；若删除，后续无可用依赖无法生成任何表。

请问上述过程中的问题出在哪里？

问题根源与正确解法 #

1. 混淆了函数依赖的有效范围 #

数据库规范化算法（包括Bernstein）仅处理非平凡且有实际约束意义的函数依赖，你列出的大部分依赖都是自反律或空依赖生成的冗余项：

• a->a、b->b、ab->ab属于自反依赖，是所有关系默认成立的，规范化时直接忽略
• {}->{}、a->{}、b->{}这类空依赖对表结构无约束作用，同样不在算法处理范围内

2. 错误识别了实际函数依赖与候选键 #

从示例数据可以看出，该表不存在任何非平凡函数依赖（即不存在X→Y，其中Y不包含于X且Y非空）。这意味着：

• 整个属性集{a,b}是唯一的候选键（没有任何属性子集能决定所有属性）
• 原表已经处于3NF（甚至BCNF），无需进行分解

Bernstein算法的正确执行流程 #

按照算法规范执行时：

1. 第一步过滤掉所有平凡、无意义的依赖，得到空的依赖集
2. 识别出唯一候选键{a,b}
3. 由于没有依赖对应的关系包含候选键，算法会直接生成包含整个候选键的关系——也就是原表，完全符合预期

内容的提问来源于stack exchange，提问作者Accidental Statistician