Embedded dependency

Last updated March 06, 2024

In relational database theory, an embedded dependency (ED) is a certain kind of constraint on a relational database. It is the most general type of constraint used in practice, including both tuple-generating dependencies and equality-generating dependencies. Embedded dependencies can express functional dependencies, join dependencies, multivalued dependencies, inclusion dependencies, foreign key dependencies, and many more besides.

Definition

An embedded dependency (ED) is a sentence in first-order logic of the form:

\forall x_{1},\ldots ,x_{n}.\phi (x_{1},\ldots ,x_{n})\rightarrow \exists z_{1},\ldots ,z_{k}.\psi (y_{1},\ldots ,y_{m})

where $\{z_{1},\ldots ,z_{k}\}=\{y_{1},\ldots ,y_{m}\}\setminus \{x_{1},\ldots ,x_{n}\}$ and $\phi$ and $\psi$ are conjunctions of relational and equality atoms.^[1] A relational atom has the form $R(w_{1},\ldots ,w_{h})$ and an equality atom has the form $w_{i}=w_{j}$ , where each of the terms $w,...,w_{h},w_{i},w_{j}$ are variables or constants.

Actually, one can remove all equality atoms from the body of the dependency without loss of generality.^[2] For instance, if the body consists in the conjunction $A(x,y)\land B(y,z,w)\land y=3\land z=w$ , then it can be replaced with $A(x,3)\land B(3,z,z)$ (analogously replacing possible occurrences of the variables $y$ and $w$ in the head). Analogously, one can replace existential variables occurring in the head if they appear in some equality atom.^[2]

Restrictions

In literature there are many common restrictions on embedded dependencies, among with:^[1]^[3]

full (or universal) dependencies, which are the ones without existentially-quantified variables ( $\exists z_{i}$ )
tuple-generating dependencies (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 $\psi$ are equalities, the ED is an EGD and, when all atoms in $\psi$ 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),^[4] which can be defined as follows:

\forall x_{1},\ldots ,x_{n}.\phi (x_{1},\ldots ,x_{n})\rightarrow \bigvee _{i=1}^{\ell }\exists z_{1}^{i},\ldots ,z_{k}^{i}.\psi (y_{1}^{i},\ldots ,y_{m}^{i})

where $\{z_{1}^{i},\ldots ,z_{k}^{i}\}=\{y_{1}^{i},\ldots ,y_{m}^{i}\}\setminus \{x_{1},\ldots ,x_{n}\}$ and $\phi$ and $\psi$ are conjunctions 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 $^{\neq }$ ), in which every $\psi$ may contain also inequality atoms.^[4]

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 (DTGD).^[5]

Related Research Articles

The proof of Gödel's completeness theorem given by Kurt Gödel in his doctoral dissertation of 1929 is not easy to read today; it uses concepts and formalisms that are no longer used and terminology that is often obscure. The version given below attempts to represent all the steps in the proof and all the important ideas faithfully, while restating the proof in the modern language of mathematical logic. This outline should not be considered a rigorous proof of the theorem.

The Riesz representation theorem, sometimes called the Riesz–Fréchet representation theorem after Frigyes Riesz and Maurice René Fréchet, establishes an important connection between a Hilbert space and its continuous dual space. If the underlying field is the real numbers, the two are isometrically isomorphic; if the underlying field is the complex numbers, the two are isometrically anti-isomorphic. The (anti-) isomorphism is a particular natural isomorphism.

<span class="mw-page-title-main">Wave function</span> Mathematical description of the quantum state of a system

In quantum physics, a wave function is a mathematical description of the quantum state of an isolated quantum system. The most common symbols for a wave function are the Greek letters $ψ$ and $Ψ$ . Wave functions are complex-valued. For example, a wave function might assign a complex number to each point in a region of space. The Born rule provides the means to turn these complex probability amplitudes into actual probabilities. In one common form, it says that the squared modulus of a wave function that depends upon position is the probability density of measuring a particle as being at a given place. The integral of a wavefunction's squared modulus over all the system's degrees of freedom must be equal to 1, a condition called normalization. Since the wave function is complex-valued, only its relative phase and relative magnitude can be measured; its value does not, in isolation, tell anything about the magnitudes or directions of measurable observables. One has to apply quantum operators, whose eigenvalues correspond to sets of possible results of measurements, to the wave function $ψ$ and calculate the statistical distributions for measurable quantities.

The Fock space is an algebraic construction used in quantum mechanics to construct the quantum states space of a variable or unknown number of identical particles from a single particle Hilbert space $H$ . It is named after V. A. Fock who first introduced it in his 1932 paper "Konfigurationsraum und zweite Quantelung".

A formula of the predicate calculus is in prenex normal form (PNF) if it is written as a string of quantifiers and bound variables, called the prefix, followed by a quantifier-free part, called the matrix. Together with the normal forms in propositional logic, it provides a canonical normal form useful in automated theorem proving.

