Queries.page (2632B)
1 All query languages presented here are subclasses of [first-order logic](Logic#first-order-logic), except Datalog and regular path queries which use [fixpoints](Logic#Fixpoints). 2 3 # Conjunctive queries and variants 4 5 ## Conjunctive queries (CQs) 6 7 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}$. 8 9 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$, 10 11 ## Unions of conjunctive queries (UCQs) 12 13 TODO 14 15 ## Constants 16 17 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}$. 18 19 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. 20 21 ## Tractable languages 22 23 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. 24 25 ## Relational algebra 26 27 Another way to express queries is via the [relational algebra](). 28 29 # Datalog 30 31 TODO 32 33 # Regular path queries 34 35 TODO