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 ...
, an embedded dependency (ED) 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 the most general type of constraint used in practice, including both
tuple-generating dependencies 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 dependency, embedded dependencies (EDs).
An algorithm known as Chase (algorithm), ...
and
equality-generating dependencies. Embedded dependencies can express functional dependencies, join dependencies, multivalued dependencies, inclusion dependencies, foreign key dependencies, and many more besides.
An algorithm known as
the chase takes as input an instance that may or may not satisfy a set of EDs, and, if it terminates (which is a priori undecidable), output an instance that does satisfy the EDs.
Definition
An embedded dependency (ED) 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
and
and
are
conjunctions
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 astronomy, a conjunction occ ...
of relational and equality atoms.
A relational atom has the form
and an equality atom has the form
, where each of the
terms are
variables or constants.
Restrictions
In literature there are many common restrictions on embedded dependencies, among with:
* ''full'' (or ''universal'') ''dependencies'', which are the ones without
existentially-quantified variables (
)
* ''
tuple-generating dependencies 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 dependency, embedded dependencies (EDs).
An algorithm known as Chase (algorithm), ...
'' (TGDs)
* ''
equality-generating dependencies'' (EGDs)
* ''single-head'' (or ''1-head'') ''dependencies'', which have only one atom in the head
* ''unirelational dependencies'', in which only one relation symbol occurs
When all atoms in
are equalities, the ED is an EGD and, when all atoms in
are relational, the ED is a TGD. Every ED is equivalent to an EGD and a TGD.
Extensions
A common extension of embedded dependencies are ''disjunctive embedded dependencies'' (DED),
which can be defined as follows:
:
where
and
and
are
conjunctions
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 astronomy, a conjunction occ ...
of relational and equality atoms.
Disjunctive embedded dependencies are more expressive than simple embedded dependencies, because DEDs in general can not be simulated using one or more EDs.
An even more expressive constraint is the disjunctive embedded dependency with inequalities (indicated with DED
), in which every
may contain also inequality atoms.
All the restriction above can be applied also to disjunctive embedded dependencies. Beside them, DEDs can also be seen as a generalization of ''disjunctive tuple-generating dependencies'' and ''disjunctive equality-generating dependencies''.
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.
* {{cite book, last=Deutsch, first=Alin, year=2009, title=FOL Modeling of Integrity Constraints (Dependencies), work=Encyclopedia of Database Systems, publisher=Springer US, place=Boston, MA, pages=1155-1161, isbn=978-0-387-39940-9, doi=10.1007/978-0-387-39940-9_980
Database theory
Logic