Referential integrity is a property of data stating that all its references are valid. In the context of relational databases, it requires that if a value of one attribute (column) of a relation (table) references a value of another attribute, then the referenced value must exist.

In the foundations of mathematics, von Neumann–Bernays–Gödel set theory (NBG) is an axiomatic set theory that is a conservative extension of Zermelo–Fraenkel–choice set theory (ZFC). NBG introduces the notion of class, which is a collection of sets defined by a formula whose quantifiers range only over sets. NBG can define classes that are larger than sets, such as the class of all sets and the class of all ordinals. Morse–Kelley set theory (MK) allows classes to be defined by formulas whose quantifiers range over classes. NBG is finitely axiomatizable, while ZFC and MK are not.

In particle physics, Fermi's interaction is an explanation of the beta decay, proposed by Enrico Fermi in 1933. The theory posits four fermions directly interacting with one another. This interaction explains beta decay of a neutron by direct coupling of a neutron with an electron, a neutrino and a proton.

In mathematics, an ordered basis of a vector space of finite dimension $n$ allows representing uniquely any element of the vector space by a coordinate vector, which is a sequence of $n$ scalars called coordinates. If two different bases are considered, the coordinate vector that represents a vector $v$ on one basis is, in general, different from the coordinate vector that represents $v$ on the other basis. A change of basis consists of converting every assertion expressed in terms of coordinates relative to one basis into an assertion expressed in terms of coordinates relative to the other basis.

Independence-friendly logic is an extension of classical first-order logic (FOL) by means of slashed quantifiers of the form $and, where is a finite set of variables. The intended reading of is "there is a which is functionally independent from the variables in ". IF logic allows one to express more general patterns of dependence between variables than those which are implicit in first-order logic. This greater level of generality leads to an actual increase in expressive power; the set of IF sentences can characterize the same classes of structures as existential second-order logic.$

In mathematical logic, an arithmetical set is a set of natural numbers that can be defined by a formula of first-order Peano arithmetic. The arithmetical sets are classified by the arithmetical hierarchy.

The following are important identities involving derivatives and integrals in vector calculus.

The term "information algebra" refers to mathematical techniques of information processing. Classical information theory goes back to Claude Shannon. It is a theory of information transmission, looking at communication and storage. However, it has not been considered so far that information comes from different sources and that it is therefore usually combined. It has furthermore been neglected in classical information theory that one wants to extract those parts out of a piece of information that are relevant to specific questions.

In mathematics, the spin representations are particular projective representations of the orthogonal or special orthogonal groups in arbitrary dimension and signature. More precisely, they are two equivalent representations of the spin groups, which are double covers of the special orthogonal groups. They are usually studied over the real or complex numbers, but they can be defined over other fields.

In set theory and mathematical logic, the Lévy hierarchy, introduced by Azriel Lévy in 1965, is a hierarchy of formulas in the formal language of the Zermelo–Fraenkel set theory, which is typically called just the language of set theory. This is analogous to the arithmetical hierarchy, which provides a similar classification for sentences of the language of arithmetic.

Dependence logic is a logical formalism, created by Jouko Väänänen, which adds dependence atoms to the language of first-order logic. A dependence atom is an expression of the form $, where are terms, and corresponds to the statement that the value of is functionally dependent on the values of .$

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).

In relational database theory, an equality-generating dependency (EGD) is a certain kind of constraint on data. It is a subclass of the class of embedded dependencies (ED).

In mathematical logic, fixed-point logics are extensions of classical predicate logic that have been introduced to express recursion. Their development has been motivated by descriptive complexity theory and their relationship to database query languages, in particular to Datalog.

Pure inductive logic (PIL) is the area of mathematical logic concerned with the philosophical and mathematical foundations of probabilistic inductive reasoning. It combines classical predicate logic and probability theory. Probability values are assigned to sentences of a first-order relational language to represent degrees of belief that should be held by a rational agent. Conditional probability values represent degrees of belief based on the assumption of some received evidence.

References

1 2 ( Kanellakis 1990 )
1 2 ( Abiteboul, Hull & Vianu 1995 , p. 217)
↑ Greco, Sergio; Zumpano, Ester (Nov 2000). Michel Parigot, Andrei Voronkov (ed.). Querying Inconsistent Databases. 7th International Conference on Logic for Programming Artificial Intelligence and Reasoning. Reunion Island, France: Springer. pp. 308–325. doi:10.1007/3-540-44404-1_20.
1 2 ( Deutsch 2009 )
↑ Zhang, Heng; Jiang, Guifei (Jun 2022). Characterizing the Program Expressive Power of Existential Rule Languages. AAAI Conference on Artificial Intelligence. Vol. 36. pp. 5950–5957. arXiv: 2112.08136 . doi:10.1609/aaai.v36i5.20540.