機能的依存性

リレーショナルデータベース理論では、関数従属関係とは、関係における 2 つの属性セット間の次の制約です。関係Rと属性セット が与えられたとき、各X値が 1 つのY値と正確に関連している場合、 X はY を関数的に決定する( X → Yと記述)と言われます。この場合、 R は関数従属関係X → Yを満たすと言われます。同様に、射影は関数、つまりY はXの関数です。^{[1] [2]簡単に言えば、} X属性の値がわかっている場合 (たとえばx )、 xに対応するY属性の値は、x を含むRの任意のタプルでそれらを検索することによって決定できます。通常、Xは決定集合、Y は従属集合と呼ばれます。関数従属関係 FD: X → Y は、 Y がXのサブセットである場合に自明であると呼ばれます。 ${\displaystyle X,Y\subseteq R}$ ${\displaystyle \Pi _{X,Y}R}$

言い換えると、依存関係 FD: X → Y は、 Yの値がXの値によって決定されることを意味します。 Xの同じ値を共有する 2 つのタプルは、必然的にYの値も同じになります。

機能的従属関係の決定は、リレーショナル モデルにおけるデータベースの設計、およびデータベースの正規化と非正規化において重要な部分です。機能的従属関係の単純な応用はヒースの定理です。これは、属性セットU上の、機能的従属関係X → Yを満たす関係Rは、ロスレス結合分解プロパティを持つ 2 つの関係、つまり に安全に分割できるというものです。ここで、 Z = U − XYは残りの属性です。(属性セットの和集合は、データベース理論では、通常、それらの並置によって表されます。) このコンテキストでの重要な概念は候補キーです。これは、関係内のすべての属性を機能的に決定する属性の最小セットとして定義されます。機能的従属関係は、属性ドメインとともに、ユーザー ドメインに不適切なデータをシステムから可能な限り排除する制約を生成するように選択されます。 ${\displaystyle \Pi _{XY}(R)\bowtie \Pi _{XZ}(R)=R}$

論理的含意の概念は、関数従属性に対して次のように定義されます。関数従属性の集合は、 からのすべての従属性を満たす 任意の関係Rが からのすべての従属性も満たす場合、別の依存関係の集合を論理的に含意します。これは通常、 と書きます。関数従属性の論理的含意の概念は、アームストロングの公理として知られる健全で完全な有限公理化を許容します。 ${\displaystyle \Sigma }$${\displaystyle \ガンマ}$${\displaystyle \Sigma }$${\displaystyle \ガンマ}$${\displaystyle \Sigma \models \Gamma }$

車両とそのエンジンの容量を追跡するシステムを設計しているとします。各車両には固有の車両識別番号(VIN) があります。車両のエンジンが複数の容量を持つことは不適切であるため、 VIN → EngineCapacityと記述します(この場合、車両には 1 つのエンジンしかないと仮定します)。一方、EngineCapacity → VIN は、同じエンジン容量の車両が多数存在する可能性があるため、誤りです。

この機能的依存関係は、属性 EngineCapacity を候補キーVIN との関係に配置することを示唆する場合があります。ただし、これは常に適切であるとは限りません。たとえば、この機能的依存関係が推移的な機能的依存関係 VIN → VehicleModel および VehicleModel → EngineCapacity の結果として発生する場合、正規化された関係にはなりません。

この例は、機能的依存性の概念を示しています。モデル化された状況は、大学生が 1 つ以上の講義に出席し、各講義にティーチング アシスタント (TA) が割り当てられているというものです。さらに、すべての学生が何らかの学期に在籍しており、一意の整数 ID で識別されていると仮定します。

この表の 2 つの行に同じ StudentID が含まれている場合、それらの行には必ず同じ Semester 値も含まれていることがわかります。この基本的な事実は、関数の依存関係によって表現できます。

• 学生ID → 学期。

学生の学期の値が異なる行が追加された場合、機能的依存関係 FD は存在しなくなります。これは、FD を無効にする値を持つ可能性があるため、FD がデータによって暗示されていることを意味します。

他にも、次のような重要な機能依存関係を特定できます。

• {学生ID、講義} → TA
• {StudentID、講義} → {TA、学期}

後者は、セット {StudentID, Lecture} が関係の スーパーキーであるという事実を表します。

機能的依存性の典型的な例は、従業員部門モデルです。

このケースは、複数の機能依存関係が単一のデータ表現に埋め込まれている例です。従業員は 1 つの部門にしか所属できないため、その従業員の一意の ID によって部門が決定されることに注意してください。

• 従業員ID → 従業員名
• 従業員ID → 部門ID

この関係に加えて、テーブルには非キー属性を介した機能的な依存関係もあります。

