Conjunctive Queries

a query (mapping) is from (or over) its input schema and to its output schema.

• query: a syntactic object
• query mapping: a function defined by a query interpreted under a specified semantics
  • its domain: the family of all instances of an input schema
  • its range: the family of instances of an output schema
  • we often blur query and query mapping when the meaning is clear from context
• input schema: a specified relation or database schema
• output schema: a relation schema or database schema
  • For a relation schema, the relation name may be specified as part of the query syntax or by the context
• $q_1\equiv q_2$ denotes two queries $q_1$ and $q_2$ over $\text{R}$ are equivalent, i.e., they have the same output schema and $q_1(\text{I})=q_2(\text{I})$ for each instance $\text{I}$ over $\text{R}$.

Logic-Based Perspective

Three versions of conjunctive queries:

1. Rule-Based Conjunctive Queries
2. Tableau Queries
3. Conjunctive Calculus

Rule-Based Conjunctive Queries

Definition

A rule-based conjunctive query (or often more simply called rules) $q$ over a relation schema $\text{R}$ is an expression of the form $$\text{ans}(u)\leftarrow {\text{R}}_1(u_1),\dots ,{\text{R}}_n(u_n)$$ where $n\ge 0$, ${\text{R}}_1,\dots ,{\text{R}}_n$ are relation names in $\text{R}$; $\text{ans}$ is a relation name not in $\text{R}$; and $u,u_1,\dots ,u_n$ are free tuples (i.e., may use either variables or constants).

• $\text{var}(q)$: the set of variables occurring in $q$.
• body: ${\text{R}}_1(u_1),\dots ,{\text{R}}_n(u_n)$
• head: $\text{ans}(u)$
• range restricted: each variable occurring in the head also occurs in the body
  • all conjunctive queries considered here are range restricted
• valuation: a valuation $v$ over $V$, a finite subset of $\text{var}$, is a total function $v$ from $V$ to $\text{dom}$ (of constants)
  • extended to be identity on $\text{dom}$ (so that the domain can contain both variables and constants)
  • extended to map free tuples to tuples (so that the domain/range can be in the tuple form)

Semantics

Let $q$ be the query, and let $\text{I}$ be a database instance of schema $\text{R}$. The image of $\text{I}$ under $q$ is:

$$q(\text{I})=\{v(u)\mid v\text{ is a valuation over }\text{var}(q)\text{ and }v(u_i)\in \text{I}({\text{R}}_i)\text{ for each }i\in [1,n]\}$$

• active domain
  • of a database instance $\text{I}$, denoted $\text{adom}(\text{I})$, is the set of constants that occur in $\text{I}$
  • of a relation instance $I$, denoted $\text{adom}(I)$, is the set of constants that occur in $I$
  • of a query $q$, denoted $\text{adom}(q)$, is the set of constants that occur in $q$
  • $\text{adom}(q,\text{I})$ is an abbreviation for $\text{adom}(q)\cup \text{adom}(\text{I})$
    • $\text{adom}(q(\text{I}))\subseteq \text{adom}(q,\text{I})$
• extensional relations: relations in the body of the query, i.e., ${\text{R}}_1,\dots ,{\text{R}}_n$
  • because they are known/provided by the input instance $\text{I}$
• intensional relation: the relation in the head of the query, i.e., $\text{ans}$
  • because it is not stored and its value is computed on request by the query
• extensional database (edb): a database instance associated with the extensional relations
• intensional database (idb): the rule itself
• idb relation: the relation defined by the idb

Properties

Conjunctive queries are:

• monotonic: a query $q$ over $\text{R}$ is monotonic if for each $\text{I},\text{J}$ over $\text{R}$, $\text{I}\subseteq \text{J}⟹q(\text{I})\subseteq q(\text{J})$
• satisfiable: a query $q$ is satisfiable if there exists a database instance $\text{I}$ such that $q(\text{I})\ne \varnothing$

Tableau Queries

A tableau query is simply a pair $(\text{T},u)$ where $\text{T}$ is a tableau and each variable in $u$ also occurs in $\text{T}$.

This is closest to the visual form provided by Query-By-Example (QBE).

• summary: the free tuple $u$ representing the tuples included in the answer to the query
• embedding: a valuation $v$ for the variables occurring in $\text{T}$ such that $v(\text{T})\subseteq \text{I}$
  • the output of $(\text{T},u)$ on $\text{I}$ consists of all tuples $v(u)$ for each embedding $v$ of $\text{T}$ into $\text{I}$
