増永教授のDB特論⑥
「RDB 設計のための分解的 vs. 合成的アプローチ」

 

1. はじめに

 リレーショナルデータベース(RDB)設計には分解的アプローチと合成的アプローチの 2 つがあることは皆さんよくご存じのことと思います.
分解的アプローチ(decomposition approach)はリレーショナルデータモデルを考案したコッド(E.F. Codd)により導入された「リレーションの正規化理論」[1, 2]に依って立つ RDBの設計法で,これまで多くの説明がなされているのでその認知度は大変高いと思います.このアプローチでは更新時異状(update anomaly)を解消するために,リレーションを関数従属性(FD)や多値従属性(MVD),
あるいは結合従属性(JD)を使って情報無損失分解して,第 1 正規形(1NF)から第 2 正規形(2NF),第 3 正規形(3NF),ボイス‐コッド正規形(BCNF),第 4 正規形(4NF),第 5 正規形(5NF)へと正規度を高めていきます.しかしながら,情報無損失分解と関数従属性保存は独立した概念なので,正規化により関数従属性が保存されない場合が生じることに十分注意する必要があります[3].
 一方,合成的アプローチ(synthetic approach)はバーンシュタイン(P.A. Bernstein)によって提案された RDB の設計法 [4] で,RDB を設計するにあたり,データベース化の対象となった世界をリレーションスキーマ R(A1, A2, , An)と所与の FD 集合 F を指定して,それを基に「関数従属性保存・3NF・情報無損失分解」と三拍子揃った RDB を設計する手法です.このアプローチでは,F を構成している FD は必ず設計された RDB を構成するいずれかのリレーションスキーマの FD として定義されるので,関数従属性保存となります.

 以下で見るように,データベース化の対象となった世界は同一でも,分解的アプローチにより設計された RDB と合成的アプローチにより設計された RDB は一般的には異なった構成となります.では,どう違うのでしょうか?また,その差異はどのように説明されるのでしょうか?本稿では,この 2 つに焦点を当てて蘊蓄うんちくを傾けてみたいと思います.

2. 基礎的事項

 RDB 設計の分解的アプローチとそれに係る基礎的事項は本稿の読者には改めて説明する必要はないと考えられるので省略します.ここでは,合成的アプローチの理解に必要な事項のみを掻い摘んで説明します.

 まず,リレーションスキーマの定義とそれに関連する定義を示します.
【定義 1】(リレーションスキーマ)
 リレーションスキーマ R とはリレーション名 R と属性集合 ΩR={A1, A2, …n} からなり,R(A1, A2,, An)と表される.リレーションスキーマ R に所与の FD 集合 F={f1, f2,, fp}を指定することができる.リレーションスキーマ R(A1, A2,, An)に所与の FD 集合 FR が指定されていることを明示したいとき,R=(ΩR, FR)と表すこととする.ここに,ΩR ={A1, A2,, An},FR={f1, f2,, fp}である.

【定義 2】(リレーションスキーマタの等価)
R1=(ΩR1, FR1)とR2=(ΩR2, FR2)をリレーションスキーマタとする.R1R2等価(equivalent,同値ともいう)とは次の条件が成立するときとし,R1R2 と表すこととする.ここに,∧は論理積,FR1+FR1 の閉包(定義 3 参照)を表す(FR2+ についても同様).iff は if and only if を表す.
   R1R2 iff ΩR1R2FR1+= FR2+

【例題 1】
 例えば,R1=({A, B, C}, {A→B, B→C}),R2=({A, B, C}, {A→B, B→C, A→C}),R3=({A, B, C}, {A→B, A→C})があった時,R1R2 は属性集合が同じでかつ{A→B, B→C}+={A→B, B→C, A→C}+ なので等価である( R1R2 )が,R1R3 は属性集合は同じであるものの{A→B, B→C}+≠{A→B, A→C}+なので等価でない(R1R3).

 この等価関係は反射律,推移律,対称律を満たします.リレーションスキーマタの等価関係に言及したのは,後段で,設計された RDB の関数従属性保存を議論するときに必用となるからです.

■ 関数従属性の集合 F の極小被覆
 関数従属性の集合 F が与えられたとき,その極小被覆(minimal cover)G を求めるアルゴリズムを示します.このアルゴリズムの時間計算量は多項式時間であり,扱いやすい(tractable)問題です.この証明に興味を抱いた者は拙著 [5] を参照してください.
 まず,FD の集合 F の閉包 F+ を定義する必要があります.
