アームストロングの公理

アームストロングの公理は、リレーショナルデータベースにおけるすべての関数従属性を推論するために使用される公理（より正確には推論規則）の集合である。これらは、ウィリアム・W・アームストロングが1974年の論文^[1]で開発した。これらの公理は、関数従属性の集合（ と表記 ）に適用された場合、その集合（ と表記）の閉包における関数従属性のみを生成するという点で健全である。また、これらの規則を繰り返し適用することで、閉包におけるすべての関数従属性が生成されるという点で完全である。 ${\displaystyle F^{+}}$ ${\displaystyle F}$ ${\displaystyle F^{+}}$

より正式には、関数従属性の集合 を持つ属性集合上の関係スキームを で表すものとします。関数従属性はによって論理的に導かれると言い、 における関数従属性を満たす のすべてのインスタンスに対して も を満たす場合のみ、 で表します。によって論理的に導かれるすべての関数従属性の集合を で表します。 ${\displaystyle \langle R(U),F\rangle }$ ${\displaystyle U}$ ${\displaystyle F}$ ${\displaystyle f}$ ${\displaystyle F}$ ${\displaystyle F\models f}$ ${\displaystyle r}$ ${\displaystyle R}$ ${\displaystyle F}$ ${\displaystyle r}$ ${\displaystyle f}$ ${\displaystyle F^{+}}$ ${\displaystyle F}$

さらに、推論規則の集合 に関して、関数従属性 は内の関数従属性から の推論規則の集合 によって導出可能であるといい、 の推論規則を内の関数従属性に繰り返し適用することによって が得られる場合のみ、それを で表します。の推論規則によってから導出可能なすべての関数従属性の集合を で表します。 ${\displaystyle A}$ ${\displaystyle f}$ ${\displaystyle F}$ ${\displaystyle A}$ ${\displaystyle F\vdash _{A}f}$ ${\displaystyle f}$ ${\displaystyle A}$ ${\displaystyle F}$ ${\displaystyle F_{A}^{*}}$ ${\displaystyle F}$ ${\displaystyle A}$

そして、推論規則のセットが健全なのは、次の条件が満たされる場合のみです。 ${\displaystyle A}$

${\displaystyle F_{A}^{*}\subseteq F^{+}}$

つまり、 によって論理的に導かれない関数従属性を用いてを導出することはできない。推論規則の集合は、以下が成り立つ場合、完全であると言われる。 ${\displaystyle A}$ ${\displaystyle F}$ ${\displaystyle A}$

${\displaystyle F^{+}\subseteq F_{A}^{*}}$

もっと簡単に言えば、によって論理的に暗示されるすべての機能的依存関係を によって導出することができます。 ${\displaystyle A}$ ${\displaystyle F}$

公理（基本ルール）

を属性集合 上の関係スキームとします。以降、、の任意の部分集合を文字 で表し、さらに、2つの属性集合 と の和集合を通常の の代わりに文字で表します。この表記法は、データベース理論において属性集合を扱う際に 標準的なものです。${\displaystyle R(U)}$ ${\displaystyle U}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle Z}$ ${\displaystyle U}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle XY}$ ${\displaystyle X\cup Y}$

反射性の公理

が属性の集合であり、が のサブセットである場合、が成り立ちます。ここで、[ ]が成り立つということは、 が機能的に を決定することを意味します。 ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle X\to Y}$ ${\displaystyle X}$ ${\displaystyle Y}$

もしそうなら。${\displaystyle Y\subseteq X}$ ${\displaystyle X\to Y}$

増加の公理

が成り立ち、が属性の集合である場合、が成り立ちます。これは、依存関係内の属性が基本的な依存関係を変更しないことを意味します。 ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle Z}$ ${\displaystyle XZ}$ ${\displaystyle YZ}$

ならば、任意の に対して となります。${\displaystyle X\to Y}$ ${\displaystyle XZ\to YZ}$ ${\displaystyle Z}$

推移性公理

