**commit** d070346413dab4f2f7a26f73c674198ae5eec678
**parent** 68ec8ee815103b1e18fa07b71cb26b1d671aaae5
**Author:** a3nm <>
**Date:** Sun, 17 Jun 2018 00:56:04 +0200
TGD
**Diffstat:**

1 file changed, 6 insertions(+), 0 deletions(-)

**diff --git a/Constraint languages.page b/Constraint languages.page**
@@ -0,0 +1,5 @@
+All constraint languages mentioned here are expressed in [first-order logic]().
+
+# Tuple-generating dependencies
+
+A **Tuple-Generating Dependency** (TGD) is a logical constraint $\tau$ of the form $\forall \mathbf{x} ~ \phi(x) \rightarrow \exists \mathbf{y} ~ \psi(\mathbf{x}, \mathbf{y})$, where $\phi$ and $\psi$ are [conjunctive queries](Queries#Conjunctive_queries). Given a [database instance](Basic database terminology#Instance) $I$, a **trigger** for $\tau$ in $I$ is a [homomorphism](Queries#Conjunctive_queries) $h$ from $\phi$ to $I$. We say that the trigger $h$ is **active** if there is no homomorphism $h'$ from $\psi$ to $I$ that extends $h$, i.e., the domain of $h'$ is a superset of that of $h$ and $h(x) = h'(x)$ for all $x$ in the domain of $h$. We say that $I$ **satisfies** the TGD $\tau$ if there are no active triggers of $\tau$ on $I$.+
\ No newline at end of file