Embedded dependency とは

リレーショナル・データベース理論では、埋め込み依存関係(ED)は、リレーショナル・データベースに対する特定の種類の制約です。タプル生成依存(TGD)と等価生成依存(EGD)の両方を含む、実際に使用される最も一般的なタイプの制約です。 EDは、関数の依存関係、依存関係の結合、複数値の依存関係、包含関係、外部キー依存関係などを表現することができます。 EDは次の形式の一次論理の文です。
∀x1… xn、P(x1、…、xn)→∃z1、…、zk、Q(y1、…、ym)
ここで、{z1、…、zk} = {y1、…、ym} \ {x1、…、xn}であり、Pはおそらく空であり、Qは、 。関係原子は形式R(w1、…、wh)を持ち、等価原子は次の形式を持ちます。wi = wjここで、w、…、wh、wi、wjはそれぞれ変数または定数です。 Qのすべての原子が等価であるとき、EDはEGDであり、Qのすべての原子が関係するとき、EDはTGDです。すべてのEDは、EGDおよびTGDに相当します。存在量限定子が空の場合、TGDは満杯であると言われます。チェースとして知られているアルゴリズムは、一組のEDを満たしていてもいなくてもよいインスタンスを入力として受け取り、それが終了する(先験的に決めることはできない)場合、EDを満たすインスタンスを出力する。