• 部門ID → 部門名

この例では、従業員 ID → 部門 ID という FD が存在するにもかかわらず、従業員 ID は部門名を決定するための論理キーではないことが示されています。データの正規化プロセスでは、すべての FD が認識され、設計者はデータに基づいてより論理的なテーブルと関係を構築できるようになります。

X、Y、Zが関係Rの属性の集合であるとすると、関数従属性のいくつかの特性を導くことができる。最も重要なものは以下の通りで、通常アームストロングの公理と呼ばれる。^[3]

• 反射性: Y がXのサブセットである場合、X → Y
• 拡張: X → Yなら、XZ → YZ
• 推移性: X → YかつY → Zならば、X → Z

「反射性」は に弱めることができる。つまり、それは実際の公理であり、他の2つは適切な推論規則であり、より正確には、次の統語的帰結の規則を生み出す。^[4]${\displaystyle X\rightarrow \varnothing }$

${\displaystyle \vdash X\rightarrow \varnothing }$
${\displaystyle X\rightarrow Y\vdash XZ\rightarrow YZ}$
${\displaystyle X\rightarrow Y,Y\rightarrow Z\vdash X\rightarrow Z}$。

これら3つの規則は、機能的依存関係の健全かつ完全な公理化である。推論規則の数が有限であるため、この公理化は有限であると説明されることがあるが^[5] 、公理と推論規則はすべてスキーマであり、X、Y、Zはすべての基本用語（属性セット）に及ぶという警告がある。^[4]

拡張と推移性を適用することで、次の 2 つの追加ルールを導き出すことができます。

• 擬似推移性：X → YかつYW → Zならば、XW → Z ^[3]
• 合成：X → YかつZ → WならばXZ → YW ^[6]

アームストロングの公理から結合と分解の規則を導くこともできる: ^{[3] [7]}

X → YかつX → Zであるのは、 X → YZの場合のみである。

値のセットの閉包とは、特定の関係に対する機能的依存関係を使用して決定できる属性のセットです。証明には、アームストロングの公理、つまり反射性、拡張性、推移性を使用します。

およびにおいて成り立つFDの集合が与えられている:におけるの閉包( ⁺と表記)は によって論理的に導かれるすべてのFDの集合である。^[8]${\displaystyle R}$${\displaystyle F}$${\displaystyle R}$${\displaystyle F}$${\displaystyle R}$${\displaystyle F}$${\displaystyle F}$

属性の集合 X の閉包は、^{+ を}使用して X によって機能的に決定されるすべての属性の集合 X ⁺です。 ${\displaystyle F}$${\displaystyle F}$

^{次の FD リストを想像してください。この関係から A の閉包 (A +}と表記) を計算します。

1. A → B
2. B → C
3. AB → D

終了は次のようになります。

したがって、A ⁺ = ABCD です。A ⁺には関係内のすべての属性が含まれるため、スーパーキーになります。

定義:内のすべての FDが から推論できる場合、 はカバーされます。⁺ ⊆ ⁺ のすべての関数従属性の集合には、標準的なカバーが存在する場合、はカバーされます。 ${\displaystyle F}$${\displaystyle G}$${\displaystyle G}$${\displaystyle F}$${\displaystyle F}$${\displaystyle G}$${\displaystyle G}$${\displaystyle F}$

スキーマ上のFDと の2 つのセットは、 ⁺ = ⁺の場合、≡と書き、同等です。≡の場合、 はの被覆であり、その逆も同様です。言い換えると、同等の機能的依存関係のセットは、互いの 被覆と呼ばれます。${\displaystyle F}$${\displaystyle G}$${\displaystyle R}$${\displaystyle F}$${\displaystyle G}$${\displaystyle F}$${\displaystyle G}$${\displaystyle F}$${\displaystyle G}$${\displaystyle F}$${\displaystyle G}$

