Tuple-generating dependency


In relational database theory, a tuple-generating dependency is a certain kind of constraint on a relational database. It is a subclass of the class of embedded dependencies. A TGD is a sentence in first-order logic of the form:
∀x1... xn, P → ∃y1,..., ym, Q, where P is a possibly empty and Q is a non-empty conjunction of relational atoms. A relational atom has the form R where each of the w,..., wh, wi, wj, are variables or constants. An algorithm known as the chase takes as input an instance that may or may not satisfy a set of TGDs, and, if it terminates, outputs an instance that does satisfy the TGDs.

Fragments

Several fragments of TGDs have been defined. For instance, full TGDs are TGDs which do not use the existential quantifier. Full TGDs can equivalently be seen as programs in the Datalog query language. There are also some fragments of TGDs that can be expressed in guarded logic, e.g., guarded TGDs, where we require that all variables used in the body of a rule must occur together in some atom.