• typed: a tableau query $q=(\text{T},u)$ under the named perspective, where $\text{T}$ is over relation schema $R$ and $\text{sort}(u)\subseteq \text{sort}(R)$, is typed if no variable of $\text{T}$ is associated with two distinct attributes in $q$

Examples

Table Movies

Table Location

Table Pariscope

The above tableau query is typed because each variable is associated with only one attribute:

• $x_{ti}$: $\text{Title}$
• $x_{ac}$: $\text{Actor}$
• $x_{th}$: $\text{Theater}$
• $x_{ad}$: $\text{Address}$
• $x_p$: $\text{Phone}$
• $x_s$: $\text{Schedule}$

However, the following tableau query is untyped:

Table Movies

Because $x_{ac}$ is associated with both $\text{Director}$ and $\text{Actor}$.

Conjunctive Calculus

The conjunctive query

$$\text{ans}(u)\leftarrow {\text{R}}_1(u_1),\dots ,{\text{R}}_n(u_n)$$

can be expressed as the following conjunctive calculus query that has the same semantics:

$$\left\{e_1,\dots ,e_m|\exists x_1,\dots ,x_k\left(\text{R}(u_1)\wedge \dots \wedge \text{R}(u_n)\right)\right\}$$

where $x_1,\dots ,x_k$ are all the variables occurring in the body and not the head.

Conjunctive Calculus Formula

Let $\text{R}$ be a relation schema. A (well-formed) formula over $\text{R}$ for the conjunctive calculus is an expression having one of the following forms:

1. an atom over $\text{R}$;
2. $\phi \wedge \psi$, where $\phi$ and $\psi$ are formulas over $\text{R}$; or
3. $\exists x\phi$, where $x$ is a variable and $\phi$ is a formula over $\text{R}$.

An occurrence of a variable $x$ in formula $\phi$ is free if:

1. $\phi$ is an atom; or
2. $\phi =(\psi \wedge \xi )$ and the occurrence of $x$ is free in $\psi$ or $\xi$; or
3. $\phi =\exists y\psi$, $x\ne y$, and the occurrence of $x$ is free in $\psi$.

$\text{free}(\phi )$: the set of free variables in $\phi$.

An occurrence of a variable that is not free is bound.

Conjunctive Calculus Query

A conjunctive calculus query over database schema $\text{R}$ is an expression of the form

$$\{e_1,\dots ,e_m\mid \phi \}$$

where

• $\phi$ is a conjunctive calculus formula,
• $⟨e_1,\dots ,e_m⟩$ is a free tuple, and
• the set of variables occurring in $⟨e_1,\dots ,e_m⟩$ is exactly $\text{free}(\phi )$.

For named perspective, the above query can be written as:

$$\{⟨e_1,\dots ,e_m⟩:A_1,\dots ,A_m\mid \phi \}$$

Note: In the previous chapter, a named tuple was usually denoted as:

$$⟨A_1:a_1,\dots ,A_m:a_m⟩$$

But here we denote the named tuple as:

$$⟨e_1,\dots ,e_m⟩:A_1,\dots ,A_m$$

Not sure which one is better or whether the author did this intentionally.

Semantics

Valuation

A valuation over $V\subset \text{var}$ is a total function $v$ from $V$ to $\text{dom}$, which can be viewed as a syntactic expression of the form:

$$\{x_1/a_1,\dots ,x_n/a_n\}$$

where

• $x_1,\dots ,x_n$ is a listing of $V$,
• $a_i=v(x_i)$ for each $i\in [1,n]$.

Interpretation as a Set

If $x\notin V$, and $c\in \text{dom}$, then $v\cup \{x/c\}$ is the valuation over $V\cup \{x\}$ that agrees with $v$ on $V$ and maps $x$ to $c$.

Satisfaction

Let $\text{R}$ be a database schema, $\phi$ a conjunctive calculus formula over $\text{R}$, and $v$ a valuation over $\text{free}(\phi )$. Then $\text{I}\models \phi [v]$, if

1. $\phi =\text{R}(u)$ is an atom and $v(u)\in \text{I}(\text{R})$; or
2. $\phi =(\psi \wedge \xi )$ and $\text{I}\models \psi [v{|}_{\text{free}(\psi )}]$ and $\text{I}\models \xi [v{|}_{\text{free}(\xi )}]$; or
3. $\phi =\exists x\psi$ and there exists a constant $c\in \text{dom}$ such that $\text{I}\models \psi [v\cup \{x/c\}]$.

Image