が成り立ち、 が成り立つ場合、 が成り立ちます。 ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle Y}$ ${\displaystyle Z}$ ${\displaystyle X}$ ${\displaystyle Z}$

かつならば。​${\displaystyle X\to Y}$ ${\displaystyle Y\to Z}$ ${\displaystyle X\to Z}$

追加ルール（二次ルール）

これらの規則は上記の公理から導き出すことができます。

分解

ならば、そして。 ${\displaystyle X\to YZ}$ ${\displaystyle X\to Y}$ ${\displaystyle X\to Z}$

証拠

1.${\displaystyle X\to YZ}$	（与えられた）
2.${\displaystyle YZ\to Y}$	（反射性）
3.${\displaystyle X\to Y}$	（1と2の推移性）

構成

ならば、。 ​${\displaystyle X\to Y}$ ${\displaystyle A\to B}$ ${\displaystyle XA\to YB}$

証拠

1.${\displaystyle X\to Y}$	（与えられた）
2.${\displaystyle A\to B}$	（与えられた）
3.${\displaystyle XA\to YA}$	（1とAの拡張）
4.${\displaystyle YA\to YB}$	（2とYの増分）
5.${\displaystyle XA\to YB}$	（3と4の推移性）

連合

ならば、。 ​${\displaystyle X\to Y}$ ${\displaystyle X\to Z}$ ${\displaystyle X\to YZ}$

証拠

1.${\displaystyle X\to Y}$	（与えられた）
2.${\displaystyle X\to Z}$	（与えられた）
3.${\displaystyle X\to XZ}$	（2とXの増分）
4.${\displaystyle XZ\to YZ}$	（1とZの拡張）
5.${\displaystyle X\to YZ}$	（3と4の推移性）

擬似推移性

ならば、。 ​${\displaystyle X\to Y}$ ${\displaystyle YZ\to W}$ ${\displaystyle XZ\to W}$

証拠

1.${\displaystyle X\to Y}$	（与えられた）
2.${\displaystyle YZ\to W}$	（与えられた）
3.${\displaystyle XZ\to YZ}$	（1とZの拡張）
4.${\displaystyle XZ\to W}$	（3と2の推移性）

自己決定

${\displaystyle I\to I}$ 任意の に対して となる。これは反射性公理から直接導かれる。 ${\displaystyle I}$

拡張性

次の特性は、 の場合の拡張の特殊なケースです。 ${\displaystyle Z=X}$

もし なら、。${\displaystyle X\to Y}$ ${\displaystyle X\to XY}$

拡張性は、他の公理とともに拡張性から証明できるという意味で、公理として拡張性を置き換えることができます。

証拠

1.${\displaystyle XZ\to X}$	（反射性）
2.${\displaystyle X\to Y}$	（与えられた）
3.${\displaystyle XZ\to Y}$	（1と2の推移性）
4.${\displaystyle XZ\to XYZ}$	（拡張度3）
5.${\displaystyle XYZ\to YZ}$	（反射性）
6.${\displaystyle XZ\to YZ}$	（4と5の推移性）

アームストロング関係

関数従属性の集合が与えられたとき、アームストロング関係とは、閉包内の全ての関数従属性と、それらの従属性のみを満たす関係である。与えられた従属性の集合に対する最小サイズのアームストロング関係は、考慮される従属性内の属性数の指数関数となるサイズを持つことができる。^[2]${\displaystyle F}$ ${\displaystyle F^{+}}$

参考文献

1. William Ward Armstrong:データベース関係の依存関係構造、580-583ページ。IFIP会議、1974年。
2. Beeri, C.; Dowd, M.; Fagin, R.; Statman, R. (1984). 「関数従属性におけるアームストロング関係の構造について」(PDF) . Journal of the ACM . 31 : 30– 46. CiteSeerX  10.1.1.68.9320 . doi :10.1145/2422.322414. 2018年7月23日時点のオリジナル(PDF)からのアーカイブ。

外部リンク

• UMBC CMSC 461 春 '99
• スタンフォード大学のCS345講義ノート