アームストロングの公理

アームストロングの公理は、リレーショナル データベースのすべての関数従属性を推論するために使用される公理のセット(より正確には推論規則) です。これらは、ウィリアム 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}$

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

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

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

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

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

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

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

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

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