In relational
database theory
Database theory encapsulates a broad range of topics related to the study and research of the theoretical realm of databases and database management systems.
Theoretical aspects of data management include, among other areas, the foundations of qu ...
, a tuple-generating dependency (TGD) is a certain kind of constraint on a
relational database
A relational database is a (most commonly digital) database based on the relational model of data, as proposed by E. F. Codd in 1970. A system used to maintain relational databases is a relational database management system (RDBMS). Many relatio ...
. 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
First-order logic—also known as predicate logic, quantificational logic, and first-order predicate calculus—is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quanti ...
of the form:
:
where
is a possibly empty and
is a non-empty
conjunction
Conjunction may refer to:
* Conjunction (grammar), a part of speech
* Logical conjunction, a mathematical operator
** Conjunction introduction, a rule of inference of propositional logic
* Conjunction (astronomy), in which two astronomical bodies ...
of
relational atoms. A relational atom has the form
, where each of the
terms are
variables or constants.
Fragments
Several
fragment
Fragment may refer to:
Entertainment
Television and film
* "Fragments" (''Torchwood''), an episode from the BBC TV series
* "Fragments", an episode from the Canadian TV series ''Sanctuary''
* "Fragments" (Steven Universe Future), an episode f ...
s 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
Datalog is a declarative logic programming language. While it is syntactically a subset of Prolog, Datalog generally uses a bottom-up rather than top-down evaluation model. This difference yields significantly different behavior and properties ...
query language.
There are also some fragments of TGDs that can be expressed in
guarded logic Guarded logic is a choice set of dynamic logic involved in choices, where outcomes are limited.
A simple example of guarded logic is as follows: if X is true, then Y, else Z can be expressed in dynamic logic as (X?;Y)∪(~X?;Z). This shows a guard ...
, in particular:
* 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.
[{{cite web, url=https://www.knaw.nl/shared/resources/actueel/bestanden/kolaitis.pdf#page=5, title=A Tutorial on Database Dependencies, publisher=University of California Santa Cruz & IBM Research - Almaden, last=Kolaitis, first=Phokion G., date=, access-date=2021-12-10]
In
SQL, inclusion dependencies are typically expressed by means of a stronger constraint called
foreign key A foreign key is a set of attributes in a table that refers to the primary key of another table. The foreign key links these two tables. Another way to put it: In the context of relational databases, a foreign key is a set of attributes subject to ...
, which forces the frontier variables to be a
candidate key A candidate key, or simply a key, of a relational database is a minimal superkey. In other words, it is any set of columns that have a unique combination of values in each row (which makes it a superkey), with the additional constraint that removin ...
in the
table
Table may refer to:
* Table (furniture), a piece of furniture with a flat surface and one or more legs
* Table (landform), a flat area of land
* Table (information), a data arrangement with rows and columns
* Table (database), how the table data ...
corresponding to the relational atom of
.
References
Further reading
* Serge Abiteboul, Richard B. Hull
Richard is a male given name. It originates, via Old French, from Old Frankish and is a compound of the words descending from Proto-Germanic ''*rīk-'' 'ruler, leader, king' and ''*hardu-'' 'strong, brave, hardy', and it therefore means 'stron ...
, Victor Vianu: Foundations of Databases. Addison-Wesley, 1995.
* Alin Deutsch, FOL Modeling of Integrity Constraints, https://web.archive.org/web/20140912044956/http://db.ucsd.edu/pubsFileFolder/305.pdf
Database theory
Logic