Table of notationTable of notationGermanTable of
notationNotationstabellesymbolsymbolGermansymbolSymbolmacro namemacro
nameGermanmacro
nameMakronameusesusesGermanusesVerw.descriptiondescriptionGermandescriptionBeschreibungno
entriesno entriesGermanno entrieskeine Einträge variable tree/.style= child
anchor=north, , query/.style= rectangle, draw, child anchor=north, ,
subquery/.style= parent anchor=south, child anchor=north, inner sep=1pt,
regular polygon, regular polygon sides=3, , TU Dortmund University,
<EMAIL_ADDRESS>TU Dortmund University,
<EMAIL_ADDRESS>TU Dortmund University,
<EMAIL_ADDRESS>TU Dortmund University,
<EMAIL_ADDRESS>Gaetano Geck, Jens Keppeler, Thomas
Schwentick, and Christopher Spinrath [500]Theory of computation Data
integration [500]Theory of computation Database query processing and
optimization (theory)

# Rewriting with Acyclic Queries: Mind your Head

Gaetano Geck  Jens Keppeler  Thomas Schwentick  Christopher Spinrath

###### Abstract

The paper studies the _rewriting problem_ , that is, the decision problem
whether, for a given conjunctive query ${Q}$ and a set ${\mathcal{V}}$ of
views, there is a conjunctive query ${Q}^{\prime}$ over ${\mathcal{V}}$ that
is equivalent to ${Q}$, for cases where the query, the views, and/or the
desired rewriting are acyclic or even more restricted.

It shows that, if ${Q}$ itself is acyclic, an acyclic rewriting exists if
there is any rewriting. An analogous statement also holds for free-connex
acyclic, hierarchical, and q-hierarchical queries.

Regarding the complexity of the rewriting problem, the paper identifies a
border between tractable and (presumably) intractable variants of the
rewriting problem: for schemas of bounded arity, the _acyclic rewriting
problem_ is NP-hard, even if both ${Q}$ and the views in ${\mathcal{V}}$ are
acyclic or hierarchical. However, it becomes tractable, if the views are free-
connex acyclic (i.e., in a nutshell, their body is (i) acyclic and (ii)
remains acyclic if their head is added as an additional atom).

###### keywords:

rewriting, acyclic rewriting, acyclic conjunctive queries, free-connex
queries, hierarchical queries, NP-hardness

###### category:

##  1 Introduction

The _query rewriting problem_ asks, for a query ${Q}$ and a set
${\mathcal{V}}$ of views, whether there is a query ${Q}^{\prime}$ over
${\mathcal{V}}$ that is equivalent to ${Q}$, and to find such a _rewriting_
${Q}^{\prime}$.

We emphasise that in the literature, various notions of rewriting are studied
and that the one above is sometimes called _exact_ [8] or _equivalent_ [2].
Since we are in this paper exclusively interested in exact rewritings, we use
the term rewriting in the sense stated above.

Over the last decades, query rewriting has been studied in a wide range of
settings with varying database models (relational, XML, graph, …), query
languages, semantics (set, bag, …) and more. A particular well-known setting
is formed by conjunctive queries (${\mathsf{CQ}}$) under set semantics, which
captures some core aspects of SQL queries. This is also the setting studied in
this paper. We refer to [2, 11, 18] for an overview of the extensive
literature.

In this paper we are interested in a modified version of the query rewriting
problem which does not merely ask for _any_ rewriting but rather for
rewritings that are structurally simple and allow for efficient evaluation.
This is relevant in a setting where access to the database is only possible
through the views, in which case the use of an efficient rewriting is obvious.
It can also be interesting in a scenario where multiple queries have to be
evaluated and it could be useful to evaluate them in some order that allows
many of them to be evaluated efficiently.

The forms of structural simplicity that we consider in this paper are acyclic
(${\mathsf{ACQ}}$) and hierarchical queries (${\mathsf{HCQ}}$), and their
slightly stronger versions free-connex acyclic (${\mathsf{CCQ}}$) and
q-hierarchical queries (${\mathsf{QHCQ}}$). For a brief discussion of the
origin and applications of these classes, we refer to Section 8.

We are interested in two kinds of questions.

  1. (1)

Under which circumstances is it guaranteed that a structurally simple
rewriting exists, if there exists a rewriting at all?

  2. (2)

What is the complexity to decide whether such a rewriting exists and to
compute one?

We study these questions depending on the structure of the given views and the
given query and we consider the same simplicity notions.

In particular, we study the decision problem
${{\textsc{Rewr}}({\mathbb{V}},{\mathbb{Q}},{\mathbb{R}})}$ that asks whether
for a given set of views from ${\mathbb{V}}$ and a query from ${\mathbb{Q}}$,
there is a rewriting from ${\mathbb{R}}$, for various classes ${\mathbb{V}}$,
${\mathbb{Q}}$ and ${\mathbb{R}}$, with an emphasis on the case where
${\mathbb{R}}$ is ${\mathsf{ACQ}}$ or a subclass. In the following we refer to
this case as the _acyclic rewriting problem_. To the best of our knowledge,
there has been no previous work dedicated to the study of questions (1) and
(2).

The answer to question (1) turns out to be very simple and also quite
encouraging: in the case that ${\mathbb{Q}}={\mathsf{ACQ}}$, whenever a
rewriting exists, there is also an acyclic rewriting. And the same is true for
the three subclasses of ${\mathsf{ACQ}}$. That is, for every query in
${\mathsf{CCQ}}$, ${\mathsf{HCQ}}$, or ${\mathsf{QHCQ}}$, whenever a rewriting
exists, there is also a rewriting in ${\mathsf{CCQ}}$, ${\mathsf{HCQ}}$, or
${\mathsf{QHCQ}}$, respectively. Thus, in these cases a rewriting with
efficient evaluation exists, if there is a rewriting at all. This answer to
question (1) simplifies the study of question (2), since it implies that for
${\mathbb{Q}}\in\\{{\mathsf{ACQ}},{\mathsf{CCQ}},{\mathsf{HCQ}},{\mathsf{QHCQ}}\\}$
and ${\mathbb{V}}\subseteq{\mathsf{CQ}}$ the decision problems
${{\textsc{Rewr}}({\mathbb{V}},{\mathbb{Q}},{\mathsf{CQ}})}$ and
${{\textsc{Rewr}}({\mathbb{V}},{\mathbb{Q}},{\mathbb{Q}})}$—and, thus, their
complexities—coincide.

The study of question (2) reveals that the complexity of the acyclic rewriting
problem, may depend on two parameters: the arity of the underlying schema and
the arity of the views. We denote the restriction of
${{\textsc{Rewr}}({\mathbb{V}},{\mathbb{Q}},{\mathbb{R}})}$ to database
schemas of arity at most $k$ by
${{\textsc{Rewr}}^{k}({\mathbb{V}},{\mathbb{Q}},{\mathbb{R}})}$, and we
indicate by ${\mathbb{V}}^{k}$ if the arity of views is at most $k$.

Table 1: Complexity results for the acyclic rewriting problem. Note that
${\mathsf{QHCQ}}\subseteq{\mathsf{CCQ}}\subseteq{\mathsf{ACQ}}$ and
${\mathsf{QHCQ}}\subseteq{\mathsf{HCQ}}\subseteq{\mathsf{ACQ}}$ hold. The head
arity of a view $V$ is the arity of its head atom ${{\textnormal{head}}(V)}$.
The weak head arity of a view is defined in Definition 6.5. In a nutshell, a
view with weak head arity $\ell$ can be ?split? into (multiple) views with
head arity at most $\ell$.

${\mathbb{V}}$ Views |  ${\mathbb{Q}}$ Query |  ${\mathbb{R}}$ Rewriting |  Restriction of views |  ${{\textsc{Rewr}}^{k}({\mathbb{V}},{\mathbb{Q}},{\mathbb{R}})}$ for every $k\in{\mathbb{N}}$
(bounded arity db-schema) |  ${{\textsc{Rewr}}({\mathbb{V}},{\mathbb{Q}},{\mathbb{R}})}$ (unbounded arity db-schema)
---|---|---|---|---|---
${\mathsf{ACQ}}$ | ${\mathsf{ACQ}}$ | ${\mathsf{ACQ}}$ |  |  NP-complete for $k\geq 3$ (Theorem 5.8)
head arity $\leq\ell$
$\ell\in{\mathbb{N}}$ | in polynomial time (Corollary 5.6)
weak head arity $\leq\ell$
$\ell\in{\mathbb{N}}$ | in polynomial time (Theorem 6.12)
${\mathsf{CCQ}}$ |  | in polynomial time (Theorem 6.3) | open
${\mathsf{HCQ}}$ | ${\mathsf{HCQ}}$ | ${\mathsf{HCQ}}$ |  |  NP-complete for $k\geq 3$ (Corollary 7.7)
${\mathsf{QHCQ}}$ |  | in polynomial time | open
${\mathsf{QHCQ}}$ | ${\mathsf{QHCQ}}$ |  | (Corollary 7.6)

Our main findings regarding the complexity of the acyclic rewriting problem
are as follows (see Table 1 for an overview).

  * •

If the query and the views are acyclic and the arity of the views is bounded
by some fixed $k$, then the acyclic rewriting problem is tractable, that is,
for every $k$:
${{\textsc{Rewr}}({\mathsf{ACQ}}^{k},{\mathsf{ACQ}},{\mathsf{ACQ}})}$ is in
polynomial time (Corollary 5.6). Furthermore, an acyclic rewriting can be
computed in polynomial time (if it exists). This follows easily with the help
of the canonical rewriting approach (see [27, Proposition 5.1]) and our answer
to question (1).

  * •

If the query and the views are acyclic and the arity of the views can be
unbounded, then the acyclic rewriting problem is intractable, even if the
database schema has bounded arity, more precisely:
${{\textsc{Rewr}}^{3}({\mathsf{ACQ}},{\mathsf{ACQ}},{\mathsf{ACQ}})}$ is NP-
complete (Theorem 5.8).

  * •

If the query is acyclic, the views are free-connex acyclic, and the arity of
the database schema is bounded by some fixed $k$, then the acyclic rewriting
problem is tractable, that is, for every $k$:
${{\textsc{Rewr}}^{k}({\mathsf{CCQ}},{\mathsf{ACQ}},{\mathsf{ACQ}})}$ is in
polynomial time (Theorem 6.3).

Many results use a characterisation of rewritability, based on the notion of
_cover partitions_ , that might be interesting in its own right. Similar
notions have been used in earlier work, but ours is particularly suited for
the study of exact (equivalent) rewritings.

Our paper is organised as follows: we introduce general basic notions in
Section 2 and notions related to rewritings in Section 3. The characterisation
of rewritability in terms of cover partitions is given in Section 4. The
answer to question (1) and the complexity of the acyclic rewriting problem for
acyclic queries and views are studied in Section 5. The feasibility for free-
connex acyclic views (and an additional class) is presented in Section 6.
Section 7 shows that the answer to question (1) is the same for hierarchical
and q-hierarchical queries and views. Section 8 discusses related work and, in
particular, the relationship of our characterisation of rewritability with
results in the literature. Section 9 concludes.

##  2 Preliminaries

In this section, we fix some notation and recall the basic concepts from
relational databases that are relevant for this paper. Let
${{\mathbb{N}}_{0}}$ denote the set of non-negative integers. Let
${\mathsf{dom}}$ and ${\mathsf{var}}$ be countably infinite sets of _data
values_ (also called _constants_) and _variables_ , respectively. We use the
natural extensions of mappings of variables onto tuples, sets without
notational distinction. That is, for a mapping $f:X\to Y$, we write
$f(X^{\prime})$ for $\\{f(x)\mid x\in X^{\prime}\\}$ and $f({\mathbf{x}})$ for
$(f(x_{1}),\dots,f(x_{k}))$ for sets $X^{\prime}\subseteq X$ and tuples
${\mathbf{x}}=(x_{1},\dots,x_{k})\in X^{k}$, respectively. By id we denote the
identity mapping (on any set of variables).

Databases and queries are formulated over _schemas_ that represent relation
names. A _schema ${\mathcal{S}}$_ is a finite set of relation symbols, where
each symbol $R$ is equipped with a fixed arity
${\textnormal{ar}}(R)\in{{\mathbb{N}}_{0}}$.

##### Databases.

A _fact_ or _$R$ -fact_ $R(a_{1},\dots,a_{r})$ comprises a relation symbol $R$
with some arity $r$ and data values $a_{1},\dots,a_{r}$. A _database_ $D$ over
schema ${\mathcal{S}}$ is a finite subset of $R$-facts for
$R\in{\mathcal{S}}$.

##### Queries.

In this paper, we consider conjunctive queries and restrictions of them. These
queries are conjunctions of relation atoms. An _atom_ is of the form
$R(x_{1},\dots,x_{r})$ with a relation symbol $R$ with arity $r$, and variable
set ${\textnormal{vars}}(A)=\\{x_{1},\dots,x_{r}\\}$. Analogously to facts, an
atom with relation symbol $R$ is called an _$R$ -atom_ if we want to stress
the associated relation (symbol). More generally, ${\mathcal{S}}$-atoms are
$R$-atoms for some symbol $R$ in schema ${\mathcal{S}}$.

We represent a _conjunctive query_ (_CQ_ for short) over schema
${\mathcal{S}}$ as a rule of the form $A\leftarrow A_{1},\dots,A_{m}$ whose
_body_ $\\{A_{1},\dots,A_{m}\\}$ consists of a positive number of atoms and
whose _head_ is a single atom $A$ such that the following two conditions are
satisfied. First, atoms $A_{1},\dots,A_{m}$ refer to relation symbols from
${\mathcal{S}}$ and atom $A$, on the contrary, does not. Second, the query is
_safe_ , that is, every variable in the head occurs in at least one atom of
the body. Let ${{\textnormal{head}}(Q)}$ and ${{\textnormal{body}}(Q)}$ denote
the head and body of a query $Q$, respectively. Variables that occur in the
head of a query are called _head variables_ ; all other variables are called
_quantified variables_. Queries with two or more body atoms that refer to the
same relation are said to have _self-joins_. The _arity_ of a query $Q$ is the
arity of its head atom. Furthermore, a query $Q$ is a Boolean query if the
arity of ${{\textnormal{head}}(Q)}$ is $0$.

Like for sets and tuples, we also use the natural extension of mappings of
variables on atoms without difference in notation: for a mapping
$f:{\mathsf{var}}\to Y$, let $f(A)$ denote $R(f(x_{1}),\dots,f(x_{r}))$ for an
atom $A=R(x_{1},\dots,x_{r})$.

A _valuation_ is a mapping
${\vartheta}:{\mathsf{var}}\mathrel{{\rightharpoonup}}{\mathsf{dom}}$. A
database $D$ _satisfies_ a set ${\mathcal{A}}$ of atoms under a valuation
${\vartheta}$, if ${\vartheta}({\mathcal{A}})\subseteq D$, that is for every
atom $R(x_{1},\ldots,x_{r})$ in ${\mathcal{A}}$ the fact
$R({\vartheta}(x_{1}),\ldots,{\vartheta}(x_{r}))$ is contained in $D$. The
_result_ of query $Q$ on database $D$ is defined as

$Q(D)=\\{{\vartheta}({{\textnormal{head}}(Q)})\mid\text{$D$ satifies
${\textnormal{body}}(Q)$ under ${\vartheta}$}\\}.$

##### Relationships between queries.

Queries over the same schema can be compared with respect to the results they
define. Let $Q_{1}$ and $Q_{2}$ be queries. We say that $Q_{1}$ is _contained_
in $Q_{2}$ (notation: $Q_{1}\mathrel{{\sqsubseteq}}Q_{2}$) if
$Q_{1}(D)\subseteq Q_{2}(D)$ for every database $D$. We say that $Q_{1}$ and
$Q_{2}$ are _equivalent_ (notation: $Q_{1}\equiv Q_{2}$) if
$Q_{1}\mathrel{{\sqsubseteq}}Q_{2}$ and $Q_{2}\mathrel{{\sqsubseteq}}Q_{1}$.

It is well-known that a conjunctive query $Q_{1}$ is contained in a
conjunctive query $Q_{2}$ if and only if there is a homomorphism from the
latter query into the first [9]. Such a _homomorphism_ is a mapping
$h:{\textnormal{vars}}(Q_{2})\to{\textnormal{vars}}(Q_{1})$ such that (1)
$h({{\textnormal{body}}(Q_{2})})\subseteq{{\textnormal{body}}(Q_{1})}$ and (2)
$h({{\textnormal{head}}(Q_{2})})={{\textnormal{head}}(Q_{1})}$. We call $h$ a
_body homomorphism_ if it fulfils condition (1).

A conjunctive query $Q_{1}$ is _minimal_ if there is no conjunctive query
$Q_{2}$ such that $Q_{2}\equiv Q_{1}$ and
$|{{\textnormal{body}}(Q_{2})}|<|{{\textnormal{body}}(Q_{1})}|$ holds.

Despite their simplicity and restricted expressibility, several interesting
problems are intractable for conjunctive queries in general. Therefore,
different fragments have been studied in the literature. In this paper, we are
particularly concerned with ?acyclic? queries, which allow, for instance,
evaluation in polynomial time. We also consider three subclasses of acyclic
queries, namely, free-connex acyclic, hierarchical, and q-hierarchical
queries.

##### Acyclic and free-connex acyclic queries.

A _join tree_ for a query $Q$ is a tree whose vertices are the atoms in the
query’s body that satisfies the following path property: for two atoms
$A,A^{\prime}\in{{\textnormal{body}}(Q)}$ with a common variable $x$, all
atoms on the path from $A$ to $A^{\prime}$ contain $x$. A query $Q$ is
_acyclic_ if it has a join tree. It is _free-connex acyclic_ if $Q$ is acyclic
and the Boolean query whose body is
${{\textnormal{body}}(Q)}\cup\\{{{\textnormal{head}}(Q)}\\}$ is acyclic as
well [3, 7].

##### Hierarchical queries.

For a fixed query $Q$ and some variable $x$ in $Q$, let
${\textnormal{atoms}}(x)$ denote the set of atoms in
${{\textnormal{body}}(Q)}$ in which $x$ appears.

######  Definition  ([12], [6, Definition 3.1]).

A conjunctive query $Q$ is _hierarchical_ if, for all variables $x,y$ in $Q$,
one of the following conditions is satisfied.

${\textnormal{atoms}}(x)\subseteq{\textnormal{atoms}}(y)$

${\textnormal{atoms}}(x)\supseteq{\textnormal{atoms}}(y)$

${\textnormal{atoms}}(x)\cap{\textnormal{atoms}}(y)=\emptyset$ Thus, the
?hierarchy? is established by the query’s variables and the sets of atoms that
contain them.

A conjunctive query $Q$ is _q-hierarchical_ if it is hierarchical and for all
variables $x,y\in{\textnormal{vars}}(Q)$ the following is satisfied: if
${\textnormal{atoms}}(x)\subsetneq{\textnormal{atoms}}(y)$ holds and $x$ is in
the head of $Q$, then $y$ is also in the head of $Q$.

For brevity, we denote by ${\mathsf{CQ}}$, ${\mathsf{ACQ}}$, ${\mathsf{CCQ}}$,
${\mathsf{HCQ}}$, and ${\mathsf{QHCQ}}$ the classes of conjunctive queries in
general and those conjunctive queries that are acyclic, free-connex acyclic,
hierarchical or q-hierarchical, respectively. We note that each q-hierarchical
query is free-connex acyclic [21, Proposition 4.25] and each hierarchical
query is acyclic.111The latter inclusion is mentioned in, e.g. [20, 22]; it
also follows readily from the former inclusion. For acyclicity the head of a
query is of no concern, and the Boolean variant of a hierarchical query is
always q-hierarchical by definition, and, thus, free-connex acyclic which
implies the existence of a join tree for the body of the original query.

