分解判断专题

关系分解 无损连接
Database Systems
专栏索引 专栏目录 / Database Systems / 章节页
Publish Date:   2026-01-03
Word Count:   2.6k

分解判断专题

一、原理

1.1 无损连接性的判断

核心定义：分解后的子关系通过“自然连接”运算，能够原封不动地还原回原关系，不产生多余的“幻影”行。

方法 1：表格法

适用于分解为多个（2个以上）关系模式的情况。

  1. 建表：行代表分解后的子模式 $R_i$，列代表原关系的属性 $A_j$。
  2. 填表：
    • 如果属性 $A_j$ 在 $R_i$ 中，填 $a_j$。
    • 如果不在，填 $b_{ij}$。
  3. 根据函数依赖修改表：针对每一个函数依赖 $X \rightarrow Y$：
    • 寻找在 $X$ 属性列上具有相同符号的行。
    • 如果这些行在 $Y$ 列上的符号不同，则修改为相同：
      • 如果其中有 $a$，则全部改为 $a$。
      • 如果没有 $a$，则改为其中序号最小的 $b$。
  4. 循环判断：反复应用所有的函数依赖，直到表格不再发生变化。
  5. 结论：如果最后有一行全是 $a$，则该分解是无损连接的；否则是有损的。

方法 2：二分解

适用于只分解为两个关系模式 $R_1, R_2$ 的情况。

判定公式：只要满足以下其中一个条件，就是无损分解：

  1. $(R_1 \cap R_2) \rightarrow (R_1 - R_2)$
  2. $(R_1 \cap R_2) \rightarrow (R_2 - R_1)$

通俗解释：两个子表的公共属性，必须是其中某一个表的候选码（或者能推导出其中一个表多出来的属性）。

1.2 保持函数依赖的判断

核心定义：原关系上的所有函数依赖，在分解后的各个子关系上依然能够被逻辑推导出来。

方法 1：观察法

  1. 检查原依赖集 $F$ 中的每一个依赖 $X \rightarrow Y$。
  2. 如果 $X$ 和 $Y$ 都在同一个子模式 $R_i$ 中，这个依赖肯定被保持了。
  3. 如果所有的依赖都满足第 2 条，直接判定为保持依赖。

方法 2：属性闭包法

当某个依赖 $X \rightarrow Y$ 的属性分散在不同的子表中时，需要用此法。

算法步骤（针对 $X \rightarrow Y$）：

  1. 令临时集合 $Z = X$。
  2. 循环更新 $Z$：对每一个子模式 $R_i$：
    • 计算 $Z \cap R_i$。
    • 求 $(Z \cap R_i)$ 在原依赖集 $F$ 下的闭包。
    • 将结果中属于 $R_i$ 的属性并入 $Z$ 中：$Z = Z \cup ((Z \cap R_i)^+ \cap R_i)$。
  3. 循环直到 $Z$ 不再增大。
  4. 结论：如果最终的 $Z$ 包含了 $Y$（即 $Y \subseteq Z$），则 $X \rightarrow Y$ 被保持了。
  5. 对 $F$ 中每一个依赖都做一遍，全部通过才叫保持依赖

二、练习

第一题：Chase算法（表格法）判断无损连接

题目： 关系模式 $R(A, B, C, D)$，函数依赖集 $F = {A \rightarrow C, B \rightarrow C, C \rightarrow D}$。
判定分解 $\rho = {R_1(A, B), R_2(A, C), R_3(B, D)}$ 是否为无损连接。

【答案与解析】

  1. 初始化表格：行代表 $R_1, R_2, R_3$，列代表 $A, B, C, D$。

