数据库笔记（补充）——分解算法浅析

写在前面：今天笔者将会对BCNF和3NF分解算法做简要的分析，不过实际上大多数的分解用肉眼即可，以下分解算法不依赖于过多的条件可以直接讲一个满足1NF的模式分解为3NF或BCNF

BCNF 分解算法

教材上关于BCNF分解算法的伪代码实现有部分印错（本科教学版）

该算法的结果是一个满足BCNF的无损分解，但可能不是保持依赖的（毕竟3NF是保持依赖并且可以满足无损分解的最高范式）

伪代码实现

对满足1NF的模式R<U, F>作如下处理可分解成满足BCNF范式的模式R₁, R₂, …, R_n

result := {R};
        done := false;
        计算F+;
        while(not done) do
              if(result中存在模式Ri不属于BCNF)
              then begin
                      令 α→β 为一个在Ri上成立的非平凡函数依赖，满足 α→β ∈ F+， 并且 α∩β  = ∅;
                      result := (result - Ri) ∪ (Ri - β) ∪ (α, β)
              end
              else done := true

先来分析一波上面的代码吧
1. 首先令reslut = {R}
2. 接着计算一下F的函数闭包F⁺（计算函数闭包还是挺麻烦的，所以在下面判断的时候挑一个函数依赖，判断一下是否被F逻辑蕴含即可）
3. 然后判断结果集result中是否还存在哪个模式不满足BCNF范式，如果都满足，则直接跳到步骤5，如果存在某个模式 R_i ∈ result，不满足BCNF范式，则执行步骤4
4. 选择一个在R_i上成立的非平凡函数依赖 α→β，并且 α→β 属于 F⁺，并且α∩β=∅。然后将模式R_i分解成两个模式，分别为 (R_i - β) 和 (α, β)。并且将R_i从result中移除，江新得到的两个模式添加到result中。接着回到步骤3继续判断
5. 分解完成，输出结果
纸上学来终觉浅，让我们拿教材上的栗子出来刷一刷～～
- 有模式class<U, F>, 通过上述算法，对其进行满足BCNF范式的分解
  - U = {course_id, title, dept_name, credits. sec_id, semester, year, building, room_number, capticy, time_slot_id}
  - F = {
    course_id → (title, dept_name, credits),
    (building, room_number)→capaticy,
    (course_id, sec_id, semester, year)→(building, room_number, time_slot_id)
    }
- 首先还是看一下上面模式的候选码是什么吧（书上的栗子是直接给出来了，但是有些题可能不给，需要自己算）
  - 通过上一篇博客讲的候选码求解算法，容易求得模式class的候选码为{course_id, sec_id, semester, year}
- 接着判断模式class是否满足BCNF范式
  - 模式R中存在依赖 course_id → (title, dept_name, credits), 但course_id并不是R的一个超码，故R不满足BCNF范式
  - 对R做如下分解
    - course(course_id, title, dept_name, credits)
    - class_1(course_id, credits. sec_id, semester, year, building, room_number, capticy, time_slot_id)
- 继续判断，易知course是满足BCNF范式的，而course_1同理不满足BCNF范式，继续分解
  - 找到非平凡依赖(building, room_number)→capaticy，且其属于F
  - 对class_1分解如下
    - classroom(building, room_number, capacity)
    - section(course_id, credits. sec_id, semester, year, building, room_number, time_slot_id)
- 检测一下发现现在模式classroom和section也满足BCNF范式了
- OK，原来的模式class现在分解为如下三个模式
  - course(course_id, title, dept_name, credits)
  - classroom(building, room_number, capacity)
  - section(course_id, credits. sec_id, semester, year, building, room_number, time_slot_id)

3NF分解算法
以下分解算法中用到了正则覆盖的概念，这个笔者在之前的博客中也提到过，点我传送

该分解算法可以保持依赖，并且是无损分解

伪代码实现

令Fc为F的正则覆盖;
i:= 0;
for each Fc 中的函数依赖 α→β
        i := i + 1
        Ri := αβ;
if 模式 Rj, j = 1, 2, ..., i 都不包含R的候选码
then
        i := i + 1
        Ri := R的任意候选码
/*(以下代码可选)用来移除冗余关系，如果没有冗余关系则可以不care*/
repeat
        if 模式 Rj包含于另一个模式Rk中
        then
               /*删除Rj*/
               Rj := Ri
                i := i - 1
until 不再有可以删除的Rj
return (R1, R2, ..., Ri)

老规矩，还是先分析一下上面的伪代码
1. 首先求出F的正则覆盖F_c（实际上就是利用Amstrong公式化简原来的函数依赖集的过程）
2. 接着将F_c中的每一个函数依赖单独分解成一个模式，得到一个模式列表S = {R₁, R₂, …, R_i}
3. 如果上述模式列表S中的任意一个模式包含模式R的候选码，则跳到步骤5，否则执行步骤4
4. 选取R的任意一个候选码，组成一个新的模式R’, 将R’添加到模式列表S中
5. （可选）如果模式列表中存在冗余（即某个模式被其他模式包含），则可以删除这个模式
6. 输出S
讲真，3NF分解的步骤还是很简单的，主要还是计算一下F的正则覆盖，详细栗子就不举了，下面简单提一提
- 比如上面分析BCNF分解算法时用到的模式class，利用上述算法分解之后可以得到和利用BCNF算法分解一样的结果
- 所以，神奇的事情发生了，利用3NF分解算法得到的结果可能还会满足BCNF范式
- 实践中BCNF分解的另一种途径：先用3NF算法分解，然后对结果中不满足BCNF范式的模式用BCNF分解算法分解，如果结果不保持依赖，则回退回3NF

BCNF 分解算法

伪代码实现

先来分析一波上面的代码吧

纸上学来终觉浅，让我们拿教材上的栗子出来刷一刷～～

3NF分解算法

伪代码实现

老规矩，还是先分析一下上面的伪代码

讲真，3NF分解的步骤还是很简单的，主要还是计算一下F的正则覆盖，详细栗子就不举了，下面简单提一提