寫在前面：今天筆者將會(huì)對(duì)BCNF和3NF分解算法做簡(jiǎn)要的分析拐揭，不過(guò)實(shí)際上大多數(shù)的分解用肉眼即可睡陪，以下分解算法不依賴于過(guò)多的條件可以直接講一個(gè)滿足1NF的模式分解為3NF或BCNF

BCNF 分解算法

• 教材上關(guān)于BCNF分解算法的偽代碼實(shí)現(xiàn)有部分印錯(cuò)（本科教學(xué)版）
• 該算法的結(jié)果是一個(gè)滿足BCNF的無(wú)損分解豹障，但可能不是保持依賴的（畢竟3NF是保持依賴并且可以滿足無(wú)損分解的最高范式）

• 偽代碼實(shí)現(xiàn)

  對(duì)滿足1NF的模式R<U, F>作如下處理可分解成滿足BCNF范式的模式R₁, R₂, ..., R_n

  result := {R};
          done := false;
          計(jì)算F+;
          while(not done) do
                if(result中存在模式Ri不屬于BCNF)
                then begin
                        令 α→β 為一個(gè)在Ri上成立的非平凡函數(shù)依賴，滿足 α→β ∈ F+嚎京， 并且 α∩β  = ?;
                        result := (result - Ri) ∪ (Ri - β) ∪ (α, β)
                end
                else done := true        
  

• 先來(lái)分析一波上面的代碼吧

  1. 首先令reslut = {R}
  2. 接著計(jì)算一下F的函數(shù)閉包F⁺（計(jì)算函數(shù)閉包還是挺麻煩的诚隙，所以在下面判斷的時(shí)候挑一個(gè)函數(shù)依賴，判斷一下是否被F邏輯蘊(yùn)含即可）
  3. 然后判斷結(jié)果集result中是否還存在哪個(gè)模式不滿足BCNF范式赎懦，如果都滿足雀鹃，則直接跳到步驟5，如果存在某個(gè)模式 R_i ∈ result励两，不滿足BCNF范式黎茎，則執(zhí)行步驟4
  4. 選擇一個(gè)在R_i上成立的非平凡函數(shù)依賴 α→β，并且 α→β 屬于 F⁺当悔，并且α∩β=?傅瞻。然后將模式R_i分解成兩個(gè)模式，分別為 (R_i - β) 和 (α, β)盲憎。并且將R_i從result中移除嗅骄，江新得到的兩個(gè)模式添加到result中。接著回到步驟3繼續(xù)判斷
  5. 分解完成饼疙，輸出結(jié)果

• 紙上學(xué)來(lái)終覺(jué)淺溺森，讓我們拿教材上的栗子出來(lái)刷一刷～～

  • 有模式class<U, F>, 通過(guò)上述算法，對(duì)其進(jìn)行滿足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)
      }
  • 首先還是看一下上面模式的候選碼是什么吧（書上的栗子是直接給出來(lái)了宏多，但是有些題可能不給儿惫，需要自己算）
    • 通過(guò)上一篇博客講的候選碼求解算法，容易求得模式class的候選碼為{course_id, sec_id, semester, year}
  • 接著判斷模式class是否滿足BCNF范式
    • 模式R中存在依賴 course_id → (title, dept_name, credits), 但course_id并不是R的一個(gè)超碼伸但，故R不滿足BCNF范式
    • 對(duì)R做如下分解
      • course(course_id, title, dept_name, credits)
      • class_1(course_id, credits. sec_id, semester, year, building, room_number, capticy, time_slot_id)
  • 繼續(xù)判斷肾请，易知course是滿足BCNF范式的，而course_1同理不滿足BCNF范式更胖， 繼續(xù)分解
    • 找到非平凡依賴(building, room_number)→capaticy铛铁， 且其屬于F
    • 對(duì)class_1分解如下
      • classroom(building, room_number, capacity)
      • section(course_id, credits. sec_id, semester, year, building, room_number, time_slot_id)
  • 檢測(cè)一下發(fā)現(xiàn)現(xiàn)在模式classroom和section也滿足BCNF范式了
  • OK隔显，原來(lái)的模式class現(xiàn)在分解為如下三個(gè)模式
    • 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分解算法

以下分解算法中用到了正則覆蓋的概念，這個(gè)筆者在之前的博客中也提到過(guò)饵逐，點(diǎn)我傳送

• 該分解算法可以保持依賴括眠，并且是無(wú)損分解

• 偽代碼實(shí)現(xiàn)

   令Fc為F的正則覆蓋;
   i:= 0;
   for each Fc 中的函數(shù)依賴 α→β 
           i := i + 1
           Ri := αβ;
   if 模式 Rj, j = 1, 2, ..., i 都不包含R的候選碼
   then
           i := i + 1
           Ri := R的任意候選碼
   /*(以下代碼可選)用來(lái)移除冗余關(guān)系，如果沒(méi)有冗余關(guān)系則可以不care*/ 
   repeat
           if 模式 Rj包含于另一個(gè)模式Rk中
           then
                  /*刪除Rj*/
                  Rj := Ri
                   i := i - 1
   until 不再有可以刪除的Rj
   return (R1, R2, ..., Ri)
  

• 老規(guī)矩倍权，還是先分析一下上面的偽代碼

  1. 首先求出F的正則覆蓋F_c（實(shí)際上就是利用Amstrong公式化簡(jiǎn)原來(lái)的函數(shù)依賴集的過(guò)程）
  2. 接著將F_c中的每一個(gè)函數(shù)依賴單獨(dú)分解成一個(gè)模式掷豺，得到一個(gè)模式列表S = {R₁, R₂, ..., R_i}
  3. 如果上述模式列表S中的任意一個(gè)模式包含模式R的候選碼，則跳到步驟5薄声，否則執(zhí)行步驟4
  4. 選取R的任意一個(gè)候選碼当船，組成一個(gè)新的模式R', 將R'添加到模式列表S中
  5. （可選）如果模式列表中存在冗余（即某個(gè)模式被其他模式包含），則可以刪除這個(gè)模式
  6. 輸出S

• 講真默辨，3NF分解的步驟還是很簡(jiǎn)單的德频，主要還是計(jì)算一下F的正則覆蓋，詳細(xì)栗子就不舉了缩幸，下面簡(jiǎn)單提一提

  • 比如上面分析BCNF分解算法時(shí)用到的模式class壹置， 利用上述算法分解之后可以得到和 利用BCNF算法分解一樣的結(jié)果
  • 所以，神奇的事情發(fā)生了表谊，利用3NF分解算法得到的結(jié)果可能還會(huì)滿足BCNF范式
  • 實(shí)踐中BCNF分解的另一種途徑： 先用3NF算法分解钞护，然后對(duì)結(jié)果中不滿足BCNF范式的模式用BCNF分解算法分解，如果結(jié)果不保持依賴爆办，則回退回3NF