##### Views and rewritings.

A view $V$ over a schema ${\mathcal{S}}$ is just a query over schema
${\mathcal{S}}$.222They are called views due to their special role which
distinguishes them from ?normal? queries. A set
${\mathcal{V}}=\\{V_{1},\ldots,V_{k}\\}$ of views induces, for each database
$D$ over schema ${\mathcal{S}}$, the __${\mathcal{V}}$ -defined_ database_
${\mathcal{V}}(D)=V_{1}(D)\cup\dots\cup V_{k}(D).$

In this paper, we consider only views that are conjunctive queries. We
furthermore assume that every view defines its own relation in the derived
database. We denote the set of relation names of the heads of the views in
${\mathcal{V}}$ by ${\mathcal{S}}_{\mathcal{V}}$.

In a nutshell, a rewriting of a query $Q$ over a set ${\mathcal{V}}$ of views
is a query over ${\mathcal{S}}_{\mathcal{V}}$ that is meant to yield, for each
database $D$, the same result over ${\mathcal{V}}(D)$ as $Q$ does over $D$.

######  Definition .

Let $Q$ be a query, ${\mathcal{V}}$ a set of views, and $Q^{\prime}$ a query
over ${\mathcal{S}}_{\mathcal{V}}$. We call $Q^{\prime}$ a _${\mathcal{V}}$
-rewriting of $Q$_ if, for every database $D$, it holds that
$Q^{\prime}({\mathcal{V}}(D))=Q(D)$.

In the literature, rewritings often only aim at approximations of the query
[29] or are defined over ${\mathcal{S}}_{\mathcal{V}}\cup{\mathcal{S}}$ [26],
However, in this paper, we are only interested in _equivalent_ and _complete_
rewritings, where $Q^{\prime}\circ{\mathcal{V}}\equiv Q$ holds and
$Q^{\prime}$ is over ${\mathcal{S}}_{\mathcal{V}}$, respectively.

We illustrate the above definitions by an example.

######  Example 2.1.

Let ${\mathcal{V}}$ be a set of two views

$\displaystyle V_{1}(x,w)$ $\displaystyle\ \leftarrow\
P(v,v^{\prime},x),\;R(x,w),\;S(w),$ $\displaystyle V_{2}(y,z)$ $\displaystyle\
\leftarrow\ S(y),\;T(y,z)$

over schema ${\mathcal{S}}=\\{P,R,S,T\\}$ and let $Q$ be the query

$H(x,y,y^{\prime})\leftarrow
P(u,u^{\prime},x),R(x,w),S(w),T(w,y),T(w,y^{\prime}).$

Query $Q$ yields the same result on database $D$ as the following query
$Q^{\prime}$

$H(x,y,y^{\prime})\leftarrow V_{1}(x,w),V_{2}(w,y),V_{2}(w,y^{\prime})$

over ${\mathcal{V}}(D)$, for each database $D$. Therefore, $Q^{\prime}$ is a
${\mathcal{V}}$-rewriting of $Q$.

##  3 The Rewriting Problem

In this section, we define the rewriting problem, recall some known results
about its complexity and discuss some relevant concepts that were used to
tackle it.

######  Definition 3.1.

Let ${\mathbb{V}}$, ${\mathbb{Q}}$, and ${\mathbb{R}}$ be classes of
conjunctive queries. The _rewriting problem_ for ${\mathbb{V}}$,
${\mathbb{Q}}$, and ${\mathbb{R}}$, denoted
${{\textsc{Rewr}}({\mathbb{V}},{\mathbb{Q}},{\mathbb{R}})}$ asks, upon input
of a query $Q\in{\mathbb{Q}}$ and a (finite) set
${\mathcal{V}}\subseteq{\mathbb{V}}$ of views, whether there is a
${\mathcal{V}}$-rewriting of $Q$ in the class ${\mathbb{R}}$. We write
${{\textsc{Rewr}}^{k}({\mathbb{V}},{\mathbb{Q}},{\mathbb{R}})}$ for the
restriction, where the arity of the database schema is bounded by $k$.

In general, the rewriting problem for conjunctive queries is NP-complete.

######  Theorem 3.2 ([26, Theorem 3.10]).

${{\textsc{Rewr}}({\mathsf{CQ}},{\mathsf{CQ}},{\mathsf{CQ}})}$ is NP-complete.

There is a straightforward, albeit in general inefficient, way of finding a
rewriting for a conjunctive query and views. In fact, it can be shown that,
for given $Q$ and ${\mathcal{V}}$, a rewriting $Q^{\prime}$ over
${\mathcal{V}}$ exists, if and only if a certain canonical query
${{\mathsf{canon}}(Q,{\mathcal{V}})}$ exists and is a rewriting.

This _canonical candidate_ ${{\mathsf{canon}}(Q,{\mathcal{V}})}$ can be
obtained by evaluating ${\mathcal{V}}$ on the canonical database
${{\mathsf{canon}}(Q)}$, which in turn is defined as the set of body atoms of
$Q$ viewed as facts, in which the variables are considered as fresh constants.
The canonical candidate has the same head as $Q$ and its body is just
${\mathcal{V}}({{\mathsf{canon}}(Q)})$.333But here the variables are again
considered as variables. If the canonical candidate turns out to be a
rewriting, then we often call it _canonical rewriting_.

An important detail should be mentioned here: the canonical candidate does not
always exist, e.g., if ${\mathcal{V}}({{\mathsf{canon}}(Q)})$ does not contain
all head variables of $Q$ or it is outright empty. In that case, there is no
rewriting.

######  Proposition 3.3 ([27, Proposition 5.1]).

Let $Q$ be a conjunctive query and ${\mathcal{V}}$ a set of views. If there is
a ${\mathcal{V}}$-rewriting of $Q$, then the canonical candidate
${{\mathsf{canon}}(Q,{\mathcal{V}})}$ is such a rewriting.

For conjunctive queries without self-joins this had been shown in [10, Lemma
7].

######  Example 3.4.

Let us consider the query $Q$ defined by

$H(x,y,z)\leftarrow C(x,y,z),\;R(x,y),\;S(y,z),\;T(z,x)$

and the views

$\displaystyle V_{1}(u,v,w)\leftarrow C(u,v,w)\ \ \text{ and }\ \
V_{2}(x,y,z,u)\leftarrow R(x,y),\;S(y,z),\;T(z,u).$

Evaluating the views $V_{1}$ and $V_{2}$ on the canonical database
${{\mathsf{canon}}(Q)}$ of $Q$ yields the result
$\\{V_{1}(x,y,z),V_{2}(x,y,z,x)\\}$. Thus, the query $Q^{\prime}$ defined by

$H(x,y,z)\leftarrow V_{1}(x,y,z),V_{2}(x,y,z,x)$

is the canonical candidate, which happens to be an actual
${\mathcal{V}}$-rewriting.

In this example, it is easy to see that canonical candidate is a
${\mathcal{V}}$-rewriting, without considering any (let alone all) databases.
In fact, in this particular case, this can be established with the help of an
expansion of the rewriting. Before we define expansions, we need one more
definition.

######  Definition 3.5 (View Application).

An _application_ of a view $V$ is a substitution
${\alpha}\colon{\textnormal{vars}}(V)\to{\mathsf{var}}$ that does not unify
any quantified variable $x$ of $V$ with another variable of $V$.

We say that a collection $\alpha_{1},\ldots,\alpha_{m}$ of applications for
views $V_{1},\ldots,V_{m}$ fulfils _quantified variable disjointness_ , if for
all $i,j\in\\{1,\ldots,m\\}$, each quantified variable $x$ of $V_{i}$ and each
variable $y$ of $V_{j}$ with $i\neq j$, it holds
$\alpha_{i}(x)\not=\alpha_{j}(y)$. That is, a quantified variable of a view is
never mapped to the same variable as any other variable of the same or any
other view. This ensures that, for all $i,j\in\\{1,\ldots,m\\}$ with $i\neq
j$, the bodies $\alpha_{i}({{\textnormal{body}}(V_{i})})$ and
$\alpha_{j}({{\textnormal{body}}(V_{j})})$ do not share any variables that do
not occur in
${{\textnormal{vars}}(\alpha_{i}({{\textnormal{head}}(V_{i})}))}\cap{{\textnormal{vars}}(\alpha_{j}({{\textnormal{head}}(V_{j})}))}$.

######  Definition 3.6 (Expansion).

Let ${\mathcal{V}}$ be a set of views over a schema ${\mathcal{S}}$ and let
$Q^{\prime}$ be a query with
${{\textnormal{body}}(Q^{\prime})}=\\{A^{\prime}_{1},\dots,A^{\prime}_{m}\\}$
over the schema ${\mathcal{S}}_{\mathcal{V}}$. Furthermore, let, for each
$i\in\\{1,\dots,m\\}$, ${\alpha}_{i}$ be an application and $V_{i}$ be a view
such that $A^{\prime}_{i}={\alpha}_{i}({{\textnormal{head}}(V_{i})})$, such
that $\alpha_{1},\ldots,\alpha_{m}$ fulfil quantified variable disjointness.

The _expansion of $Q^{\prime}$ w.r.t. ${\mathcal{V}}$ and
${\alpha}_{1},\ldots,{\alpha}_{m}$_ is the query that has the same head as
$Q^{\prime}$ and body
$\bigcup_{i=1}^{m}{\alpha}_{i}({{\textnormal{body}}(V_{i})}).$

Since the applications ${\alpha}_{1},\ldots,{\alpha}_{m}$ in Definition 3.6
are uniquely determined up to renaming of quantified variables, we usually do
not mention them explicitly and just speak of an expansion of $Q^{\prime}$
w.r.t. ${\mathcal{V}}$.

We note that the expansion of $Q^{\prime}$ can be directly compared with $Q$
since it is over the same schema. In fact, $Q^{\prime}$ is a
${\mathcal{V}}$-rewriting of $Q$ if and only if the expansion is equivalent to
$Q$. In Example 3.4, this is obviously the case, since (the only) expansion of
$Q^{\prime}$ w.r.t. ${\mathcal{V}}$ even coincides with $Q$.

If there is no a priori bound on the arity of views, then the canonical
candidate can be of exponential size in $|Q|+|{\mathcal{V}}|$. However, if
there is a rewriting, then there always is one of polynomial size. In fact, at
most $n$ view applications are needed if the body of query $Q$ contains $n$
atoms [26, Lemma 3.5]. Therefore, and because equivalence of ${\mathsf{CQ}}$
can be tested in NP,
${{\textsc{Rewr}}({\mathsf{CQ}},{\mathsf{CQ}},{\mathsf{CQ}})}$ is in NP.

In general, the above characterisation of rewritability is not algorithmically
useful for our purposes, due to the potentially exponential size of canonical
candidates. However, in some cases it can be used to obtain efficient
algorithms. However, for acyclic views of bounded arity and acyclic queries,
the situation is much better. For a class ${\mathbb{V}}$ of views, we write
${\mathbb{V}}^{k}$ for the restriction to views of arity at most $k$.

######  Proposition 3.7.

For every $k\geq 0$,
${{\textsc{Rewr}}({\mathsf{ACQ}}^{k},{\mathsf{ACQ}},{\mathsf{CQ}})}$ is in
polynomial time.

######  Proof 3.8 (Proof idea.).

We first observe that, if it exists, the canonical candidate always obeys
$Q\mathrel{{\sqsubseteq}}{{\mathsf{canon}}(Q,{\mathcal{V}})}$. Indeed, a
homomorphism from an expansion of ${{\mathsf{canon}}(Q,{\mathcal{V}})}$ to $Q$
can be obtained by combining the valuations that yield
${\mathcal{V}}({{\mathsf{canon}}(Q)})$ from ${{\mathsf{canon}}(Q)}$ as
follows: To improve readability and avoid technical clutter we identify the
variables in $Q$ with their corresponding constants in ${{\mathsf{canon}}(Q)}$
in the following. Notably, this means that we identify ${{\mathsf{canon}}(Q)}$
with ${{\textnormal{body}}(Q)}$, i.e. we write
${{\mathsf{canon}}(Q)}={{\textnormal{body}}(Q)}$.

Let $A^{\prime}_{1},\ldots,A^{\prime}_{m}$ be the atoms of
${{\mathsf{canon}}(Q,{\mathcal{V}})}$ and, for each $i\in\\{1,...,m\\}$, let
${\alpha}_{i}$ be an application and $V_{i}$ be a view such that
$A^{\prime}_{i}={\alpha}_{i}({{\textnormal{head}}(V_{i})})$, such that
${\alpha}_{1},\ldots,{\alpha}_{m}$ fulfil quantified variables disjointness.
Furthermore, since the $A^{\prime}_{i}$ are also contained in
${\mathcal{V}}({{\mathsf{canon}}(Q)})$ by definition of
${{\mathsf{canon}}(Q,{\mathcal{V}})}$, there are valuations ${\vartheta}_{i}$
such that $A_{i}^{\prime}={\vartheta}_{i}({{\textnormal{head}}(V_{i})})$ and
${\vartheta}_{i}({{\textnormal{body}}(V_{i})})\subseteq{{\mathsf{canon}}(Q)}$
holds. In particular, we have that
${\vartheta}_{i}({{\textnormal{head}}(V_{i})})={\alpha}_{i}({{\textnormal{head}}(V_{i})})$
for all $i\in\\{1,\ldots,m\\}$.

Let $y$ be a variable occuring in ${\alpha}_{i}({{\textnormal{body}}(V_{i})})$
and $x$ such that $y={\alpha}_{i}(x)$ for some $i\in\\{1,\ldots,m\\}$. Then
the desired homomorphism $h$ maps $y$ to ${\vartheta}_{i}(x)$. Note that $h$
is the identity on variables occuring in
${\alpha}_{i}({{\textnormal{head}}(V_{i})})$ because
${\alpha}_{i}({{\textnormal{head}}(V_{i})})={\vartheta}_{i}({{\textnormal{head}}(V_{i})})$
and, thus, $y={\alpha}_{i}(x)={\vartheta}_{i}(x)=h(y)$. Hence, $h$ is well-
defined, since, if a variable $y$ occurs in
${\alpha}_{i}({{\textnormal{body}}(V_{i})})$ and
${\alpha}_{j}({{\textnormal{body}}(V_{j})})$ with $i\neq j$ then it also
occurs in ${\alpha}_{i}({{\textnormal{head}}(V_{i})})$ and
${\alpha}_{j}({{\textnormal{head}}(V_{j})})$ thanks to quantified variable
disjointness.

It is easy to see that $h$ is a homomorphism from
${{\mathsf{canon}}(Q,{\mathcal{V}})}$ to $Q$, since
$h({\alpha}_{i}({{\textnormal{body}}(V_{i})}))={\vartheta}_{i}({{\textnormal{body}}(V_{i})})\subseteq{{\mathsf{canon}}(Q)}$
holds for all $i\in\\{1,\ldots,m\\}$ and $h$ is the identity on all variables
occuring in the head of ${{\mathsf{canon}}(Q,{\mathcal{V}})}$.

Therefore, to test for rewritability, it suffices to check whether
${{\mathsf{canon}}(Q,{\mathcal{V}})}\mathrel{{\sqsubseteq}}Q$. If the query
and views are acyclic and the arity of the views is bounded by a constant,
thus rewritability can be tested efficiently by computing the polynomial-sized
canonical candidate ${{\mathsf{canon}}(Q,{\mathcal{V}})}$ in polynomial time
and then testing in polynomial time whether a homomorphism from $Q$ to
${{\mathsf{canon}}(Q,{\mathcal{V}})}$ exists.444Evaluating and testing
containment for acyclic conjunctive queries is in polynomial time [31, 1].
Thus, the statement follows due to Proposition 3.3.

Chekuri and Rajaraman have shown that the rewriting problem is in P for
acyclic queries without self-joins and arbitrary views using a similar idea
[10, Theorem 5].

However, even for Boolean views and databases over a small fixed schema, it
does not suffice to restrict only the query or only the views to acyclic
queries.

######  Proposition 3.9.

${{\textsc{Rewr}}^{k}({\mathsf{CQ}}^{0},{\mathsf{ACQ}},{\mathsf{CQ}})}$ and
${{\textsc{Rewr}}^{k}({\mathsf{ACQ}}^{0},{\mathsf{CQ}},{\mathsf{CQ}})}$ are
NP-hard, for every $k\geq 3$. This even holds for Boolean queries, view sets
with only one Boolean view and a schema with two relations of maximum arity 3.

######  Proof 3.10.

We first show, by a reduction from the three-colouring problem, that it is NP-
hard to test whether, for an _acyclic_ Boolean conjunctive query $Q_{1}$ and a
Boolean conjunctive query $Q_{2}$, whether $Q_{1}\mathrel{{\sqsubseteq}}Q_{2}$
holds.555We think that this is folklore knowledge but could not find a
reference for it.

To this end, let $G$ be an undirected graph without isolated vertices and
self-loops (i.e. edges of the form $(v,v)$). With each vertex $v$ of $G$ we
associate a variable $x_{v}$. We define $Q_{2}$ to be the Boolean conjunctive
query with head $H()$ that consists of all atoms $E(x_{v},x_{w})$ such that
$(v,w)$ is an edge in $G$. The Boolean query $Q_{1}$ is defined by the rule

$H()\leftarrow E(b,r),E(r,y),E(y,b),E(r,b),E(y,r),E(b,y),C(b,r,y).$

where $b,r,y$ are variables representing the colours blue, red, and yellow.
Observe that $Q_{1}$ is acyclic, because all variables are contained in the
?cover-atom? $C(b,r,y)$.

It is well-known that $Q_{1}\mathrel{{\sqsubseteq}}Q_{2}$ holds if and only if
there is a homomorphism $h$ from $Q_{2}$ to $Q_{1}$. For the correctness of
our reduction it suffices to observe that any such $h$ represents a valid
colouring, since two variables $x_{v}$ and $x_{w}$ cannot be mapped to the
same variable in $Q_{1}$ if there is an edge $(v,w)$ in $G$. Conversely, every
valid colouring of $G$ gives rise to a homomorphism from $Q_{2}$ to $Q_{1}$.

Since it is well-known that $Q_{1}\mathrel{{\sqsubseteq}}Q_{2}$ if and only if
$Q_{1}\equiv Q_{2}\land Q_{1}$, we conclude in the second step that the
equivalence problem for Boolean conjunctive queries $Q_{1},Q_{2}$ is NP-hard,
even if $Q_{1}$ is acyclic.

Finally, we reduce the latter problem to the rewriting problem. Let thus
$Q_{1}$ and $Q_{2}$ be Boolean conjunctive queries. The input instance
$(Q_{1},Q_{2})$ for the equivalence problem is mapped to an input instance for
the rewriting problem by assigning $Q_{1}$ the role of the query and $Q_{2}$
the role of (the sole) view.

The canonical rewriting, if it exists, consists only of the single atom
$Q_{2}()$, since $Q_{2}$ is a Boolean query. Thus, there is a
$Q_{2}$-rewriting of $Q_{1}$ if and only if $Q_{1}$ is equivalent to $Q_{2}$.
This reduction establishes that
${{\textsc{Rewr}}^{3}({\mathsf{CQ}}^{0},{\mathsf{ACQ}},{\mathsf{CQ}})}$ is NP-
hard. For the NP-hardness of
${{\textsc{Rewr}}^{3}({\mathsf{ACQ}}^{0},{\mathsf{CQ}},{\mathsf{CQ}})}$, the
roles of $Q_{1}$ and $Q_{2}$ are simply swapped in the last reduction.

By composing the three reductions, the second statement of the proposition is
established.

##  4 A Characterisation

