BCNF分解数量与依赖保持性相关技术咨询

问题背景 #

给定关系模式 R = {A, B, C, D, E, F, G, H, I, J, K, L, M, N, O}，函数依赖集如下：

• FD1: {A,B} → {C,D}
• FD2: {E} → {F,G,J,K}
• FD3: {F, G, I, K, M} → {H}
• FD4: {K} → {L,M}
• FD5: {M} → {I}
• FD6: {A, B, E} → {N, O}

已知唯一候选键为 {A,B,E}，FD1-FD5均违反BCNF规则，需解决：

1. 计算该关系模式通过BCNF分解算法得到的不同分解结果数量
2. 列出所有无损且保持依赖的BCNF分解

一、计算BCNF分解数量的简便方法 #

BCNF分解的结果数量核心取决于违反BCNF的函数依赖的处理顺序，以及依赖间的推导逻辑，可按以下步骤梳理：

1. 归类依赖组：把存在推导关联的依赖归为一组，避免重复计数。这里FD4、FD5、FD3属于同一依赖链：K→L,M 推导得出 M→I，进而支撑 F,G,I,K,M→H，必须按此顺序处理，不能反向；FD1、FD2是独立的违反BCNF的依赖，无推导关联。
2. 计算顺序组合数：
   • 独立依赖FD1、FD2的处理顺序有2种排列
   • 依赖链作为一个整体，和FD1、FD2进行全排列，即3个元素的全排列共6种
3. 验证唯一性：每种排列对应的分解结果结构不同，因此总共有6种不同的BCNF分解结果，和你手动推导的数量一致。

二、所有无损且保持依赖的BCNF分解 #

BCNF分解算法天然保证无损连接性，保持依赖则要求分解后的子关系能覆盖所有原函数依赖。所有符合要求的分解如下（按处理顺序分类）：

类型1：先FD1 → 再FD2 → 最后依赖链（FD4→FD5→FD3）

分解结果：

• R1(A,B,C,D)（覆盖FD1）
• R2(E,F,G,J,K)（覆盖FD2）
• R3(K,L,M)（覆盖FD4）
• R4(M,I)（覆盖FD5）
• R5(F,G,I,K,M,H)（覆盖FD3）
• R6(A,B,E,N,O)（覆盖FD6，保留候选键）

类型2：先FD1 → 再依赖链 → 最后FD2

分解结果：

• R1(A,B,C,D)（覆盖FD1）
• R2(K,L,M)（覆盖FD4）
• R3(M,I)（覆盖FD5）
• R4(F,G,I,K,M,H)（覆盖FD3）
• R5(E,F,G,J,K)（覆盖FD2）
• R6(A,B,E,N,O)（覆盖FD6）

类型3：先FD2 → 再FD1 → 最后依赖链

分解结果：

• R1(E,F,G,J,K)（覆盖FD2）
• R2(A,B,C,D)（覆盖FD1）
• R3(K,L,M)（覆盖FD4）
• R4(M,I)（覆盖FD5）
• R5(F,G,I,K,M,H)（覆盖FD3）
• R6(A,B,E,N,O)（覆盖FD6）

类型4：先FD2 → 再依赖链 → 最后FD1

分解结果：

• R1(E,F,G,J,K)（覆盖FD2）
• R2(K,L,M)（覆盖FD4）
• R3(M,I)（覆盖FD5）
• R4(F,G,I,K,M,H)（覆盖FD3）
• R5(A,B,C,D)（覆盖FD1）
• R6(A,B,E,N,O)（覆盖FD6）

类型5：先依赖链 → 再FD1 → 最后FD2

分解结果：

• R1(K,L,M)（覆盖FD4）
• R2(M,I)（覆盖FD5）
• R3(F,G,I,K,M,H)（覆盖FD3）
• R4(A,B,C,D)（覆盖FD1）
• R5(E,F,G,J,K)（覆盖FD2）
• R6(A,B,E,N,O)（覆盖FD6）

类型6：先依赖链 → 再FD2 → 最后FD1

分解结果：

• R1(K,L,M)（覆盖FD4）
• R2(M,I)（覆盖FD5）
• R3(F,G,I,K,M,H)（覆盖FD3）
• R4(E,F,G,J,K)（覆盖FD2）
• R5(A,B,C,D)（覆盖FD1）
• R6(A,B,E,N,O)（覆盖FD6）

所有上述分解均满足无损连接性，且每个原函数依赖都被至少一个子关系覆盖，因此保持依赖。

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