| | A | B | C | D |
| :——– | :——- | :——- | :——- | :——- |
| $R_1(AB)$ | $a_1$ | $a_2$ | $b_{13}$ | $b_{14}$ |
| $R_2(AC)$ | $a_1$ | $b_{22}$ | $a_3$ | $b_{24}$ |
| $R_3(BD)$ | $b_{31}$ | $a_2$ | $b_{33}$ | $a_4$ |

  1. 应用 $A \rightarrow C$：

    • 观察 A 列，$R_1$ 和 $R_2$ 都是 $a_1$。
    • 修改 C 列：$R_1$ 的 $b_{13}$ 改为 $a_3$。表格变为：
    A B C D
    $R_1$ $a_1$ $a_2$ $a_3$ $b_{14}$
    $R_2$ $a_1$ $b_{22}$ $a_3$ $b_{24}$
    $R_3$ $b_{31}$ $a_2$ $b_{33}$ $a_4$

  2. 应用 $B \rightarrow C$：

    • 观察 B 列，$R_1$ 和 $R_3$ 都是 $a_2$。
    • 修改 C 列：$R_3$ 的 $b_{33}$ 改为 $a_3$。表格变为：
    A B C D
    $R_1$ $a_1$ $a_2$ $a_3$ $b_{14}$
    $R_2$ $a_1$ $b_{22}$ $a_3$ $b_{24}$
    $R_3$ $b_{31}$ $a_2$ $a_3$ $a_4$

  3. 应用 $C \rightarrow D$：

    • 观察 C 列，$R_1, R_2, R_3$ 现在都是 $a_3$。
    • 修改 D 列：全部改为 $a_4$。
    A B C D
    $R_1$ $a_1$ $a_2$ $a_3$ $a_4$
    … … … … …

  4. 结论：第一行变为了 $(a_1, a_2, a_3, a_4)$。分解是无损连接的。

第二题：闭包法判断保持函数依赖

题目： 关系模式 $R(A, B, C)$，函数依赖集 $F = {A \rightarrow B, B \rightarrow C, C \rightarrow A}$。
判断分解 $\rho = {R_1(A, B), R_2(B, C)}$ 是否保持依赖。

【答案与解析】

  1. 检查 $A \rightarrow B$：$A, B$ 都在 $R_1(A, B)$ 中，保持。
  2. 检查 $B \rightarrow C$：$B, C$ 都在 $R_2(B, C)$ 中，保持。
  3. 检查 $C \rightarrow A$：属性分散在 $R_1, R_2$ 中，需使用闭包算法。
    • 设 $Z = {C}$。
    • 考虑 $R_1(A, B)$：$Z \cap R_1 = \varnothing$。
    • 考虑 $R_2(B, C)$：$Z \cap R_2 = {C}$。求 ${C}^+ = {C, A, B}$。
    • 将结果中属于 $R_2$ 的属性并入 $Z$：$Z = {C} \cup ({C, A, B} \cap {B, C}) = {B, C}$。
    • 再次考虑 $R_1(A, B)$：$Z \cap R_1 = {B}$。求 ${B}^+ = {B, C, A}$。
    • 将结果中属于 $R_1$ 的属性并入 $Z$：$Z = {B, C} \cup ({B, C, A} \cap {A, B}) = {A, B, C}$。
    • 此时 $A \subseteq Z$，说明 $C \rightarrow A$ 逻辑上被保持了。
  4. 结论：所有原依赖都被保持，分解保持函数依赖。

第三题：经典“有损”案例（用二分解准则快速判断）

题目： 关系模式 $R(A, B, C)$，$F = {B \rightarrow A}$。
判断分解 $\rho = {R_1(A, C), R_2(B, C)}$ 的无损连接性和保持依赖性。

【答案与解析】

  1. 无损连接性判断（使用二分解快捷准则）：
    • $R_1 \cap R_2 = {C}$。
    • $R_1 - R_2 = {A}$，$R_2 - R_1 = {B}$。
    • 检查是否满足 $C \rightarrow A$ 或 $C \rightarrow B$。
    • 根据 $F = {B \rightarrow A}$， ${C}^+ = {C}$。既推不出 $A$，也推不出 $B$。
    • 结论：是有损连接。（数据拼回去会产生大量错误行）
  2. 保持依赖性判断：
    • 检查 $B \rightarrow A$：$B$ 在 $R_2$，$A$ 在 $R_1$。
    • 计算闭包：$Z={B}$。$Z \cap R_2 = {B}$，${B}^+ \cap R_2 = {B}$。$Z \cap R_1 = \varnothing$。
    • $Z$ 最终无法包含 $A$。
    • 结论：不保持依赖。

第四题：BCNF分解的陷阱