Let $q=\{e_1,\dots ,e_m\mid \phi \}$ be a conjunctive calculus query over $\text{R}$. For an instance $\text{I}$ over $\text{R}$, the image of $\text{I}$ under $q$ is: $$q(\text{I})=\{v(⟨e_1,\dots ,e_m⟩)\mid v\text{ is a valuation over }\text{free}(\phi )\text{ and }\text{I}\models \phi [v]\}$$

• active domain
  • of a formula $\phi$, denoted $\text{adom}(\phi )$, is the set of constants that occur in $\phi$
  • $\text{adom}(\phi ,\text{I})$ is an abbreviation for $\text{adom}(\phi )\cup \text{adom}(\text{I})$
  • If $\text{I}\models \phi [v]$, then the range of $v$ is contained in $\text{adom}(\text{I})$
    • to evaluate a conjunctive calculus query, one need only consider valuations with range constrained in $\text{adom}(\phi ,\text{I})$, i.e., only a finite number of them
• equivalent: conjunctive calculus formulas $\phi$ and $\psi$ over $\text{R}$ are equivalent, if
  • they have the same free variables and,
  • for each $\text{I}$ over $\text{R}$ and valuation $v$ over $\text{free}(\phi )=\text{free}(\psi )$, $\text{I}\models \phi [v]$ if and only if $\text{I}\models \psi [v]$

Normal Form

$$\exists x_1,\dots ,x_m\left({\text{R}}_1(u_1)\wedge \dots \wedge {\text{R}}_n(u_n)\right)$$

Each conjunctive calculus query is equivalent to a conjunctive calculus query in normal form.

Expressiveness of Query Languages

Let ${\mathcal{Q}}_1$ and ${\mathcal{Q}}_2$ be two query languages.

• ${\mathcal{Q}}_1⊑{\mathcal{Q}}_2$: ${\mathcal{Q}}_1$ is dominated by ${\mathcal{Q}}_2$ (or ${\mathcal{Q}}_2$ is weaker than ${\mathcal{Q}}_1$), if for each query $q_1\in {\mathcal{Q}}_1$, there exists a query $q_2\in {\mathcal{Q}}_2$ such that $q_1\equiv q_2$.
• ${\mathcal{Q}}_1\equiv {\mathcal{Q}}_2$: ${\mathcal{Q}}_1$ and ${\mathcal{Q}}_2$ are equivalent, if ${\mathcal{Q}}_1⊑{\mathcal{Q}}_2$ and ${\mathcal{Q}}_2⊑{\mathcal{Q}}_1$.

The rule-based conjunctive queries, tableau queries, and conjunctive calculus queries are all equivalent.

Incorporating Equality

The conjunctive query

$$\begin{array}{rl}\text{ans}(x_{th},x_{ad})\leftarrow & \text{Movies}(x_{ti},\text{"Bergman"},x_{ac}),\\ & \text{Location}(x_{th},x_{ad},x_p),\text{Pariscope}(x_{th},x_{ti},x_s)\end{array}$$

can be expressed as:

$$\begin{array}{rl}\text{ans}(x_{th},x_{ad})\leftarrow & \text{Movies}(x_{ti},x_d,x_{ac}),x_d=\text{"Bergman"},\\ & \text{Location}(x_{th},x_{ad},x_p),\text{Pariscope}(x_{th},x_{ti},x_s)\end{array}$$

Problem 1: Infinite Answers

Unrestricted rules with equality may yield infinite answers:

$$\text{ans}(x,y)\leftarrow \text{R}(x),y=z$$

A rule-based conjunctive query with equality is a range-restricted rule-based conjunctive query with equality.

Problem 2: Unsatisfiable Queries

Consider the following query:

$$\text{ans}(x)\leftarrow \text{R}(x),x=a,x=b$$

where $\text{R}$ is a unary relation and $a,b\in \text{dom}$ with $a\ne b$.

Each satisfiable rule with equality is equivalent to a rule without equality.
No expressive power is gained if the query is satisfiable.

Query Composition and Views

a conjunctive query program (with or without equality) is a sequence $P$ of rules having the form:

$$\begin{array}{rl}{S}_1(u_1)& \leftarrow {\text{body}}_1\\ S_2(u_2)& \leftarrow {\text{body}}_2\\ & ⋮\\ S_m(u_m)& \leftarrow {\text{body}}_m\end{array}$$

where

• each $S_i$ is a distinct relation name not in $\text{R}$,
• for each $i\in [1,m]$, the only relation names that may occur in ${\text{body}}_i$ are in $\text{R}\cup \{S_1,\dots ,S_{i-1}\}$.