FD の集合は、≡となるの適切な部分集合が存在しない場合に非冗長です 。そのような が存在する場合、は冗長です。が の被覆であり、 が非冗長である場合、 は の非冗長被覆です。 非冗長性の別の特徴付けは、 - { X → Y } X → YとなるFD X → Yが に存在しない場合に は非冗長である ということです。- { X → Y } X → Yである場合、のFD X → Yをで冗長と呼びます。 ${\displaystyle F}$${\displaystyle F'}$${\displaystyle F}$${\displaystyle F'}$${\displaystyle F}$${\displaystyle F'}$${\displaystyle F}$${\displaystyle F}$${\displaystyle G}$${\displaystyle F}$${\displaystyle G}$${\displaystyle F}$
${\displaystyle F}$${\displaystyle F}$${\displaystyle F}$${\displaystyle \models}$ ${\displaystyle F}$${\displaystyle F}$${\displaystyle F}$${\displaystyle \models}$

関数従属性の重要な特性（すぐに応用できる）は、R が列名のある属性セットUを持つリレーションであり、R が関数従属性X → Yを満たす場合、 Z = U − XY が成り立つという点です。直感的には、関数従属性X → Y がRで成り立つ場合、列X（ のキー）に沿って 2 つのリレーションに安全に分割でき、2 つの部分を結合してもデータが失われないことが保証されます。つまり、関数従属性は、Rを2 つの小さなリレーションにロスレス結合分解する簡単な方法を提供します。この事実はヒースの定理と呼ばれることもあり、データベース理論の初期の結果の 1 つです。^[9]${\displaystyle R=\Pi _{XY}(R)\bowtie \Pi _{XZ}(R)}$${\displaystyle \Pi _{XY}(R)\蝶ネクタイ \Pi _{XZ}(R)}$

ヒースの定理は、実質的には、大きなリレーションRからYの値を抽出して 1 つの に格納できることを示しています。この 1 つのテーブルには、 Xの行に値の重複がなく、実質的にはXをキーとするYの参照テーブルであり、したがって、各Xに対応するYを更新する場所は 1 つしかありません。この点は、 「大きな」リレーションRとは異なります。「大きな」リレーション R では、各Xのコピーが多数存在する可能性があり、各コピーは更新時に同期を保つ必要があるYのコピーを持ちます。(この冗長性の排除は、多くの変更が予想されるOLTPコンテキストでは利点になりますが、主にクエリを伴うOLAPコンテキストではそれほど利点になりません。) ヒースの分解により、大きなテーブル の残りの部分では、外部キーとして機能するのはXのみになります。 ${\displaystyle \Pi _{XY}(R)}$${\displaystyle \Pi _{XZ}(R)}$

ただし、機能的依存関係を、外部キーの形式である包含依存関係と混同しないでください。正規化に使用されますが、機能的依存関係は 1 つのリレーション (スキーマ) に対する制約を表現するのに対し、包含依存関係はデータベース スキーマ内のリレーション スキーマ間の制約を表現します。さらに、この 2 つの概念は依存関係の分類においても交差しません。機能的依存関係は等値生成依存関係であるのに対し、包含依存関係はタプル生成依存関係です。リレーション スキーマ分解 (正規化) 後に参照制約を適用するには、包含依存関係という新しい形式が必要です。ヒースの定理から生じる分解では、に見つからないXの値を持つタプルの挿入を妨げるものは何もありません。 ${\displaystyle \Pi _{XZ}(R)}$${\displaystyle \Pi _{XY}(R)}$

正規形は、テーブルの「良さ」を決定するデータベース正規化レベルです。一般的に、第 3 正規形はリレーショナル データベースの「良さ」の標準であると考えられています。^{[引用が必要]}

正規化の目的は、データベースを更新、挿入、削除の異常から解放することです。また、新しい値がリレーションに導入されたときに、データベースへの影響が最小限に抑えられ、データベースを使用するアプリケーションへの影響も最小限に抑えられます。^{[引用が必要]}

関数従属集合 S が次の 3 つの特性を持つ場合、その集合は既約ではありません。

1. S の機能的依存関係の各右セットには、属性が 1 つだけ含まれます。
2. S の機能的従属関係の各左集合は、既約ではありません。つまり、左集合からいずれかの属性を削減すると、S の内容が変わります (S は一部の情報を失います)。
3. 機能的な依存関係を減らすと、S の内容が変更されます。

これらの特性を持つ関数従属関係の集合は、標準的または最小とも呼ばれる。入力として与えられたある入力集合S'と同等な関数従属関係の集合Sを見つけることは、S'の最小被覆を見つけることと呼ばれ、この問題は多項式時間で解くことができる。^[10]

• チェイス（アルゴリズム）
• 包含依存性
• 結合依存関係
• 多値依存関係(MVD)
• データベースの正規化
• 第一正規形

• Codd, EF (1972)。「データベースリレーショナルモデルのさらなる正規化」(PDF)。ACM Transactions on Database Systems。カリフォルニア州サンノゼ: Association for Computing Machinery。

• Gary Burt (1999 年夏)。「CS 461 (データベース管理システム) 講義ノート」。メリーランド大学ボルチモア郡校、コンピュータ サイエンスおよび電気工学部。
• Jeffrey D. Ullman. 「CS345 講義ノート」( PostScript )スタンフォード大学。
• Osmar Zaiane (1998 年 6 月 9 日)。「第 6 章: 整合性制約」。CMPT 354 (データベース システム I) 講義ノート。サイモン フレーザー大学コンピューティング サイエンス学部。