著書/データベースの仕組み/リレーショナルモデルの設計論/関数従属性

出典: Fukudat.com

目次

§6.1.5 属性集合の閉包 と 定理6.1

本書の中で唯一，証明が与えられているのが定理6.1である．

定理6.1
D \in \{A_1, A_2, \ldots, A_n\}^{+}ならば，そしてその時に限り，FD A_1 A_2 \ldots A_n \rightarrow D が成り立つ．

この定理は，人によっては当たり前と感じるかもしれない[1]のだが，証明は長ったらしいので，煙に巻かれてしまった読者もいるだろう．完全理解を目指して解説を加えてみようと思う．

準備

まず，リレーション R で FD X \rightarrow A が成り立つとはどういうことか，復習しておく（§6.1.1）．

RでX \rightarrow A が成り立つとは，Rの任意の2つのタプルt_1, t_2 \in RでXの値が等しい (t1[X] = t2[X]) ならば，必ずAの値も等しい (t1[A] = t2[A])ことを言うのであった（定義6.1）．

関数従属性を論じるとき，それが成り立つ特定のリレーションインスタンスを考えているのではなく，例6.1の後半に述べられているように，その関数従属性を満たす任意のリレーションインスタンスについて考えているのだ．X \rightarrow Aが成り立っているRは，いろいろ値を変えることができるのだが，何でも勝手な値をとることはできず，Xの値が等しければAの値も等しいという制約が課せられているわけだ．

さて，複数の関数従属性が存在する場合のことを考える．その関数従属性の集合をFとする[2]．F中のすべての関数従属性を満たすリレーションインスタンスは，図6.2に示されるように，個々の関数従属性が許す範囲の共通部分に入っていなければならない． 定理6.1は閉包を求めることでこの共通部分がどのようなものかを正確に過不足なく知ることができると主張している[3]．

定理6.1の証明

さて，定理が主張している次の2点をそれぞれ細かく見ていこう．

(十分性)
D \in \{A_1, A_2, \ldots, A_n\}^{+}ならば， A_1 A_2 \ldots A_n \rightarrow D である．
(必要性)
A_1 A_2 \ldots A_n \rightarrow Dならば，D \in \{A_1, A_2, \ldots, A_n\}^{+}である．

十分性

(十分性)は，「\{A_1, A_2, \ldots, A_n\}^{+}に含まれる属性(D)はすべて，Fを満たす任意のリレーションインスタンスにおいて\{A_1, A_2, \ldots, A_n\}に関数従属する」という意味である．

証明は，基本的な数学的帰納法に則っている．

  • (基底) はアルゴリズムが１回も繰り返しを行わなかった場合に，(十分性)が成り立っていることを確認している．
  • (導出) はアルゴリズムがk − 1回繰り返しを行った時点で(十分性)が成り立っていると仮定したときに，k回目の繰り返しを行っても(十分性)が満たされていることを確認している．

これで，関数従属しない属性を閉包が含むことがないことが確認できた．

必要性

(必要性)は，「Fを満たす任意のリレーションインスタンスにおいてある関数従属性A_1 A_2 \ldots A_n \rightarrow Dが成り立っているのであれば，Dは閉包\{A_1, A_2, \ldots, A_n\}^{+}に必ず含まれる」という意味である．

この対偶を取って，「Bが閉包\{A_1, A_2, \ldots, A_n\}^{+}に含まれないならば，Fを満たすあるリレーションインスタンスにおいてA_1 A_2 \ldots A_n \rightarrow Bは成り立たない」ことを示せばよい．ここで対偶を取ったことで「任意の」が「ある」に変わったことに注意しよう．「任意のXXXでYYYが成り立つ」の否定は「あるXXXが存在してYYYが成り立たない」である[4]．

(必要性)の証明では，成り立たない例(反例)を実際に構成して見せている．

脚注

  1. ↑ 実際，石川博先生の「データベース」（森北出版）では『定義から明らか』(p.53)とし，証明は演習問題5.3として出題されている．
  2. ↑ 本書ではFD集合を飾り文字のエフで表記しているが，ここでは飾り文字が使えないのでイタリックで表記する．
  3. ↑ 厳密に言うと，このためには関数従属性集合の閉包F + を求める必要があるのだが，属性集合の閉包はそれを求めるための手段となる．
  4. ↑ 高校の数Iで学んだと思う．全称命題参照．
"http://www.fukudat.com/wiki/ja/%E8%91%97%E6%9B%B8/%E3%83%87%E3%83%BC%E3%82%BF%E3%83%99%E3%83%BC%E3%82%B9%E3%81%AE%E4%BB%95%E7%B5%84%E3%81%BF/%E3%83%AA%E3%83%AC%E3%83%BC%E3%82%B7%E3%83%A7%E3%83%8A%E3%83%AB%E3%83%A2%E3%83%87%E3%83%AB%E3%81%AE%E8%A8%AD%E8%A8%88%E8%AB%96/%E9%96%A2%E6%95%B0%E5%BE%93%E5%B1%9E%E6%80%A7" より作成
個人用ツール
広告