Tuple-generating dependency とは

リレーショナルデータベース理論では、タプル生成依存関係(TGD)は、リレーショナルデータベースの特定の種類の制約です。これは、埋め込み依存性(ED)のクラスのサブクラスです。 TGDは、∀x1… xn、P(x1、…、xn)→∃y1、…、yk、Q(x1、…、xn)の形式の一次論理の文である。 、y1、…、ym)。ここで、Pは空である可能性があり、Qは関係する原子の空ではない結合です。リレーショナル・アトムは、R(w1、…、wh)の形式を持ちます。ここで、w、…、wh、wi、wjはそれぞれ変数または定数です。追跡として知られているアルゴリズムは、TGD(またはより一般的にはED)のセットを満たすこともあれば満たさないこともあるインスタンスを入力として受け取り、終了する(これは先験的に決定不可能である)場合、TGDを満たすインスタンスを出力する。