【定義 3】(FD 集合の閉包)
 リレーションスキーマ R(A1, A2, , An) に所与の FD 集合 F が指定されているとする.このとき, F の閉包 F+ は次のように定義される.ここに,F ⊨ X→Y は X→Y がアームストロングの公理系のもとで F から導出されることを表す.

   F+={X→Y | X, Y⊆ΩR ∧ F ⊨ X→Y}

 続いて,極小被覆を定義します.
【定義 4】(FD 集合の極小被覆)
 関数従属性の集合 G が関数従属性の集合 F の極小被覆(minimal cover)であるとは,次の条件を満たすときをいう.
  (a) GF は等価(equivalent,同値ともいう),すなわち,GF+ である.
  (b) G の全ての関数従属性は X→A,ここに A は単一の属性,の形をしている.
  (c) G に,ある関数従属性 X→A と X の真部分集合 Z(Z⊂X)が存在して,
     G−{X→A}∪{Z→A} と G が等価になることはない.ここに,− は差集合演算である.
  (d) G に,ある関数従属性 g が存在して,G−{g} と G が等価になることはない.

 極小被覆を求めるアルゴリズムは次の通りです.
【FD 集合 F の極小被覆 G を求めるアルゴリズム】
  (ステップ 1) G = F とおく.
  (ステップ 2) G 中の各関数従属性で右辺(=被決定子(resultant))が単一の属性で
        ないものがあれば(これを X→{ A1, A2, · · ·, Ap } とする),右辺が単一
        の属性である p 個の関数従属性 X→A1, X→A2, · · ·, X→Ap で置き換える.
  (ステップ 3) G 中の各関数従属性 X→A に対して,X を構成する各属性 B に対して,
        G−{X→A}∪{{X−B}→A} と G が等価ならば,G の X→A を {X−B}→A
        で置き換える.
  (ステップ 4) G の各関数従属性 X→A に対して,G−{X→A} が G と等価ならば,
        G から X→A を取り除く.

 ステップ 3 とステップ 4 はこの順番で行う必要があります.例えば,リレーションスキーマ R(A, B, C)に所与の FD 集合 F={AB→C, C→B, A→B} が指定されているとき,もし,まずステップ 4 を,続いてステップ 3 を適用すると,結果として極小被覆もどきの集合 H= {A→C, C→B, A→B} が得られますが,これは I= H-{ A→B } とすると,A→B は A→C と C→B に推移律を適用すると得られる関数従属性であることから分かるように,H+ = I+ であり,H は極小被覆にはなっていません.

 ここで,極小被覆を求める簡単な例を示します.
【例題 2】(極小被覆を求める)
 リレーションスキーマ R(A, B, C, D)に所与の FD 集合 F = {AB→CD, C→D} が指定されているとする.F の極小被覆を求めなさい.
(解答)
F にステップ 1 とステップ 2 を適用することにより G ={AB→C, AB→D, C→D} となる.ステップ 3 を行う.まず,AB→C の左辺に注目し,A あるいは B が余分ではないか検証する.そこで,A が余分であるかどうかを検証するために,H = G−{AB→C}∪{B→C} とし,H+= G+ かどうかをチェックする.H+G+ は明らかなので,H+G+ かどうかをチェックする.そのため H にあり G にない関数従属性 B→C が G+ の元かチェックするが,B の G に関する閉包 B+ を求めれば,適用する G 中の関数従属性がないので B+= {B} である.明らかに,C⊆{B} ではないので,H+G+ ではなく,よって H+G+ である.以下同様な論理でステップ 3 を実行した結果,置き換えられる G の関数従属性はないことが分かる.続いてステップ 4 を行う.I = G−{AB→D} とし,I+ = G+ をチェックする.G の関数従属性 AB→D について,{A, B} の I に関する閉包を求めると,X(0) ={A, B}, X(1) = X(0)∪{C}, X(2) = X(1)∪{D} (= {A, B, C, D}) = X(3)となり,D∈X(3) である.したがって,I = {AB→C, C→D} が F の極小被覆となる.この例では I 以外に F の極小被覆はない.

(解答終)

 なお,一般に F の極小被覆 G はただ 1 つとは限りません.したがって,最小(minimum)とは言わずに極小(minimal)というわけです.一般に極小被覆が複数個ある簡単な例を示しておきます.

【例題 3】(一般に極小被覆は複数個ある)
 リレーションスキーマ R(A, B, C)に所与の FD 集合 F = {A→BC, B→AC, C→AB} が指定されているとする.F の極小被覆を求めなさい.
(解答)
G={A→B, A→C, B→A, B→C, C→A, C→B} として,極小被覆を求めるアルゴリズムを稼働すると次の 5 つを得る.
  ① A→B, A→C, B→A, C→A
  ② B→A, B→C, A→B, C→B
  ③ C→A, C→B, A→C, B→C
  ④ A→B, B→C, C→A
  ⑤ A→C, B→A, C→B

