git clone
Log | Files | Refs

commit e4b28e0ad0df194efea289c9a930b5d1114cedd7
parent d070346413dab4f2f7a26f73c674198ae5eec678
Author: a3nm <>
Date:   Sun, 17 Jun 2018 01:09:37 +0200


Diffstat: | 32++++++++++++++++++++++++++++++++
1 file changed, 32 insertions(+), 0 deletions(-)

diff --git a/ b/ @@ -0,0 +1,31 @@ +All query languages presented here are subclasses of [first-order logic](), except Datalog and regular path queries which use [fixpoints](First-order_logic#Fixpoints). + +# Conjunctive queries and variants + +## 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}$. + +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$, + +## Unions of conjunctive queries (UCQs) + +TODO + +## Constants + +We sometimes allow CQs and UCQs to contain **constants**, i.e., their atoms $R_i(\mathbf{x^i})$ can use constants in addition to the variables of $\mathbf{x}$. + +We can usually rewrite CQs and UCQs to disallow constants, at the expense of changing the [signature](Basic database terminology#Signature): for each constant $a$ used in the CQ, we replace it by a fresh variable $x_a$ which is existentially quantified, and we add to the CQ the atom $R_a(x_a)$ where $R_a$ is a fresh unary relation. We can then rewrite the input instances by adding the fact $R_a(a)$ for every constant $a$. This clearly ensures that the rewritten CQ on the rewritten instance is equivalent to the original CQ on the original instance. + +## Tractable languages + +Many restrictions of CQs and UCQs have been designed in order to ensure the tractability of the [query evaluation]() task; check this article for such definitions. + +# Datalog + +TODO + +# Regular path queries + +TODO+ \ No newline at end of file