tcswiki

wiki-style
git clone https://a3nm.net/git/tcswiki/
Log | Files | Refs

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