(解答終)

■ 関数従属性保存
 リレーションスキーマ R が情報無損失分解されたとき,R 上で成立していた FD が定義できなくなくなることはない,つまり保存されているという概念が関数従属性保存です.そのためには,まず FD 集合の閉包の射影を定義することが必要です.

【定義 5】(FD 集合の閉包の射影)
 リレーションスキーマ R に所与の関数従属性の集合 F が指定されているとする.このとき,一般に Z⊆ΩR として,F+の Z 上の射影 F+[Z]は次のように定義される.
   F+[Z]={X→Y|X→Y∈F+ ∧ X∪Y⊆Z}

  この定義を用いて関数従属性保存の定義を与えることができます.
【定義 6】(関数従属性保存)
 リレーションスキーマ R に所与の関数従属性の集合 F が指定されているとする.X→Y∈F+として,X→Yによる RR[X, Y]と RR-Y]への情報無損失分解が関数従属性保存であるとは,次が成立するときをいう.
   (F+[X∪Y]∪F+R-Y])+=F+

 以上で,基礎的事項の説明は終了です.F+ を求める具体例や,リレーションスキーマを FD で情報無損失分解した場合に,どのようなときに関数従属性が保存されない状況が発生するのかなどの例題は SRA OSS Tech Blog に収録されている拙稿 [3]に掲載されているので,参照してください.
 続いて,RDB 設計の合成的アプローチの説明に移りましょう.

3. RDB 設計の合成的アプローチ

 1976 年にバーンシュタイン(P.A. Bernstein)が提案した RDB 設計の合成的アプローチ(synthetic approach)[4] は,データベース化の対象となった世界を表すリレーションスキーマ R(A1, A2,, An)に所与の FD 集合 F が指定されているとして,それを基に「関数従属性保存・3NF・情報無損失分解」と三拍子揃った RDB を設計するという手法です.そのアルゴリズムは次の通りです.
【合成的アプローチによる RDB 設計アルゴリズム】
  リレーションスキーマ R に所与の関数従属性の集合 F が指定されているとする.このとき,合成的アプローチによる RDB 設計のアルゴリズムは次の通りである.

(ステップ 1) F の極小被覆 G を一つ見つける.
(ステップ 2) X を決定子(determinant)に持つ G の全ての関数従属性 X→B1, X→B2, · · ·, X→Bk
       に対して(G が極小だから各 Bi は単一属性),Y = {B1, B2, …, Bk} とし,リレー
       ションスキーマ R(X, Y) を作る.この操作を G の全ての関数従属性に対して行う.
       その結果,リレーションスキーマタ R1(X1, Y1), R2(X2, Y2), · · · , Rm(Xm, Ym) を得る.
(ステップ 3) もし,ステップ 2 で作ったリレーションスキーマタ R1, R2, · · · , Rm の中に,R
       候補キーを含むリレーションスキーマが存在すれば,{ R1, R2, · · · , Rm } が所望の
       分解であり,もしそうでなければ R の候補キーのひとつを K として R (K) を作る
       と(作り方から,R 上には自明でない関数従属性は存在していない),{R (K), R1,
       R2, · · · , Rm} が所望の分解である.

 前述の通り,一般に F の極小被覆 G はただ 1 つとは限らないので,求められた G の違いで,得られる RDB が異なってくる可能性があることに注意します.
 また,このアルゴリズムの正しさ,つまりこのアルゴリズムにより R の関数従属性保存で情報無損失な 3NF への分解が得られることは,ステップ 2 とステップ 3 で行った R の分解が,(1) 関数従属性保存であること,続いて,(2) (各成分リレーションスキーマが)3NFであること,そして,(3) 情報無損失分解であることを証明することで示されます.特に(3)の証明は結構難易度が高いので,ここでは立ち入らないことにしますが,アルゴリズムの正しさの証明は拙著 [5] でも与えられているので,興味を抱いた読者はご参照ください.
 なお,この手法が合成的と呼ばれるのは,ステップ 2 で同じ決定子を持つ関数従属性がまとめ上げられて 1 つの候補キーが合成されて(synthesized),その結果,1 つのリレーションスキーマが合成されることからきています.