In this section we give a characterisation of rewritability of a query $Q$
with respect to a set ${\mathcal{V}}$ of views. It is in terms of a partition
of the atoms of ${{\textnormal{body}}(Q)}$, where each set of the partition
can be matched with a view in a specific way. We refer to such partitions as
_cover partitions_ and the matches as _cover descriptions_. The
characterisation is very similar to other such characterisations in the
literature [17, 2], in particular to ?MiniCon Descriptions? [29]. However, in
its specific form and notation it is tailored for our needs in the subsequent
sections. We will discuss the relationship of our characterisation with others
further below.

Next we define the notions of _cover descriptions_ and _cover partitions_. Let
$Q$ be a conjunctive query. For a set
${\mathcal{A}}\subseteq{{\textnormal{body}}(Q)}$ we define
${{\textnormal{bvars}}_{Q}({\mathcal{A}})}$ as the set of _bridge variables_
of ${\mathcal{A}}$, that occur in ${\mathcal{A}}$ as well as in the head of
$Q$ or in some atom of $Q$ not in ${\mathcal{A}}$. More formally,
${{\textnormal{bvars}}_{Q}({\mathcal{A}})}={{\textnormal{vars}}({\mathcal{A}})}\cap({{\textnormal{vars}}({{\textnormal{head}}(Q)})}\cup{{\textnormal{vars}}({{\textnormal{body}}(Q)}\setminus{\mathcal{A}})})$.

######  Definition 4.1 (Cover Description).

A _cover description_ $C$ for a query $Q$ is a tuple
$({\mathcal{A}},V,{\alpha},\psi)$ where

  * •

${\mathcal{A}}$ is a subset of ${{\textnormal{body}}(Q)}$,

  * •

$V$ is a view,

  * •

${\alpha}$ is an application of $V$, and

  * •

$\psi$ is a mapping from ${{\textnormal{vars}}({\alpha}(V))}$ to
${{\textnormal{vars}}(Q)}$,

such that

${\mathcal{A}}\subseteq\alpha({{\textnormal{body}}(V)})$,

${{\textnormal{bvars}}_{Q}({\mathcal{A}})}\subseteq\alpha({{\textnormal{vars}}({{\textnormal{head}}(V)})})$,

$\psi$ is a body homomorphism from ${\alpha}(V)$ to $Q$, and

$\psi$ is the identity on ${{\textnormal{vars}}({\mathcal{A}})}$.

######  Example 4.2.

Consider the query $Q$ given by the rule

$H(x,y,z)\leftarrow R(x,y,z),T(x,v),F(v),E(w),S(w,z)$

and the following views.

$\displaystyle V_{1}(x_{1},y_{1},w_{1})\leftarrow\leavevmode\nobreak\ $
$\displaystyle
R(x_{1},y_{1},u_{1}),T(x_{1},v_{1}),F(v_{1}),E(w_{1}),S(w_{1},u_{1})$
$\displaystyle V_{2}(x_{2},y_{2},z_{2})\leftarrow\leavevmode\nobreak\ $
$\displaystyle R(x_{2},y_{2},z_{2}),F(v_{2})$ $\displaystyle
V_{3}(w_{3},z_{3})\leftarrow\leavevmode\nobreak\ $ $\displaystyle
S(w_{3},z_{3}),E(w_{3})$

The tuple $C_{1}=({\mathcal{A}}_{1},V_{1},{\alpha}_{1},\psi_{1})$ with
${\mathcal{A}}_{1}=\\{T(x,v),F(v)\\}$,

$\displaystyle{\alpha}_{1}=$ $\displaystyle\leavevmode\nobreak\
\\{x_{1}\mapsto x,y_{1}\mapsto y^{\prime},u_{1}\mapsto u^{\prime},v_{1}\mapsto
v,w_{1}\mapsto w^{\prime}\\}\textnormal{, and}$ $\displaystyle\psi_{1}=$
$\displaystyle\leavevmode\nobreak\ \\{x\mapsto x,y^{\prime}\mapsto
y,u^{\prime}\mapsto z,v\mapsto v,w^{\prime}\mapsto w\\}$

is a cover description for $Q$ with
${{\textnormal{bvars}}_{Q}({\mathcal{A}}_{1})}=\\{x\\}$. Although $\psi_{1}$
could be chosen as id (by adapting ${\alpha}_{1}$ accordingly), we will see in
Example 4.4, that this is not always desirable.

Now we can simply characterise rewritability of a query $Q$ by the existence
of a partition of ${{\textnormal{body}}(Q)}$ whose subsets have cover
descriptions with views from ${\mathcal{V}}$.

######  Definition 4.3.

Let $Q$ be a query and ${\mathcal{V}}$ be a set of views. A collection
${\mathcal{C}}=C_{1},\ldots,C_{m}$ of cover descriptions
$C_{i}=({\mathcal{A}}_{i},V_{i},{\alpha}_{i},\psi_{i})$ for $Q$ with
$V_{i}\in{\mathcal{V}}$ is a _cover partition_ for $Q$ over ${\mathcal{V}}$ if
the sets ${\mathcal{A}}_{1},\ldots,{\mathcal{A}}_{m}$ constitute a partition
of ${{\textnormal{body}}(Q)}$.

We call a cover partition _consistent_ if variables of any $\alpha_{j}(V_{j})$
are in the range of any other $\alpha_{i}$, only if they also appear in
${{\textnormal{bvars}}_{Q}({\mathcal{A}}_{j})}$. We note that, since each
$\alpha_{i}$ is a view application, in a consistent cover partition, the
applications obey quantified variable disjointness.666 For the sake of
contradiction, assume two quantified variables $x$ and $y$ are mapped to the
same variable $z$ by two different view applications ${\alpha}_{i}$ and
${\alpha}_{j}$, respectively. Then, due to consistency, $z$ is in
${{\textnormal{bvars}}({\mathcal{A}}_{i})}$ and, thus, in
${\alpha}_{i}({{\textnormal{head}}(V_{i})})$ due to Definition 4.1(4.1). It
follows that ${\alpha}_{i}$ unifies $x$ with a head variable. But this is a
contradiction to ${\alpha}_{i}$ being a view application.

######  Example 4.4 (Continuation of Example 4.2).

Let $C_{1}=({\mathcal{A}}_{1},V_{1},{\alpha}_{1},\psi_{1})$ be the cover
description defined in Example 4.2. In addition, we consider the cover
descriptions $C_{2}$ and $C_{3}$ with
$C_{i}=({\mathcal{A}}_{i},V_{i},{\alpha}_{i},\psi_{i})$ for $i\in\\{2,3\\}$
where

$\displaystyle{\mathcal{A}}_{2}=$ $\displaystyle\leavevmode\nobreak\
\\{R(x,y,z)\\},$ $\displaystyle{\mathcal{A}}_{3}=\\{E(w),S(w,z)\\},$
$\displaystyle{\alpha}_{2}=$ $\displaystyle\leavevmode\nobreak\
\\{x_{2}\mapsto x,y_{2}\mapsto y,z_{2}\mapsto z,v_{2}\mapsto v\\},$
$\displaystyle{\alpha}_{3}=\\{w_{3}\mapsto w,z_{3}\mapsto z\\},$

and $\psi_{2}=\psi_{3}={\textnormal{id}}$. The cover descriptions
$C_{1},C_{2},C_{3}$ constitute a cover partition for $Q$ over
$\\{V_{1},V_{2},V_{3}\\}$. It is, however, not consistent, since $v$ is in the
range of ${\alpha}_{1}$ and ${\alpha}_{2}$, but not in
${{\textnormal{bvars}}({\mathcal{A}}_{1})}$. Replacing ${\alpha}_{2}$ and
$\psi_{2}$ by mappings $\hat{{\alpha}}_{2}$ and $\hat{\psi}_{2}$ with
$\hat{{\alpha}}_{2}(v_{2})=\hat{v}$ and $\hat{\psi}_{2}(\hat{v})=v$ that agree
with ${\alpha}_{2}$ and $\psi_{2}$ on all other variables, respectively,
yields a consistent cover partition. Note that there is no consistent cover
partition of the form
$({\mathcal{A}}_{1},V_{1},{\alpha}^{\prime}_{1},{\textnormal{id}})$ because
necessarily $\alpha^{\prime}_{1}(w_{1})=w$ would hold and thus $w$ would be in
the range of ${\alpha}^{\prime}_{1}$ and ${\alpha}_{3}$.

A consistent cover partition ${\mathcal{C}}$ induces a query
$Q_{{\mathcal{C}}}$ and an expansion $Q^{\prime}_{{\mathcal{C}}}$ as follows.
We note first that each variable in ${{\textnormal{head}}(Q)}$ occurs in at
least one of the sets ${\mathcal{A}}_{i}$ and thus in some set
${{\textnormal{bvars}}_{Q}({\mathcal{A}}_{i})}$. Therefore, Condition (4.1)
guarantees that each head variable of $Q$ occurs in some set
${\alpha}_{i}({{\textnormal{head}}(V_{i})})$ and thus a cover partition
${\mathcal{C}}=C_{1},\ldots,C_{m}$ with
$C_{i}=({\mathcal{A}}_{i},V_{i},{\alpha}_{i},\psi_{i})$ induces a query
$Q_{{\mathcal{C}}}$ with

$\displaystyle{{\textnormal{head}}(Q_{{\mathcal{C}}})}={{\textnormal{head}}(Q)}\textnormal{
and
}{{\textnormal{body}}(Q_{{\mathcal{C}}})}=\\{{\alpha}_{i}({{\textnormal{head}}(V_{i})})\mid
1\leq i\leq m\\}.$

Likewise, and thanks to quantified variable disjointness, it induces an
expansion $Q^{\prime}_{{\mathcal{C}}}$ with

$\displaystyle{{\textnormal{head}}(Q^{\prime}_{{\mathcal{C}}})}={{\textnormal{head}}(Q)}\textnormal{
and
}{{\textnormal{body}}(Q^{\prime}_{{\mathcal{C}}})}=\\{{\alpha}_{i}({{\textnormal{body}}(V_{i})})\mid
1\leq i\leq m\\}.$

Next, we show that the existence of a cover partition indeed characterises
rewritability.

######  Theorem 4.5.

Let $Q$ be a minimal query and ${\mathcal{V}}$ be a set of views. The
following three statements are equivalent.

$Q$ is ${\mathcal{V}}$-rewritable.

There is a cover partition ${\mathcal{C}}$ for $Q$ over ${\mathcal{V}}$.

There is a consistent cover partition ${\mathcal{C}}$ for $Q$ over
${\mathcal{V}}$. If ${\mathcal{C}}$ is a consistent cover partition, then
$Q_{C}$ is a ${\mathcal{V}}$-rewriting of $Q$.

######  Proof 4.6.

We first show that (c) implies (a). To this end, let
${\mathcal{C}}=C_{1},\ldots,C_{m}$ be a consistent cover partition for $Q$
over ${\mathcal{V}}$, where, for each $i$,
$C_{i}=({\mathcal{A}}_{i},V_{i},{\alpha}_{i},\psi_{i})$.

We prove that the query $Q_{{\mathcal{C}}}$ induced by ${\mathcal{C}}$ is a
${\mathcal{V}}$-rewriting of $Q$: first, since the ${\mathcal{A}}_{i}$
partition ${{\textnormal{body}}(Q)}$ and thanks to Condition (4.1), id is a
homomorphism from $Q$ into $Q^{\prime}_{C}$.

Therefore, it suffices to show that the mapping $h^{\prime}$ from
$Q^{\prime}_{{\mathcal{C}}}$ into $Q$, defined as the union of the mappings
$\psi_{i}$ is a homomorphism.

We first show that $h^{\prime}$ is well-defined: let us assume that a variable
$z$ occurs in $\alpha_{i}(V_{i})$ and $\alpha_{j}(V_{j})$ with $i\not=j$.
Thanks to consistency, $z$ is in ${{\textnormal{bvars}}({\mathcal{A}}_{i})}$
and ${{\textnormal{bvars}}({\mathcal{A}}_{j})}$ and therefore
$\psi_{i}(z)=\psi_{j}(z)$ thanks to Condition (4.1).

That $h^{\prime}$ is a homomorphism follows easily, since each $\psi_{i}$ is a
(body) homomorphism (Condition (4.1)) and $h^{\prime}$ is the identity on
${{\textnormal{head}}(Q)}$ (Condition (4.1)).

Next we show that (a) implies (b). Let us assume that $Q$ has a
${\mathcal{V}}$-rewriting $Q_{R}$ with an expansion $Q_{E}$ and let the
equivalence of $Q$ and $Q_{E}$ be witnessed by homomorphisms $h$ from $Q$ to
$Q_{E}$ and $h^{\prime}$ from $Q_{E}$ to $Q$.

Since $Q$ is minimal, we can assume, thanks to Lemma 4.7 below, that $h$ is
injective and $h^{\prime}$ is the inverse of $h$ on the atoms of
$h({{\textnormal{body}}(Q)})$. Since $h$ is injective, we can further assume,
without loss of generality, that $h$ is the identity mapping on the variables
in $Q$ and that $h^{\prime}(x)=x$ for every such variable.777This can be
easily achieved by renaming the variables of $Q_{R}$ and $Q_{E}$
appropriately.

That is, we have
${{\textnormal{head}}(Q)}={{\textnormal{head}}(Q_{E})}={{\textnormal{head}}(Q_{R})}$
as well as ${{\textnormal{body}}(Q)}\subseteq{{\textnormal{body}}(Q_{E})}$.

Let ${\alpha}_{1},\dots,{\alpha}_{m}$ be applications of views
$V_{1},\dots,V_{m}$ that result in expansion $Q_{E}$, that is,

${{\textnormal{body}}(Q_{E})}=\bigcup_{i=1}^{m}{{\textnormal{body}}({\alpha}_{i}(V_{i}))},$

where the applications fulfil the quantified variable disjointness property.
These applications induce a partition
${\mathcal{A}}_{1},\dots,{\mathcal{A}}_{m}$ of ${{\textnormal{body}}(Q_{E})}$
in the following way: For every $i\in\\{1,\ldots,m\\}$ we define

$\displaystyle{\mathcal{A}}_{i}=\\{A\in{{\textnormal{body}}(Q)}\mid$
$\displaystyle\leavevmode\nobreak\ \textnormal{$i$ is minimal such that
}A\in{\alpha}_{i}({{\textnormal{body}}(V_{i})})\\}.$

Now, let $C_{i}=({\mathcal{A}}_{i},V_{i},{\alpha}_{i},h^{\prime}_{i})$, where
$h^{\prime}_{i}$ is the restriction of $h^{\prime}$ to the variables in
${\alpha}_{i}(V_{i})$, for every $i\in\\{1,\dots,m\\}$. To show that the
$C_{i}$ yield a cover partition, it only remains to show that each $C_{i}$ is
a cover description.

To this end, we show that all four conditions in Definition 4.1 are satisfied
for $C_{i}$, for every $i\in\\{1,\dots,m\\}$. Condition (4.1) holds by the
definition of ${\mathcal{A}}_{i}$. Condition (4.1) is true because each
$h^{\prime}_{i}$ is a restriction of the body homomorphism $h^{\prime}$.
Condition (4.1) follows since $h^{\prime}$ is the identity on all variables in
${{\textnormal{body}}(Q)}$ and thus also on _all_ variables of
${\mathcal{A}}_{i}\subseteq{{\textnormal{body}}(Q)}$.

Hence, it only remains to show that Condition (4.1) is satisfied. To this end,
let $x$ be an arbitrary bridge variable in some ${\mathcal{A}}_{i}$. If $x$
occurs in a subset ${\mathcal{A}}_{j}$ where $j\neq i$, then it is a head
variable in both ${\alpha}_{i}(V_{i})$ and ${\alpha}_{j}(V_{j})$ because of
the quantified variable disjointness of ${\alpha}_{1},\dots,{\alpha}_{m}$.
Otherwise (when ${\mathcal{A}}_{i}$ is the only subset containing $x$),
variable $x$ has to be a head variable of $Q$ in order to be a bridge variable
in ${\mathcal{A}}_{i}$. Because of
${{\textnormal{head}}(Q)}={{\textnormal{head}}(Q_{R})}$, it is then also a
head variable of $Q_{R}$. This, in turn, implies that it is a head variable of
${\alpha}_{i}(V_{i})$ because the quantified variables of
${\alpha}_{i}(V_{i})$ do _not_ occur in $Q_{R}$.

Finally, we show that (b) implies (c). Let thus
${\mathcal{C}}=C_{1},\ldots,C_{m}$ be a cover partition for $Q$ over
${\mathcal{V}}$, where, for each $i$,
$C_{i}=({\mathcal{A}}_{i},V_{i},{\alpha}_{i},\psi_{i})$. Let $z$ be a variable
that occurs in some ${\alpha}_{i}(V_{i})$, but not in
${{\textnormal{bvars}}({\mathcal{A}}_{i})}$, and also in some
${\alpha}_{j}(V_{j})$ with $j\not=i$. Since
$z\not\in{{\textnormal{bvars}}({\mathcal{A}}_{i})}$ we have
$z\not\in{{\textnormal{vars}}({\mathcal{A}}_{j})}$. We define
${\alpha}^{\prime}_{j}$ like ${\alpha}_{j}$ but, for some fresh variable
$z^{\prime}$, we set ${\alpha}^{\prime}_{j}(x)=z^{\prime}$ whenever
${\alpha}_{j}(x)=z$. Accordingly, we define $\psi^{\prime}_{j}$ like
$\psi_{j}$ but with $\psi^{\prime}_{j}(z^{\prime})=\psi_{j}(z)$. It is easy to
verify that
$C^{\prime}_{j}=({\mathcal{A}}_{j},V_{j},{\alpha}^{\prime}_{j},\psi^{\prime}_{j})$
is a cover description, as well. By repeating this process, a consistent cover
partition for $Q$ over ${\mathcal{V}}$ can be obtained.

The previous proof used the following lemma. It is similarly stated in the
proof of Lemma 10 in [15]. We give its short proof to keep the paper self-
contained.

######  Lemma 4.7.

Let $Q_{1}$ be a minimal conjunctive query, $Q_{2}$ a conjunctive query
equivalent to $Q_{1}$ and ${h_{1}\colon{Q_{1}}\rightarrow{Q_{2}}}$ a
homomorphism. Then there is a homomorphism
${h_{2}\colon{Q_{2}}\rightarrow{Q_{1}}}$ that is the inverse of $h_{1}$ on
$h_{1}({{\textnormal{body}}(Q_{1})})$.

######  Proof 4.8.

Since $Q_{1}$ and $Q_{2}$ are equivalent, there is a homomorphism
$h_{2}^{\prime}\colon Q_{2}\rightarrow Q_{1}$.

The mapping $h_{2}^{\prime}\circ h_{1}$ is an automorphism888We note that
compositions of homomorphisms are applied from right to left. on $Q_{1}$,
because $Q_{1}$ is minimal. Then there is some $k>0$ such that
$(h_{2}^{\prime}\circ h_{1})^{k}$ is the identity on $Q_{1}$. We choose
$h_{2}=(h_{2}^{\prime}\circ h_{1})^{k-1}\circ h^{\prime}_{2}$. Clearly,
$h_{2}$ is a homomorphism from $Q_{2}$ to $Q_{1}$ and $h_{2}$ is the inverse
of $h_{1}$ on $h_{1}(Q)$.

######  Remark 4.9.

We note that the requirement in Theorem 4.5 for $Q$ to be minimal is only
seemingly a restriction in our setting, since we apply it only to acyclic
queries. If $Q$ is acyclic but not minimal, an equivalent minimal query
$Q^{\prime}$ can be computed in polynomial time by iteratively removing atoms
from its body [9, 10]. Moreover, it is guaranteed that the minimal query
$Q^{\prime}$ is also acyclic (we believe this to be folklore, it follows
readily from more general results, cf. for instance [5]).