Closure under Composition

If conjunctive query program $P$ defines final relation $S$, then there is a conjunctive query $q$, possibly with equality, such that on all input instances $\text{I}$, $q(\text{I})=P(\text{I})(S)$.

If $P$ is satisfiable, then there is a $q$ without equality.

Composition and User Views

views are specified as queries (or query programs), which may be

• materialized: a physical copy of the view is stored and maintained
• virtual: relevant information about the view is computed as needed
  • queries against the virtual view generate composed queries against the underlying database

Algebraic Perspectives

The Unnamed Perspective: The SPC Algebra

Unnamed conjunctive algebra:

• Selection ($\sigma$)
• Projection ($\pi$)
• Cross-Product (or Cartesian Product, $\times$)

Selection (“Horizontal” Operator)

Primitive Forms: ${\sigma }_{j=a}$ and ${\sigma }_{j=k}$
where $j,k$ are positive integers, and $a\in \text{dom}$ (constants are usually surrounded by quotes).

$${\sigma }_{j=a}(I)=\{t\in I\mid t(j)=a\}$$

${\sigma }_{j=k}$ is sometimes called atomic selection.

Projection (“Vertical” Operator)

General Form: ${\pi }_{j_1,\dots ,j_n}$
where $n\ge 0$ and $j_1,\dots ,j_n$ are positive integers (empty sequence is written $[]$).

$${\pi }_{j_1,\dots ,j_n}(I)=\{⟨t(j_1),\dots ,t(j_n)⟩\mid t\in I\}$$

Cross-Product (or Cartesian Product)

$$I\times J=\{⟨t(1),\dots ,t(n),s(1),\dots ,s(m)⟩\mid t\in I,s\in J\}$$

Formal Inductive Definition

Let $\text{R}$ be a relation schema.

There are two kinds of base SPC (algebra) queries:

1. Input Relation: Expression $R$; with arity equal to $\text{arity}(R)$
2. Unary Singleton Constant: Expression $\{⟨a⟩\}$, where $a\in \text{dom}$; with arity equal to 1

The family of SPC (algebra) queries contains all above base SPC queries and, for SPC queries $q_1,q_2$ with arities ${\alpha }_1,{\alpha }_2$, respectively,

• Selection: ${\sigma }_{j=1}(q_1)$ and ${\sigma }_{j=k}(q_1)$, whenever $j,k\le {\alpha }_1$ and $a\in \text{dom}$; these have arity ${\alpha }_1$.
• Projection: ${\pi }_{j_1,\dots ,j_n}(q_1)$, where $j_1,\dots ,j_n\le {\alpha }_1$; this has arity $n$.
• Cross-Product: $q_1\times q_2$; this has arity ${\alpha }_1+{\alpha }_2$.

Unsatisifiable Queries

E.g. ${\sigma }_{1=a}({\sigma }_{1=b}(R))$ where $\text{arity}(R)\ge 1$ and $a\ne b$.

This is equivalent to $q^{\varnothing }$.

Generalized SPC Algebra

• Intersection ($\cap$): is easily simulated by selection and cross-product.
• Generalized Selection ($\sigma$): permits the specification of multiple conditions.
  • Positive Conjunctive Selection Formula: $F={\gamma }_1\wedge \dots \wedge {\gamma }_n(n\ge 1)$ where each ${\gamma }_i$ is either $j=k$ or $j=a$
  • Positive Conjunctive Selection Operator: an expression of the form ${\sigma }_F$, where $F$ is a positive conjunctive selection formula
  • can be simulated by a sequence of selections
• Equi-Join ($\bowtie$): a binary operator that combines cross-product and selection
  • Equi-Join Condition: $F={\gamma }_1\wedge \dots \wedge {\gamma }_n(n\ge 1)$ where each ${\gamma }_i$ is of the form $j=k$
  • Equi-Join Operator: an expression of the form $I{\bowtie }_{F}J$, where $F$ is an equi-join condition
  • can be simulated by ${\sigma }_{F^{\prime }}(I\times J)$, where $F^{\prime }$ is obtained from $F$ by replacing each condition $j=k$ with $j=\alpha (I)+k$

Normal Form

$${\pi }_{j_1,\dots ,j_n}(\{⟨a_1⟩\}\times \dots \times \{⟨a_m⟩\}\times {\sigma }_F(R_1\times \dots \times R_k))$$ where