■ 実は,3NF より正規度の高い BCNF であること
 1993年にビンセント(M.W. Vincent)らにより「重複する候補キーのペアがない 3NF リレーションスキーマは BCNF であること」が証明されました[6].上記,合成的アプローチによる RDB 設計アルゴリズムのステップ 2 を見て分かるように,得られるリレーションスキーマ R(X, Y)では X のみが候補キーで,R に重複する候補キーのペアはあり得ません.したがって,合成的アプローチで設計された RDB は BCNF のリレーションスキーマタからなると言えます(もちろん,3NF です).よって,合成的アプローチは「関数従属性保存・BCNF・情報無損失分解」と三拍子揃った RDB を設計する手法と言い換えた方が正確でしょう.3NF ではなく BCNF となっていることで,3NF ではあるが BCNF ではないリレーションで発生する更新時異状を合成的アプローチで RDB を設計することで抑制することが可能となってきます.このことについては,例題 6 でより具体的に論じます.なお,以下ではこのことを十分に承知したうえで「関数従属性保存・3NF・情報無損失分解」という伝統的な表現を使用します.

 次章では,上記のアルゴリズムの下で RDB がどのように設計されていくかについてその感触をつかんでいただくと共に,分解的アプローチと合成的アプローチでは,たとえ最初に与えられたリレーションスキーマが同一でも得られた RDB は一般には異なることを観察してみたいと思います.

4. 分解的 vs. 合成的アプローチ―その差異の本質は?―

 本章では,RDB を分解的アプローチと合成的アプローチで設計してみて,両アプローチの違いを観察することによって,特に合成的アプローチの持っている意味合いについて検証してみたいと思います.合成的アプローチの目標は「情報無損失・3NF・関数従属性保存」の RDB を設計することなので,それに合わせて分解的アプローチでの RDB 設計のゴールは「情報無損失・3NF」のリレーションスキーマタからなる RDB を設計することとします.分解的アプローチでは一般に関数従属性は保存されませんから[3],両者を比較するには妥当な条件設定と考えられます.
 それでは,幾つかの例題を通して両アプローチで得られた結果を比較し,その差異を検討してみましょう.

【例題 4】
 リレーションスキーマ R(A, B, C, D)に所与の FD 集合 F={A→B,B→C} が指定されているとする.RDB を合成的アプローチと分解的アプローチで設計してみなさい.
(解答)
 (1) 分解的アプローチで設計した RDB
   R の候補キーは{A, D}で,R の非キー属性は B と C であり,B と C は A に関数従属している,
   つまり{A, D}には完全関数従属していないので R は 2NF ではない.そこで,B→C を使って
   RR[B,C] と R[A, B, D] に情報無損失分解すると,R[A, B, D]も 2NF ではないので,それを
   A→B で R[A, B]と R[A, D]に情報無損失分解する.その結果,{R[A, B], R[B,C], R[A, D]}が
   所望の RDB となる.この場合,関数従属性保存であることは A→B が R[A, B]で,B→C が
   R[B,C]で定義されていることから分かる.
 (2) 合成的アプローチで設計した RDB
   F 自体が F の極小被覆である(ステップ 1).A→B の決定子 A と B→C の決定子 B は異
   なるので,リレーションスキーマタ R1(A, B), R2(B, C) を得る(ステップ 2).ところで,
   R の候補キーは {A, D} であるが,これは R1 にも R2 にも含まれないので,R(A, D) を作
   る(ステップ 3).その結果,{R1(A, B), R2(B, C), R(A, D)}が所望の RDB である.

(解答終)

 この例では,どちらのアプローチをとっても,設計された RDB は同一で,共に「情報無損失分解・3NF・関数従属性保存」となっていることが分かります.

【例題 5】
 リレーションスキーマ R(A, B, C, D)に所与の FD 集合 F={A→B, B→C, A→D, D→C}が指定されているとする.RDB を分解的アプローチと合成的アプローチで設計してみなさい.
(解答)
 (1) 分解的アプローチで設計した RDB
   R の候補キーは A で,R の非キー属性 B, C, D は A に完全関数従属しているので,R は 2NF
   である.しかし,A→B→C と A→D→Cという推移的関数従属性が存在するので 3NF ではない.
   そこで,A→B→C を解消するべく,R を B→C を使って R[B, C] と R[A, B, D] に情報無損失
   分解すると,それらは 3NF になるが D→C を保存できなく,この情報無損失分解は関数従属性
   保存ではないことが分かる.同様に,A→D→C を解消するべく,R を D→C を使って R[D, C]
   と R[A, B, D] に情報無損失分解すると,それらは 3NF になるが B→C を保存できなく,この
   情報無損失分解も関数従属性保存ではないことが分かる[3].したがって,設計された RDB
   {R[B, C], R[A, B, D]} と {R[D, C], R[A, B, D]} はいずれも「情報無損失分解・3NF」ではある
   ものの関数従属性保存ではない.
 (2) 合成的アプローチで設計した RDB
   F 自体が F の極小被覆である(ステップ 1).A→B,A→D であり,B→C,D→C であるので,
   リレーションスキーマタ R1(A, B, D), R2(B, C), R3(D, C) を得る(ステップ 2)ところで,R
   の候補キーは A であるが,A は R1 に含まれているので,{R1(A, B, D), R2(B, C) , R3(D, C)}
   が所望の RDB である(ステップ 3).合成的アプローチをとったことにより,得られた RDB
   は「情報無損失分解・3NF・関数従属性保存」である.