The same is true for free-connex acyclic queries: every homomorphism from $Q$
to $Q^{\prime}$ is also a homomorphism from
${{\textnormal{body}}(Q)}\cup\\{{{\textnormal{head}}(Q)}\\}$ to
${{\textnormal{body}}(Q^{\prime})}\cup\\{{{\textnormal{head}}(Q^{\prime})}\\}$
and vice versa, since the relation symbol of
${{\textnormal{head}}(Q)}={{\textnormal{head}}(Q^{\prime})}$ does not occur in
${{\textnormal{body}}(Q^{\prime})}$. Thus, $Q^{\prime}$ is minimal if and only
if the Boolean query whose body is
${{\textnormal{body}}(Q^{\prime})}\cup\\{{{\textnormal{head}}(Q^{\prime})}\\}$
is minimal. Therefore, if
${{\textnormal{body}}(Q)}\cup\\{{{\textnormal{head}}(Q)}\\}$ is acyclic, so is
${{\textnormal{body}}(Q^{\prime})}\cup\\{{{\textnormal{head}}(Q^{\prime})}\\}$.
In other words, if $Q$ is free-connex acyclic, then $Q^{\prime}$ is free-
connex acyclic as well.

For hierarchical and q-hierarchical queries the same holds: it is easy to see
that removing atoms does not change the conditions in their respective
definitions.

##  5 Towards Acyclic Rewritings

In this section, we turn our focus to the main topic of this paper: acyclic
rewritings and the decision problem that asks whether such a rewriting exists.
We study the complexity of
${{\textsc{Rewr}}({\mathbb{V}},{\mathbb{Q}},{\mathsf{ACQ}})}$ for the case
that ${\mathbb{V}}$ and ${\mathbb{Q}}$ are the class of conjunctive queries
and for various subclasses. It will be helpful to analyse the case that
${\mathbb{Q}}={\mathsf{ACQ}}$ and ${\mathbb{V}}={\mathsf{CQ}}$ first.

###  5.1 A Characterisation of Acyclic Rewritability for Acyclic Queries

The following example illustrates that, even if an acyclic rewriting exists,
the canonical rewriting need not be acyclic. Furthermore, it may be that each
?sub-rewriting? of the canonical candidate is cyclic or not a rewriting, and
thus none of them is an acyclic rewriting.

######  Example 5.1.

Consider the query $Q$ given by the rule

$H()\leftarrow R_{1}(x),R_{2}(y),S(x,z),T_{1}(z),T_{2}(y)$

and the following views ${\mathcal{V}}=\\{V_{1},V_{2},V_{3}\\}$.

$\displaystyle V_{1}(u,v)\leftarrow R_{1}(u),R_{2}(v)\quad\quad
V_{2}(u,v)\leftarrow S(u,v)\quad\quad V_{3}(u,v)\leftarrow T_{1}(u),T_{2}(v)$

The canonical candidate $Q_{R}=H()\leftarrow V_{1}(x,y),V_{2}(x,z),V_{3}(z,y)$
is a ${\mathcal{V}}$-rewriting, but it is _cyclic_. Each query whose body is a
proper subset of the body of $Q_{R}$ is not a ${\mathcal{V}}$-rewriting for
${Q}$. However, an _acyclic_ ${\mathcal{V}}$-rewriting for ${Q}$ exists. One
such rewriting is the query ${Q}^{\prime}_{R}$.

$H()\leftarrow V_{1}(x,y),V_{2}(x,z),V_{3}(z,y^{\prime}),V_{3}(z^{\prime},y)$

Even though the example suggests that general and acyclic rewritings can be
seemingly unrelated, it turns out that there is a close connection between
them. In fact, we will show next that an acyclic ${\mathcal{V}}$-rewriting
exists if and only if an arbitrary ${\mathcal{V}}$-rewriting exists.
Furthermore, from an arbitrary rewriting $Q_{R}$, an acyclic one $Q_{C}$ can
be constructed.

Towards a proof, we study the relationship between the target query ${Q}$ and
the view applications that can occur in any rewriting of ${Q}$ more closely,
to determine the circumstances under which a decomposition of view atoms is
possible.

######  Example 5.2 (Continuation of Example 5.1).

We first have a closer look at the $V_{3}$-atoms in the rewritings of the
previous example. In the SPJ-algebra999SPJ-algebra refers to the select-
project-join-algebra., the $V_{3}$-atom in $Q_{R}$ can be expressed as the
SPJ-expression $\pi_{z,y}(V_{3}(z,y))$, whereas the two $V_{3}$-atoms in
$Q^{\prime}_{R}$ can be expressed as
$\pi_{z,y}(V_{3}(z,y^{\prime})\mathrel{{\bowtie}}V_{3}(z^{\prime},y))$. When
expanded by the SPJ-expressions that define $V_{3}$, these two expressions are
equivalent. That is, the acyclic rewriting can be obtained from the canonical
rewriting by replacing an atom by a set of atoms that is equivalent with
respect to view expansions.101010We note that one could also replace the
$V_{1}$-atom in $Q_{R}$.

In Example 5.1 the acyclic rewriting was obtained from the canonical rewriting
by replacing a view atom by a set that contained one view atom for each
connected component of $V_{3}$. The following example shows that the required
modifications can be more involved.

######  Example 5.3.

Consider the query $Q$ given by the rule

$H(x,y,z)\leftarrow R(x,y,z),E_{1}(x),E_{2}(y),E_{3}(w),S(w,z)$

and the following views.

$\displaystyle V_{1}(x,y,w)\leftarrow\leavevmode\nobreak\ $ $\displaystyle
R(x,y,v),E_{1}(x),E_{3}(w),S(w,v)$ $\displaystyle
V_{2}(x,y,z)\leftarrow\leavevmode\nobreak\ $ $\displaystyle R(x,y,z),E_{2}(y)$
$\displaystyle V_{3}(w,z)\leftarrow\leavevmode\nobreak\ $ $\displaystyle
S(w,z),E_{3}(w)$

The canonical candidate $H(x,y,z)\leftarrow
V_{1}(x,y,w),V_{2}(x,y,z),V_{3}(w,z)$ is a cyclic
$\\{V_{1},V_{2},V_{3}\\}$-rewriting of $Q$. In contrast to Example 5.1, all
view bodies are connected. Therefore, replacing a view atom by a set of
representatives of connected components of some views does not yield an
acyclic rewriting. However, there is an acyclic
$\\{V_{1},V_{2},V_{3}\\}$-rewriting of $Q$, namely $H(x,y,z)\leftarrow
V_{1}(x,y^{\prime},w^{\prime}),V_{2}(x,y,z),V_{3}(w,z).$

Now we turn to the main result of this section.

######  Theorem 5.4.

Let $Q$ be a (free-connex) acyclic conjunctive query and ${\mathcal{V}}$ a set
of ${\mathsf{CQ}}$-views. If $Q$ is ${\mathcal{V}}$-rewritable, then there is
an (free-connex) acyclic ${\mathcal{V}}$-rewriting of $Q$.

######  Proof 5.5.

Since $Q$ is acyclic, we can assume that it is minimal (cf. Remark 4.9).
Moreover, it has a join tree $J_{Q}$. Furthermore, thanks to Theorem 4.5,
since $Q$ is ${\mathcal{V}}$-rewritable, there is a consistent cover partition
${\mathcal{C}}=C_{1},\ldots,C_{m}$ for $Q$ over ${\mathcal{V}}$ and the query
$Q_{\mathcal{C}}$ is a ${\mathcal{V}}$-rewriting of $Q$. For each $i$, let
$C_{i}=({\mathcal{A}}_{i},V_{i},{\alpha}_{i},\psi_{i})$.

We show first that $Q_{C}$ is acyclic, if each set ${\mathcal{A}}_{i}$ is
connected in $J_{Q}$. Afterwards we show that a consistent cover partition
with that property can always be constructed from ${\mathcal{C}}$.

To this end, we show how to construct a join tree $J$ for ${Q}_{\mathcal{C}}$:
we first cluster, for each $j$, the nodes for ${\mathcal{A}}_{j}$ in $J_{Q}$
together into one node that is labelled by
$\alpha_{j}({{\textnormal{head}}(V_{j})})$. Since the ${\mathcal{A}}_{j}$ are
connected in $J_{Q}$, the resulting graph $J$ is a tree.

To verify that $J$ is a join tree, let us consider two nodes $u,v$ of $J$
labelled by $\alpha_{j}({{\textnormal{head}}(V_{j})})$ and
$\alpha_{k}({{\textnormal{head}}(V_{k})})$, respectively, and $x$ be a
variable that appears in $\alpha_{j}({{\textnormal{head}}(V_{j})})$ _and_
$\alpha_{k}({{\textnormal{head}}(V_{k})})$. Thanks to consistency of
${\mathcal{C}}$, $x$ appears in
${{\textnormal{bvars}}_{Q}({\mathcal{A}}_{j})}$ and in
${{\textnormal{bvars}}_{Q}({\mathcal{A}}_{k})}$. It follows that $x$ appears
in two atoms $A_{j}\in{\mathcal{A}}_{j}$ and $A_{k}\in{\mathcal{A}}_{k}$.
Moreover, since $J_{Q}$ is a join tree, $x$ appears in every node on the
(shortest) path from $A_{j}$ to $A_{k}$ in $J_{Q}$. Again thanks to
consistency, $x$ is in ${{\textnormal{bvars}}_{Q}({\mathcal{A}}_{\ell})}$ for
every $\alpha_{\ell}({{\textnormal{head}}(V_{\ell})})$ along the corresponding
contracted path in $J$ from $u$ to $v$. In particular, $x$ appears in all sets
$\alpha_{\ell}({{\textnormal{head}}(V_{\ell})})$ on the path from $u$ to $v$.
Thus, $u$ and $v$ are $x$-connected. We conclude that $J$ is a join tree for
${Q}_{\mathcal{C}}$. Hence, ${Q}_{\mathcal{C}}$ is acyclic.

If $Q$ is also free-connex acyclic, there is a join tree $J_{Q}^{+}$ for
${{\textnormal{body}}(Q)}\cup\\{{{\textnormal{head}}(Q)}\\}$. As we show
later, we can assume that the sets ${\mathcal{A}}_{i}$ of the cover partition
${\mathcal{C}}$ are also connected in $J_{Q}^{+}$. Clustering the
nodes111111The node labelled ${{\textnormal{head}}({Q})}$ is not clustered
with any other node, since it does not occur in any ${\mathcal{A}}_{i}$. of
$J_{Q}^{+}$ analogously as for $J_{Q}$ yields a join tree for
${{\textnormal{body}}(Q_{\mathcal{C}})}\cup\\{{{\textnormal{head}}(Q_{\mathcal{C}})}\\}$
since ${{\textnormal{head}}(Q_{\mathcal{C}})}={{\textnormal{head}}(Q)}$ and
all head variables in a set ${\mathcal{A}}_{i}$ also occur in the new label
$\alpha_{i}({{\textnormal{head}}(V_{i})})$ thanks to Condition (4.1) of
Definition 4.1.

We now show how we can construct from a consistent cover partition
${\mathcal{C}}$ a consistent cover partition
${\mathcal{C}}^{\prime}=C^{\prime}_{1},\ldots,C^{\prime}_{m}$ in which each
set ${\mathcal{A}}^{\prime}_{i}$ is connected. To this end, let us assume that
some set ${\mathcal{A}}_{j}$ is not connected in $J_{Q}$. Let
${\mathcal{B}}_{j}\subseteq{\mathcal{A}}_{j}$ be a maximal connected subset
and let
${\mathcal{A}}_{j}^{\prime}={\mathcal{A}}_{j}\setminus{\mathcal{B}}_{j}$. We
observe that each variable $x$ that appears in ${\mathcal{B}}_{j}$ and
${\mathcal{A}}_{j}^{\prime}$, is also in
${{\textnormal{bvars}}_{Q}({\mathcal{A}}_{j})}$, since $x$ has to occur in at
least one other atom in $J_{Q}$ (otherwise, ${\mathcal{B}}_{j}$ and
${\mathcal{A}}_{j}^{\prime}$ would be connected in $J_{Q}$). Thus,
${{\textnormal{bvars}}_{Q}({\mathcal{B}}_{j})}\subseteq{{\textnormal{bvars}}_{Q}({\mathcal{A}}_{j})}$.
We conclude that
$C_{{\mathcal{B}}_{j}}=({\mathcal{B}}_{j},V_{j},{\alpha}_{j},\psi_{j})$ is a
cover description. Likewise,
$C_{j}^{\prime}=({\mathcal{A}}_{j}^{\prime},V_{j},{\alpha}_{j},\psi_{j})$ is a
cover description. By repeated application of this modification step
eventually a cover partition
${\mathcal{C}}^{\prime}=C^{\prime}_{1},\ldots,C^{\prime}_{m}$ is obtained, in
which each set ${\mathcal{A}}^{\prime}_{i}$ is connected. If ${Q}$ is free-
connex ${\mathcal{C}}^{\prime}$ can be further refined as described above but
w.r.t. $J_{Q}^{+}$ instead of $J_{Q}$. Refining the cover partition
iteratively w.r.t. $J_{Q}$ and $J_{Q}^{+}$ yields a cover partition
${\mathcal{C}}^{\prime\prime}=C^{\prime\prime}_{1},\ldots,C^{\prime\prime}_{p}$
in which each set ${\mathcal{A}}^{\prime\prime}_{i}$ is connected in $J_{Q}$
and $J_{Q}^{+}$. The number of iterations is bounded by the number of atoms of
$Q$.

Thanks to Theorem 4.5 it can be turned into a consistent cover partition (and
the required renamings of variables do not affect the connectedness
condition).

Theorem 5.4 delivers good news as well as bad news. The good news is that,
since the proofs of Theorem 5.4 and Theorem 4.5 are constructive, we
altogether have a procedure to construct an acyclic rewriting from an
arbitrary rewriting $Q_{R}$ if the query $Q$ is acyclic. Furthermore, if a
homomorphism from an expansion of $Q_{R}$ to $Q$ can be computed in polynomial
time, the overall procedure can be performed in polynomial time. In
particular, we get the following collary.

######  Corollary 5.6.

For every $k$,
${{\textsc{Rewr}}({\mathsf{ACQ}}^{k},{\mathsf{ACQ}},{\mathsf{ACQ}})}$ is in
polynomial time and an acyclic rewriting can be computed in polynomial time
(if it exists).

That the decision problem is in polynomial time follows immediately from
Proposition 3.7 and Theorem 5.4. Moreover, the canonical candidate for an
acyclic query $Q$ and a set ${\mathcal{V}}$ of acyclic views with bounded
arity can be computed in polynomial time, since the size of
${\mathcal{V}}({{\mathsf{canon}}(Q)})$ is bounded by a polynomial and query
evaluation for acyclic queries is in polynomial time [31, 1]. In case the
canonical candidate is a rewriting, valuations witnessing
${\mathcal{V}}({{\mathsf{canon}}(Q)})$ can be computed in polynomial time [24]
and combined into a homomorphism from an expansion of the rewriting to $Q$.
Thus, an acyclic rewriting can then be efficiently constructed by the above
procedure.

However, this leaves open the complexity of
${{\textsc{Rewr}}({\mathsf{ACQ}},{\mathsf{ACQ}},{\mathsf{ACQ}})}$ (as well as
that of ${{\textsc{Rewr}}({\mathsf{ACQ}},{\mathsf{ACQ}},{\mathsf{CQ}})}$), and
of their restrictions to schemas of bounded arity. The bad news is that, since
${{\textsc{Rewr}}({\mathbb{V}},{\mathsf{ACQ}},{\mathsf{CQ}})}$ and
${{\textsc{Rewr}}({\mathbb{V}},{\mathsf{ACQ}},{\mathsf{ACQ}})}$ are basically
the same problem, lower bounds on
${{\textsc{Rewr}}({\mathbb{V}},{\mathsf{ACQ}},{\mathsf{CQ}})}$ transfer to
${{\textsc{Rewr}}({\mathbb{V}},{\mathsf{ACQ}},{\mathsf{ACQ}})}$. In fact, we
get the following, due to NP-hardness of
${{\textsc{Rewr}}^{k}({\mathsf{CQ}},{\mathsf{ACQ}},{\mathsf{CQ}})}$ in the
general case (Proposition 3.9).121212We note that Corollary 5.7 also follows
from the proof of Proposition 3.9, since the canonical candidate constructed
in that proof is trivially acyclic. Indeed, NP-hardness of
${{\textsc{Rewr}}({\mathsf{ACQ}},{\mathsf{CQ}},{\mathsf{ACQ}})}$ is also
implied.

######  Corollary 5.7.

For every $k\geq 3$, the problem
${{\textsc{Rewr}}^{k}({\mathsf{CQ}},{\mathsf{ACQ}},{\mathsf{ACQ}})}$ and,
therefore, also
${{\textsc{Rewr}}^{k}({\mathsf{CQ}},{\mathsf{CQ}},{\mathsf{ACQ}})}$ is NP-
hard.

In the next part of this section, we resolve the complexity of
${{\textsc{Rewr}}({\mathsf{ACQ}},{\mathsf{ACQ}},{\mathsf{CQ}})}$ and
${{\textsc{Rewr}}({\mathsf{ACQ}},{\mathsf{ACQ}},{\mathsf{ACQ}})}$ and their
restrictions to schemas of bounded arity.

###  5.2 The Complexity of Acyclic Rewritability for Acyclic Queries

It may be tempting to assume that, since acyclic queries are so well-behaved
in general, it should be tractable to decide whether for an acyclic query and
a set of acyclic views there exists an acyclic rewriting. However, as we show
next, this is (probably) not the case, and this surprising finding even holds
for the even better behaved hierarchical queries as well.

######  Theorem 5.8.

The problems
${{\textsc{Rewr}}^{k}({\mathsf{ACQ}},{\mathsf{ACQ}},{\mathsf{CQ}})}$ and
${{\textsc{Rewr}}^{k}({\mathsf{ACQ}},{\mathsf{ACQ}},{\mathsf{ACQ}})}$, as well
as ${{\textsc{Rewr}}^{k}({\mathsf{HCQ}},{\mathsf{HCQ}},{\mathsf{CQ}})}$ are
NP-complete, for $k\geq 3$.131313 These results hold for schemas of unbounded
arity, as well.  The lower bounds even hold for instances with a single view.

We will see in Section 7 that Theorem 5.4 has an analogue for hierarchical
queries from which it can be concluded that deciding the existence of a
hierarchical rewriting, given a hierarchical query and hierarchical views, is
still NP-complete.

Theorem 5.8 will easily follow from NP-hardness of a seemingly simpler
problem. From the characterisation in Theorem 4.5, we already know that
deciding the existence of a rewriting is the same as deciding the existence of
a cover partition. We show next that it is even NP-hard to decide the
existence of a _cover description_ , given a query, a set of atoms, and a
single view.

######  Definition 5.9.

Let ${\mathbb{V}}\subseteq{\mathsf{CQ}}$ and
${\mathbb{Q}}\subseteq{\mathsf{CQ}}$ be classes of conjunctive queries. The
_cover description problem_ for ${\mathbb{V}}$ and ${\mathbb{Q}}$, denoted
CovDesc(${\mathbb{V}}$, ${\mathbb{Q}}$) asks, upon input of a query
$Q\in{\mathbb{Q}}$, a subset ${\mathcal{A}}\subseteq{{\textnormal{body}}(Q)}$
and a view $V\in{\mathbb{V}}$, whether mappings ${\alpha}$ and $\psi$ exist
such that $({\mathcal{A}},V,{\alpha},\psi)$ is a cover description.

