commit 6a7a49d6fa0a03f61c14f34ff0c34911dbd9ba09
parent 365f602c7ce3f0d333a99d8cbf12960d98330116
Author: a3nm <>
Date: Sun, 17 Jun 2018 02:18:33 +0200
arity
Diffstat:
1 file changed, 1 insertion(+), 1 deletion(-)
diff --git a/Queries.page b/Queries.page
@@ -4,7 +4,7 @@ All query languages presented here are subclasses of [first-order logic](Logic#f
## Conjunctive queries (CQs)
-A **conjunctive query** (CQ) $Q$ is an existentially quantified conjunction of [atoms](Basic_database_terminology#Atom), i.e., it is of the form $Q : \exists \mathbf{x} ~ R_1(\mathbf{x^1}) \land \cdots \land R_n(\mathbf{x^n})$ where each $\mathbf{x^i}$ uses only variables from $\mathbf{x}$ and each $R_i$ is a [relation](Basic_database_terminology#Relation). We say that $Q$ is **Boolean** if it has no [free variables](First-order logic). We say that an [instance](Basic_database_terminology#Instance) **satisfies** a Boolean conjunctive query $Q$ if there is a **homomorphism** from $Q$ to $I$, i.e., a function $h$ from $\mathbf{x}$ to the [active domain](Basic database terminology#Active_domain) of $I$ such that for all $i$ the fact $R_i(h(\mathbf{x^i}))$ is a fact of $I$, where $h(\mathbf{x^i})$ denotes the tuple obtained by applying $h$ to each element of the tuple $\mathbf{x^i}$.
+A **conjunctive query** (CQ) $Q$ is an existentially quantified conjunction of [atoms](Basic_database_terminology#Atom), i.e., it is of the form $Q : \exists \mathbf{x} ~ R_1(\mathbf{x^1}) \land \cdots \land R_n(\mathbf{x^n})$ where each $\mathbf{x^i}$ uses only variables from $\mathbf{x}$ and each $R_i$ is a [relation](Basic_database_terminology#Relation). The **arity** of $Q$ is its number of [free variables](First-order logic); we call $Q$ **Boolean** if it has no free variables. We say that an [instance](Basic_database_terminology#Instance) **satisfies** a Boolean conjunctive query $Q$ if there is a **homomorphism** from $Q$ to $I$, i.e., a function $h$ from $\mathbf{x}$ to the [active domain](Basic database terminology#Active_domain) of $I$ such that for all $i$ the fact $R_i(h(\mathbf{x^i}))$ is a fact of $I$, where $h(\mathbf{x^i})$ denotes the tuple obtained by applying $h$ to each element of the tuple $\mathbf{x^i}$.
As for non-Boolean queries, given a query $Q(\mathbf{x'})$ with free variables $\mathbf{x'}$, given a tuple $\mathbf{a}$ of elements of the active domain of $I$ with same arity as $\mathbf{x'}$, we say that $\mathbf{a}$ is a **result** to the query $Q(\mathbf{x'})$ on the instance $I$ if there is a homomorphism from $Q(\mathbf{a})$ to $I$,