(解答終)

 では,この例で、もう少し詳しく両アプローチを比較・検討してみましょう.両アプローチの下で設計された RDB は次のようでした.

  分解的アプローチ:{R[B, C], R[A, B, D]},あるいは{R[D, C], R[A, B, D]}
  合成的アプローチ:{R1(A, B, D), R2(B, C), R3(D, C)}

 以下,一般性を失うことなく,分解的アプローチで設計された RDB は{R[B, C], R[A, B, D]} であるとして議論を進めます.
 そこで,両者の違いを理解するために,具体的にリレーション R へのタップルの挿入を想定して,その時に観察される現象を見てみることにします.分かり易さのため,R のインスタンス R は単純に 1 本のタップル (a, b, c, d) からなっている,すなわち R={(a, b, c, d)},とします.すると,(a, b, c, d) は分解的アプローチでは R[B, C] ={(b, c)}, R[A, B, D] ={(a, b, d)}} と格納され,合成的アプローチでは R1(A, B, D) ={(a, b, d)}, R2(B, C) ={(b, c)}, R3(D, C) ={(d, c)} と格納されます.そこで,R に D→C に抵触するタップル(a’, b’, c’, d),ここに a’≠a, b≠’b, c≠’c,を挿入しようと目論もくろくんだ場合,何が起こるのか観察してみます(もちろん,R では D→C が成立していますから (a’, b’, c’, d) を挿入することはできません).両アプローチの下で設計された RDB で発生する現象は次の通りです.
 (1) 分解的アプローチで観察される現象

 R[B, C] への (b’, c’) の挿入は既存の (b, c) と抵触しないので行えます.また,R[A, B, D] への (a’, b’, d) の挿入は既存の (a, b, d) と抵触しないので行えます.したがって,R[B, C]={(b, c), (b’, c’)},R[A, B, D]={(a, b, d), (a’, b’, d)} となります.そこで,R[B, C]*R[A, B, D] をとってみると,R[B, C]*R[A, B, D]={(a, b, c, d), (a’, b’, c’, d)} となります.R[B, C] と R[A, B, D] は R の B→C による情報無損失分解なので,これは R= R[B, C]*R[A, B, D]={(a, b, c, d), (a’, b’, c’, d)} を意味することになりますが,R に所与の D→C に抵触することは明らかです.これが B→C による R の{R[B, C], R[A, B, D]} への情報無損失分解が関数従属性保存でないことによる結果なわけです.
 この現象はよりフォーマルに次のように説明できるでしょう.
 まず,リレーションスキーマ R(A, B, C, D) の B→C による分解は情報無損失分解ですが,それは次式を意味します.ここに,(∀R∈R)は R は R の任意のインスタンスを表します.
 (∀R∈R)(R=R[B, C]*R[A, B, D])
 次に,リレーションスキーマ R の定義は次の通りです.
R=(ΩR, FR),ここに,ΩR ={A, B, C, D},FR={A→B, B→C, A→D, D→C}.
 一方,R[B, C]*R[A, B, D] のリレーションスキーマとしての定義は次の通りとなります.
R’=R[B, C]*R[A, B, D]= (ΩR’, FR’),ここに,ΩR’ ={A, B, C, D},FR’ ={A→B, B→C, A→D}.
 そこで,R=(ΩR, FR) と R’ =(ΩR’, FR’)を比較してみると,ΩRR’ ですが,FR+FR’+です.つまり,RR’ はリレーションスキーマとして等価でないことが分かります.
 従って,分解的アプローチで得られた RDB については,次が成立しているといえます.

   (∀R∈R)(R=R[B, C]*R[A, B, C]) ∧
   RR[B, C]*R[A, B, D]      ・・・・・・・・・・(1)

 (2) 合成的アプローチで観察される現象

 R2(B, C) への (b’, c’) の挿入は既存の (b, c) と抵触しないので行えます.また,R1(A, B, D) への (a’, b’, d) の挿入は既存の (a, b, d) と抵触しないので行えます.これらは分解的アプローチでの R[B, C] への (b’, c’) の挿入と R[A, B, D] への (a’, b’, d) の挿入に対応しています.しかし,