######  Theorem 5.10.

CovDesc(${\mathsf{ACQ}}$, ${\mathsf{ACQ}}$) is NP-hard. Indeed, even
CovDesc(${\mathsf{HCQ}}$, ${\mathsf{HCQ}}$) is NP-hard and even if the input
is restricted to ${\mathcal{A}}={{\textnormal{body}}({Q})}$.

######  Proof 5.11.

We reduce problem 3SAT to CovDesc(${\mathsf{HCQ}}$, ${\mathsf{HCQ}}$). This
lower bound directly translates to CovDesc(${\mathsf{ACQ}}$, ${\mathsf{ACQ}}$)
since every hierarchical query is acyclic. For a formula ${f}$ in 3CNF, we
describe how a query ${Q}$ and a view ${V}$ can be derived in polynomial time
such that both ${Q}$ and ${V}$ are hierarchical and such that ${f}$ is
satisfiable if and only if there are mappings ${\alpha}$ and $\psi$ such that
$({{\textnormal{body}}({Q})},V,{\alpha},\psi)$ is a cover description for
${Q}$.

##### Construction.

Let ${f}={f}_{1}\land\dots\land{f}_{k}$ be a propositional formula in 3CNF
over variables $x_{1},\dots,x_{n}$ in clauses ${f}_{1},\dots,{f}_{k}$, where
${f}_{j}=({\ell_{j,1}}\lor{\ell_{j,2}}\lor{\ell_{j,3}})$ for each
$j\in\\{1,\dots,k\\}$.

We start with the construction of query ${Q}$. This query is Boolean, with
head $H()$, and uses only three variables ${w_{0}}$, ${w_{1}}$ and ${u}$,
where the first two are intended to represent the truth values false and true.
The structure of ${Q}$ is depicted in Figure 1(a). The body of ${Q}$ is
defined as the union

$\\{{{\texttt{Form}}({w_{0}},{w_{1}},{u})}\\}\uplus{{{{\mathcal{C}}_{\text{0}}}}}\uplus{{{{\mathcal{C}}_{\text{1}}}}}\uplus{{{\mathcal{N}}_{\text{$1$}}}}\uplus\dots\uplus{{{\mathcal{N}}_{\text{$n$}}}}$

of the following sets of atoms.

  * •

Set ${{{{\mathcal{C}}_{\text{0}}}}}$ contains an atom
${{{\texttt{C}}_{j}({w_{0}},{w_{1}},{u})}}$ for each clause ${f}_{j}$ in
${f}$.

Intuitively, these atoms represent _unsatisfied_ clauses as opposed to the
next atoms that represent _satisfied_ clauses. Note that these atoms differ in
the order of variables ${w_{0}}$ and ${w_{1}}$ only.

  * •

Set ${{{{\mathcal{C}}_{\text{1}}}}}$ contains an atom
${{{\texttt{C}}_{j}({w_{1}},{w_{0}},{u})}}$ for each clause ${f}_{j}$ in
${f}$.

  * •

There is a set ${{{\mathcal{N}}_{\text{$i$}}}}$ for each variable $x_{i}$ in
formula ${f}$. The sets differ only in the name of the relation they address
and contain two atoms ${{\texttt{Neg}}_{i}({w_{0}},{w_{1}},{u})}$ and
${{\texttt{Neg}}_{i}({w_{1}},{w_{0}},{u})}$ each.

Query ${Q}$ is hierarchical since every atom in each of the sets above refers
to all three variables ${w_{0}}$, ${w_{1}}$ and ${u}$. Thus, query ${Q}$ is
acyclic in particular.

for tree=query [${{\texttt{Form}}({w_{0}},{w_{1}},\makebox[9.36668pt][c]{\vbox
to8.46664pt{\vfil}${{{{\mathcal{C}}_{\text{0}}}}}$},subquery)}$
[${{{{\mathcal{C}}_{\text{1}}}}}$,subquery]
[${{{\mathcal{N}}_{\text{$1$}}}}$,subquery] [ … ,subquery,draw=none,no edge]
[${{{\mathcal{N}}_{\text{$n$}}}}$,subquery] ]

(a) Structure of query $\boldsymbol{{Q}}$, induced by formula
$\boldsymbol{{f}}$.

for tree=query [${{\texttt{Form}}({w_{0}},{w_{1}},\makebox[9.36668pt][c]{\vbox
to8.46664pt{\vfil}${{{{\mathcal{C}}_{\text{0}}}}}$},subquery)}$
[${{{{\mathcal{C}}_{\text{1}}}}}$,subquery,phantom]
[${{{\mathcal{X}}_{\text{$1$}}}}$,subquery
[${{{\mathcal{X}}^{+}_{\text{$1$}}}}$,subquery]
[${{{\mathcal{X}}^{-}_{\text{$1$}}}}$,subquery] ] [ … ,subquery,draw=none,no
edge] [${{{\mathcal{X}}_{\text{$n$}}}}$,subquery
[${{{\mathcal{X}}^{+}_{\text{$n$}}}}$,subquery]
[${{{\mathcal{X}}^{-}_{\text{$n$}}}}$,subquery] ] ]

(b) Structure of view $\boldsymbol{{V}}$, induced by formula
$\boldsymbol{{f}}$.

Figure 1: Structure of the query $\boldsymbol{{Q}}$ and the view
$\boldsymbol{{V}}$, induced by formula $\boldsymbol{{f}}$.

We now proceed with the construction of view ${V}$, which refers to the same
relations as query ${Q}$. Like query ${Q}$, the view uses variables ${w_{0}}$,
${w_{1}}$ and ${u}$ but also additional variables for the propositions
$x_{1},\dots,x_{n}$ in formula ${f}$. For each proposition $x_{i}$, there are
two variables $x_{i}$ and ${\bar{x}}_{i}$, intended to represent the positive
and negated literal over the proposition, respectively. With the exception of
variable ${u}$, all other variables are in the head
$H({w_{0}},{w_{1}},x_{1},{\bar{x}}_{1},\dots,x_{n},{\bar{x}}_{n})$ of view
${V}$. The body of ${V}$, whose structure is depicted in Figure 1(b), is
defined as the union

$\\{{{\texttt{Form}}({w_{0}},{w_{1}},{u})}\\}\uplus{{{{\mathcal{C}}_{\text{0}}}}}\uplus\big{(}{{{\mathcal{X}}_{\text{$1$}}}}\uplus{{{\mathcal{X}}^{+}_{\text{$1$}}}}\uplus{{{\mathcal{X}}^{-}_{\text{$1$}}}}\big{)}\uplus\dots\uplus\big{(}{{{\mathcal{X}}_{\text{$n$}}}}\uplus{{{\mathcal{X}}^{+}_{\text{$n$}}}}\uplus{{{\mathcal{X}}^{-}_{\text{$n$}}}}\big{)}$

of sets of atoms, where the first two sets
$\\{{{\texttt{Form}}({w_{0}},{w_{1}},{u})}\\}$ and
${{{{\mathcal{C}}_{\text{0}}}}}$ are the same as above. The bodies of query
${Q}$ and view ${V}$ thus differ in the sets ${{{{\mathcal{C}}_{\text{1}}}}}$
and ${{{\mathcal{N}}_{\text{$1$}}}},\dots,{{{\mathcal{N}}_{\text{$n$}}}}$ of
atoms on the one hand as well as
${{{\mathcal{X}}_{\text{$1$}}}},\dots,{{{\mathcal{X}}_{\text{$n$}}}}$ and
${{{\mathcal{X}}^{+}_{\text{$1$}}}},\dots,{{{\mathcal{X}}^{+}_{\text{$n$}}}}$
and
${{{\mathcal{X}}^{-}_{\text{$1$}}}},\dots,{{{\mathcal{X}}^{-}_{\text{$n$}}}}$
on the other hand. Sets
${{{\mathcal{N}}_{\text{$1$}}}},\dots,{{{\mathcal{N}}_{\text{$n$}}}}$ and
${{{\mathcal{X}}_{\text{$1$}}}},\dots,{{{\mathcal{X}}_{\text{$n$}}}}$ are
intended to guide the assignment of propositions while sets
${{{\mathcal{X}}^{+}_{\text{$1$}}}},\dots,{{{\mathcal{X}}^{+}_{\text{$n$}}}}$
and
${{{\mathcal{X}}^{-}_{\text{$1$}}}},\dots,{{{\mathcal{X}}^{-}_{\text{$n$}}}}$
represent the occurrences of literals in the clauses of formula ${f}$ and set
${{{{\mathcal{C}}_{\text{1}}}}}$ represents the aim to satisfy all of them.
The new sets are defined as follows.

  * •

For each proposition $x_{i}$, set ${{{\mathcal{X}}_{\text{$i$}}}}$ contains
atoms ${\texttt{Neg}}_{i}(x_{i},{\bar{x}}_{i},{u})$ and
${\texttt{Neg}}_{i}({\bar{x}}_{i},x_{i},{u})$, intended to enforce the mapping
of $(x_{i},{\bar{x}}_{i})$ to either $({w_{0}},{w_{1}})$ or
$({w_{1}},{w_{0}})$, that is, to ?complementary truth values?.

  * •

For each positive literal $x_{i}$ and each clause ${f}_{j}$ that contains
literal $x_{i}$, set ${{{\mathcal{X}}^{+}_{\text{$i$}}}}$ contains an atom
${{\texttt{C}}_{j}(x_{i},{\bar{x}}_{i},{u})}$.

  * •

For each negated literal ${\bar{x}}_{i}$ and each clause ${f}_{j}$ that
contains literal $\neg x_{i}$, set ${{{\mathcal{X}}^{-}_{\text{$i$}}}}$
contains an atom ${{\texttt{C}}_{j}({\bar{x}}_{i},x_{i},{u})}$.

Thus defined, the view is also hierarchical as shown in the following. Every
atom in every set contains variable ${u}$. Therefore, it follows that
${\textnormal{atoms}}(x)\subseteq{\textnormal{atoms}}({u})$ for all
$x\in{\textnormal{vars}}({V})$. Furthermore, all atoms in
$\\{{{\texttt{Form}}({w_{0}},{w_{1}},{u})}\\}$ and
${{{{\mathcal{C}}_{\text{0}}}}}$ additionally contain both variables ${w_{0}}$
and ${w_{1}}$ and they are the only atoms to contain these variables. Thus, we
have that ${\textnormal{atoms}}({w_{0}})={\textnormal{atoms}}({w_{1}})$ and
${\textnormal{atoms}}(y)\cap{\textnormal{atoms}}({w_{0}})=\emptyset$ and
${\textnormal{atoms}}(y)\cap{\textnormal{atoms}}({w_{1}})=\emptyset$ for all
$y\in{\textnormal{vars}}(V)\setminus\\{u,{w_{0}},{w_{1}}\\}$. Similarly, for
each $i\in\\{1,\dots,n\\}$, all atoms in
${{{\mathcal{X}}_{\text{$i$}}}}\cup{{{\mathcal{X}}^{+}_{\text{$i$}}}}\cup{{{\mathcal{X}}^{-}_{\text{$i$}}}}$
contain both variables $x_{i}$ and ${\bar{x}}_{i}$, which do not occur in any
other atom. It follows that
${\textnormal{atoms}}(x_{i})={\textnormal{atoms}}({\bar{x}}_{i})$ and
${\textnormal{atoms}}({\bar{x}}_{i})\cap{\textnormal{atoms}}(y)=\emptyset$ and
${\textnormal{atoms}}(x_{i})\cap{\textnormal{atoms}}(y)=\emptyset$ for all
$y\in{\textnormal{vars}}(V)\setminus\\{x_{i},{\bar{x}}_{i},u\\}$ and
$i\in\\{1,\ldots,n\\}$. Therefore, we obtain that each pair of variables in
${V}$ satisfies at least one of the conditions in Definition 2 and thus ${V}$
is hierarchical—and acyclic in particular.

For the correctness argument, however, the structure of the join tree of view
${V}$, depicted in Figure 1(b) is probably more helpful. We close the
description of the construction by remarking that query and view can be
computed in polynomial time for any given propositional formula in 3CNF.

##### Correctness.

We prove now that formula ${f}$ is satisfiable if and only if there are
mappings ${\alpha}$ and $\psi$ such that
$({{\textnormal{body}}({Q})},V,{\alpha},\psi)$ is a cover description for
${Q}$.

First, we show that if formula ${f}$ is satisfiable, then there are mappings
${\alpha}$ and $\psi$ such that $({{\textnormal{body}}(Q)},V,{\alpha},\psi)$
is a cover description for ${Q}$.

To this end, let us assume that ${f}$ is satisfiable and that this is
witnessed by a satisfying truth assignment ${\beta}$. From this assignment for
propositions $x_{1},\dots,x_{n}$, we derive the application ${\alpha}$ of
${V}$. Let ${\alpha}$ be the mapping that is the identity on variables
${w_{0}}$, ${w_{1}}$ and ${u}$ and behaves as follows on the literal
variables, for every $i\in\\{1,\dots,n\\}$.

${\alpha}(x_{i},{\bar{x}}_{i})=\begin{cases}({w_{0}},{w_{1}})&\text{if
${\beta}(x_{i})=0$}\\\ ({w_{1}},{w_{0}})&\text{if
${\beta}(x_{i})=1$}\end{cases}$

We choose mapping $\psi$ to be the identity on the variables of ${\alpha}(V)$.
Then $({{\textnormal{body}}(Q)},V,{\alpha},\psi)$ is a cover description for
${Q}$ because application ${\alpha}$ establishes the following relationships
between the atoms of view ${V}$ (on the left-hand side) and the atoms of query
${Q}$ (on the right-hand side).

${\alpha}({{{{\mathcal{C}}_{\text{0}}}}})={{{{\mathcal{C}}_{\text{0}}}}}$

${\alpha}({{{\mathcal{X}}_{\text{$1$}}}})={{{\mathcal{N}}_{\text{$1$}}}}$, …,
${\alpha}({{{\mathcal{X}}_{\text{$n$}}}})={{{\mathcal{N}}_{\text{$n$}}}}$

${\alpha}({{{\mathcal{X}}^{+}_{\text{$1$}}}}\cup{{{\mathcal{X}}^{-}_{\text{$1$}}}}\cup\dots\cup{{{\mathcal{X}}^{+}_{\text{$n$}}}}\cup{{{\mathcal{X}}^{-}_{\text{$n$}}}})\subseteq{{{{\mathcal{C}}_{\text{0}}}}}\cup{{{{\mathcal{C}}_{\text{1}}}}}$

${\alpha}({{{\mathcal{X}}^{+}_{\text{$1$}}}}\cup{{{\mathcal{X}}^{-}_{\text{$1$}}}}\cup\dots\cup{{{\mathcal{X}}^{+}_{\text{$n$}}}}\cup{{{\mathcal{X}}^{-}_{\text{$n$}}}})\supseteq{{{{\mathcal{C}}_{\text{1}}}}}$
Property (5.2) is rather obvious since the application ${\alpha}$ behaves like
the identity on the variables ${w_{0}}$, ${w_{1}}$ and ${u}$ in
${{{{\mathcal{C}}_{\text{0}}}}}$. Next, let us consider the set
${{{\mathcal{X}}_{\text{$i$}}}}=\\{{{\texttt{Neg}}_{i}({w_{0}},{w_{1}},{u})},{{\texttt{Neg}}_{i}({w_{1}},{w_{0}},{u})}\\}$
for an arbitrary $i\in\\{1,\dots,n\\}$. By definition, application ${\alpha}$
maps $(x_{i},{\bar{x}}_{i})$ either to $({w_{0}},{w_{1}})$ or
$({w_{1}},{w_{0}})$. In each case, we get

${\alpha}({{{\mathcal{X}}_{\text{$i$}}}})=\\{{\texttt{Neg}}_{i}({w_{0}},{w_{1}},{u}),{\texttt{Neg}}_{i}({w_{1}},{w_{0}},{u})\\}={{{\mathcal{N}}_{\text{$i$}}}}.$

Hence, Property (5.2) holds too. Again by definition of ${\alpha}$, the atoms
in
${{{\mathcal{X}}^{+}_{\text{$1$}}}}\cup\dots\cup{{{\mathcal{X}}^{+}_{\text{$n$}}}}$,
which are of the form ${{\texttt{C}}_{j}(x_{i},{\bar{x}}_{i},{u})}$, are
mapped to ${{{\texttt{C}}_{j}({w_{0}},{w_{1}},{u})}}$ or
${{{\texttt{C}}_{j}({w_{1}},{w_{0}},{u})}}$, contained in
${{{{\mathcal{C}}_{\text{0}}}}}\cup{{{{\mathcal{C}}_{\text{1}}}}}$. An
analogous argument holds for the atoms in
${{{\mathcal{X}}^{-}_{\text{$1$}}}}\cup\dots\cup{{{\mathcal{X}}^{-}_{\text{$n$}}}}$.
Thus, Property (5.2) is also satisfied. Finally, we show that Property (5.2)
holds. To this end, let ${{{\texttt{C}}_{j}({w_{1}},{w_{0}},{u})}}$ be an
arbitrary atom in ${{{{\mathcal{C}}_{\text{1}}}}}$. By our assumption, clause
${f}_{j}$ in formula ${f}$ is satisfied by truth assignment ${\beta}$. Hence,
there is a literal ${\ell_{j,h}}$ in clause ${f}_{j}$ such that
${\beta}\models{\ell_{j,h}}$. Let us assume ${\ell_{j,h}}=x_{i}$ for some
$i\in\\{1,\dots,n\\}$; the argument for a negated literal is analogous. This
assumption implies ${\alpha}(x_{i})={w_{1}}$ by the definition of ${\alpha}$,
which depends on ${\beta}$. Since literal $x_{i}$ is a literal in clause
${f}_{j}$, we have
${{\texttt{C}}_{j}(x_{i},{\bar{x}}_{i},{u})}\in{{{\mathcal{X}}^{+}_{\text{$i$}}}}$
and thus
${\alpha}({{{\mathcal{X}}^{+}_{\text{$i$}}}})\ni{{{\texttt{C}}_{j}({w_{1}},{w_{0}},{u})}}$.

Since properties (5.2) – (5.2) consider all body atoms of query ${Q}$ and view
${V}$, they imply that the bodies are identical:
${{\textnormal{body}}({Q})}={\alpha}({{\textnormal{body}}({V})})$. For
$\psi={\textnormal{id}}$, this trivially implies
${{\textnormal{body}}({Q})}\subseteq{\alpha}({{\textnormal{body}}({V})})$ and
$\psi({\alpha}({{\textnormal{body}}({V})}))\subseteq{{\textnormal{body}}({Q})}$,
namely conditions (4.1) and (4.1) in Definition 4.1. Furthermore, since query
${Q}$ is Boolean, set ${\mathcal{A}}={{\textnormal{body}}({Q})}$ has _no_
bridge variables. Thus, conditions (4.1) and (4.1) are trivially satisfied.

Therefore, $({\mathcal{A}},V,{\alpha},\psi)$ is a cover description for ${Q}$.

Now, we show that formula ${f}$ is satisfiable if there are mappings
${\alpha}$ and $\psi$ such that $({{\textnormal{body}}({Q})},V,{\alpha},\psi)$
is a cover description for ${Q}$.