题目： 关系模式 $R(S, T, J)$，$F = { (S, J) \rightarrow T, T \rightarrow J }$。
分解为 $\rho = {R_1(T, J), R_2(S, T)}$。判断其无损连接性和保持依赖性。

【答案与解析】

  1. 无损连接性（二分解准则）：
    • $R_1 \cap R_2 = {T}$。
    • $R_1$ 的属性是 $(T, J)$。在 $R_1$ 中，由于 $T \rightarrow J$，所以 $T$ 是 $R_1$ 的码。
    • 满足“公共属性是其中一个子表的码”，所以是无损连接。
  2. 保持依赖性：
    • $T \rightarrow J$ 包含在 $R_1$ 中，保持。
    • 检查 $(S, J) \rightarrow T$：
      • $Z = {S, J}$。
      • $Z \cap R_1 = {J}$，${J}^+ \cap R_1 = {J}$。$Z$ 不变。
      • $Z \cap R_2 = {S}$，${S}^+ \cap R_2 = {S}$。$Z$ 不变。
      • 循环结束，$Z$ 始终无法得到 $T$。
    • 结论：不保持函数依赖。（这是 BCNF 分解典型的副作用：为了消除冗余导致约束丢失）

第五题：多级依赖合并

题目： 关系模式 $R(A, B, C, D, E)$，函数依赖集 $F = {A \rightarrow C, B \rightarrow D, C \rightarrow E, D \rightarrow E}$。
判定分解 $\rho = {R_1(A, B, E), R_2(A, C), R_3(B, D)}$ 是否为无损连接。

【答案与解析】

  1. 初始化表格：

| | A | B | C | D | E |
| :——— | :——- | :——- | :——- | :——- | :——- |
| $R_1(ABE)$ | $a_1$ | $a_2$ | $b_{13}$ | $b_{14}$ | $a_5$ |
| $R_2(AC)$ | $a_1$ | $b_{22}$ | $a_3$ | $b_{24}$ | $b_{25}$ |
| $R_3(BD)$ | $b_{31}$ | $a_2$ | $b_{33}$ | $a_4$ | $b_{35}$ |

  1. 应用 $A \rightarrow C$：$R_1, R_2$ 在 A 列相同，将 $R_1$ 的 $b_{13}$ 改为 $a_3$。

  2. 应用 $B \rightarrow D$：$R_1, R_3$ 在 B 列相同，将 $R_1$ 的 $b_{14}$ 改为 $a_4$。
    此时 $R_1$ 行变为：$(a_1, a_2, a_3, a_4, a_5)$

  3. 结论：第一行已经出现了全 $a$ 行。分解是无损连接的。
    注：即便不继续应用 $C \rightarrow E$ 等，只要有一行全 $a$ 即可停止。

第六题：循环依赖下的 Chase

题目： 关系模式 $R(A, B, C, D)$，函数依赖集 $F = {A \rightarrow B, B \rightarrow C, C \rightarrow D, D \rightarrow A}$。
判定分解 $\rho = {R_1(A, B), R_2(B, C), R_3(C, D)}$ 是否为无损连接。

【答案与解析】

  1. 初始化表格：

| | A | B | C | D |
| :——– | :——- | :——- | :——- | :——- |
| $R_1(AB)$ | $a_1$ | $a_2$ | $b_{13}$ | $b_{14}$ |
| $R_2(BC)$ | $b_{21}$ | $a_2$ | $a_3$ | $b_{24}$ |
| $R_3(CD)$ | $b_{31}$ | $b_{32}$ | $a_3$ | $a_4$ |

  1. 应用 $B \rightarrow C$：$R_1, R_2$ 在 B 列相同，将 $R_1$ 的 $b_{13}$ 改为 $a_3$。

  2. 应用 $C \rightarrow D$：$R_1, R_2, R_3$ 在 C 列现在都是 $a_3$，将 $R_1, R_2$ 的 D 列改为 $a_4$。
    此时 $R_1$ 变为：$(a_1, a_2, a_3, a_4)$

  3. 结论：第一行变为全 $a$。分解是无损连接的。
    技巧：这种链式依赖，只要分解是“环环相扣”的，通常都是无损的。

第七题：跨表依赖的验证