R3(D,C)への (d, c’) の挿入は R3 (D,C) で D→C が成立しているので既存の (d, c) と抵触しそれを行えません.したがって,よしんば R2 と R1 へそれぞれ (b’, c’) と (a’, b’, d) が挿入され,R2(B, C)={(b, c), (b’, c’)},R1(A, B, D)={(a, b, d), (a’, b’, d)}となったとしても,R3 には (d, c’) の挿入は許されずに R3(D, C)={(d, c)}のままなので,R=R2(B, C)*R1(A, B, D)*R3(D, C)={(a, b, c, d)}となり,R に D→C に抵触するようなタップルの挿入は許されない仕組みとなっています.つまり,R の {R1(A, B, D), R2(B, C), R3(D, C)}への分解は情報無損失でかつ関数従属性保存の分解となっています.そして,この現象はよりフォーマルに次のように説明できます.
R”=R2(B, C)*R1(A, B, D)*R3(D, C)= (ΩR”, FR”) とすると,ΩR”={A, B, C, D},FR”={A→B, B→C, A→D, D→C} となり,RR” は等価です.つまり,合成的アプローチで得られた RDB については,次が成立していることとなります.

   (∀R∈R)( R=R1(A, B, D)* R2(B, C)*R3(D, C)) ∧
   RR1(A, B, D)*R2(B, C)*R3(D, C) ・・・・・・・・・・(2)

 (1)式と(2)式は分解的アプローチと合成的アプローチの差異をフォーマルに表現していることになります.繰り返しになりますが,両アプローチで設計された RDB は共に情報無損失分解であることは保証されてはいますが,(1)式により分解的アプローチで設計された RDB はリレーションスキーマタの等価関係の不成立により関数従属性保存ではないことを,一方,(2)式により合成的アプローチで設計された RDB はリレーションスキーマタの等価関係の成立により関数従属性保存であることが明確に読み取れます.

 さて,分解的アプローチで設計された RDB と合成的アプローチで設計された RDB を見比べると,R[B, C]≡R2(B, C), R[A, B, D]≡R1(A, B, D) なので,合成的アプローチで設計された RDB では,分解的アプローチにより設計された RDB と比べて R3(D, C) だけ余計(?)に設計されている,と感じるかもしれません.実際,リレーションを RDB に格納するとなると,その分だけ余計にメモリを食うことになります.しかし,上で見た通り,これが関数従属性保存を保証する代償であったわけです.

 RDB の設計にあたっては,設計者は分解的アプローチを採用するべきか,合成的アプローチを採用するべきか,その選択を迫られます.少し乱暴な表現をすれば,「(データを格納するための)メモリは食わないが関数従属性保存の確約はない分解的アプローチ」を選ぶか,「分解的アプローチに比べれば,一般にはメモリを食うものの関数従属性保存を保証してくれる合成的アプローチ」を選ぶか,その決断を RDB 設計者は行わなくてはならないということです.これが分解的 vs. 合成的アプローチのpros and cons(利点と問題点)の一面です.

■ 合成的アプローチでは BCNF にまでなっていることの恩恵
 ところで,3 章で述べた通り,合成的アプローチで設計された RDB のリレーションスキーマタは 3NF より正規度の高い BCNF となっています.このことが,両アプローチの pros and cons と大いに関係することになります.議論は RDB の更新時異状と絡みます.例題を挙げて論じてみましょう.

【例題 6】
 ある学校での,学生(学生名で一意識別),学生が履修する科目(科目名で一意識別),そしてその科目を教授する教員(教員名で一意識別)の関係を表すリレーションスキーマを SCT=(ΩSCT, FSCT),ここに,ΩSCT ={学生,科目名,教員名},FSCT ={{学生名, 科目名}→教員名,教員名→科目名}とする.RDB を分解的アプローチと合成的アプローチで設計してみなさい.
(解答)
 (1) 分解的アプローチで設計した RDB
   リレーションスキーマ SCT の候補キーは{学生名, 科目名}と{学生名, 教員名} と 2 つある.
   したがって,非キー属性は存在しないので 3NF である.そこで,一般性を失うことなく,
   たとえば,{学生名, 科目名} を主キーとすれば,SCT(学生名, 科目名,教員名)が所望の
   RDB である.
 (2) 合成的アプローチで設計した RDB
   FSCT 自体がその極小被覆である(ステップ 1).{学生名, 科目名}→教員名,教員名→科目名
   なので,R1(学生名, 科目名,教員名)と R2 (教員名,科目名)が得られる(ステップ 2).SCT
   の候補キーは{学生名, 科目名}と{学生名, 教員名}であるが,R1 は候補キー{学生名, 科目名}
   を含んでいるので,R1(学生名, 科目名,教員名)と R2(教員名,科目名)が所望の RDB の
   設計結果となる(ステップ 3).