Consider the set ${\mathcal{B}}={\alpha}({\textnormal{body}}({V}))$ of atoms.
From Definition (4.1), we know that
${{\textnormal{body}}({Q})}\subseteq{\mathcal{B}}$ and
$\psi({\mathcal{B}})\subseteq{{\textnormal{body}}({Q})}$ hold. Since both sets
${{\textnormal{body}}({Q})}$ and ${\mathcal{B}}$ contain only one Form-atom
$B={{\texttt{Form}}({w_{0}},{w_{1}},{u})}$, we can conlude ${\alpha}(B)=B$ by
Condition (4.1) and $\psi({\alpha}(B))=\psi(B)=B$ by Condition (4.1).
Therefore, each mapping ${\alpha}$ and $\psi$ is the identity on variables
${w_{0}}$, ${w_{1}}$ and ${u}$. Hence, application ${\alpha}$ induces
unambiguously a truth assignment ${\beta}$ that maps proposition $x_{i}\mapsto
1$ if ${\alpha}(x_{i})={w_{1}}$; and maps $x_{i}\mapsto 0$ otherwise.

It suffices to show that ${\beta}$ satisfies formula ${f}$. Let ${f}_{j}$ be
an arbitrary clause of the formula. From
${{\textnormal{body}}({Q})}\subseteq{\alpha}({{\textnormal{body}}({V})})$, we
know that atom ${{{\texttt{C}}_{j}({w_{1}},{w_{0}},{u})}}$ from
${{{{\mathcal{C}}_{\text{1}}}}}\subseteq{{\textnormal{body}}({Q})}$ is in
${\alpha}({{\textnormal{body}}({V})})$ in particular. Since it cannot be atom
${{{\texttt{C}}_{j}({w_{0}},{w_{1}},{u})}}={\alpha}({{{\texttt{C}}_{j}({w_{0}},{w_{1}},{u})}})$,
there has to be an atom
${{\texttt{C}}_{j}(x_{i},{\bar{x}}_{i},{u})}\in{{{\mathcal{X}}^{+}_{\text{$i$}}}}$
or
${{\texttt{C}}_{j}({\bar{x}}_{i},x_{i},{u})}\in{{{\mathcal{X}}^{-}_{\text{$i$}}}}$
for some $i\in\\{1,\dots,n\\}$ in ${\textnormal{body}}({V})$. Let us assume
the former—the other case is analogous again—, which implies that literal
$x_{i}$ occurs in clause ${f}_{j}$. Then, from
${\alpha}({{\texttt{C}}_{j}(x_{i},{\bar{x}}_{i},{u})})={{{\texttt{C}}_{j}({w_{1}},{w_{0}},{u})}}$,
we can infer ${\alpha}(x_{i})={w_{1}}$. Hence, truth assignment ${\beta}$
satisfies literal $x_{i}$ in clause ${f}_{j}$ because ${\beta}(x_{i})=1$ if
${\alpha}(x_{i})={w_{1}}$.

Thus, truth assignment ${\beta}$ satisfies every clause of formula ${f}$ and
formula ${f}$ is satisfiable if a rewriting of query ${Q}$ in terms of view
${V}$ exists.

This concludes our proof. The proof of Theorem 5.8 can now be stated easily.

######  Proof 5.12 (Proof of Theorem 5.8).

The upper bound follows from Theorem 3.2. For the lower bound, we observe that
the proof of Theorem 5.10 shows that query ${Q}$ has a ${V}$-rewriting _if_
the formula ${f}$ is satisfiable. Moreover, the query cannot be covered (non-
redundantly) by multiple applications of this view because variable ${u}$ is
no head variable of view ${V}$. Thus, we can conclude that ${Q}$ has a
${V}$-rewriting _only if_ formula ${f}$ is satisfiable. Hence, NP-hardness
transfers to the rewriting problem.

Notably, the complexity does not result from the restriction to rewritings
that are acyclic since the last argument does not depend on the acyclicity.

The fact that, for Theorem 5.8, a single view application is sufficient if
there is any rewriting, allows to draw yet another conclusion for a related
problem, defined next. In the following, a _selection_ is a query that can be
expressed by a composition of select-operators.

######  Definition 5.13.

Given a query class ${\mathbb{Q}}\subseteq{\mathsf{CQ}}$, the _select-full-
project equivalence_ problem for ${\mathbb{Q}}$, denoted
SelProjEquiv(${\mathbb{Q}}$), asks, upon input of a Boolean query
$Q\in{\mathbb{Q}}$ and a query $Q^{\prime}\in{\mathbb{Q}}$ whether there is a
selection $\sigma$ such that $Q$ is equivalent to
$(\pi_{\emptyset}\circ\sigma)(Q^{\prime})$ where $\pi_{\emptyset}$ denotes the
projection to the empty set.

The selection $\sigma$ is reflected141414An application can be decomposed into
a selection which unifies head variables and an injective renaming of
variables. in application ${\alpha}$ of the hardness proof and the projection
in the fact that set ${\mathcal{A}}={{\textnormal{body}}({Q})}$ has no bridge
variables. Hence, the following holds.

######  Corollary 5.14.

SelProjEquiv(${\mathsf{ACQ}}$) and SelProjEquiv(${\mathsf{HCQ}}$) are NP-
hard.151515We note that the restriction of the select-full-project equivalence
problem to Boolean queries $Q^{\prime}$ is just the equivalence problem for
Boolean queries which is in P for acyclic queries [10].

Surprisingly, the select-full-project equivalence problem is NP-hard not only
for hierarchical but even for _q_ -hierarchical queries—while the rewriting
problem for q-hierarchical views is in P (Corollary 7.6).

######  Corollary 5.15.

SelProjEquiv(${\mathsf{QHCQ}}$) is NP-hard, even over database schemas with
fixed arity.

######  Proof 5.16 (Proof idea).

The proof is essentially the same as for Theorem 5.8. We first prove the
result for hierarchical queries and then lift it to q-hierarchical queries.

Let $Q$ and $V$ be the Boolean query and the view constructed in the proof for
Theorem 5.8, respectively. If $({{\textnormal{body}}(Q)},V,{\alpha},\psi)$,
for some mappings ${\alpha}$ and $\psi$, is a cover description for $Q$, then
the Boolean query with body ${\alpha}({{\textnormal{head}}(V)})$ is a
rewriting of $Q$ since the cover description constitutes a consistent cover
partition for $Q$ (a cover partition consisting of a single cover description
is consistent by definition). Thus, $Q$ is equivalent to
$(\pi_{\emptyset}\circ\sigma)(V)$ where $\sigma$ is the selection that unifies
precisely those variables unified by ${\alpha}$. Conversely, if $Q$ is
equivalent to $(\pi_{\emptyset}\circ\sigma)(V)$ for a selection $\sigma$, then
the Boolean query with body ${\alpha}({{\textnormal{head}}(V)})$ with
${\alpha}=\sigma$ is a rewriting of $Q$. Hence, by choosing the second input
query $Q^{\prime}=V$, Corollary 5.14 follows because $Q$ and $Q^{\prime}$ are
hierarchical.

To lift the result to q-hierarchical queries, we have to adapt $Q^{\prime}$
since it is not q-hierarchical. Adding the variable $u$ to the head of
$Q^{\prime}$ yields the desired q-hierarchical query, since every full
hierarchical query is q-hierarchical.

Note that, for the proof of Theorem 5.10, which builds upon the proof for
Theorem 5.8, it is required that $u$ is _not_ in the head of $V$: it ensures
that the whole query has to be covered by a single application of the view
$V$. In other words, it ensures that, if there is a rewriting of $Q$, there is
a rewriting that consists only of a single atom. Since this restriction is not
necessary in the setting of the select-full-project equivalence problem, we
can indeed simply add161616In fact, we could also remove $u$ from $Q^{\prime}$
altogether. In this case, we also have to remove it from $Q$. $u$ to the head
of $Q^{\prime}$.

##  6 A Tractable Case

In this section, we first show that the acyclic rewriting problem becomes
tractable for free-connex acyclic views and acyclic queries over database
schemas of bounded arity. We then define a slightly larger class of views, for
which this statement holds as well. For the first result, we mainly show that
rewritability with respect to a set ${\mathcal{V}}$ of free-connex acyclic
views can be reduced to rewritability with respect to a set ${\mathcal{W}}$ of
views of bounded arity.

######  Proposition 6.1.

There is a polynomial-time algorithm that computes from each set
${\mathcal{V}}$ of free-connex acyclic views a set ${\mathcal{W}}$ of
acyclic171717In fact, the views in ${\mathcal{W}}$ are even free-connex
acyclic again. However, we do not claim it here, since it is not needed in the
following, and it does not need to hold for the subsequent generalisation.
views such that

  1. (a)

the arity of the views of ${\mathcal{W}}$ is bounded by the arity of the
underlying schema, and

  2. (b)

every conjunctive query $Q$ is ${\mathcal{V}}$-rewritable if and only if it is
${\mathcal{W}}$-rewritable.

Furthermore, given a ${\mathcal{W}}$-rewriting of $Q$, a
${\mathcal{V}}$-rewriting of $Q$ can be computed in polynomial time.

######  Proof 6.2.

Let ${\mathcal{V}}$ be a set of free-connex acyclic views over a schema
${\mathcal{S}}$ with arity at most $k$. Let $V\in{\mathcal{V}}$ and $J$ be a
join tree for $V$ including its head atom ${{\textnormal{head}}(V)}$. Since a
join tree is undirected, we can assume that the root of $J$ is the node
labelled with ${{\textnormal{head}}(V)}$. Let $A_{1},\ldots,A_{n}$ be the
labels of the children of the root node. Furthermore, let, for each $1\leq
i\leq n$, ${\mathcal{B}}_{i}$ be the set of atoms in the subtree of $J$ with
root $A_{i}$. Since $J$ is a join tree, each variable that occurs in some atom
of a set ${\mathcal{B}}_{i}$ and in ${{\textnormal{head}}(V)}$ also occurs in
$A_{i}$. Furthermore, variables that occur in two sets ${\mathcal{B}}_{i}$,
${\mathcal{B}}_{j}$, $i\not=j$, necessarily occur also in
${{\textnormal{head}}(V)}$. Thus, the following two conditions hold, for every
$i\in\\{1,\dots,n\\}$ and every $j<i$,

$|{\textnormal{vars}}({\mathcal{B}}_{i})\cap{\textnormal{vars}}({{\textnormal{head}}(V)})|\leq
k$, and

${\textnormal{vars}}({\mathcal{B}}_{i})\cap{\textnormal{vars}}({\mathcal{B}}_{j})\subseteq{{\textnormal{head}}(V)}$.

For each $1\leq i\leq n$ we define the view $V_{i}$ as the projection of $V$
to the variables that occur in ${{\textnormal{head}}(V)}$ and in
${\mathcal{B}}_{i}$. That is, the body of $V_{i}$ is just the body of $V$ and
the head of $V_{i}$ contains precisely those head variables of $V$ that occur
in ${\mathcal{B}}_{i}$. By construction, the views $V_{i}$ have arity
${\textnormal{ar}}(A_{i})\leq k$. Furthermore, the views $V_{i}$ are acyclic
since they have the same body as $V$ which is acyclic.181818We observe that,
since all head variables of $V_{i}$ occur in $A_{i}$, each $V_{i}$ is even
free-connex acyclic.

The desired set ${\mathcal{W}}$ of views can thus be obtained by replacing
each view $V\in{\mathcal{V}}$ by views $V_{1},\ldots,V_{n}$ as constructed
above. It is easy to see that ${\mathcal{W}}$ can be computed in polynomial
time.

It remains to show that an arbitrary CQ $Q$ is ${\mathcal{V}}$-rewritable if
and only if it is ${\mathcal{W}}$-rewritable. For the direction from right to
left, let ${\mathcal{C}}_{\mathcal{W}}$ be a cover partition witnessing that
$Q$ is ${\mathcal{W}}$-rewritable. Consider a cover description
$({\mathcal{A}},V_{i},{\alpha},\psi)$ where $V_{i}$ is a view constructed as
above, originating from a view $V\in{\mathcal{V}}$. Since the only difference
between $V$ and $V_{i}$ is that $V$ has more head variables, replacing $V_{i}$
with $V$ yields a cover description $({\mathcal{A}},V,{\alpha},\psi)$.
Analogous replacements in all cover descriptions in
${\mathcal{C}}_{\mathcal{W}}$ yield a cover partition witnessing
${\mathcal{V}}$-rewritability of $Q$. Moreover, given a
${\mathcal{W}}$-rewriting of $Q$, a ${\mathcal{V}}$-rewriting of $Q$ can be
obtained by replacing every $V_{i}$-atom in the ${\mathcal{W}}$-rewriting by a
$V$-atom where $V$ is, as above, the view $V_{i}$ originated from. Variables
not occurring in ${\mathcal{B}}_{i}$ but in the head of $V$ are replaced by
fresh variables (i.e. variables not occurring anywhere else) in the $V$-atom.

For the direction from left to right, let ${\mathcal{C}}_{\mathcal{V}}$ be a
consistent cover partition witnessing ${\mathcal{V}}$-rewritability of $Q$. We
replace the cover descriptions in ${\mathcal{C}}_{\mathcal{V}}$ to obtain a
cover partition witnessing ${\mathcal{W}}$-rewritability of $Q$. To this end,
let $C=({\mathcal{A}},V,{\alpha},\psi)$ be a cover description in
${\mathcal{C}}_{\mathcal{V}}$. Furthermore, let
${\mathcal{B}}_{1},\ldots,{\mathcal{B}}_{n}$ and $V_{1},\ldots,V_{n}$ be as in
the construction of ${\mathcal{W}}$ above. For each $1\leq i\leq n$, let
${\mathcal{A}}_{i}$ be the set of all atoms of ${\mathcal{A}}$ which are in
${\alpha}({\mathcal{B}}_{i})$ but in no ${\alpha}({\mathcal{B}}_{j})$, for
$j<i$. Since
${{\textnormal{vars}}({\mathcal{A}})}\subseteq{\alpha}({{\textnormal{body}}(V)})$,
this yields a partition of ${\mathcal{A}}$. We claim that, for each $1\leq
i\leq n$, $C_{i}=({\mathcal{A}}_{i},V_{i},{\alpha},\psi)$ is a cover
description. Since $V_{i}$ and $V$ have the same body, conditions (4.1) and
(4.1) hold. Condition (4.1) holds since
${{\textnormal{vars}}({\mathcal{A}}_{i})}\subseteq{{\textnormal{vars}}({\mathcal{A}})}$.

In the remainder, we prove that Condition (4.1) holds. Let
$x\in{{\textnormal{bvars}}({\mathcal{A}}_{i})}$. Then $x$ is either in
${{\textnormal{bvars}}(A)}$ or it is a ?new? bridge variable that also occurs
in some ${\mathcal{A}}_{j}\subseteq{\mathcal{A}}$, $j\neq i$. In the former
case, $x\in{\alpha}({{\textnormal{head}}(V)})$ since Condition (4.1) holds for
$C$. Thus, there are variables $y\in{{\textnormal{head}}(V)}$ and $y^{\prime}$
in ${\mathcal{B}}_{i}$ such that ${\alpha}(y)=x={\alpha}(y^{\prime})$. Since,
thanks to quantified variable disjointness, ${\alpha}$ maps quantified and
head variables disjointly, it follows that $y^{\prime}$ must be from
${{\textnormal{head}}(V)}$ as well. But then $y^{\prime}$ occurs in
${{\textnormal{head}}(V_{i})}$ since it is in ${{\textnormal{head}}(V)}$ and
in ${\mathcal{B}}_{i}$. Therefore,
$x={\alpha}(y^{\prime})\in{\alpha}({{\textnormal{head}}(V_{i})})$.

In the other case, let $j\not=i$ be such that $x$ occurs in
${\mathcal{A}}_{j}$ and, hence, in ${\alpha}({\mathcal{B}}_{j})$. Let $y,z$ be
variables from ${\mathcal{B}}_{i}$ and ${\mathcal{B}}_{j}$, respectively, such
that ${\alpha}(y)=x={\alpha}(z)$. If $y=z$, then $y$ is a head variable of
$V$, since ${\mathcal{B}}_{i}$ and ${\mathcal{B}}_{j}$ have only head
variables of $V$ in common. If $y\neq z$, then both $y$ and $z$ occur in the
head of $V$ thanks to quantified variable disjointness. In both cases, we can
conclude that $x={\alpha}(y)$ occurs in
${\alpha}({{\textnormal{head}}(V_{i})})$. Thus, Condition (4.1) holds for
$C_{i}$.

Since the ${\mathcal{A}}_{i}$ form a partition of ${\mathcal{A}}$, replacing
$C$ in ${\mathcal{C}}_{\mathcal{V}}$ with $C_{1},\ldots,C_{n}$ yields a cover
partition (with respect to ${\mathcal{V}}\cup{\mathcal{W}}$) and iterating
this process for all cover descriptions in the original partition
${\mathcal{C}}_{\mathcal{V}}$ yields a cover partition witnessing
${\mathcal{W}}$-rewritability of $Q$.

The main result of this section is now a simple corollary to Proposition 6.1.

######  Theorem 6.3.

For every fixed $k$,
${{\textsc{Rewr}}^{k}({\mathsf{CCQ}},{\mathsf{ACQ}},{\mathsf{ACQ}})}$ is in
polynomial time and an acyclic rewriting can be computed in polynomial time,
if it exists.

######  Proof 6.4.

Let $Q\in{\mathsf{ACQ}}$ be an acyclic query and
${\mathcal{V}}\subseteq{\mathsf{CCQ}}$ be a set of free-connex acyclic views
over a schema ${\mathcal{S}}$ with arity at most $k$. Thanks to Proposition
6.1, from ${\mathcal{V}}$ an equivalent set ${\mathcal{W}}$ of acyclic views
of arity at most $k$ can be computed in polynomial time. The statements of the
theorem thus follow immediately from Corollary 5.6.

We leave the complexity of
${{\textsc{Rewr}}({\mathsf{CCQ}},{\mathsf{ACQ}},{\mathsf{ACQ}})}$ as an open
problem.

A closer inspection of the proof of Proposition 6.1 reveals that it does not
exactly require that the views are free-connex acyclic. In fact, it suffices
that each view has a partition
${\mathcal{B}}_{1}\uplus\dots\uplus{\mathcal{B}}_{m}$ of its body that obeys
Conditions (6.5) and (6.5). Therefore, we turn these two requirements into a
new notion. We formulate and study this notion for conjunctive queries ${Q}$,
but we emphasise that we will use it for queries that define views only.

######  Definition 6.5.

The _weak head arity_ of a query $Q$ is the smallest $k$ for which there is a
partition ${\mathcal{B}}_{1}\uplus\dots\uplus{\mathcal{B}}_{n}$ of
${{\textnormal{body}}(Q)}$ such that, for every $i\in\\{1,\dots,n\\}$ and
every $j<i$,

$|{\textnormal{vars}}({\mathcal{B}}_{i})\cap{\textnormal{vars}}({{\textnormal{head}}(Q)})|\leq
k$, and

${\textnormal{vars}}({\mathcal{B}}_{i})\cap{\textnormal{vars}}({\mathcal{B}}_{j})\subseteq{{\textnormal{head}}(Q)}$.

From the proof of Proposition 6.1 it follows that every free-connex acyclic
query over a fixed schema has bounded weak head arity. The following example
illustrates that there are indeed views over a fixed schema that have bounded
weak head arity but are not free-connex acyclic.

######  Example 6.6.

Let us consider the family ${\big{(}V_{n}\big{)}}_{n\in{\mathbb{N}}}$ of views
with

  * •

head $V_{n}(x,y_{1},\ldots,y_{n},z_{1},\ldots,z_{n})$, and

  * •

body $\\{R(x,u_{i},y_{i}),S(x,u_{i},z_{i}),T(y_{i})\mid 1\leq i\leq n\\}$.

For $n\geq 1$ the view $V_{n}$ is acyclic but _not_ free-connex acyclic. It
has, however, weak head arity $3$. This is witnessed by the sets
${\mathcal{B}}_{i}=\\{R(x,u_{i},y_{i}),S(x,u_{i},z_{i}),T(y_{i})\\}$ for
$1\leq i\leq n$ which form a partition satisfying the conditions of Definition
6.5.

