Tuple-generating dependency explained

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.

Definition

A tuple-generating dependency is a sentence in first-order logic of the form:^[1]

\forall x _{1,\ldots,} x _{n} . \phi(x _{1,} \ldots, x _{n)} → \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.

Fragments

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:^{[2] [3]}

• 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.^[4]

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 .

References

1. Book: Fagin, Ronald. Encyclopedia of Database Systems. limited. 2009. Springer US. 9780387355443. LIU. LING. Ling Liu (computer scientist). 3201–3202. en. 10.1007/978-0-387-39940-9_1274. ÖZSU. M. TAMER. Tuple-Generating Dependencies.
2. Reasoning about Disclosure in Data Integration in the Presence of Source Constraints. Michael. Benedikt. Pierre. Bourhis. Louis. Jachiet. Michaël. Thomazo. 1906.00624. 10.24963/ijcai.2019/215. IJCAI 2019 - 28th International Joint Conference on Artificial Intelligence. 1551–1557. Aug 2019. Macao, China.
3. Marco. Console. Phokion G.. Kolaitis. Andreas. Pieris. Model-theoretic Characterizations of Rule-based Ontologies. Symposium on Principles of Database Systems. PODS'21: Proceedings of the 40th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems. June 2021. Virtual Event, China. 416–428. 10.1145/3452021.3458310. free. 11573/1568516. free.
4. Web site: A Tutorial on Database Dependencies. University of California Santa Cruz & IBM Research - Almaden. Kolaitis. Phokion G.. 2021-12-10.

Further reading

• Book: Abiteboul, Serge . Serge Abiteboul . Hull . Richard B. . Richard B. Hull . Vianu . Victor . Victor Vianu . 1995 . Foundations of Databases . Addison-Wesley . 0-201-53771-0.
• Alin Deutsch, FOL Modeling of Integrity Constraints, https://web.archive.org/web/20140912044956/http://db.ucsd.edu/pubsFileFolder/305.pdf