(解答終)

 さて,両アプローチを比較・検討してみましょう.両アプローチの下で設計された RDB は次のようです.

   分解的アプローチ:SCT(学生名, 科目名,教員名)
   合成的アプローチ:R1(学生名, 科目名,教員名), R2(教員名,科目名)

この結果で注意しておくべき点は,SCTR1 の属性集合は等しいものの,リレーションスキーマとしてきちんと表現すれば,SCT=({学生名, 科目名,教員名}, {{学生名, 科目名}→教員名,教員名→科目名}),R1=({学生名, 科目名,教員名}, {{学生名, 科目名}→教員名})であり,{{学生名, 科目名}→教員名,教員名→科目名}+≠{{学生名, 科目名}→教員名}+なので,SCTR1 であること,もう一つは,R1 では定義されていない 教員名→科目名 が R2 で定義されていることです.

 さて,分解的アプローチではリレーションスキーマ SCT そのものが RDB の設計ゴールとなり,この場合「情報無損失分解・3NF・関数従属性保存」となっています.一見,めでたしめでたし,と映りますが,よく知られているように,SCT は 3NF であるが BCNF ではありません.なぜならば,重複する候補キーのペア {学生名, 科目名} と {学生名, 教員名} が存在するからです.したがって,BCNF ではないことによる「更新時異状が発生する」ことになります[5].これらの異状は,「タップル挿入時異状」,「タップル削除時異状」,「タップル修正時異状」として現れますが,たとえばリレーション SCT が図 1 に示すようであったとすると,以下に示すような現象として観察されます.

         SCT

  

  

 

  

 

  

 

  

   学生名   
  科目名  
   教員名   
伊藤
データベース
増永
伊藤
ソフトウェア
西川
中村
データベース
大林
山本
ハードウェア
北川

図 1 分解的アプローチで得られた RDB

タップル挿入時異状:たとえば,新任教員の佐藤が赴任しプログラミングを担当することになったとします.まだ,佐藤先生のプログラミングを履修登録した学生がいないと,タップル(―,プログラミング,佐藤)はキー制約に抵触するので,リレーション SCT には挿入できません.ここに ― はナル(null)を表します.
タップル削除時異状:たとえば,学生の伊藤が西川先生の教えるソフトウェアが難しそうなので履修を取りやめたとすると,タップル(伊藤,ソフトウェア,西川)を削除することになりますが,西川先生の教えるソフトウェアを履修している学生が伊藤一人だったので,西川先生がソフトウェアを教えているという事実を SCT に保存できなくなります.もちろん,(―,ソフトウェア,西川)はキー制約に抵触するので挿入できません.
タップル修正時異状:たとえば,学生の伊藤がソフトウェアではなく北川先生のハードウェアに履修を変更すると,タップル(伊藤,ソフトウェア,西川)を(伊藤,ハードウェア,北川)に修正するのは良いが,同時に西川先生がソフトウェアを教えているという事実を SCT に保存できなくなります.この更新時異状を解消するために,分解的アプローチでは,SCT を SCT[教員名,科目名]と SCT[学生名教員名]に情報無損失分解することになりますが,そうすると関数従属性 {学生名, 科目名}→教員名 が保存できなくなるという新たな異状に直面することになります.

 一方,合成的アプローチではどのような現象が観察されるのか見てみましょう.図 2 に合成的アプローチにより得られた RDB を示します.

         R1

  

  

 

  

 

  

 

  

   学生名   
  科目名  
   教員名   
伊藤
データベース
増永
伊藤
ソフトウェア
西川
中村
データベース
大林
山本
ハードウェア
北川

              R2

  

 

 

 

 

 

 

 

   教員名   
  科目名  
増永
データベース
西川
ソフトウェア
大林
データベース
北川
ハードウェア

