Encyclopedia

Tuple-generating dependency

Wikipedia contributorsAdapted for Fathomly · View authors

2 min read
Source updated November 18, 2025

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.

01Definition

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.

02Fragments

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.

The expressive power of these fragments and TGDs has been studied in depth. For example, Heng Zhang et al., as well as Marco Console and Phokion G. Kolaitis, have developed a series of model-theoretic characterizations for these languages. In addition, Heng Zhang and Guifei Jiang have provided characterizations of the program expressive power of TGDs, several of their extensions, and Linear TGDs, specifically in the context of query answering.

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$ .

Watch videos about Tuple-generating dependencyExplainers and documentaries on YouTube (opens in a new tab)

Sources and credits

This article is adapted from the Wikipedia article “Tuple-generating dependency”, written by its contributors and licensed under CC BY-SA 4.0. Fathomly has changed the layout, removed citation markers, navigation and maintenance notices, and adjusted punctuation. This adapted version is shared under the same license. For references, see the original article.

Fathomly is not affiliated with or endorsed by the Wikimedia Foundation. Spotted a problem? Tell us.