Tuple-generating dependency

In relational database theory, a tuple-generating dependency (TGD) is a certain kind of constraint on a relational database. It is a subclass of the class of embedded dependencies (EDs).

An algorithm known as the chase takes as input an instance that may or may not satisfy a set of TGDs (or more generally EDs) and, if it terminates (which is a priori undecidable), outputs an instance that does satisfy the TGDs.

Definition

A tuple-generating dependency is a sentence in first-order logic of the form:

$\forall x_{1},\ldots ,x_{n}.\phi (x_{1},\ldots ,x_{n})\rightarrow \exists y_{1},\ldots ,y_{m},\psi (x_{1},\ldots ,x_{n},y_{1},\ldots ,y_{m})$

where $\phi$ is a possibly empty and $\psi$ is a non-empty conjunction of relational atoms. A relational atom has the form $R(w_{1},\ldots ,w_{h})$, where each of the terms $w,\ldots ,w_{h}$ are variables or constants.

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, in particular:

• in frontier-guarded TGDs (FGTGD), all the variables shared by the body and the head of a rule (called frontier variables) must occur together in some atom;
• guarded TGDs (GTGD) are particular FGTGDs where all variables used in the body of a rule must occur together in some atom;
• linear TGDs (LTGD) are particular GTGDs where whose body consists of a single atom;
• inclusion dependencies (IND) are particular LTGDs where in both the sides of the rule there is only one relational atom.

In SQL, inclusion dependencies are typically expressed by means of a stronger constraint called foreign key, which forces the frontier variables to be a candidate key in the table corresponding to the relational atom of $\psi$.

Further reading

• Abiteboul, Serge; Hull, Richard B.; Vianu, Victor (1995). Foundations of Databases. Addison-Wesley. ISBN 0-201-53771-0.
• Alin Deutsch, FOL Modeling of Integrity Constraints, https://web.archive.org/web/20140912044956/http://db.ucsd.edu/pubsFileFolder/305.pdf