• $n\ge 0;m\ge 0$;
• $a_1,\dots ,a_m\in \text{dom}$;
• $\{1,\dots ,m\}\subseteq \{j_1,\dots ,j_n\}$;
• $R_1,\dots ,R_k$ are relation names (repeats permitted);
• $F$ is a positive conjunctive selection formula.

For each (generalized) SPC query, there is an equivalent SPC query in normal form.

The proof is based on repeated application of the following equivalence-preserving SPC algebra rewrite rules (or transformations):

• Merge-Select: $${\sigma }_F({\sigma }_{F^{\prime }}(q))\equiv {\sigma }_{F\wedge F^{\prime }}(q)$$
• Merge-Project: $${\pi }_{\mathbf{j}}({\pi }_{\mathbf{k}}(q))\equiv {\pi }_{\mathbf{l}}(q),\text{ where }{l}_i=k_{j_i}\text{ for each term }{l}_i\text{ in }\mathbf{l}$$
• Push-Select-Though-Project: $${\sigma }_F({\pi }_{\mathbf{j}}(q))\equiv {\pi }_{\mathbf{j}}({\sigma }_{F^{\prime }}(q)),\text{ where }{F}^{\prime }\text{ is obtained from }F\text{ by replacing each }k\text{ with }{j}_k$$
• Push-Select-Though-Singleton: $${\sigma }_{1=j}(⟨a⟩\times q)\equiv ⟨a⟩\times {\sigma }_{(j-1)=a}(q)$$
• Associate-Cross: $$(q_1\times \dots \times q_n)\times q\equiv q_1\times \dots \times q_n\times q$$ $$q\times (q_1\times \dots \times q_n)\equiv q_1\times \dots \times q_n\times q$$
• Commute-Cross: $$(q\times q^{\prime })\equiv {\pi }_{\mathbf{j}{\mathbf{j}}^{\prime }}(q^{\prime }\times q)$$ where ${\mathbf{j}}^{\prime }=[1,\dots ,\text{arity}(q^{\prime })]$ and $\mathbf{j}=[\text{arity}(q^{\prime })+1,\dots ,\text{arity}(q^{\prime })+\text{arity}(q)]$
• Push-Cross-Though-Select: $${\sigma }_F(q)\times q^{\prime }\equiv {\sigma }_F(q\times q^{\prime })$$ $$q\times {\sigma }_F(q^{\prime })\equiv {\sigma }_{F^{\prime }}(q\times q^{\prime })$$ where $F^{\prime }$ is obtained from $F$ by replacing each $j$ with $\text{arity}(q)+j$
• Push-Cross-Though-Project: $${\pi }_{\mathbf{j}}(q)\times q^{\prime }\equiv {\pi }_{\mathbf{j}}(q\times q^{\prime })$$ $$q\times {\pi }_{\mathbf{j}}(q^{\prime })\equiv {\pi }_{{\mathbf{j}}^{\prime }}(q\times q^{\prime })$$ where ${\mathbf{j}}^{\prime }$ is obtained from $\mathbf{j}$ by replacing each $j$ with $\text{arity}(q)+j$

Notation for Rewriting

$$\begin{array}{rl}q& {\to }_{\mathcal{S}}{q}^{\prime }\text{or}\\ \text{simply}q& \to q^{\prime }\end{array}$$

• for a set $\mathcal{S}$ of rewrite rules and algebra expressions $q,q^{\prime }$,
• if $\mathcal{S}$ is understood from the context,
• if $q^{\prime }$ is the result of replacing a subexpression of $q$ according to one of the rules in $\mathcal{S}$.

${\to }_S^{\ast }$: the reflexive and transitive closure of $\to$.

A family $\mathcal{S}$ of rewrite rules is sound if $q{\to }_{\mathcal{S}}{q}^{\prime }$ implies $q\equiv q^{\prime }$. If $\mathcal{S}$ is sound, then $q{\to }_{\mathcal{S}}^{\ast }{q}^{\prime }$ implies $q\equiv q^{\prime }$.

The Named Perspective: The SPJR Algebra

Named conjunctive algebra:

• Selection ($\sigma$)
• Projection ($\pi$); repeats not permitted
• Join ($\bowtie$); natural join
• Renaming ($\delta$)

Selection

${\sigma }_{A=a},{\sigma }_{A=B}$ where $A,B\in \text{att},a\in \text{dom}$

These operators apply to any instance $I$ with $A,B\in \text{sort}(I)$.

Projection

${\pi }_{A_1,\dots ,A_n}$ where $n\ge 0$ and $A_1,\dots ,A_n\in \text{sort}(I)$

