Tuple-generating dependency

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

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) → ∃y1, ..., ym, Q(x1, ..., xn,y1, ..., ym),[1] where 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.


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.


  1. ^ Fagin, Ronald (2009). "Tuple-Generating Dependencies". In LIU, LING; ÖZSU, M. TAMER (eds.). Encyclopedia of Database Systems. Springer US. pp. 3201–3202. doi:10.1007/978-0-387-39940-9_1274. ISBN 9780387355443.