図 2 合成的アプローチで得られた RDB

 この場合,分解的アプローチで指摘された更新時異状は発生しません.たとえば,新任教員の佐藤が赴任しプログラミングを担当することになったとすれば,R2 にタップル(佐藤,プログラミング)を挿入すればそれで済みます.したがって,タップル挿入時異状は発生しません.学生の伊藤が西川先生の教えるソフトウェアが難しそうなので履修を取りやめたとすると,R1 からタップル(伊藤,ソフトウェア,西川)を削除することになりますが,西川先生がソフトウェアを教えているという事実は R2 にしっかり保存されています.したがって,タップル削除時異状は観察されません.たとえば,学生の伊藤がソフトウェアではなく北川先生のハードウェアに履修を変更すると,R1 のタップル(伊藤,ソフトウェア,西川)を(伊藤,ハードウェア,北川)に修正するだけでよく,西川先生がソフトウェアを教えているという事実は R2 に保存されており,タップル修正時異状は発生しません.

 フォーマルに上記の議論をまとめておくと,次のようです.
 分解的アプローチで得られた RDB については,次が成立しています.

      (∀R∈R)(R=R) ∧ RR      ・・・・・・・・・・・・・(3)

 一方,合成的アプローチで得られた RDB については,次が成立していいます.

      (∀R∈R)( R=R1(学生名, 科目名,教員名)*R2(教員名,科目名)) ∧
      RR1(学生名, 科目名,教員名)*R2(教員名,科目名)  ・・・・・(4)

 分解的アプローチ,合成的アプローチ,共に情報無損失分解とリレーションスキーマタの等価関係が肯定的に示されましたが,分解的アプローチでは R が 3NF ではあるものの BCNF ではありませんでした.一方,合成的アプローチで得られた R1R2 は共に BCNF です.この差が,分解的アプローチで RDB を設計した場合に,更新時異状発生の原因となったわけです.

 さて,上に示した現象は,RDB を設計するに当たり,分解的アプローチを採るのか合成的アプローチを採るのかという意思決定に際して,関数従属性保存を保証するために必要となるリレーションを格納するために「メモリ」が増加するという視点に加えて,3NF ではあるが BCNF ではないために発生する「更新時異状」という視点も勘案したうえで,どちらのアプローチを採るかを決定しないといけないということを主張しているということで,この 2 軸を勘案すると,これまた少し乱暴な表現となりますが,その選択は次のようにまとめられると思います.
選択 1 :(データを格納するための)メモリは食わないが,設計された RDB が関数従属性保存であ
     るという確約はなく,また,RDB を構成するリレーションスキーマが 3NF ではあるものの
     BCNF の確約はないので,そのことにより更新時異状が発生するかもしれないというリスク
     のある分解的アプローチ
選択 2 : 分解的アプローチに比べれば一般にメモリを食うものの,設計された RDB が関数従属性保
     存で,また,RDB を構成するリレーションスキーマが BCNF であるので,3NF ではあるが
     BCNF ではないことによる更新時異状は発生しないことが約束されている合成的アプローチ

5. おわりに

 本稿では,RDB 設計のための「分解的アプローチ」と「合成的アプローチ」を俎上に上げて蘊蓄うんちくを傾けました.RDB 設計にあたり与えられたリレーションスキーマと指定された所与の関数従属性の集合が同一でも,分解的アプローチと合成的アプローチでは一般に RDB の設計結果は異なります.分解的アプローチは設計された RDB が「情報無損失分解・3NF」であることは保障してくれますが,一般には関数従属性保存は保証してくれません.一方,合成的アプローチは「情報無損失分解・3NF・関数従属性保存」という 3 拍子揃った RDB 設計を保証してくれます.加えて,合成的アプローチでは作られたリレーションスキーマは厳密には BCNF まで正規度が上がっているので,いわゆるリレーションが 3NF ではあるが BCNF ではないために発生してしまう更新時異状も回避することができます.ただ,合成的アプローチは関数従属性保存を担保する代償として,分解的アプローチに比べて格納するべきデータ量は多くなり,メモリを食うことになります.
 さて,この二者択一,貴方ならどちらを選択しますか?

【文献】

[1]

E.F. Codd. A Relational Model of Data for Large Shared Data Banks. Communications of the ACM, Vol.13, No.6, pp.377-387, 1970.

[2]

E.F. Codd. Further Normalization of the Data Base Relational Model. R. Rustin (Ed.), Data Base Systems (Courant Computer Science Symposia 6). Prentice-Hall, Englewood Cliffs, NJ, 1972.

[3]

増永良文.増永教授のDB特論⑤「3NF分解と関数従属性保存」,SRA OSS Tech Blog, 2022.05.11.
https://www.sraoss.co.jp/tech-blog/db-special-lecture/masunaga-db-special-lecture-5/

[4]

P.A. Bernstein. Synthesizing Third Normal Form Relations from Functional Dependencies. ACM Transactions on Database Systems, Vol.1, No.4, pp.277-298, 1976.

[5]

増永良文.リレーショナルデータベース入門[第3版].サイエンス社,2017.

[6]

M.W. Vincent and B. Srinivasan. A Note on Relational Schemes Which Are in 3NF But Not in BCNF. Information Processing Letters 48(6), pp. 281–283, 1993.