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.
A tuple-generating dependency is a sentence in first-order logic of the form:[1] where
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:[2][3] 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