To generalise Theorem 6.3 for views of bounded weak head arity, we thus only
need to show that partitions obeying Conditions (6.5) and (6.5) of Definition
6.5 can be efficiently computed. In the remainder of this section we design an
algorithm that determines the weak head arity of a given conjunctive query
${Q}$ and computes a corresponding partition.

The algorithm relies on the concept of a cover graph for ${Q}$.

######  Definition 6.7.

The cover graph ${G({Q})}$ of a conjunctive query ${Q}$ is the undirected
graph with node set ${{\textnormal{body}}({Q})}$ and edges $(A,A^{\prime})$
for atoms $A$ and $A^{\prime}$ that share a variable that does not belong to
${{\textnormal{head}}({Q})}$.

######  Example 6.8.

The cover graph of the view $V_{3}$ from Example 6.6 is depicted in Figure 2.

$R(x,u_{1},y_{1})$$S(x,u_{1},z_{1})$$T(y_{1})$$R(x,u_{2},y_{2})$$S(x,u_{2},z_{2})$$T(y_{2})$$R(x,u_{3},y_{3})$$S(x,u_{3},z_{3})$$T(y_{3})$
Figure 2: The cover graph ${G(V_{3})}$ of the query $V_{n}$ for $n=3$ defined
in Example 6.6.

The following lemma states the relationship between weak head arity and cover
graph.

######  Lemma 6.9.

Let ${Q}$ be a conjunctive query and
${\mathcal{B}}_{1},\ldots,{\mathcal{B}}_{n}$ the connected components of its
cover graph. The weak head arity of ${Q}$ is the maximal number $\ell$ of head
variables of ${Q}$ in a set ${\mathcal{B}}_{i}$. Moreover, the connected
components ${\mathcal{B}}_{1},\ldots,{\mathcal{B}}_{n}$ witness that ${Q}$ has
weak head arity $\ell$.

######  Proof 6.10.

Let ${Q}$ be a conjunctive query and let
${\mathcal{B}}^{\prime}_{1}\uplus\cdots\uplus{\mathcal{B}}^{\prime}_{m}$ be a
partition of ${{\textnormal{body}}({Q})}$ witnessing that ${Q}$ has weak head
arity $k$.

Since by definition of the cover graph, two different sets ${\mathcal{B}}_{i}$
and ${\mathcal{B}}_{j}$ only share head variables,
${\mathcal{B}}_{1}\uplus\cdots\uplus{\mathcal{B}}_{n}$ is a partition of
${{\textnormal{body}}({Q})}$ witnessing that ${Q}$ has weak head arity at most
$\ell$, hence it holds $k\leq\ell$.

To show that $\ell\leq k$, it suffices to show that every connected component
${\mathcal{B}}$ in ${G({Q})}$ is contained in some atom set
${\mathcal{B}}^{\prime}_{i}$. Towards a contradiction we assume that there is
a connected component ${\mathcal{B}}$ with atoms from two different subsets of
the partition. Since ${\mathcal{B}}$ is connected there must be some
$A_{1},A_{2}\in{\mathcal{B}}$, connected by an edge, such that
$A_{1}\in{\mathcal{B}}^{\prime}_{i}$ and $A_{2}\in{\mathcal{B}}^{\prime}_{j}$,
for some $i\not=j$. By definition of ${G({Q})}$, $A_{1}$ and $A_{2}$ share a
variable that is not part of the head of ${Q}$. But that contradicts Condition
(6.5) in Definition 6.5. Thus, we can conclude $\ell\leq k$.

Lemma 6.9 offers an algorithm to compute the weak head arity of a conjunctive
query ${Q}$ and a witness partition for it. It simply computes the cover graph
${G({Q})}$ of ${Q}$ and its connected components. Then the weak head arity is
the maximum number of head variables that occur in any connected component.
Furthermore, the connected components form the desired partition satisfying
the conditions of Definition 6.5. We thus have the following corollary.

######  Corollary 6.11.

There is an algorithm that, upon input of a conjunctive query $Q$, computes in
polynomial time the weak head arity of $Q$ and a partition of
${{\textnormal{body}}(Q)}$ that witnesses it.

By combining Corollary 6.11 with the proofs of Proposition 6.1 and Theorem
6.3, we obtain the following generalisation of Theorem 6.3.

######  Theorem 6.12.

For each fixed $k\in{\mathbb{N}}$, the acyclic rewriting problem for acyclic
queries and acyclic views with weak head arity $k$ is in polynomial time.

##  7 The Existence of Hierarchical and q-hierarchical Rewritings

In Section 5, we have shown that every _acyclic_ query has an _acyclic_
rewriting if it has a rewriting at all. This gives us a guarantee that there
is a rewriting that has the same complexity benefits for query evaluation as
the original query.

It is natural to ask whether other, stronger properties transfer in the same
fashion. In this section, we consider this question for hierarchical and
q-hierarchical queries.

The following example illustrates that, as for acyclic rewritings, even if a
hierarchical rewriting for a hierarchical query exists, the canonical
rewriting is not necessarily hierarchical.

######  Example 7.1.

Consider the hierarchical query $H(x,y)\leftarrow R(x),S(y),T(x),T(y)$ and the
views $V_{1}(x,y)\leftarrow R(x),S(y)$ and $V_{2}(z)\leftarrow T(z)$. The
canonical rewriting leads us to the non-hierarchical rewriting
$H(x,y)\leftarrow V_{1}(x,y),V_{2}(x),V_{2}(y)$, since
${\textnormal{atoms}}(y)$ and ${\textnormal{atoms}}(z)$ are neither disjoint
nor subsets of one another. However, a hierarchical rewriting exists, for
instance $H(x,y)\leftarrow
V_{1}(x,y^{\prime}),V_{1}(x^{\prime},y),V_{2}(x),V_{2}(y)$ is a hierarchical
rewriting.

It turns out that Theorem 5.4 also holds for hierarchical and q-hierarchical
queries.

######  Theorem 7.2.

Let ${\mathcal{V}}$ be a set of views.

  1. (a)

Every hierarchical query that has some ${\mathcal{V}}$-rewriting also has a
hierarchical ${\mathcal{V}}$-rewriting.

  2. (b)

Every q-hierarchical query that has some ${\mathcal{V}}$-rewriting also has a
q-hierarchical ${\mathcal{V}}$-rewriting.

Similarly as for Theorem 5.4, the proof of Theorem 7.2 partitions cover
descriptions. However, the strategy for doing so is different here: instead of
defining the partition as the connected components of an atom set with respect
to a join tree of the query at hand, here the partition guaranteed by the
following lemma is used.

######  Lemma 7.3.

Let ${Q}$ be a hierarchical query and $({\mathcal{A}},V,{\alpha},\psi)$ a
cover description for ${Q}$. There is a partition
${\mathcal{A}}_{1}\uplus\cdots\uplus{\mathcal{A}}_{n}={\mathcal{A}}$ such that
the following conditions hold.

  1. (A)

Each variable
$y\notin{{\textnormal{vars}}({\alpha}({{\textnormal{head}}(V)}))}$ appears in
at most one set ${\mathcal{A}}_{i}$.

  2. (B)

Each ${\mathcal{A}}_{i}$ is

    1. (Ba)

a singleton set or

    2. (Bb)

there is a variable
$x\notin{{\textnormal{vars}}({\alpha}({{\textnormal{head}}(V)}))}$ that
appears in every atom in ${\mathcal{A}}_{i}$.

######  Proof 7.4.

The algorithm uses an undirected graph $G$ similar to the cover graph of
Section 6. The graph $G$ has vertex set ${\mathcal{A}}$ and an edge labelled
by variable $x$ between two atoms $A_{1},A_{2}$, if
$x\notin{{\textnormal{vars}}({{\textnormal{head}}({\alpha}(V))})}$ if $x$
occurs in $A_{1}$ and $A_{2}$. We note that there can be more than one edge
between two atoms.

Clearly, for each variable
$x\notin{{\textnormal{vars}}({{\textnormal{head}}({\alpha}(V))})}$, the atoms
that contain $x$ constitute a clique in $G$ with edges labelled by $x$. In
particular, each variable
$x\notin{{\textnormal{vars}}({{\textnormal{head}}({\alpha}(V))})}$ can occur
in at most one connected component. Since ${Q}$ is hierarchical, for two
cliques $C_{x},C_{y}$ induced by different variables $x$ and $y$ it holds that
either they are disjoint or one contains the other. It readily follows that
for each connected component $H$ of $G$ there is a variable $x$, such that
$C_{x}$ contains all atoms of $H$.

Therefore the partition
${\mathcal{A}}_{1}\uplus\cdots\uplus{\mathcal{A}}_{n}={\mathcal{A}}$ given by
the connected components of $G$ fulfils the conditions of the Lemma.

Now we are prepared to prove Theorem 7.2.

######  Proof 7.5 (Proof of Theorem 7.2).

Towards (a), let ${Q}$ be a hierarchical query with some
${\mathcal{V}}$-rewriting ${R}^{\prime}$. W.l.o.g. we can assume that ${Q}$ is
minimal (cf. Remark 4.9). Thanks to Theorem 4.5, there is a cover partition
${\mathcal{C}}^{\prime}=C^{\prime}_{1},\dots,C^{\prime}_{k}$ for ${Q}$ over
${\mathcal{V}}$. We replace every cover description
$({\mathcal{A}},V,{\alpha},\psi)$ in ${\mathcal{C}}^{\prime}$ by
$({\mathcal{A}}_{1},V,{\alpha},\psi),\ldots,({\mathcal{A}}_{n},V,{\alpha},\psi)$
were ${\mathcal{A}}_{1}\uplus\cdots\uplus{\mathcal{A}}_{n}={\mathcal{A}}$ is
the partition of ${\mathcal{A}}$ from Lemma 7.3 and let ${\mathcal{C}}$ be the
collection we obtain after the replacement. For each
$({\mathcal{A}}_{i},V,{\alpha},\psi)$ Condition (4.1) of Definition 4.1 is
satisfied thanks to Condition (A) of Lemma 7.3. It is easy to verify that the
other conditions in Definition 4.1 are satisfied for each
$({\mathcal{A}}_{i},V,{\alpha},\psi)$. All in all, the collection
${\mathcal{C}}$ is a cover partition for ${Q}$ over ${\mathcal{V}}$. We can
further assume that ${\mathcal{C}}$ is consistent since the construction to
obtain consistency in the proof of Theorem 4.5 does only change the mappings
in cover descriptions, not the partition of ${{\textnormal{body}}({Q})}$.

Let ${R}$ be the rewriting obtained from ${\mathcal{C}}$, i.e., the query
${Q}_{{\mathcal{C}}}$. In the remainder of the proof we show that ${R}$ is
hierarchical, i.e., every pair of variables in $x$ and $y$ in ${R}$ satisfies
the conditions in Definition 2. Let $x$ and $y$ be two variables in ${R}$.
Observe that, if $x$ (or $y$) occurs in two different atoms of ${R}$ then $x$
(resp. $y$) also occurs in ${Q}$ and is a bridge variable thanks to Condition
(4.1) of Definition 4.1 and ${\mathcal{C}}$ being consistent.

If neither of $x$ and $y$ is a bridge variable, each occurs in only one cover
description, and there are two cases: (i) they can be in the same cover
description, in which case they both occur in the same atom of $R$ and thus
${\textnormal{atoms}}_{R}(x)={\textnormal{atoms}}_{R}(y)$; or (ii) they occur
in different cover descriptions and thus in different atoms of $R$ and we have
${\textnormal{atoms}}_{R}(x)\cap{\textnormal{atoms}}_{R}(y)=\emptyset$.

If $x$ is a bridge variable and $y$ is not, then there are again two cases:
(i) if in the only cover description, in which $y$ occurs, $x$ occurs as well,
then ${\textnormal{atoms}}_{R}(y)\subseteq{\textnormal{atoms}}_{R}(x)$, and
(ii) otherwise
${\textnormal{atoms}}_{R}(x)\cap{\textnormal{atoms}}_{R}(y)=\emptyset$.

Let us finally assume that both $x$ and $y$ are bridge variables. Since ${Q}$
is hierarchical we have the three cases.

Case 1:

${\textnormal{atoms}}_{{Q}}(x)\subseteq{\textnormal{atoms}}_{{Q}}(y)$. Hence,
if a cover description $({\mathcal{A}},V,{\alpha},\psi)$ in $\mathcal{C}$
fulfils $x\in{\alpha}({{\textnormal{head}}(V)})$ it also fulfils
$y\in{\alpha}({{\textnormal{head}}(V)})$, and thus,
${\textnormal{atoms}}_{{R}}(x)\subseteq{\textnormal{atoms}}_{{R}}(y)$.

Case 2:

${\textnormal{atoms}}_{{Q}}(y)\subseteq{\textnormal{atoms}}_{{Q}}(x)$. This
case is analogous to the first case.

Case 3:

${\textnormal{atoms}}_{{Q}}(x)\cap{\textnormal{atoms}}_{{Q}}(y)=\emptyset$. If
there is no cover description in ${\mathcal{C}}$, in which $x$ and $y$ occur
together, then
${\textnormal{atoms}}_{{R}}(x)\cap{\textnormal{atoms}}_{{R}}(y)=\emptyset$
holds. Let us thus assume that there is a cover description
$({\mathcal{A}},V,{\alpha},\psi)$ in $\mathcal{C}$, in which both $x$ and $y$
occur. Thanks to
${\textnormal{atoms}}_{{Q}}(x)\cap{\textnormal{atoms}}_{{Q}}(y)=\emptyset$,
${\mathcal{A}}$ contains at least two atoms. Thanks to Lemma 7.3, there is a
variable $u\notin{{\textnormal{vars}}({{\textnormal{head}}({\alpha}(V))})}$
that appears in all atoms of ${\mathcal{A}}$. Since $Q$ is hierarchical, we
must have
${\textnormal{atoms}}_{{Q}}(x)\subsetneq{\textnormal{atoms}}_{{Q}}(u)$.
However, this yields a contradiction, since $x$ occurs in atoms not in
${\mathcal{A}}$, whereas $u$ does not.

This concludes the proof of statement (a).

Towards (b), let us assume that ${Q}$ is q-hierarchical. Our goal is to show
that for all variables $x,y\in{\textnormal{vars}}(Q)$, if
${\textnormal{atoms}}_{R}(x)\subsetneq{\textnormal{atoms}}_{R}(y)$ holds and
$x$ is in the head of $R$, then $y$ is also in the head of $R$. Since the
heads of $Q$ and $R$ are the same, whenever
${\textnormal{atoms}}_{Q}(x)\subsetneq{\textnormal{atoms}}_{Q}(y)$ holds, we
can conclude that if $x$ is in the head of $R$, then $y$ is also in the head
of $R$.

A case inspection of the proof of statement (a) reveals that the only case, in
which ${\textnormal{atoms}}_{R}(x)\subsetneq{\textnormal{atoms}}_{R}(y)$ might
hold without
${\textnormal{atoms}}_{Q}(x)\subsetneq{\textnormal{atoms}}_{Q}(y)$ being the
case, is, when $y$ is a bridge variable and $x$ a non-bridge variable that co-
occurs with $y$ in some set ${\mathcal{A}}_{i}$, but for which
${\textnormal{atoms}}_{{Q}}(x)\cap{\textnormal{atoms}}_{{Q}}(y)=\emptyset$
holds. However, in this case, there is a non-head variable $u$ that occurs in
all atoms of ${\mathcal{A}}_{i}$, thanks to Lemma 7.3. Therefore,
${\textnormal{atoms}}_{Q}(x)\subsetneq{\textnormal{atoms}}_{Q}(u)$ and, since
$u$ is a non-head variable, $x$ is a non-head variable as well, since $Q$ is
q-hierarchical. Thus we can conclude that $R$ is q-hierarchical.

Similarly to Theorem 5.4, Theorem 7.2 delivers good news as well as bad news.
The good news is that, since ${\mathsf{QHCQ}}\subseteq{\mathsf{CCQ}}$ and
${\mathsf{QHCQ}}\subseteq{\mathsf{HCQ}}\subseteq{\mathsf{ACQ}}$ hold, the
rewriting problem for q-hierarchical views and hierarchical queries over a
fixed schema is tractable thanks to Theorems 6.3 and 7.2. The bad news is that
Theorems 5.8 and 7.2 imply NP-completeness for hierarchical queries and views.

######  Corollary 7.6.

${{\textsc{Rewr}}^{k}({\mathsf{QHCQ}},{\mathsf{HCQ}},{\mathsf{HCQ}})}$ and
${{\textsc{Rewr}}^{k}({\mathsf{QHCQ}},{\mathsf{QHCQ}},{\mathsf{QHCQ}})}$ are
in polynomial time for every $k\in{\mathbb{N}}$.

######  Corollary 7.7.

${{\textsc{Rewr}}^{k}({\mathsf{HCQ}},{\mathsf{HCQ}},{\mathsf{HCQ}})}$ is NP-
complete for every $k\geq 3$.

##  8 Related Work

We already mentioned that our notion of cover partitions is similar to various
notions from the literature. We mention three of them here.

In [2] algorithms for finding exact rewritings with a minimal number of atoms
and (maximally) contained rewritings are presented. For this purpose triples
$(S,S^{\prime},h)$ are considered which are comparable to cover descriptions.
Namely, $S^{\prime}$ corresponds to the set ${\mathcal{A}}$ in a cover
description, $S={{\textnormal{body}}({Q})}$, and $h$ is a homomorphism from
$S^{\prime}$ into a view $V$. In our characterisation we can assume
$h={\textnormal{id}}$ (and, thus, omit it in the specification of a cover
description) thanks to the view application ${\alpha}$. We note that $h$ can
be assumed to be one-to-one for (equivalent) ${\mathcal{V}}$-rewritings [2,
Theorem 3.15]. Furthermore, for (equivalent) rewritings, only candidates whose
body is a proper subset of the canonical rewriting’s body are considered (cf.
[2, Section 3.2.3]). Note that the existence of body homomorphisms $\psi_{i}$
mapping the ${\alpha}_{i}(V_{i})$ into $Q$ is guaranteed for such candidates
and $\psi_{i}$ determines the application ${\alpha}_{i}$ (in particular, the
unification of variables in the head of a view). This is, however, too
restrictive for our purposes (cf., for instance, Example 5.1) which is why
${\alpha}$ and $\psi$ are part of a cover description. We emphasise that
Condition (4.1) is equivalent to the _shared-variable property_ [2, Definition
3.12]. An analog of the implication (4.5) $\Rightarrow$ (4.5) of Theorem 4.5
is proven [2, Theorem 3.15] and, based on that, an algorithm (called
CoreCover) for finding (equivalent) rewritings is derived. This algorithm,
however, considers only triples with maximal sets $S^{\prime}$ (called _tuple
cores_) and they are allowed to overlap, i.e. they do not have to form a
partition. In contrast, we consider non-maximal sets, for instance in the
proof of Theorem 5.4 which depends upon the possibility to split these sets.
For (maximally) contained rewritings, an analogue of (4.5) $\Rightarrow$ (4.5)
is implied by [2, Theorem 4.19]. Interestingly, the proof of this result (and
the associated algorithm) exploits triples with minimal sets $S^{\prime}$
(that still satisfy the shared-variable property) and a partition property. We
discuss the relation of this minimality constraint with our results below in
more detail. An analogue of (4.5) $\Rightarrow$ (4.5) for (equivalent)
${\mathcal{V}}$-rewritings, and, therefore, a characterisation for
${\mathcal{V}}$-rewritability, is not stated (nor implied).