题目： 关系模式 $R(A, B, C, D)$，函数依赖集 $F = {A \rightarrow B, B \rightarrow C, C \rightarrow D, D \rightarrow A}$。
判断分解 $\rho = {R_1(A, B), R_2(B, C), R_3(C, D)}$ 是否保持函数依赖。

【答案与解析】

  1. 直接观察法：
    • $A \rightarrow B$ 在 $R_1$ 中，保持。
    • $B \rightarrow C$ 在 $R_2$ 中，保持。
    • $C \rightarrow D$ 在 $R_3$ 中，保持。
  2. 验证最后一个依赖 $D \rightarrow A$（属性分散）：
    • 设 $Z = {D}$。
    • 考虑 $R_3(C, D)$：$Z \cap R_3 = {D}$。求 ${D}^+ = {D, A, B, C}$。
      将结果中属于 $R_3$ 的并入 $Z$：$Z = {D} \cup ({D, A, B, C} \cap {C, D}) = {D, C}$。
    • 考虑 $R_2(B, C)$：$Z \cap R_2 = {C}$。求 ${C}^+ = {C, D, A, B}$。
      将结果中属于 $R_2$ 的并入 $Z$：$Z = {D, C} \cup ({C, D, A, B} \cap {B, C}) = {D, C, B}$。
    • 考虑 $R_1(A, B)$：$Z \cap R_1 = {B}$。求 ${B}^+ = {B, C, D, A}$。
      将结果中属于 $R_1$ 的并入 $Z$：$Z = {D, C, B} \cup ({B, C, D, A} \cap {A, B}) = {D, C, B, A}$。
  3. 结论：最终 $Z = {A, B, C, D}$，包含 $A$。该分解保持了函数依赖。

第八题：部分依赖丢失

题目： 关系模式 $R(A, B, C, D)$，函数依赖集 $F = {AB \rightarrow C, C \rightarrow D, D \rightarrow B}$。
判断分解 $\rho = {R_1(A, B), R_2(B, C, D)}$ 是否保持函数依赖。

【答案与解析】

  1. 检查 $C \rightarrow D$ 和 $D \rightarrow B$：都在 $R_2$ 中，保持。
  2. 检查 $AB \rightarrow C$：属性分散，$A$ 在 $R_1$，$B, C$ 在 $R_1, R_2$。
    • 设 $Z = {A, B}$。
    • 考虑 $R_1(A, B)$：$Z \cap R_1 = {A, B}$。求 ${A, B}^+ = {A, B, C, D}$。
      将结果中属于 $R_1$ 的并入 $Z$：$Z = {A, B} \cup ({A, B, C, D} \cap {A, B}) = {A, B}$（没变）。
    • 考虑 $R_2(B, C, D)$：$Z \cap R_2 = {B}$。求 ${B}^+ = {B}$。
      将结果并入 $Z$：还是 ${A, B}$。
    • 由于 $Z$ 不再增大，且最终 $Z$ 不包含 $C$。
  3. 结论：$AB \rightarrow C$ 无法被保持。该分解不保持函数依赖。

三、注意事项

  1. Chase 算法的顺序：应用 FD 的顺序不影响最终结论。如果你发现应用完一轮没出现全 $a$ 行，记得再检查一遍，有时候需要多次循环应用（比如依赖是 $A \rightarrow B, B \rightarrow A$ 这种）。
  2. 闭包法的 $Z$ 更新：在更新 $Z$ 时，公式是 $Z = Z \cup ((Z \cap R_i)^+ \cap R_i)$。注意： 那个闭包 $(Z \cap R_i)^+$ 必须是在原函数依赖集 $F$ 下计算的，而不仅仅是在子模式里。
  3. 判断逻辑：
    • 无损连接：只要有一行全 $a$，就是无损。
    • 保持依赖：必须每一个原 FD 都能推导出来，才算保持。

👉 点击这里阅读下一篇：《范式分解专题》

Author: linda1729
Link: https://linda1729-blog.netlify.app/posts/2026-01-03-databases-decomposition-checks/
Reprint policy: All articles in this blog are used except for special statements CC BY 4.0 reprint policy. If reproduced, please indicate source linda1729 !
关系分解 无损连接
赏
评论
  TOC