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.


  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.