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). A TGD is a sentence in first-order logic of the form: ∀x1 ... xn, P(x1, ..., xn) → ∃z1, ..., zk, Q(y1, ..., ym) where {z1, ..., zk} = {y1, ..., ym} \ {x1, ..., xn}, and P is a possibly empty and Q is a non-empty conjunction of relational atoms. A relational atom has the form R(w1, ..., wh) 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 (or more generally EDs), and, if it terminates (which is a priori undecidable), outputs an instance that does satisfy the TGDs.

References

• Serge Abiteboul, Richard B. Hull, Victor Vianu: Foundations of Databases. Addison-Wesley, 1995.
• Alin Deutsch, FOL Modeling of Integrity Constraints, http://db.ucsd.edu/pubsFileFolder/305.pdf