In [17] a characterisation for ${\mathcal{V}}$-rewritability is employed to
find rewritings efficiently. It is in terms of _tuple coverages_ and a
_partition condition_ corresponding to cover descriptions and partitions,
respectively [17, Theorem 5, Theorem 6]. A tuple coverage, denoted
$s(t_{V},Q)$, is a (non-empty) set $G$, where $t_{V}$ corresponds to
${\alpha}(V)$ and $G$ to the set ${\mathcal{A}}$ of a cover description.
Similar to [2] the most crucial differences in comparison with our
characterisation are that only rewritings whose body is contained in the
canonical rewriting, i.e.
${{\textnormal{vars}}({\alpha}(V))}\subseteq{{\textnormal{vars}}(Q)}$ holds
for all tuple coverages, are considered. Also the mappings $\psi$ and
${\alpha}$ (and their associated conditions) are not denoted explicitly,
instead it is required that $G$ is isomorphic to a subset of ${\alpha}(V)$ and
Condition (4.1) holds (this is equivalent to our conditions if restricted to
the rewritings considered in [17]).

Lastly, in [29] _MiniCon descriptions (MCDs)_ are used to compute (maximally)
contained rewritings (which are unions of conjunctive queries, in general). A
MCD is a tuple of the form $(h,V,\varphi,G)$ which relates to a cover
description $({\mathcal{A}},V,{\alpha},\psi)$ as follows: $h$ is called a head
homomorphism and is basically the restriction of an application ${\alpha}$ to
the head variables of the view $V$, $G$ corresponds to the set
${\mathcal{A}}$, and $\varphi$ is mapping embedding $G$ into $h(V)$. The
component $\varphi$ has no counterpart in a cover description because, thanks
to ${\alpha}$ being able to rename any variable in $V$, we can assume
$\varphi={\textnormal{id}}$. We note that the applications ${\alpha}_{i}$ of a
consistent cover partition ${\mathcal{C}}$ also allow us to conveniently
denote the expansion of the associated rewriting ${Q}_{\mathcal{C}}$. On the
other hand, there is no counterpart for the body-homomorphism $\psi$ in a MCD
(since the $\psi_{i}$ in a consistent cover partition ensure that the query is
contained in the associated expansion of the rewriting, there is also no need
for them if contained rewritings are considered). Condition (4.1) is stated as
[29, Property 1] and the idea of a cover partition in [29, Property 2].

#### Minimal cover descriptions

In [2], ?minimal? triples are used to construct maximally contained
rewritings. In terms of cover descriptions, an analogous definition of
minimality is as follows.

######  Definition 8.1 (Minimal Cover Descriptions).

A cover description $({\mathcal{A}},V,{\alpha},\psi)$ for a query $Q$ is
called _minimal_ if there is no partition
${\mathcal{A}}_{1}\uplus\dots\uplus{\mathcal{A}}_{k}={\mathcal{A}}$ for $k\geq
2$ with nonempty subsets ${\mathcal{A}}_{1},\dots,{\mathcal{A}}_{k}$ such that
cover descriptions $C_{1},\dots,C_{k}$ with
$C_{i}=({\mathcal{A}}_{i},V,{\alpha}_{i},\psi_{i})$ for $Q$ exist.

It seems to be obvious to exploit such minimal cover description for the
constructions in Theorem 5.4 and 7.2, instead of partitioning the set
${\mathcal{A}}$ of a cover description ?manually?. However, in contrast to our
constructions, this would (possibly) not result in efficient algorithms to
compute an acyclic or hierarchical rewriting from an arbitrary one, since it
turns out that deciding whether a cover description is minimal is coNP-hard.

######  Proposition 8.2.

Let ${Q}$ be a hierarchical conjunctive query. It is coNP-hard to decide
whether a cover description $(\mathcal{A},{Q},\alpha,\psi)$ is minimal.

######  Proof 8.3.

We reduce problem
${{\textsc{Rewr}}({\mathsf{HCQ}},{\mathsf{HCQ}},{\mathsf{CQ}})}$ to the
minimisation problem. For a hierarchical query ${Q}$ and a set of hierarchical
views ${\mathcal{V}}$, we describe how we can derive a cover description
$C_{{\mathcal{V}}}^{{Q}}$ and a query $Q^{\prime}$ such that
$C_{{\mathcal{V}}}^{{Q}}$ is not minimal for $Q^{\prime}$ if and only if there
is a ${\mathcal{V}}$-rewriting for ${Q}$.

For convenience, we introduce some notation. For a set of atoms
${\mathcal{A}}$ and a variable $u$ we define with ${{\mathcal{A}}}^{u}$ the
set of atoms of ${\mathcal{A}}$ where every atom is extended by the variable
$u$, i.e.

${{\mathcal{A}}}^{u}\ =\ \left\\{R(u,x_{1},\ldots,x_{r})\mid
R(x_{1},\ldots,x_{r})\in{\mathcal{A}}\right\\}$

Let $V_{1},\ldots,V_{n}$ be the views in ${\mathcal{V}}$. W.l.o.g. assume that
each view in ${\mathcal{V}}$ does not share any variable with another view in
${\mathcal{V}}$ or ${Q}$. Otherwise, one can rename the variables in the views
in polynomial time.

##### Construction.

We start with the construction of the cover description
$C_{{\mathcal{V}}}^{{Q}}$. To define a view and a query for the cover
description, we consider views ${V_{1}}^{v_{1}},\ldots,{V_{n}}^{v_{n}}$ that
are copies of the input views $V_{1},\ldots,V_{n}$ where each atom will be
expanded by a special variable, that only appears in the associated view, in
the first component and in the head, i.e. for every $i\in\\{1,\ldots,n\\}$ we
define a view ${V_{i}}^{v_{i}}$ with
${{\textnormal{head}}({V_{i}}^{v_{i}})}={{{\textnormal{head}}(V_{i})}}^{v_{i}}$
and
${{\textnormal{body}}({V_{i}}^{v_{i}})}={{{\textnormal{body}}(V_{i})}}^{v_{i}}$
where $v_{1},\ldots,v_{n}$ are distinct variables that do not occur in the
query or in any of the views in ${\mathcal{V}}$. In the same fashion, we
define a set of atoms for the atoms in the query, but we add a new atom whose
relation symbol does not occur in ${Q}$ or in any of the views in
${\mathcal{V}}$. For a new variable $u$ and a new relation symbol $S$, we
define
$\mathcal{A}_{\mathcal{Q}}={{{\textnormal{body}}({Q})}}^{u}\cup\\{S(u)\\}$.
Let us now turn to the definition of the view $W$ that is used in the cover
description. The view $W$ contains the atoms in $\mathcal{A}_{\mathcal{Q}}$,
the atoms in ${{\textnormal{body}}({V_{i}}^{v_{i}})}$ for all
$i\in\\{1,\ldots,n\\}$ and a special atom $S(v_{n+1})$ with a new191919a
variable that is not used yet variable $v_{n+1}$ in the body. The head of $W$
contains the variables in the head of ${Q}$ and variables in the head $V_{i}$
for all $i\in\\{1,\ldots,n\\}$ as well as the variables $v_{1},\ldots,v_{n+1}$
, but not $u$. Note, that for each view ${V_{i}}^{v_{i}}$, the set
${{\textnormal{body}}({V_{i}}^{v_{i}})}$ is contained in
${{\textnormal{body}}(W)}$.

The query $Q^{\prime}$ is defined by the rule
${{{\textnormal{head}}({Q})}\leftarrow{{\textnormal{body}}(W)}}$, that is
$Q^{\prime}$ has the head variables of ${Q}$ and the body of $Q^{\prime}$ has
the same atoms as the body of $W$.

The cover description $C_{{\mathcal{V}}}^{{Q}}$ is defined as
$(\mathcal{A}_{\mathcal{Q}},W,{\textnormal{id}},{\textnormal{id}})$. Note that
the bridge variables of $\mathcal{A}_{\mathcal{Q}}$ with respect to
$Q^{\prime}$ are contained in the head variables in $W$. Hence,
$C_{{\mathcal{V}}}^{{Q}}$ is a cover description for $Q^{\prime}$.

Note that the views ${V_{i}}^{v_{i}}$ are hierarchical since for the new
variables $v_{i}$ we have that
${\textnormal{atoms}}_{V_{i}}(v_{i})\supseteq{\textnormal{atoms}}_{V_{i}}(y)$
for all $y\in{{\textnormal{vars}}(V_{i})}$. The same is true for ${{Q}}^{u}$.
Moreover, $W$ and $Q^{\prime}$ are also hierarchical since the views and the
query do not share any variable.

##### Correctness.

In the following, we show that ${Q}$ has a ${\mathcal{V}}$-rewriting if and
only if $C_{{\mathcal{V}}}^{{Q}}$ for $Q^{\prime}$ is not minimal.

For the only if-direction assume that $Q$ has a ${\mathcal{V}}$-rewriting.
Then there is a consistent cover partition $\mathcal{C}$ for ${Q}$. Note that
by construction each cover description $({\mathcal{A}},V_{j},{\alpha},\psi)$
in $\mathcal{C}$ can be turned into a cover description
$({{\mathcal{A}}}^{u},{V_{j}}^{v_{j}},{\alpha}\cup\\{v_{j}\mapsto
u\\},\psi\cup\\{u\mapsto u\\})$ for $Q^{\prime}$ and, furthermore into a cover
description $({{\mathcal{A}}}^{u},W,{\alpha}^{\prime},\psi^{\prime})$ for
$Q^{\prime}$ where ${\alpha}^{\prime}$ and $\psi^{\prime}$ coincide with
${\alpha}\cup\\{v_{j}\mapsto u\\}$ and $\psi\cup\\{u\mapsto u\\}$ on their
domain, respectively, and are the identity on all other variables. Let
$\mathcal{C}^{\prime}$ be the collection of cover descriptions we obtain by
transforming every cover description in $\mathcal{C}$ to a cover description
as described above and the additional cover description
$(\\{S(u)\\},W,\\{v_{n+1}\mapsto u\\},{\textnormal{id}})$ for $Q^{\prime}$.
Clearly, $\mathcal{C}^{\prime}$ is a collection with at least two cover
description whose union of their atoms is $\mathcal{A}_{\mathcal{Q}}$ and
hence, $(\mathcal{A}_{\mathcal{Q}},W,{\textnormal{id}},{\textnormal{id}})$ for
$Q^{\prime}$ is not minimal.

For the if-direction assume that $C_{{\mathcal{V}}}^{{Q}}$ is not minimal for
$Q^{\prime}$. Let

$\mathcal{C}=({\mathcal{A}}_{1},W,{\alpha}_{1},\psi_{1}),\ldots,({\mathcal{A}}_{k},W,{\alpha}_{k},\psi_{k})$

be the collection of cover descriptions witnessing that
$(\mathcal{A}_{\mathcal{Q}},W,{\textnormal{id}},{\textnormal{id}})$ is not
minimal for $Q^{\prime}$. We can assume that the ${\alpha}_{i}$ fulfil the
quantified variable disjointness. Note, that $k\geq 2$ and $u$ is a bridge
variable of each set ${\mathcal{A}}_{i}$ since it occurs in every atom in
$\mathcal{A}_{\mathcal{Q}}$. Therefore, no atom in ${\mathcal{A}}_{i}$ can be
mapped into the copy of ${\alpha}_{i}(\mathcal{A}_{\mathcal{Q}})$ in
$\alpha_{i}(W)$ because the variable $u$ is not a head variable of $W$. Hence,
${\mathcal{A}}_{i}$ is a subset of
${\alpha}_{i}({{{\textnormal{body}}(V_{1})}}^{v_{1}})\cup\ldots\cup{\alpha}_{i}({{{\textnormal{body}}(V_{n})}}^{v_{n}})\cup\\{{\alpha}_{i}(S(v_{n+1}))\\}$.

Since the sets ${\alpha}_{i}({{{\textnormal{body}}(V_{j})}}^{v_{j}})$ do not
share any variable that is not in the
${{\textnormal{head}}({\alpha}_{i}(W))}$, each cover description in
$\mathcal{C}$ can be partitioned into cover descriptions

$({\mathcal{B}}_{i_{1}},W,{\alpha}_{i},\psi_{i}),\ldots,({\mathcal{B}}_{i_{\ell}},W,{\alpha}_{i},\psi_{i})$

for $Q^{\prime}$ where
${\mathcal{B}}_{i_{j}}={\mathcal{A}}_{i}\cap{\alpha}_{i}({{{\textnormal{body}}(V_{i_{j}})}}^{v_{i_{j}}})\neq\emptyset$
and, if $S(u)\in{\mathcal{A}}_{i}$, a cover description
$(\\{S(u)\\},W,{\alpha}_{i},\psi_{i})$. Note that the view $W$ can be replaced
by ${V_{i_{j}}}^{v_{i_{j}}}$, because
${\mathcal{B}}_{i_{j}}\subseteq{\alpha}_{i}({{\textnormal{body}}({V_{i_{j}}}^{v_{i_{j}}})})$.
Hence, each cover description
$({\mathcal{B}}_{i_{j}},W,{\alpha}_{i},\psi_{i})$ can be transformed into a
cover description
$({\mathcal{B}}_{i_{j}},{V_{i_{j}}}^{v_{i_{j}}},{\alpha}_{i_{j}},\psi_{i_{j}})$
where $\alpha_{i_{j}}$ and $\psi_{i_{j}}$ are the restriction of
${\alpha}_{i}$ and $\psi_{i}$ resp. on
${{\textnormal{vars}}({V_{i_{j}}}^{v_{i_{j}}})}$. The cover description
$({\mathcal{B}}_{i_{j}},{V_{i_{j}}}^{v_{i_{j}}},{\alpha}_{i_{j}},\psi_{i_{j}})$
can be transformed to a cover description
$({\mathcal{B}}_{i_{j}}^{\prime},V_{i_{j}},{\alpha}_{i_{j}}^{\prime},\psi_{i_{j}}^{\prime})$
for ${Q}$ where ${\mathcal{B}}_{i_{j}}^{\prime}$ is the atom set with
${{\mathcal{B}}_{i_{j}}^{\prime}}^{v_{i_{j}}}={\mathcal{B}}_{i_{j}}$, and
${\alpha}_{i_{j}}^{\prime}$ and $\psi_{i_{j}}^{\prime}$ are the restriction of
${\alpha}_{i_{j}}$ and $\psi_{i_{j}}$ on ${{\textnormal{vars}}(V_{i_{j}})}$.
Let $\widehat{\mathcal{C}}$ be the collection of cover descriptions in
$\mathcal{C}$, we obtain by replacing the other cover description by the
corresponding cover descriptions as described above removing cover
descriptions with atom set $\\{S(v_{n+1})\\}$. Note, that by construction, the
union of the atoms sets in $\widehat{\mathcal{C}}$ is equal to
${{\textnormal{body}}({Q})}$. Thus $\widehat{\mathcal{C}}$ is a cover
partition and hence, ${Q}$ is ${\mathcal{V}}$-rewritable.

#### Applications of acyclic, free-connex acyclic, hierarchical and
q-hierarchical queries

It is well known that many problems are tractable for acyclic conjunctive
queries but (presumably) not for conjunctive queries in general. Notably, the
evaluation, minimisation, and the containment problem are tractable for
acyclic queries [31, 10, 16] but NP-complete for the class of conjunctive
queries [9].

The class of free-connex conjunctive queries played a central role in the
enumeration complexity of conjunctive queries. In [3], Bagan, Durand and
Grandjean showed that the result of a free-connex acyclic conjunctive query
can be enumerated with constant delay after a linear time preprocessing phase.
Moreover, they also showed that the result of a self-join free acyclic
conjunctive query that is not free-connex can not be enumerated with constant
delay after a linear time preprocessing, unless $n\times n$ matrices can be
multiplied in time $O(n^{2})$.

Hierarchical queries have played a central role in different contexts. On the
one hand, Dalvi and Suciu [12] showed that the class of hierarchical Boolean
conjunctive queries characterises precisely the Boolean CQs that can be
answered in polynomial time on probabilistic databases. This has been extended
by Fink and Olteanu [13] to the notion of non-Boolean queries and queries with
negation. On the other hand, Koutris and Suciu [25] studied hierarchical join
queries in the context of query evaluation on massively parallel
architectures. We refer to [14] for further applications of hierarchical
queries.

The notion of q-hierarchical queries has played a central role in the
evaluation of conjunctive queries under single tuple updates [6]. In [6] it is
shown that the result of a q-hierarchical conjunctive query can be evaluated
(by answering a Boolean CQ in constant time, enumerating the result of a non-
Boolean CQ with constant delay, or output the number of results in constant
time) with constant update time after a linear time preprocessing. Moreover,
they showed that the result of a self-join free conjunctive query that is not
q-hierarchical can not be evaluated with constant update time after a linear
time preprocessing, unless some algorithmic conjectures on Online Matrix-
Vector multiplication (see [19] for more information about the conjecture)
does not hold.

The notion of q-hierarchical queries is also related to factorised databases
[23]. The notion of factorised databases has already been considered in
various contexts [28, 4, 30]. A further recent source of information on
structurally simple queries is [22].

##  9 Conclusion

We studied rewritability by acyclic queries or queries from ${\mathsf{CCQ}}$,
${\mathsf{HCQ}}$, or ${\mathsf{QHCQ}}$. Based on a new characterisation of
(exact) rewritability, we showed that acyclic queries have acyclic rewritings,
if they have any CQ rewriting. The same holds for the other three query
classes.

We showed that for acyclic queries and views the decision problem, whether an
acyclic rewriting exists, is intractable, even for schemas with bounded arity,
but becomes tractable if views have a bounded arity (even with unbounded
schema arity) or are free-connex acyclic.

We leave the case of free-connex acyclic views and unbounded schemas open.
Another interesting open question is the complexity of rewriting problems
${{\textsc{Rewr}}({\mathbb{V}},{\mathbb{Q}},{\mathbb{R}})}$ with
${\mathbb{R}}\subsetneq{\mathbb{Q}}$, e.g.
${{\textsc{Rewr}}({\mathsf{ACQ}},{\mathsf{ACQ}},{\mathsf{HCQ}})}$. Finally, it
would be interesting to study whether our results can be extended to other
classes of queries that can be evaluated efficiently like conjunctive queries
of bounded treewidth.

## References

  * [1] Serge Abiteboul, Richard Hull, and Victor Vianu.  Foundations of Databases.  Addison-Wesley, 1995.  URL: http://webdam.inria.fr/Alice/.
  * [2] Foto N. Afrati and Rada Chirkova.  Answering Queries Using Views, Second Edition.  Synthesis Lectures on Data Management. Morgan & Claypool Publishers, 2019.  doi:10.2200/S00884ED2V01Y201811DTM054.
  * [3] Guillaume Bagan, Arnaud Durand, and Etienne Grandjean.  On acyclic conjunctive queries and constant delay enumeration.  In Jacques Duparc and Thomas A. Henzinger, editors, Computer Science Logic, 21st International Workshop, CSL 2007, 16th Annual Conference of the EACSL, Lausanne, Switzerland, September 11-15, 2007, Proceedings, volume 4646 of Lecture Notes in Computer Science, pages 208–222. Springer, 2007.  doi:10.1007/978-3-540-74915-8\\_18.
  * [4] Nurzhan Bakibayev, Tomás Kociský, Dan Olteanu, and Jakub Zavodny.  Aggregation and ordering in factorised databases.  Proc. VLDB Endow., 6(14):1990–2001, 2013.  URL: http://www.vldb.org/pvldb/vol6/p1990-zavodny.pdf, doi:10.14778/2556549.2556579.
  * [5] Pablo Barceló, Andreas Pieris, and Miguel Romero.  Semantic optimization in tractable classes of conjunctive queries.  SIGMOD Rec., 46(2):5–17, 2017.  doi:10.1145/3137586.3137588.