(Natural) Join

$$\begin{array}{rl}I\bowtie J=\{t\text{ over }V\cup W|& \text{ for some }v\in I\text{ and }w\in J,\\ & t[V]=v\wedge t[W]=w\}\end{array}$$ where $I$ and $J$ have sorts $V$ and $W$, respectively.

• When $\text{sort}(I)=\text{sort}(J)$, $I\bowtie J=I\cap J$.
• When $\text{sort}(I)\cap \text{sort}(J)=\varnothing$, $I\bowtie J=I\times J$.

Renaming

An attribute renaming for a finite set $U$ of attributes is a one-one mapping from $U$ to $\text{att}$.

$${\delta }_f(I)=\{v\text{ over }f[U]|\text{ for some }u\in I,v(f(A))=u(A)\text{ for each }A\in U\}$$ where

• input is an instance $I$ over $U$
• $f$ is an attribute renaming for $U$
  • which can be described by $(A,f(A))$, where $f(A)\ne A$
    • usually written as $A_1{A}_2\dots A_n\to B_1{B}_2\dots B_n$ to indicate that $f(A_i)=B_i$ for each $i\in [1,n](n\ge 0)$

Formal Inductive Definition

The base SPJR algebra queries are:

1. Input Relation: Expression $R$; with sort equal to $\text{sort}(R)$
2. Unary Singleton Constant: Expression $\{⟨A:a⟩\}$, where $a\in \text{dom}$; with $\text{sort}=A$

The remainder of the syntax and semantics of the SPJR algebra is defined in analogy to those of the SPC algebra.

Normal Form

$${\pi }_{B_1,\dots ,B_m}(\{⟨A_1:a_1⟩\}\bowtie \dots \bowtie \{⟨A_m:a_m⟩\}\bowtie {\sigma }_F({\delta }_{f_1}(R_1)\bowtie \dots \bowtie {\delta }_{f_k}(R_k)))$$ where

• $n\ge 0;m\ge 0$;
• $a_1,\dots ,a_m\in \text{dom}$;
• $\{A_1,\dots ,A_m\}$ occurs in $\{B_1,\dots ,B_n\}$;
• the $A_i$s are distinct;
• $R_1,\dots ,R_k$ are relation names (repeats permitted);
• ${\delta }_{f_i}$ is a renaming operator for $\text{sort}(R_i)$;
• no $A_i$ occur in any ${\delta }_{f_j}(R_j)$;
• the sorts of ${\delta }_{f_1}(R_1),\dots ,{\delta }_{f_k}(R_k)$ are pairwise disjoint;
• $F$ is a positive conjunctive selection formula.

For each SPJR query, there is an equivalent SPJR query in normal form.

Equivalence Theorem

• Lemma: The SPC and SPJR algebras are equivalent.
• Equivalence Theorem: The rule-based conjunctive queries, tableau queries, conjunctive calculus queries, satisifiable SPC algebra, and satisifiable SPJR algebra are all equivalent.

Adding Union

The following have equivalent expressive power:

• the nonrecursive datalog programs (with single relation target)
• the SPCU queries
• the SPJRU queries
  • union can only be applied to expressions having the same sort

Nonrecursive Datalog Program

A nonrecursive datalog program (nr-datalog program) over schema $\text{R}$ is a set of rules:

$$\begin{array}{rl}{S}_1& \leftarrow {\text{body}}_1\\ S_2& \leftarrow {\text{body}}_2\\ & ⋮\\ S_m& \leftarrow {\text{body}}_m\end{array}$$

where

• no relation name in $\text{R}$ occurs in a rule head
• the same relation name may appear in more than one rule head
• there is some ordering $r_1,\dots ,r_m$ of the rules such that the relation name in the head of $r_i$ does not occur in the body of any rule $r_j$ with $j\le i$

Union and the Conjunctive Calculus

Simply permitting disjunction (denoted $\vee$) in the formula of a conjunctive calculus along with conjunction can have serious consequences.

E.g.,

$$q=\{x,y,z|R(x,y)\vee R(y,z)\}$$

The answer of $q$ on nonempty instance $I$ will be

$$q(I)=(I\times \text{dom})\cup (\text{dom}\times I)$$

Because $R(x,y)$ decides that the first two components in $⟨x,y,z⟩$ are in $I$ and $z$ can be anything in $\text{dom}$, and $R(y,z)$ decides that the last two components in $⟨x,y,z⟩$ are in $I$ and $x$ can be anything in $\text{dom}$.