# Ontological Queries: Rewriting and Optimization (Extended Version)111This is
an extended and revised version of the paper [1].

Georg Gottlob1,2, Giorgio Orsi1,3, Andreas Pieris1

$~{}^{1}$Department of Computer Science, University of Oxford, UK
$~{}^{2}$Oxford-Man Institute of Quantitative Finance, University of Oxford,
UK
$~{}^{3}$Institute for the Future of Computing, University of Oxford, UK

<EMAIL_ADDRESS>
###### Abstract

Ontological queries are evaluated against an ontology rather than directly on
a database. The evaluation and optimization of such queries is an intriguing
new problem for database research. In this paper we discuss two important
aspects of this problem: query rewriting and query optimization. Query
rewriting consists of the compilation of an ontological query into an
equivalent query against the underlying relational database. The focus here is
on soundness and completeness. We review previous results and present a new
rewriting algorithm for rather general types of ontological constraints. In
particular, we show how a conjunctive query against an ontology can be
compiled into a union of conjunctive queries against the underlying database.
Ontological query optimization, in this context, attempts to improve this
process so to produce possibly small and cost-effective UCQ rewritings for an
input query. We review existing optimization methods, and propose an effective
new method that works for linear Datalog±, a class of Datalog-based rules that
encompasses well-known description logics of the _DL-Lite_ family.

##  1 Introduction

This paper is about ontological query processing, an important new challenge
to database research. We will review existing methods and propose new
algorithms for compiling an ontological query, that is, a query against an
ontology on top of a relational database, into a direct query against this
database, and we will deal with optimization issues related to this process so
as to obtain possibly small and efficient compiled queries. In this section,
we first discuss a number of relevant concepts, and then illustrate query
rewriting and optimization processes in the context of a small but non-trivial
example.

#### Ontologies.

The use of ontologies and ontological reasoning in companies, governmental
organizations, and other enterprises has become widespread in recent years. An
ontology is an explicit specification of a conceptualization of an area of
interest [2], and consists of a formal representation of knowledge as a set of
concepts within a domain, and the relationships between those concepts [3]. To
distinguish an enterprise ontology from a data dictionary, Dave McComb
explicitly refers to the formal semantics of ontologies that enables automated
processing and inferencing, while the interpretation of a data dictionary is
strictly done by humans [4]. Moreover, ontologies have been adopted as high-
level conceptual descriptions of the data contained in data repositories that
are sometimes distributed and heterogeneous in the data models. Due to their
high expressive power, ontologies are also substituting more traditional
conceptual models such as UML class-diagrams and E/R schemata.

#### Description Logics.

Description logics (DLs) are logical languages for expressing and modelling
ontologies. The best known DLs are those underlying the _OWL_
language222http://www.w3.org/TR/owl2-overview/. The main ontological reasoning
and query answering tasks in the complete OWL language, called _OWL Full_ ,
are undecidable. For the most well-known decidable fragments of OWL,
ontological reasoning and query answering is still computationally very hard,
typically 2exptime-complete.

In description logics, the ontological axioms are usually divided into two
sets: The ABox (assertional box), which essentially contains factual knowledge
such as “IBM is a company”, denoted by $\mathit{company}(\mathit{ibm})$, or
“IBM is listed on the NASDAQ”, which could be represented as a fact of the
form $\mathit{list\\_comp}(\mathit{ibm},\mathit{nasdaq})$, and a TBox
(terminological box) which contains axioms and constraints that allow us, on
the one hand, to infer new facts from those given in the ABox, and, on the
other hand, to express restrictions such as keys. For example, a TBox may
contain an axiom stating that for each fact $\mathit{list\\_comp}(X,Y)$, $Y$
must be a financial index, which in DL is expressed as
$\exists\mathit{list\\_comp}^{-}\sqsubseteq\mathit{fin\\_idx}$. If the fact
$\mathit{fin\\_idx}(\mathit{nasdaq})$ is not already present in the ABox, it
can be derived via the above axiom from
$\mathit{list\\_comp}(\mathit{ibm},\mathit{nasdaq})$. Thus, the atomic query
“$q(X)\leftarrow\mathit{fin\\_idx}(X)$” would return $\mathit{nasdaq}$ as one
of the answers. Note that the axiom
$\exists\mathit{list\\_comp}^{-}\sqsubseteq\mathit{fin\\_idx}$, which
corresponds to an inclusion dependency, is enforced by adding new tuples,
rather than just being checked. This is one main difference between
ontological constraints and classical database dependencies. In database
terms, the above axiom is to be interpreted more like a trigger than a
classical constraint.

#### Ontology Based Data Access (OBDA).

We are currently witnessing the marriage of ontological reasoning and database
technology. In fact, this amalgamation consists in the realization of the
obvious idea that ABoxes shall be implemented in form of a relational
database, or even stored in classical RDBMSs. Moreover, very large existing
databases are semantically enriched with ontological constraints. There are a
number of recent commercial systems and experimental prototypes that extend
RDBMSs with the possibility of querying an ontology that is rooted in a
database (for examples, see Section 2). The main problem here is how to couple
these two different types of technology smoothly and efficiently, and this is
also the main theme of the present paper.

One severe obstacle to efficient OBDA is the already mentioned high
computational complexity of query answering with description logics. The
situation clearly worsens when the ABoxes of enterprise ontologies are very
large databases. To tackle this problem, new, lightweight DLs have been
designed, that guarantee polynomial-time data complexity for conjunctive query
answering. This means that based on a fixed TBox, a fixed query can be
answered in polynomial time over variable databases. The best-known and best-
studied examples of such lightweight DLs are the _DL-Lite_ [5] and
$\mathcal{E}\mathcal{L}$ (see, e.g., [6]) families. These languages can be
considered tractable subclasses of OWL. It was convincingly argued that simple
DLs such as DL-Lite or $\mathcal{E}\mathcal{L}$ are sufficient for modelling
an overwhelming number of applications.

More recently, the Datalog± family of description logics was introduced [7, 8,
9, 10]. Its syntax is based on classical first-order logic, more specifically,
on variants of the well-known Datalog language [11]. The basic Datalog± rules
are known as _tuple-generating dependencies_ (TGDs) in the database literature
[12]. Tractable DLs in this framework are guarded Datalog±, which is
noticeably more general than both DL-Lite and $\mathcal{E}\mathcal{L}$, and
the DLs linear Datalog± and sticky-join Datalog±, which both encompass DL-
Lite.

Besides being more expressive than DL-Lite, suitable Datalog± languages offer
a more compact representation of the attributes of concepts and roles, since
description logics are usually restricted to unary and binary predicates only.
Consider, as an example, a relation $\mathit{stock}(\underline{{\sf id}},{\sf
name},{\sf unit}$-${\sf price})$. Representing this relation in DL would
require the introduction of a concept symbol $\mathit{stock}$, and of three
attribute symbols $\mathit{id}$, $\mathit{name}$ and
$\mathit{unit}$-$\mathit{price}$. These entities must be then weaved together
by the TBox formula $\mathit{stock}\sqsubseteq\exists
id\sqcap\exists\mathit{name}\sqcap\exists\mathit{unit}$-$\mathit{price}$.
Datalog± represents the relation in a natural way by means of a ternary
predicate $\mathit{stock}$. In the same way, Datalog± provides a more natural
syntax for many other DL formulae; for example, an inverse role assertion
$r\sqsubseteq s^{-}$ is represented as a (full) TGD $r(X,Y)\rightarrow
s(Y,X)$, while an existential restriction $p\sqsubseteq\exists r.q$ is
represented as a (partial) TGD $p(X)\rightarrow\exists Y\,r(X,Y),q(Y)$.

#### First-Order Rewritability.

Polynomial-time tractability is often considered not to be good enough for
efficient query processing. Ideally, one would like to achieve the same
complexity as for processing SQL queries, or, equivalently, first-order (FO)
queries. An ontology language $\mathcal{L}$ is _first-order rewritable_ if,
for every TBox $\Sigma$ expressed in $\mathcal{L}$ and a query $q$, a first-
order query $q_{\Sigma}$ (called the perfect rewriting) can be constructed
such that, given a database $D$, $q_{\Sigma}$ evaluated over $D$ yields
exactly the same result as $q$ evaluated against $D$ and $\Sigma$. Since
answering first-order queries is in the class ac0 in data complexity [13], it
immediately follows that under FO-rewritable TGDs, query answering is also in
ac0 in data complexity

This notion was first introduced by Calvanese et al. [5] in the concept of
description logics. If a DL guarantees the FO-rewritability of each query
under every TBox, we simply say that the logic is FO-rewritable. FO-
rewritability is a most desirable property since it ensures that the reasoning
process can be largely decoupled from data access. In fact, to answer query
$q$, a separate software can compile $q$ into $q_{\Sigma}$, and then just
submit $q_{\Sigma}$ as a standard SQL query to the DBMS holding $D$, where it
is evaluated and optimized in the usual way.

Excitingly, it was shown that the members of the DL-Lite family, as well as
the slightly more expressive language linear Datalog± are FO-rewritable.
Moreover, even the much more expressive language of sticky-join Datalog± is
FO-rewritable. For these languages, a pair $\langle\Sigma,q\rangle$, where $q$
is a CQ, is rewritten as an SQL expression equivalent to a UCQ $q_{\Sigma}$.
The research challenge we address in this paper is precisely the question of
how to rewrite $\langle\Sigma,q\rangle$ to $q_{\Sigma}$ correctly and
efficiently. Let us illustrate this process by a small, but comprehensive
example.

Consider the following relational schema $\mathcal{R}$ representing financial
information about companies and their stocks:

$\begin{array}[]{rcl}&&\mathit{stock}({\sf id},{\sf name},{\sf unit}$-${\sf
price})\\\ &&\mathit{company}({\sf name},{\sf country},{\sf segment})\\\
&&\mathit{list\\_comp}({\sf stock},{\sf list})\\\ &&\mathit{fin\\_idx}({\sf
name},{\sf type},{\sf ref}$-${\sf mkt})\\\ &&\mathit{stock\\_portf}({\sf
company},{\sf stock},{\sf qty}).\end{array}$

The $\mathit{stock}$ relation contains information about stocks such as the
name, and the price per unit. The relation $\mathit{company}$ contains
information about companies; in particular, the name, the country, and the
market segment of a company. The relation $\mathit{list\\_comp}$ relates a
stock to a financial index (i.e., NASDAQ, FTSE, NIKKEI) represented by the
relation $fin\\_idx$ which, in turn, contains information about the types of
stocks in the index, and the reference market (e.g., London Stock Exchange).
Finally, $\mathit{stock\\_portf}$ relates companies to their stocks along with
an indication of the amount of the investment.

Datalog± provides the necessary expressive power to extend $\mathcal{R}$ with
ontological constraints in an easy and intuitive way. Examples of such
constraints follow:

$\begin{array}[]{rcl}\sigma_{1}&:&\mathit{stock\\_portf(X,Y,Z)}\rightarrow\exists
V\exists W\ \mathit{company(X,V,W)}\\\
\sigma_{2}&:&\mathit{stock\\_portf(X,Y,Z)}\rightarrow\exists V\exists W\
\mathit{stock(Y,V,W)}\\\
\sigma_{3}&:&\mathit{list\\_comp(X,Y)}\rightarrow\exists Z\exists W\
\mathit{fin\\_idx(Y,Z,W)}\\\
\sigma_{4}&:&\mathit{list\\_comp(X,Y)}\rightarrow\exists Z\exists W\
\mathit{stock(X,Z,W)}\\\
\sigma_{5}&:&\mathit{stock\\_portf(X,Y,Z)}\rightarrow\mathit{has\\_stock(Y,X)}\\\
\sigma_{6}&:&\mathit{has\\_stock(X,Y)}\rightarrow\exists Z\
\mathit{stock\\_portf(Y,X,Z)}\\\
\sigma_{7}&:&\mathit{stock(X,Y,Z)}\rightarrow\exists V\exists W\
\mathit{stock\\_portf(V,X,W)}\\\
\sigma_{8}&:&\mathit{stock(X,Y,Z)}\rightarrow\mathit{fin\\_ins(X)}\\\
\sigma_{9}&:&\mathit{company(X,Y,Z)}\rightarrow\mathit{legal\\_person(X)}\\\
\delta_{1}&:&\mathit{legal\\_person(X,Y,Z),fin\\_ins(X,V,W)\rightarrow\bot}.\end{array}$

Figure 1: A (partial) rewriting for the Stock Exchange example.
$q^{[0]}(A,B,C)\leftarrow\mathit{fin\\_ins}(A),\mathit{stock\\_portf}(B,A,D),\mathit{company}(B,E,F),\mathit{list\\_comp}(A,C),\mathit{fin\\_idx}(C,G,H)$
---
$q^{[1]}(A,B,C)\leftarrow\mathit{fin\\_ins}(A),\underline{\mathit{has\\_stock}(A,B)},\mathit{company}(B,E,F),\mathit{list\\_comp}(A,C),\mathit{fin\\_idx}(C,G,H)$
$q^{[2]}(A,B,C)\leftarrow\mathit{fin\\_ins}(A),\mathit{has\\_stock}(A,B),\underline{\mathit{stock\\_portf}(B,E,F)},\mathit{list\\_comp}(A,C),\mathit{fin\\_idx}(C,G,H)$
$q^{[3]}(A,B,C)\leftarrow\underline{\mathit{stock}(A,J,K)},\mathit{has\\_stock}(A,B),\mathit{stock\\_portf}(B,E,F),\mathit{list\\_comp}(A,C),\mathit{fin\\_idx}(C,G,H)$
$\ldots$

The first four TGDs set the “domain” and the “range” of the
$\mathit{stock\\_portf}$ and $\mathit{list\\_comp}$ relations, respectively.
TGDs $\sigma_{5}$ and $\sigma_{6}$ assert that $\mathit{stock\\_portf}$ and
$\mathit{has\\_stock}$ are “inverse relations”, while $\sigma_{7}$ expresses
that each stock must belong to some stock portfolio. TGDs $\sigma_{8}$ and
$\sigma_{9}$ model taxonomic relationships such as the facts that each stock
is a financial instrument, and each company is a legal person. Finally, the
negative constraint $\delta_{1}$ (where $\bot$ denotes the truth constant
$\mathit{false}$) states that legal persons and financial instruments are
disjoint sets.

Consider now the following conjunctive query $q$ asking for all the triples
$\langle a,b,c\rangle$, where $a$ is a financial instrument owned by the
company $b$ and listed on $c$:

$\begin{array}[]{rcl}\mathit{q(A,B,C)}&\leftarrow&\mathit{fin\\_ins}(A),\mathit{stock\\_portf}(B,A,D),\mathit{company}(B,E,F),\\\
&&\mathit{list\\_comp}(A,C),\mathit{fin\\_idx}(C,G,H).\end{array}$

Since $\Sigma=\\{\sigma_{1},\ldots,\sigma_{9}\\}$ is a set of linear TGDs,
i.e., TGDs with single body-atom, query answering under $\Sigma$ is FO-
rewritable. Thus, it is possible to reformulate $\langle\Sigma,q\rangle$ to a
first-order query $q_{\Sigma}$ such that, for every database $D$,
$D\cup\Sigma\models q$ iff $D\models q_{\Sigma}$. A naive rewriting procedure
would use the TGDs of $\Sigma$ as rewriting rules for the atoms in $q$ to
generate all the CQs of the perfect rewriting. Figure 1 shows a (partial)
rewriting for $q$, where the query obtained at the $i$-th step is denoted as
$q^{[i]}$, and the newly introduced atoms are underlined. In particular,
$q^{[0]}$ is the given query $q$, $q^{[1]}$ is obtained from $q^{[0]}$ by
using $\sigma_{6}$, $q^{[2]}$ is obtained from $q^{[1]}$ by applying
$\sigma_{1}$, and $q^{[3]}$ is obtained from $q^{[2]}$ by using $\sigma_{8}$.

The complete perfect rewriting contains more than 200 queries executing more
than 1000 joins. However, by exploiting the set of constraints, it is possible
to eliminate redundant atoms in the generated queries, and thus reduce the
number of the CQs in the rewritten query. For example, in the given query $q$
above it is possible to eliminate the atom $\mathit{fin\\_ins(A)}$ since, due
to the existence of the TGDs $\sigma_{2}$ and $\sigma_{8}$ in $\Sigma$, if the
atom $\mathit{stock\\_portf}(B,A,D)$ is satisfied, then immediately the atom
$\mathit{fin\\_ins(A)}$ is also satisfied. Notice that by eliminating a
redundant atom from a query, we also eliminate all the atoms that are
generated starting from it during the rewriting process. Moreover, due to the
TGD $\sigma_{3}$, if the atom $\mathit{list\\_comp(A,C)}$ in $q$ is satisfied,
then the atom $\mathit{fin\\_idx(C,G,H)}$ is also satisfied, and therefore can
be eliminated. Finally, due to the TGD $\sigma_{1}$, if the atom
$\mathit{stock\\_portf}(B,A,D)$ is satisfied, then the atom
$\mathit{company(B,E,F)}$ is also satisfied, and hence is redundant. The query
that has to be considered as input of the rewriting process is therefore
$q(A,B,C)\leftarrow\mathit{stock\\_portf}(B,A,D),\mathit{list\\_comp}(A,C)$
that produces a perfect rewriting containing the following two queries
executing only two joins:

$\begin{array}[]{rcl}q(A,B,C)&\leftarrow&\mathit{list\\_comp}(A,C),\mathit{stock\\_portf}(B,A,D)\\\
q(A,B,C)&\leftarrow&\mathit{list\\_comp}(A,C),\mathit{has\\_stock}(A,B).\end{array}$

#### Contributions and Roadmap.

After a review of previous work on ontology based data access in the next
section, and some formal definitions and preliminaries in Section 3, we
present a short overview of the Datalog± family in Section 4. We then proceed
with new research results. In Section 5, we propose a new rewriting algorithm
that improves the one stated in [14] by substantially reducing the number of
redundant queries in the perfect rewriting. In Section 6, we present a
polynomial-time optimization strategy based on the early-pruning of redundant
atoms produced during the rewriting process. An implementation and
experimental evaluation of the new method is discussed in Section 7. We also
discuss the relationship between our optimization technique and optimal query
minimization algorithms such as the _chase & back-chase_ algorithm [15]. We
conclude with a brief outlook on further research.

##  2 Ontology Based Data Access

Answering queries under constraints and the related optimization techniques
are important topics in data management beyond the obvious research interest.
In particular, they are profitable opportunities for companies that need to
deliver efficient and effective data management solutions to their customers.
This trend is becoming even more evident as a plethora of robust systems and
APIs for Semantic Web data management proposed in the recent years. These
systems span from open-source solutions such as
Virtuoso333http://virtuoso.openlinksw.com/, Sesame444http://www.openrdf.org/,
RDFSuite [16], KAON555http://kaon.semanticweb.org/ and
Jena666http://jena.sourceforge.net/, to commercial implementations such as the
semantic extensions implemented in Oracle Database 11g R2 [17] and
BigOWLLim777http://www.ontotext.com/owlim/. In this Section we briefly analyze
the systems providing rewriting-based access to databases under ontological
constraints, and we highlight some crucial points that we want to address in
this work.

We first present the class of constraints identified by the members of the DL-
Lite family [5], namely, DL-LiteA, DL-LiteF, and DL-LiteR, underlying the W3C
OWL-QL profile of the OWL language. These constraints correspond to unary and
binary _inclusion dependencies_ combined with a restricted form of _key
constraints_. In order to perform query answering under this class of
constraints, a rewriting algorithm, introduced in [5] and implemented in the
QuOnto system, reformulates the given query into unions of conjunctive
queries. The size of the reformulated query is unnecessarily large due to a
number of reasons. In the first place, _(i)_ basic optimization techniques
such as the identification of the connected components in the body of the
input query, or the computation of any form of query decomposition [18], are
not applied. Moreover, _(ii)_ the fact that the given set of constraints can
be used to identify existential joins in the reformulated query which can be
eliminated is not exploited. Finally, _(iii)_ the factorization step (which is
needed to guarantee completeness) is applied exhaustively, and as a result
many superfluous queries are generated.

Peréz-Urbina et al. [19] proposed an alternative resolution-based rewriting
algorithm, implemented in the Requiem system, that addressed the issue of the
useless factorizations (and therefore of the redundant queries generated due
to this weakness) by directly handling existential quantification through
proper functional terms. The algorithm has then been extended to more
expressive DL languages [19]. In this case the output of the rewriting is a
Datalog program.

Rosati et al. [20] recently proposed a very sophisticated rewriting technique,
implemented in the Presto system, that addresses some of the issues described
above. In particular, _(i)_ the unnecessary existential joins are eliminated
by resorting to the concept of _most-general subsumees_ , which also avoids
the unnecessary factorizations, and _(ii)_ the connectivity of the given query
is checked before executing the algorithm; in case the query is not connected,
Presto splits the query in connected components and rewrites them separately.
Notice that Presto produces a non-recursive Datalog program, and not a union
of conjunctive queries. This allows the “hiding” of the exponential blow-up
inside the rules instead of generating explicitly the disjunctive normal form.
The final rewriting is exponential only in the number of non-eliminable
existential joins, but not in the size of the input query.

The approaches presented above have been proven very effective when applied to
very particular classes of description logic constraints. Following a more
general approach for ontological query answering, Calì et al. [14] presented a
backward-chaining rewriting algorithm which is able to deal with arbitrary
sets of TGDs, providing that the class of TGDs under consideration satisfies
suitable syntactic restrictions that guarantee the termination of the
algorithm. However, this algorithm is inspired by the original QuOnto
algorithm and inherits all its drawbacks.

Despite the possibly exponential number of queries to be constructed, we know
that all such queries are independent from each other, and thus they can be
easily executed in parallel threads and distributed on multiple processors.
Notice that a non-recursive Datalog program is not equally easy to distribute.
Moreover, the optimizations implemented in current DBMS systems for (unions
of) conjunctive queries are much more advanced than those implemented for the
positive existential first-order queries resulting from the translation of a
non-recursive Datalog program into a concrete query language such as SQL. It
is clear that a trade-off between these two approaches must be found in order
to exploit as much as possible the current optimization techniques, while
keeping the size of the rewriting reasonably small in order to make the
execution of it feasible in practice.

A related research field is that of query minimization [21], in particular, in
presence of views and constraints [22, 15]. Given a conjunctive query $q$, and
a set of constraints $\Sigma$, the goal is to find all the minimal equivalent
reformulations of $q$ under the constraints of $\Sigma$. The most interesting
approach in this respect is the chase & back-chase algorithm (C&B) [15],
implemented in the MARS system [23]. The algorithm freezes the atoms of
$\mathit{body}(q)$ and, by considering them as a database $D_{q}$, applies the
following two steps. During the chase-step, the chase of $D_{q}$ w.r.t.
$\Sigma$ is constructed, and then the atoms of $\mathit{chase}(D_{q},\Sigma)$
are considered as the body-atoms of a query $q_{u}$, called the universal
plan. The back-chase step considers all the possible subsets of the atoms of
$\mathit{body}(q_{u})$, starting from those with a single-atom, which are then
considered as the body of a query $q^{\prime}$. Whenever there exists a
containment mapping from $\mathit{body}(q_{u})$ to
$\mathit{chase}(D_{q^{\prime}},\Sigma)$, where $D_{q^{\prime}}$ is the
database obtained by freezing $\mathit{body}(q^{\prime})$, then $q^{\prime}$
is an equivalent reformulation of $q$. Moreover, every time an equivalent
reformulation $q^{\prime}$ is found, the back-chase does not consider any of
the supersets of the atoms of $\mathit{body}(q^{\prime})$ because they will be
automatically implied by the atoms of $q^{\prime}$, and therefore the produced
query would be redundant. This particular exploration strategy guarantees the
minimality of the reformulations. A non-negligible drawback of this approach
is the fact that we need to compute the chase of $D_{q}$ w.r.t. $\Sigma$, and
also the chase for the (exponentially many) databases $D_{q^{\prime}}$ w.r.t
$\Sigma$. Clearly, this makes the procedure computationally expensive.

##  3 Preliminaries

In this section we recall some basics on relational databases, conjunctive
queries, tuple-generating dependencies, and the chase procedure.

###  3.1 Relational Databases and Conjunctive Queries

Consider two pairwise disjoint (infinite) sets of symbols $\Delta_{c}$ and
$\Delta_{z}$ such that: $\Delta_{c}$ is a set of _constants_ (which
constitutes the domain of a database), and $\Delta_{z}$ is a set of _labeled
nulls_ (used as placeholders for unknown values). Different constants
represent different values (_unique name assumption_), while different nulls
may represent the same value. Throughout the paper, we denote by $\mathbf{X}$
sequences of variables $X_{1},\ldots,X_{k}$, where $k\geq 0$, and by $[n]$ the
set $\\{1,\ldots,n\\}$, for any $n\geq 1$.

A _relational schema_ $\mathcal{R}$ (or simply _schema_) is a set of
_relational symbols_ (or _predicate symbols_), each with its associated arity.
A _position_ $r[i]$ (or $\langle r,i\rangle$) is identified by a predicate
$r\in\mathcal{R}$ and its $i$-th argument. A _term_ $t$ is a constant, labeled
null, or variable. An _atomic formula_ (or simply _atom_) has the form
$r(t_{1},\ldots,t_{n})$, where $r\in\mathcal{R}$ has arity $n$, and
$t_{1},\ldots,t_{n}$ are terms. Conjunctions of atoms are often identified
with the sets of their atoms.

A _substitution_ from one set of symbols $S_{1}$ to another set of symbols
$S_{2}$ is a function $h:S_{1}\rightarrow S_{2}$. A _homomorphism_ from a set
of atoms $A_{1}$ to a set of atoms $A_{2}$, both over the same schema
$\mathcal{R}$, is a substitution $h$ from the set of terms of $A_{1}$ to the
set of terms of $A_{2}$ such that: (i) if $t\in\Delta_{c}$, then $h(t)=t$, and
(ii) if $r(t_{1},\ldots,t_{n})$ is in $A_{1}$, then
$h(r(t_{1},\ldots,t_{n}))=r(h(t_{1}),\ldots,h(t_{n}))$ is in $A_{2}$. The
notion of homomorphism naturally extends to conjunctions of atoms.

A _relational instance_ (or simply _instance_) $I$ for a schema $\mathcal{R}$
is a (possibly infinite) set of atoms of the form $r({\bf t})$, where
$r\in\mathcal{R}$ has arity $n$ and ${\bf
t}\in(\Delta_{c}\cup\Delta_{z})^{n}$. A _database_ is a finite relational
instance. A _conjunctive query_ (CQ) $q$ of arity $n$ over a schema
$\mathcal{R}$ is a formula of the form
$q(\mathbf{X})\leftarrow\phi(\mathbf{X},\mathbf{Y})$, where
$\phi(\mathbf{X},\mathbf{Y})$ is a conjunction of atoms over $\mathcal{R}$,
and $q$ is an $n$-ary predicate. $\phi(\mathbf{X},\mathbf{Y})$ is called the
body of $q$, denoted as $body(q)$, and $q(\mathbf{X})$ is the head of $q$,
denoted as $head(q)$. A Boolean conjunctive query (BCQ) is a CQ of arity zero.
The answer to a CQ $q$ of arity $n$ over an instance $I$, denoted as $q(I)$,
is the set of all $n$-tuples $\mathbf{t}\in(\Delta_{c})^{n}$ for which there
exists a homomorphism
$h:\mathbf{X}\cup\mathbf{Y}\rightarrow\Delta_{c}\cup\Delta_{z}$ such that
$h(\phi(\mathbf{X},\mathbf{Y}))\subseteq I$ and $h(\mathbf{X})=\mathbf{t}$. A
BCQ has only the empty tuple $\langle\rangle$ as possible answer, in which
case it is said that has positive answer. Formally, a BCQ has _positive_
answer over $I$, denoted as $I\models q$, iff $\langle\rangle\in q(I)$. A
_union of CQs_ (UCQ) $Q$ of arity $n$ is a set of CQs, where each $q\in Q$ has
the same arity $n$ and uses the same predicate symbol in the head. The answer
to $Q$ over an instance $I$, denoted as $Q(I)$, is defined as the set of
tuples $\\{\mathbf{t}~{}|~{}\textrm{there~{}exists~{}}q\in
Q\textrm{~{}such~{}that~{}}\mathbf{t}\in q(I)\\}$.

###  3.2 Tuple-Generating Dependencies

A tuple-generating dependency (TGD) $\sigma$ over a schema $\mathcal{R}$ is a
first-order formula $\forall{\bf X}\forall{\bf Y}\phi({\bf X},{\bf
Y})\rightarrow\exists\mathbf{Z}\,\psi({\bf X},{\bf Z})$, where
$\phi(\mathbf{X},\mathbf{Y})$ and $\psi(\mathbf{X},\mathbf{Z})$ are
conjunctions of atoms over $\mathcal{R}$, called the body and the head of
$\sigma$, denoted as $\mathit{body}(\sigma)$ and $\mathit{head}(\sigma)$,
respectively. Henceforth, to avoid notational clutter, we will omit the
universal quantifiers in TGDs. Such $\sigma$ is satisfied by an instance $I$
for $\mathcal{R}$ iff, whenever there exists a homomorphism $h$ such that
$h(\phi(\mathbf{X},\mathbf{Y}))\subseteq I$, there exists an extension
$h^{\prime}$ of $h$ (i.e., $h^{\prime}\supseteq h$) such that
$h^{\prime}(\psi(\mathbf{X},\mathbf{Z}))\subseteq I$.

We now define the notion of _query answering_ under TGDs. Given a database $D$
for $\mathcal{R}$, and a set $\Sigma$ of TGDs over $\mathcal{R}$, the _models_
of $D$ w.r.t. $\Sigma$, denoted as $\mathit{mods}(D,\Sigma)$, is the set of
all instances $I$ such that $I\models D\cup\Sigma$, which means that
$I\supseteq D$ and $I$ satisfies $\Sigma$. The _answer_ to a CQ $q$ w.r.t. $D$
and $\Sigma$, denoted as $\mathit{ans}(q,D,\Sigma)$, is the set
$\\{\mathbf{t}~{}|~{}\mathbf{t}\in
q(I){\rm~{}for~{}each~{}}I\in\mathit{mods}(D,\Sigma)\\}$. The _answer_ to a
BCQ $q$ w.r.t. $D$ and $\Sigma$ is _positive_ , denoted as $D\cup\Sigma\models
q$, iff $\mathit{ans}(q,D,\Sigma)\neq\varnothing$. Note that query answering
under general TGDs is undecidable [24], even when the schema and the set of
TGDs are fixed [25]. We recall that the two problems of answering CQs and BCQs
under TGDs are equivalent [21, 26]. Roughly speaking, we can enumerate the
polynomially many tuples of constants which are possible answers to $q$, and
then, instead of answering the given query $q$, we answer the polynomially
many BCQs that we obtain by replacing the variables in the body of $q$ with
the appropriate constants. A certain tuple $\mathbf{t}$ of constants is in the
answer of $q$ iff the answer to the BCQ that we obtain from $\mathbf{t}$ is
positive. Henceforth, we thus focus only on the BCQ answering problem.

###  3.3 The TGD Chase

The _chase procedure_ (or simply _chase_) is a fundamental algorithmic tool
introduced for checking implication of dependencies [27], and later for
checking query containment [28]. Informally, the chase is a process of
repairing a database w.r.t. a set of dependencies so that the resulted
database satisfies the dependencies. We shall use the term chase
interchangeably for both the procedure and its result. The chase works on an
instance through the so-called TGD _chase rule_.

TGD Chase Rule: Consider a database $D$ for a schema $\mathcal{R}$, and a TGD
$\sigma:\phi(\mathbf{X},\mathbf{Y})\rightarrow\exists\mathbf{Z}\,\psi(\mathbf{X},\mathbf{Z})$
over $\mathcal{R}$. If $\sigma$ is applicable to $D$, i.e., there exists a
homomorphism $h$ such that $h(\phi(\mathbf{X},\mathbf{Y}))\subseteq D$ then:
_(i)_ define $h^{\prime}\supseteq h$ such that $h^{\prime}(Z_{i})=z_{i}$, for
each $Z_{i}\in\mathbf{Z}$, where $z_{i}\in\Delta_{z}$ is a “fresh” labeled
null not introduced before, and _(ii)_ add to $D$ the set of atoms in
$h^{\prime}(\psi(\mathbf{X},\mathbf{Z}))$, if not already in $D$.

Given a database $D$ and a set of TGDs $\Sigma$, the chase algorithm for $D$
and $\Sigma$ consists of an exhaustive application of the TGD chase rule in a
breadth-first fashion, which leads as result to a (possibly infinite) chase
for $D$ and $\Sigma$, denoted as $\mathit{chase}(D,\Sigma)$. For the formal
definition of the chase algorithm we refer the reader to [8].

The (possibly infinite) chase for $D$ and $\Sigma$ is a _universal model_ of
$D$ w.r.t. $\Sigma$, i.e., for each instance $I\in\mathit{mods}(D,\Sigma)$,
there exists a homomorphism from $\mathit{chase}(D,\Sigma)$ to $I$ [26, 29].
Using this fact it can be shown that $D\cup\Sigma\models q$ iff
$\mathit{chase}(D,\Sigma)\models q$, for every BCQ $q$.

##  4 The Datalog± Family

In this section we present the main Datalog± languages under which query
answering is decidable, and (almost in all cases) also tractable in data
complexity.

###  4.1 Decidability Paradigms

We first discuss the three main paradigms for ensuring decidability of query
answering, namely, chase termination, guardedness and stickiness.

#### Chase Termination.

In this case the chase always terminates and produces a finite universal model
$U$. Thus, given a query we just need to evaluate it over the finite database
$U$. The most notable syntactic restriction of TGDs guaranteeing chase
termination is _weak-acyclicity_ , which is defined by means of a graph-based
condition, for which we refer the reader to the landmark paper [29]. Roughly
speaking, in the chase constructed under a weakly-acyclic set of TGDs over a
schema $\mathcal{R}$, only a finite number of distinct values can appear at
any position of $\mathcal{R}$, and thus after finitely many steps the chase
procedure terminates. It is known that query answering under a weakly-acyclic
set of TGDs is ptime-complete [29] and 2exptime-complete [10] in data and
combined complexity, respectively. More general syntactic restrictions that
guarantee chase termination were proposed in [26] and [30].

#### Guardedness.

_Guarded_ TGDs, introduced and studied in [25], have an atom in their body,
called the _guard_ , that contains all the universally quantified variables.
For example, the TGD $r(X,Y),s(X,Y,Z)\rightarrow\exists Ws(Z,X,W)$ is guarded
via the guard atom $s(X,Y,Z)$, while the TGD $r(X,Y),r(Y,Z)\rightarrow r(X,Z)$
is not. Decidability of query answering follows from the fact that the chase
constructed under a set of guarded TGDs has the bounded treewidth property,
i.e., is a “tree-like” structure. The data and combined complexity of query
answering under a set of guarded TGDs is ptime-complete [7] and 2exptime-
complete [25], respectively.

_Linear_ TGDs, proposed in [7], is a FO-rewritable variant of guarded TGDs. A
TGD is linear iff it contains only one atom in its body. Obviously a linear
TGD is trivially guarded since the singleton body-atom is automatically a
guard. Linear TGDs are more expressive than the well-known class of inclusion
dependencies. Query answering under linear TGDs is in the highly tractable
class ac0 in data complexity [7]. The same problem is pspace-complete in
combined complexity; this result is immediately implied by results in [28].

An expressive class, which forms a generalization of guarded TGDs, is the
class of _weakly-guarded_ sets of TGDs introduced in [25]. Intuitively
speaking, a set $\Sigma$ of TGDs is weakly-guarded iff in the body of each TGD
of $\Sigma$ there exists an atom, called the _weak-guard_ , that contains all
the universally quantified variables that appear only at positions where a
“fresh” null of $\Delta_{z}$ can appear during the construction of the chase.
Query answering under a weakly-guarded set of TGDs is exptime-complete [25]
and 2exptime-complete [25] in data and combined complexity, respectively.

#### Stickiness.

In this paragraph we present a Datalog± language (and its extensions), which
hinges on a paradigm that is very different from guardedness. _Sticky_ sets of
TGDs are defined formally by an efficiently testable condition involving
variable-marking [9]. In what follows we just give an intuitive definition of
this class. For every database $D$, assume that during the construction of
chase of $D$ under a sticky set of TGDs, we apply a TGD $\sigma\in\Sigma$ that
has a variable $V$ appearing more than once in its body; assume also that $V$
maps (via homomorphism) on the symbol $z$, and that by virtue of this
application the atom $\underline{a}$ is introduced. In this case, for each
atom $\underline{b}$ in $\mathit{body}(\sigma)$, we say that $\underline{a}$
is _derived_ from $\underline{b}$. Then, we have that $z$ appears in
$\underline{a}$ and in all atoms resulting from some chase derivation sequence
starting from $\underline{a}$, “sticking” to them (hence the name “sticky”
sets of TGDs). Interestingly, sticky sets of TGDs are FO-rewritable, and thus
query answering is feasible in ac0 in data complexity [9]. Combined complexity
of query answering is known to be exptime-complete [9].

In [10] the FO-rewritable class of _sticky-join_ sets of TGDs, that captures
both linear TGDs and sticky sets of TGDs, is introduced. Similarly to sticky
sets of TGDs, sticky-join sets are defined formally by a testable condition
based on variable-marking. However, this variable-marking procedure is more
sophisticated than the one used for sticky sets, and due to this fact the
problem of identifying sticky-join sets of TGDs is harder than the one of
identifying sticky sets. In particular, given a set $\Sigma$ of TGDs, we can
decide in ptime whether $\Sigma$ is sticky, while the problem whether $\Sigma$
is sticky-join is pspace-complete. Note that the data and combined complexity
of query answering under sticky and sticky-join sets of TGDs coincide.

###  4.2 Additional Features

In this subsection we briefly discuss how the languages presented above can be
combined with negative constraints and key dependencies, without altering the
complexity of query answering.

#### Negative Constraints.

A _negative constraint_ (NC) $\nu$ over a schema $\mathcal{R}$ is a first-
order formula $\forall{\bf X}\,\phi({\bf X})\rightarrow\bot$, where $\bot$
denotes the truth constant false. NCs are vital when representing ontologies
(see, e.g., [7, 9]), as well as conceptual schemas such as Entity-Relationship
diagrams (see, e.g., [31, 32]). With NCs we can assert, for example, that
students and professors are disjoint sets: $\forall
X\mathit{student}(X),\mathit{professor}(X)\rightarrow\bot$. Also, we can state
that a student cannot be the leader of a research group: $\forall X\forall
Y\mathit{student}(X),\mathit{leads}(X,Y)\rightarrow\bot$.

It is known that checking NCs is tantamount to query answering [7]. In
particular, given an instance $I$, a set $\Sigma_{\bot}$ of NCs, and a set
$\Sigma$ of TGDs, for each NC $\nu$ of the form
$\forall\mathbf{X}\,\phi(\mathbf{X})\rightarrow\bot$, we answer the BCQ
$q_{\nu}()\leftarrow\phi(\mathbf{X})$. If at least one of such queries answers
positively, then $I\cup\Sigma\cup\Sigma_{\bot}\models\bot$ (i.e., the theory
is inconsistent), and therefore $I\cup\Sigma\cup\Sigma_{\bot}\models q$, for
every BCQ $q$; otherwise, given a BCQ $q$, we have
$I\cup\Sigma\cup\Sigma_{\bot}\models q$ iff $I\cup\Sigma\models q$, i.e., we
can answer $q$ by ignoring the set of NCs.

#### Key Dependencies.

It is well-known that the interaction of general TGDs and key dependencies
(KDs) leads to undecidability of query answering [33]; we assume that the
reader is familiar with the notion of KD (see, e.g., [34]). Thus, the classes
of TGDs presented above cannot be combined arbitrarily with KDs. Suitable
syntactic restrictions are needed in order to ensure decidability of query
answering.

A crucial concept towards this direction is separability [35], which
formulates a controlled interaction of TGDs and KDs. Formally speaking, a set
$\Sigma=\Sigma_{T}\cup\Sigma_{K}$ over a schema $\mathcal{R}$, where
$\Sigma_{T}$ and $\Sigma_{K}$ are sets of TGDs and KDs, respectively, is
_separable_ iff for every instance $I$ for $\mathcal{R}$, either $I$ violates
$\Sigma_{K}$, or for every BCQ $q$ over $\mathcal{R}$, $I\cup\Sigma\models q$
iff $I\cup\Sigma_{T}\models q$. Notice that separability is a semantic notion.
A sufficient syntactic criterion for separability of TGDs and KDs is given in
[7]; TGDs and KDs satisfying the criterion are called _non-conflicting_.

Obviously, in case of non-conflicting sets of TGDs and KDs, we just need to
perform a preliminary check whether the given instance satisfies the KDs, and
if this is the case, then we eliminate them, and proceed by considering only
the set of TGDs. This preliminary check can be done using negative
constraints. For example, to check whether the KD $\mathit{key}(r)=\\{1\\}$,
stating that the first attribute of the binary relation $r$ is a key
attribute, is satisfied by the database $D$, we just need to check whether the
database $D_{\neq}$ obtained by adding to $D$ the set of atoms
$\\{\mathit{neq}(a,b)~{}|~{}a\neq
b,\textrm{~{}and~{}}a,b\textrm{~{}are~{}constants~{}occurring~{}in~{}}D\\}$,
where $\mathit{neq}$ is an auxiliary predicate, satisfies the negative
constraint $r(X,Y),r(X,Z),\mathit{neq}(Y,Z)\rightarrow\bot$. The atom
$\mathit{neq}(a,b)$ implies that $a$ and $b$ are different constants. Since,
as already mentioned, checking NCs is tantamount to query answering, we
immediately get that the complexity of query answering under non-conflicting
sets of TGDs and KDs is the same as in the case of TGDs only.

Interestingly, by combining non-conflicting linear (or sticky) sets of TGDs
and KDs with NCs, we get strictly more expressive formalisms than the most
widely-adopted tractable ontology languages, in particular DL-LiteA, DL-LiteF
and DL-LiteR, without loosing FO-rewritability, and consequently high
tractability of query answering in data complexity. For more details, we refer
the interested reader to [7, 9].

##  5 Datalog± for OBDA

In this section we consider the problem of BCQ answering under the FO-
rewritable members of the Datalog± family, namely, linear, sticky and sticky-
join sets of TGDs. Given a BCQ $q$ and a set $\Sigma$ of TGDs, the actual
computation of the rewriting is done by applying a backward-chaining
resolution procedure using the rules of $\Sigma$ as rewriting rules. Our
algorithm optimizes the algorithm presented in [14] by greatly reducing the
number of BCQs in the rewriting, and therefore improves the overall
performance of query answering. Before going into the details of the rewriting
algorithm, we first give some useful notions.

A set of atoms $A=\\{\underline{a}_{1},\ldots,\underline{a}_{n}\\}$, where
$n\geqslant 2$, _unifies_ if there exists a substitution $\gamma$, called
_unifier_ for $A$, such that
$\gamma(\underline{a}_{1})=\ldots=\gamma(\underline{a}_{n})$. A _most general
unifier (MGU)_ for $A$ is a unifier for $A$, denoted as $\gamma_{A}$, such
that for each other unifier $\gamma$ for $A$, there exists a substitution
$\gamma^{\prime}$ such that $\gamma=\gamma^{\prime}\circ\gamma_{A}$. Notice
that if a set of atoms unify, then there exists a MGU. Furthermore, the MGU
for a set of atoms is unique (modulo variable renaming). The MGU for a
singleton set $\\{\underline{a}\\}$ is defined as the identity substitution on
the set of terms that occur in $\underline{a}$.

Let us now give some auxiliary results which will allow us to simplify our
later technical definitions and proofs. The first such lemma states that we
can restrict our attention on TGDs that have only one head-atom.

###### Lemma 1

BCQ answering under (general) TGDs and BCQ answering under TGDs with just one
head-atom are logspace-equivalent problems.

Proof. It suffices to show that BCQ answering under (general) TGDs can be
reduced in logspace to BCQ answering under TGDs with just one head-atom.
Consider a BCQ $q$ over a schema $\mathcal{R}$, a database $D$ for
$\mathcal{R}$, and a set $\Sigma$ of TGDs over $\mathcal{R}$. We construct
$\Sigma^{\prime}$ from $\Sigma$ by applying the following procedure. For each
TGD $\sigma\in\Sigma$, where
$\mathit{head}(\sigma)=\\{\underline{a}_{1},\ldots,\underline{a}_{k}\\}$ and
$\mathbf{X}$ is the set of variables that occur in $\mathit{head}(\sigma)$,
replace $\sigma$ with the following set of TGDs:

$\begin{array}[]{rcl}\mathit{body}(\sigma)&\rightarrow&r_{\sigma}(\mathbf{X}),\\\
r_{\sigma}(\mathbf{X})&\rightarrow&\underline{a}_{1},\\\
r_{\sigma}(\mathbf{X})&\rightarrow&\underline{a}_{2},\\\ &\vdots&\\\
r_{\sigma}(\mathbf{X})&\rightarrow&\underline{a}_{k},\end{array}$

where $r_{\sigma}$ is an auxiliary predicate not occurring in $\mathcal{R}$
having the same arity as the number of variables in $\mathbf{X}$. It is not
difficult to see that the above construction is feasible in logspace. By
construction, except for the atoms with an auxiliary predicate,
$\mathit{chase}(D,\Sigma)$ and $\mathit{chase}(D,\Sigma^{\prime})$ coincide.
The auxiliary predicates, being introduced only during the above
transformation, do not match any predicate symbol in $q$, and hence
$\mathit{chase}(D,\Sigma)\models q$ iff
$\mathit{chase}(D,\Sigma^{\prime})\models q$, or, equivalently,
$D\cup\Sigma\models q$ iff $D\cup\Sigma^{\prime}\models q^{\prime}$.

The next lemma implies that we can restrict our attention on TGDs that have
only one existentially quantified variable which occurs only once.

###### Lemma 2

BCQ answering under (general) TGDs and BCQ answering under TGDs with at most
one existentially quantified variable that occurs only once are logspace-
equivalent problems.

Proof. It suffices to show that BCQ answering under (general) TGDs can be
reduced in logspace to BCQ answering under TGDs that have at most one
existentially quantified variable which occurs only once. Consider a BCQ $q$
over a schema $\mathcal{R}$, a database $D$ for $\mathcal{R}$, and a set
$\Sigma$ of TGDs over $\mathcal{R}$. We construct $\Sigma^{\prime}$ from
$\Sigma$ by applying the following procedure. For each TGD $\sigma\in\Sigma$,
where $\\{X_{1},\ldots,X_{n}\\}$, for $n\geqslant 1$, is the set of variables
that occur both in $\mathit{body}(\sigma)$ and $\mathit{head}(\sigma)$, and
$\\{Z_{1},\ldots,Z_{m}\\}$, for $m>1$, is the set of the existentially
quantified variables of $\sigma$, replace $\sigma$ with the following set of
TGDs:

$\begin{array}[]{rcl}\mathit{body}(\sigma)&\rightarrow&\exists
Z_{1}\,r_{\sigma}^{1}(X_{1},\ldots,X_{n},Z_{1}),\\\
r_{\sigma}^{1}(X_{1},\ldots,X_{n},Z_{1})&\rightarrow&\exists
Z_{2}\,r_{\sigma}^{2}(X_{1},\ldots,X_{n},Z_{1},Z_{2}),\\\ &\vdots&\\\
r_{\sigma}^{m-1}(X_{1},\ldots,X_{n},Z_{1},\ldots,Z_{m-1})&\rightarrow&\exists
Z_{m}\,r_{\sigma}^{m}(X_{1},\ldots,X_{n},Z_{1},\ldots,Z_{m}),\\\
r_{\sigma}^{m}(X_{1},\ldots,X_{n},Z_{1},\ldots,Z_{m})&\rightarrow&\mathit{head}(\sigma),\end{array}$

where $r_{\sigma}^{i}$ is an auxiliary predicate of arity $n+i$, for each
$i\in[m]$. It is easy to see that the above procedure can be carried out in
logspace. By construction, except for the atoms with an auxiliary predicate,
$\mathit{chase}(D,\Sigma)$ and $\mathit{chase}(D,\Sigma^{\prime})$ are the
same (modulo bijective variable renaming). The auxiliary predicates, being
introduced only during the above construction, do not match any predicate
symbol in $q$, and hence $\mathit{chase}(D,\Sigma)\models q$ iff
$\mathit{chase}(D,\Sigma^{\prime})\models q$, or, equivalently,
$D\cup\Sigma\models q$ iff $D\cup\Sigma^{\prime}\models q$.

Since the transformations given above preserve the syntactic condition of
linear, sticky and sticky-join sets of TGDs, henceforth we assume w.l.o.g.
that every TGD has just one atom in its head which contains only one
existentially quantified variable that occurs only once. In the rest of the
paper, for notational convenience, given a TGD $\sigma$, we denote by
$\pi_{\sigma}$ the position in $\mathit{head}(\sigma)$ at which the
existentially quantified variable occurs.

We now give the notion of _applicability_ of a TGD to a set of body-atoms of a
query. Let us assume w.l.o.g that the variables that appear in the query, and
those that appear in the TGD, constitute two disjoint sets. Given a BCQ $q$, a
variable is called _shared_ in $q$ if it occurs more than once in
$\mathit{body}(q)$. Notice that in the case of (non-Boolean) CQs, a variable
is shared in $q$ if it occurs more than once in $q$ (considering also the head
of $q$ and not just its body).

######  Definition 1 (Applicability)

Consider a BCQ $q$ over a schema $\mathcal{R}$, and a TGD $\sigma$ over
$\mathcal{R}$. Given a set of atoms $A\subseteq\mathit{body}(q)$ that unifies,
we say that $\sigma$ is _applicable_ to $A$ if the following conditions are
satisfied: (i) the set $A\cup\\{\mathit{head}(\sigma)\\}$ unifies, and (ii)
for each $\underline{a}\in A$, if the term at position $\pi$ in
$\underline{a}$ is either a constant or a shared variable in $q$, then
$\pi\neq\pi_{\sigma}$.

Let us now introduce the notion of _factorizability_ which, as we explain
below, makes one of the main differences between our algorithm and the one
presented in [14], due to which a perfect rewriting with less BCQs is
obtained.

######  Definition 2 (Factorizability)

Consider a BCQ $q$ over a schema $\mathcal{R}$, and a TGD $\sigma$ over
$\mathcal{R}$ which contains an existentially quantified variable. A set of
atoms $A\subseteq\mathit{body}(q)$, where $|A|\geqslant 2$, that unifies is
_factorizable_ w.r.t. $\sigma$ if there exists a variable $V$ that occurs in
every atom of $S$ only at position $\pi_{\sigma}$, and also $V$ does not occur
in $\mathit{body}(q)\setminus S$.

It is important to clarify that in the case of (non-Boolean) CQs, the notion
of factorizability is defined as above, except that the variable $V$ does not
occur in $(\\{\mathit{head}(\sigma)\\}\cup\mathit{body}(\sigma))\setminus S$.

######  Example 1 (Factorization)

Consider the BCQs

$\begin{array}[]{rcl}q_{1}&:&q()\,\leftarrow\,\underbrace{t(A,B,C),t(A,E,C)}_{S_{1}}\\\
q_{2}&:&q()\,\leftarrow\,s(C),\underbrace{t(A,B,C),t(A,E,C)}_{S_{2}}\\\
q_{3}&:&q()\,\leftarrow\,\underbrace{t(A,B,C),t(A,C,C)}_{S_{3}}\end{array}$

and the TGD $\sigma:s(X),r(X,Y)\,\rightarrow\,\exists Z\,t(X,Y,Z).$ Clearly,
$S_{1}$ is factorizable w.r.t. $\sigma$ since the substitution
$\\{E\rightarrow B\\}$ is a unifier for $S_{1}$, and also $C$ appears in both
atoms of $S_{1}$ only at position $\pi_{\sigma}$. The factorization results in
the query $q()\leftarrow t(A,B,C)$; notice that $\sigma$ is not applicable to
$S_{1}$, but it is applicable to $\\{t(A,B,C)\\}$. On the contrary, despite
the fact that $S_{2}$ unifies, it is not factorizable w.r.t. $\sigma$ since
$C$ occurs also in $\mathit{body}(q_{2})\setminus S_{2}$. Finally, even if
$S_{3}$ unifies, it is not factorizable w.r.t. $\sigma$ since $C$ appears in
$S_{3}$, not only at position $\pi_{\sigma}$, but also at position $t[2]$.

We are now ready to describe the algorithm TGD-rewrite, depicted in Algorithm
1, which is based on the rewriting algorithm presented in [14]. The perfect
rewriting of a BCQ $q$ w.r.t. a set of TGDs $\Sigma$ is computed by
exhaustively applying (i.e., until a fixpoint is reached) two steps:
_factorization_ and _rewriting_.

Input: a BCQ $q$ over a schema $\mathcal{R}$, a set $\Sigma$ of TGDs over
$\mathcal{R}$

Output: the FO-rewriting $Q_{\textsc{fin}}$ of $q$ w.r.t. $\Sigma$

$Q_{\textsc{rew}}:=\\{\langle q,1\rangle\\}$;

repeat

$Q_{\textsc{temp}}:=Q_{\textsc{rew}}$;

foreach  _$\\{\langle q,x\rangle\\}\in Q_{\textsc{temp}}$ , where
$x\in\\{0,1\\}$,_ do

/* factorization step */

foreach  _$\sigma\in\Sigma$_ do

$q^{\prime}:=\mathit{factorize}(q,\sigma)$;

if  _$\mathit{notExists}(\langle q^{\prime},y\rangle,Q_{\textsc{rew}})$ ,
where $y\in\\{0,1\\}$,_ then

$Q_{\textsc{rew}}:=Q_{\textsc{rew}}\cup\\{\langle q^{\prime},0\rangle\\}$;

/* rewriting step */

foreach  _$A\subseteq\mathit{body}(q)$_ do

foreach  _$\sigma\in\Sigma$_ do

if  _$\mathit{isApplicable}(\sigma,A,q)$_ then

$q^{\prime}:=\gamma_{A\cup\\{\mathit{head}(\sigma)\\}}(q[A/\mathit{body}(\sigma)])$;

if  _$\mathit{notExists}(\langle q^{\prime},1\rangle,Q_{\textsc{rew}})$_ then

$Q_{\textsc{rew}}:=Q_{\textsc{rew}}\cup\\{\langle q^{\prime},1\rangle\\}$;

until  _$Q_{\textsc{temp}}=Q_{\textsc{rew}}$_ ;

$Q_{\textsc{fin}}:=\\{q~{}|~{}\langle q,x\rangle\in
Q_{\textsc{rew}}\textrm{~{}and~{}}x=1\\}$;

return _$Q_{\textsc{fin}}$_

Algorithm 1 The algorithm TGD-rewrite

Factorization Step. The function $\mathit{factorize}(q,\sigma)$, providing
that there exists a subset of $\mathit{body}(q)$ which is factorizable w.r.t.
$\sigma$ (otherwise, the query $q$ is returned), first selects such a set
$S\subseteq\mathit{body}(q)$. Then, the query $q^{\prime}$ is constructed by
applying the MGU $\gamma_{S}$ for $S$ on $q$. Providing that there is no pair
$\langle q^{\prime\prime},y\rangle$, where $y\in\\{0,1\\}$, in
$Q_{\textsc{rew}}$ such that $q^{\prime}$ and $q^{\prime\prime}$ are the same
(modulo bijective variable renaming), the pair $\langle q^{\prime},0\rangle$
is added to $Q_{\textsc{rew}}$; the label $0$ keeps track of the queries
generated by the factorization step that must be excluded from the final
rewriting. This is carried out by the $\mathit{notExists}$ function.

Rewriting Step. If there exists a pair $\langle q,y\rangle$ and a TGD
$\sigma\in\Sigma$ which is applicable to a set of atoms
$A\subseteq\mathit{body}(q)$, then the algorithm constructs a new query
$q^{\prime}=\gamma_{A\cup\\{\mathit{head}(\sigma)\\}}(q[A/\mathit{body}(\sigma)])$,
that is, the BCQ obtained from $q$ by replacing $A$ with
$\mathit{body}(\sigma)$ and then applying the MGU for the set
$A\cup\\{\mathit{head}(\sigma)\\}$. Providing that there is no pair $\langle
q^{\prime\prime},1\rangle$ in $Q_{\textsc{rew}}$ such that $q^{\prime}$ and
$q^{\prime\prime}$ are the same (modulo bijective variable renaming), the pair
$\langle q^{\prime},1\rangle$ is added to $Q_{\textsc{rew}}$; the label $1$
keeps track of the queries generated by the rewriting step which will be the
final rewriting.

######  Example 2 (Rewriting)

Consider the set $\Sigma$ of TGDs

$\begin{array}[]{rcl}\sigma_{1}&:&s(X)\,\rightarrow\exists Z\ \,t(X,X,Z)\\\
\sigma_{2}&:&t(X,Y,Z)\,\rightarrow\,r(Y,Z)\end{array}$

and the query $q()\leftarrow t(A,B,C),r(B,C).$ TGD-rewrite first applies
$\sigma_{2}$ to $\\{r(B,C)\\}$ since $\sigma_{1}$ is not applicable. The query
$q_{1}:q()\leftarrow t(A,B,C),t(V^{1},B,C)$ is produced. Clearly,
$\mathit{body}(q_{1})$ is factorizable w.r.t. $\sigma_{1}$ and the query
$q_{2}:q()\leftarrow t(A,B,C)$ is obtained. Now, $\sigma_{1}$ is applicable to
$\\{t(A,B,C)\\}$ and the query $q_{3}:q()\leftarrow s(A)$ is obtained. The
perfect rewriting constructed by the algorithm is the set
$\\{q,q_{1},q_{3}\\}$.

The next example shows that dropping the applicability condition, then TGD-
rewrite may produce unsound rewritings.

######  Example 3 (Loss of soundness)

Suppose that we ignore the applicability condition during the rewriting
process. Consider the set $\Sigma$ of TGDs given in Example 2, and also the
BCQ $q_{1}:q()\leftarrow t(A,B,c)$, where $c$ is a constant of $\Delta_{c}$. A
BCQ $q^{\prime}$ of the form $q()\leftarrow s(V)$ is obtained, where the
information about the constant $c$ is lost. Consider now the database
$D=\\{s(b),t(a,b,d)\\}$ for $\mathcal{R}$. The query $q^{\prime}$ maps to the
atom $s(b)$ which implies that $D\models q^{\prime}$. However, the original
query $q$ does not map to $\mathit{chase}(D,\Sigma)$, and thus
$D\cup\Sigma\not\models q$. Therefore, any rewriting containing $q^{\prime}$
is not a sound rewriting of $q$ given $\Sigma$. Consider now the query
$q^{\prime\prime}:q()\leftarrow t(A,B,B)$. The same query $q^{\prime}$ mapping
to the atom $s(b)$ of $D$ is obtained. However, during the construction of
$\mathit{chase}(D,\Sigma)$ it is not possible to get an atom of the form
$t(X,Y,Y)$, where at positions $t[2]$ and $t[3]$ the same value occurs. This
implies that there is no homomorphism that maps $q$ to
$\mathit{chase}(D,\Sigma)$, and hence $D\cup\Sigma\not\models q$. Therefore,
any rewriting containing $q^{\prime}$ is again unsound.

The applicability condition may prevent the generation of queries that are
vital to guarantee completeness of the rewritten query, as shown by the
following example. This is exactly the reason why the factorization step is
also needed.

######  Example 4 (Loss of completeness)

Consider the set $\Sigma$ of TGDs

$\begin{array}[]{rcl}\sigma_{1}&:&p(X)\,\rightarrow\,\exists Y\,t(X,Y)\\\
\sigma_{2}&:&t(X,Y)\,\rightarrow\,s(Y)\end{array}$

and the query $q:q()\leftarrow t(A,B),s(B).$ The only viable strategy in this
case is to apply $\sigma_{2}$ to $\\{s(B)\\}$, since $\sigma_{1}$ is not
applicable to $\\{t(A,B)\\}$ due to the shared variable $B$. The query that we
obtain is $q^{\prime}:q()\leftarrow t(A,B),t(V^{1},B)$, where $V^{1}$ is a
fresh variable. Notice that in $q^{\prime}$ the variable $B$ remains shared
thus it is not possible to apply $\sigma_{1}$. It is obvious that without the
factorization step there is no way to obtain the query
$q^{\prime\prime}:q()\leftarrow p(A)$ during the rewriting process. Now,
consider the database $D=\\{p(a)\\}$. Clearly,
$\mathit{chase}(D,\Sigma)=\\{p(a),t(a,z_{1}),s(z_{1})\\}$, and therefore
$\mathit{chase}(D,\Sigma)\models q$, or, equivalently, $D\cup\Sigma\models q$.
However, the rewritten query is not entailed by the given database $D$, since
$q^{\prime\prime}$ does not belong to it, which implies that it is not
complete.

We proceed now to establish soundness and completeness of the proposed
algorithm. Towards this aim we need two auxiliary technical lemmas. The first
one, which is needed for soundness, states that once the chase entails the
rewritten query constructed by the rewriting algorithm, then the chase entails
also the given query. In the sequel, for brevity, given a BCQ $q$ over a
schema $\mathcal{R}$ and a set $\Sigma$ of TGDs over $\mathcal{R}$, we denote
by $q_{\Sigma}$ the rewritten query $\textsf{TGD-rewrite}(q,\Sigma)$.

###### Lemma 3

Consider a BCQ $q$ over a schema $\mathcal{R}$, a database $D$ for
$\mathcal{R}$, and a set $\Sigma$ of TGDs over $\mathcal{R}$. If
$\mathit{chase}(D,\Sigma)\models q_{\Sigma}$, then
$\mathit{chase}(D,\Sigma)\models q$.

Proof. The proof is by induction on the number of applications of the
rewriting step. We denote by $q_{\Sigma}^{[i]}$ the part of the rewritten
query $q_{\Sigma}$ obtained by applying $i$ times the rewriting step.

Base Step. Clearly, $q_{\Sigma}^{0}=q_{\Sigma}$, and the claim holds
trivially.

Inductive Step. Suppose now that $\mathit{chase}(D,\Sigma)\models
q_{\Sigma}^{[i]}$, for $i\geq 0$. This implies that there exists $p\in
q_{\Sigma}^{[i]}$ such that $\mathit{chase}(D,\Sigma)\models p$, and thus
there exists a homomorphism $h$ such that
$h(\mathit{body}(p))\subseteq\mathit{chase}(D,\Sigma)$. If $p\in
q_{\Sigma}^{[i-1]}$, then the claim follows by induction hypothesis. The
interesting case is when $p$ was obtained during the $i$-th application of the
rewriting step from a BCQ $p^{\prime}\in q_{\Sigma}^{[i-1]}$, i.e.,
$q_{\Sigma}^{[i]}=q_{\Sigma}^{[i-1]}\cup\\{p\\}$. By induction hypothesis, it
suffices to show that $\mathit{chase}(D,\Sigma)\models q_{\Sigma}^{[i-1]}$.

Clearly, there exists a TGD $\sigma\in\Sigma$ of the form
$\phi(\mathbf{X},\mathbf{Y})\rightarrow\exists Z\,r(\mathbf{X},Z)$ which is
applicable to a set $A\subseteq\mathit{body}(p^{\prime})$, and $p$ is such
that $\mathit{body}(p)=\gamma(p^{\prime}[A/\phi(\mathbf{X},\mathbf{Y})])$,
where $\gamma$ is the MGU for the set $A\cup\\{\mathit{head}(\sigma)\\}$.
Observe that
$h(\gamma(\phi(\mathbf{X},\mathbf{Y})))\subseteq\mathit{chase}(D,\Sigma)$, and
hence $\sigma$ is applicable to $\mathit{chase}(D,\Sigma)$; let
$\mu=h\circ\gamma$. Thus,
$\mu^{\prime}(r(\mathbf{X},Z))\in\mathit{chase}(D,\Sigma)$, where
$\mu^{\prime}\supset\mu$. We define the substitution
$h^{\prime}=h\cup\\{\gamma(Z)\rightarrow\mu^{\prime}(Z)\\}$.

Let us first show that $h^{\prime}$ is a well-defined substitution. It
suffices to show that $\gamma(Z)$ is not a constant, and also that $\gamma(Z)$
does not appear in the left-hand side of an assertion of $h$. Towards a
contradiction, suppose that $\gamma(Z)$ is either a constant or appears in the
left-hand side of an assertion of $h$. It is easy to verify that in this case
there exists an atom $\underline{a}\in A$ such that at position $\pi_{\sigma}$
in $\underline{a}$ occurs either a constant or a variable which is shared in
$p^{\prime}$. But this contradicts the fact that $\sigma$ is applicable to
$A$. Consequently, $h^{\prime}$ is well-defined. It remains to show that the
substitution $h^{\prime}\circ\gamma$ maps $\mathit{body}(p^{\prime})$ to
$\mathit{chase}(D,\Sigma)$, and thus $\mathit{chase}(D,\Sigma)\models
q_{\Sigma}^{[i-1]}$. Clearly, $\gamma(\mathit{body}(p^{\prime})\setminus
A)\subseteq\mathit{body}(p)$. Since
$h(\mathit{body}(p))\subseteq\mathit{chase}(D,\Sigma)$, we get that
$h^{\prime}(\gamma(\mathit{body}(p^{\prime})\setminus
A))\subseteq\mathit{chase}(D,\Sigma)$. Moreover,

$\begin{array}[]{rcl}h^{\prime}(\gamma(A))&=&h^{\prime}(\gamma(r(\mathbf{X},Z)))\\\
&=&r(h^{\prime}(\gamma(\mathbf{X})),h^{\prime}(\gamma(Z)))\\\
&=&r(\mu(\mathbf{X}),\mu^{\prime}(Z))\\\ &=&\mu^{\prime}(r(\mathbf{X},Z))\\\
&\in&\mathit{chase}(D,\Sigma).\end{array}$

The proof is now complete.

The second auxiliary lemma, which is needed for completeness, asserts that
once the chase entails the rewritten query constructed by the rewriting
algorithm, then the given database also entails the rewritten query.

###### Lemma 4

Consider a BCQ $q$ over a schema $\mathcal{R}$, a database $D$ for
$\mathcal{R}$, and a set $\Sigma$ of TGDs over $\mathcal{R}$. If
$\mathit{chase}(D,\Sigma)\models q_{\Sigma}$, then $D\models q_{\Sigma}$.

Proof. We proceed by induction on the number of applications of the chase
step.

Base Step. Clearly, $\mathit{chase}^{[0]}(D,\Sigma)=D$, and the claim holds
trivially.

Inductive Step. Suppose now that $\mathit{chase}^{[i]}(D,\Sigma)\models
q_{\Sigma}$, for $i\geq 0$. This implies that there exists $p\in q_{\Sigma}$
such that $\mathit{chase}^{[i]}(D,\Sigma)\models p$, and thus there exists a
homomorphism $h$ such that
$h(\mathit{body}(p))\subseteq\mathit{chase}^{[i]}(D,\Sigma)$. If
$h(\mathit{body}(p))\subseteq\mathit{chase}^{[i-1]}(D,\Sigma)$, then the claim
follows by induction hypothesis. The non-trivial case is when the atom
$\underline{a}$, obtained during the $i$-th application of the chase step due
to a TGD $\sigma\in\Sigma$ of the form
$\phi(\mathbf{X},\mathbf{Y})\rightarrow\exists Z\,r(\mathbf{X},Z)$, belongs to
$h(\mathit{body}(p))$. Clearly, there exists a homomorphism $\mu$ such that
$\mu(\phi(\mathbf{X},\mathbf{Y}))\subseteq\mathit{chase}^{[i-1]}(D,\Sigma)$
and $\underline{a}=\mu^{\prime}(r(\mathbf{X},\mathbf{Y}))$, where
$\mu^{\prime}\supseteq\mu$. By induction hypothesis, it suffices to show that
$\mathit{chase}^{[i-1]}(D,\Sigma)\models q_{\Sigma}$. Before we proceed
further, we need to establish an auxiliary technical claim.

###### Claim 5

There exists a BCQ $p^{\prime}\in q_{\Sigma}$ and a set of atoms
$A\subseteq\mathit{body}(p^{\prime})$ such that $\sigma$ is applicable to $A$,
and also there exists a homomorphism $\lambda$ such that
$\lambda(\mathit{body}(p^{\prime})\setminus
A)\subseteq\mathit{chase}^{[i-1]}(D,\Sigma)$ and $\lambda(A)=\underline{a}$.

Proof. Clearly, there exists a set of atoms $B$ such that
$h(\mathit{body}(p)\setminus B)\subseteq\mathit{chase}^{[i-1]}(D,\Sigma)$ and
$h(B)=\underline{a}$. Observe that the null value that occurs in
$\underline{a}$ at position $\pi_{\sigma}$ does not occur in
$\mathit{chase}^{[i-1]}(D,\Sigma)$ or in $\underline{a}$ at some position
other than $\pi_{\sigma}$. Therefore, the variables that occur in the atoms of
$B$ at $\pi_{\sigma}$ do not appear at some other position. Consequently, $B$
can be partitioned into the sets $B_{1},\ldots,B_{m}$, where $m\geq 1$, and
the following holds: for each $i\in[m]$, in the atoms of $B_{i}$ at position
$\pi_{\sigma}$ the same variable $V_{i}$ occurs, and also $V_{i}$ does not
occur in some other set $B\in\\{B_{1},\ldots,B_{m}\\}\setminus\\{B_{i}\\}$ or
in $B_{i}$ at some position other than $\pi_{\sigma}$. It is easy to verify
that each set $B_{i}$ is factorizable w.r.t. $\sigma$.

Suppose that we factorize $B_{1}$. Then, the query $p_{1}=\gamma_{1}(p)$,
where $\gamma_{1}$ is the MGU for $B_{1}$, is obtained. Observe that $h$ is a
unifier for $B_{1}$. By definition of the MGU, there exists a substitution
$\theta_{1}$ such that $h=\theta_{1}\circ\gamma_{1}$. Clearly,

$\begin{array}[]{rcl}\theta_{1}(\mathit{body}(p_{1})\setminus\gamma_{1}(B))&=&\theta_{1}(\gamma_{1}(\mathit{body}(p))\setminus\gamma_{1}(B))\\\
&=&h(\mathit{body}(p)\setminus B)\\\
&\subseteq&\mathit{chase}^{[i-1]}(D,\Sigma),\end{array}$

and $\theta_{1}(\gamma_{1}(B))=h(B)=\underline{a}$.

Now, observe that the set $\gamma_{1}(B_{2})\subseteq\mathit{body}(p_{1})$ is
factorizable w.r.t. $\sigma$. By applying factorization we get the query
$p_{2}=\gamma_{2}(p_{1})$, where $\gamma_{2}$ is the MGU for
$\gamma_{1}(B_{2})$. Since $\theta_{1}$ is a unifier for $\gamma_{1}(B_{2})$,
there exists a substitution $\theta_{2}$ such that
$\theta_{1}=\theta_{2}\circ\gamma_{2}$. Clearly,

$\begin{array}[]{rcl}\theta_{2}(\mathit{body}(p_{2})\setminus\gamma_{2}(\gamma_{1}(B)))&=&\theta_{2}(\gamma_{2}(\mathit{body}(p_{1}))\setminus\gamma_{2}(\gamma_{1}(B)))\\\
&=&\theta_{1}(\gamma_{1}(\mathit{body}(p))\setminus\gamma_{1}(B))\\\
&=&h(\mathit{body}(p)\setminus B)\\\
&\subseteq&\mathit{chase}^{[i-1]}(D,\Sigma),\end{array}$

and
$\theta_{2}(\gamma_{2}(\gamma_{1}(B)))=\theta_{1}(\gamma_{1}(B))=h(B)=\underline{a}$.

Eventually, by applying the factorization step as above, we will get the BCQ

$p_{m}\ =\ \gamma_{m}\circ\ldots\circ\gamma_{1}(p),$

where $\gamma_{j}$ is the MGU for the set
$\gamma_{j-1}\circ\ldots\circ\gamma_{1}(B_{j})$, for $j\in\\{2,\ldots,m\\}$
(recall that $\gamma_{1}$ is the MGU for $B_{1}$), such that
$\theta_{m}(\mathit{body}(p_{m})\setminus\gamma_{m}\circ\ldots\circ\gamma_{1}(B))\subseteq\mathit{chase}^{[i-1]}(D,\Sigma)$
and $\theta_{m}(\gamma_{m}\circ\ldots\circ\gamma_{1}(B))=\underline{a}$.

It is easy to verify that $\sigma$ is applicable to $A$. The claim follows
with $p^{\prime}=p_{m}$, $A=\gamma_{m}\circ\ldots\circ\gamma_{1}(B)$ and
$\lambda=\theta_{m}$.

The above claim implies that during the rewriting process eventually we will
get a BCQ $p^{\prime\prime}$ such that
$\mathit{body}(p^{\prime\prime})=\gamma(\mathit{body}(p^{\prime})\setminus
A)\cup\gamma(\phi(\mathbf{X},\mathbf{Y}))$, where $\gamma$ is the MGU for the
set $A\cup\\{\mathit{head}(\sigma)\\}$. It remains to show that there exists a
homomorphism that maps $\mathit{body}(p^{\prime\prime})$ to
$\mathit{chase}^{[i-1]}(D,\Sigma)$. Since $\lambda\cup\mu^{\prime}$ is a well-
defined substitution, we get that $\lambda\cup\mu^{\prime}$ is a unifier for
$A\cup\\{\mathit{head}(\sigma)\\}$. By definition of the MGU, there exists a
substitution $\theta$ such that $\lambda\cup\mu^{\prime}=\theta\circ\gamma$.
Observe that

$\begin{array}[]{rcl}\theta(\mathit{body}(p^{\prime\prime}))&=&\theta(\gamma(\mathit{body}(p^{\prime})\setminus
A)\cup\gamma(\phi(\mathbf{X},\mathbf{Y})))\\\
&=&(\lambda\cup\mu^{\prime})(\mathit{body}(p^{\prime})\setminus
A)\cup(\lambda\cup\mu^{\prime})(\phi(\mathbf{X},\mathbf{Y}))\\\
&=&\lambda(\mathit{body}(p^{\prime})\setminus
A)\cup\mu^{\prime}(\phi(\mathbf{X},\mathbf{Y}))\\\
&\subseteq&\mathit{chase}^{[i-1]}(D,\Sigma).\end{array}$

Consequently, the desired homomorphism is $\theta$, and the claim follows.

We are now ready to establish soundness and completeness of the algorithm TGD-
rewrite.

###### Theorem 6

Consider a BCQ $q$ over a schema $\mathcal{R}$, a database $D$ for
$\mathcal{R}$, and a set $\Sigma$ of TGDs over $\mathcal{R}$. It holds that,
$D\models q_{\Sigma}$ iff $D\cup\Sigma\models q$.

Proof. Suppose first that $D\models q_{\Sigma}$. Since
$D\subseteq\mathit{chase}(D,\Sigma)$, we get that
$\mathit{chase}(D,\Sigma)\models q_{\Sigma}$, and the claim follows by Lemma
3. Suppose now that $D\cup\Sigma\models q_{\Sigma}$. Since $q\in q_{\Sigma}$,
we get that $\mathit{chase}(D,\Sigma)\models q_{\Sigma}$, and the claim
follows by Lemma 4.

Notice that the above result holds for arbitrary TGDs. However, termination of
TGD-rewrite is guaranteed if we consider linear, sticky or sticky-join sets of
TGDs since, during the rewriting process, only finitely many queries (modulo
bijective variable renaming) are generated.

###### Theorem 7

The algorithm TGD-rewrite terminates under linear, sticky or sticky-join sets
of TGDs.

Approaches such as those of [5] and [14] resort to exhaustive factorizations
of the atoms in the queries generated by the rewriting algorithm. By
factorizing a query $q$ we obtain a subquery $q^{\prime}$, that is, $q$
implies $q^{\prime}$ (w.r.t. the given set of TGDs). Observe that by computing
the factorized query $q^{\prime}$ we eliminate unnecessary shared variables,
in the body of $q$, due to which the applicability condition is violated.
Consider for example the query $q^{\prime}$ of Example 4. By factorizing the
body of $q^{\prime}$ we obtain the query $q()\leftarrow t(A,B)$ which is a
subquery (w.r.t. to the given set $\Sigma$ of TGDs) of $q^{\prime}$ (in this
case equivalent to $q^{\prime}$), where the variable $B$ is no longer shared.
Thus, the rewriting step can now apply $\sigma_{1}$ to $\\{t(A,B)\\}$ and
produce the query $q()\leftarrow p(A)$ which is needed to ensure completeness.

The exhaustive factorization produces a non-negligible number of redundant
queries as demonstrated by the simple example above. It is thus necessary to
apply a restricted form of factorization that generates a possibly small
number of BCQs that are necessary to guarantee completeness of the rewritten
query. This corresponds to the identification of all the atoms in the query
whose shared existential variables come from the same atom in the chase, and
they can be thus unified with no loss of information. The key principle behind
our factorization process is that, in order to be applied, there must exist a
TGD that can be applied to the output of the factorization.

###  5.1 Exploiting Negative Constraints

It is well-known that negative constraints (NCs) of the form
$\forall\mathbf{X}\,\phi(\mathbf{X})\rightarrow\bot$ are vital for
representing ontologies. As already explained in Subsection 4.2, given a
database $D$ for a schema $\mathcal{R}$, a set $\Sigma$ of TGDs over
$\mathcal{R}$, and a set $\Sigma_{\bot}$ of NCs over $\mathcal{R}$, once the
theory $D\cup\Sigma\cup\Sigma_{\bot}$ is consistent, then we are allowed to
ignore the NCs since, for every BCQ $q$, $D\cup\Sigma\cup\Sigma_{\bot}\models
q$ iff $D\cup\Sigma\models q$. However, as shown in the following example, by
exploiting the given set of NCs it is possible to further reduce the size of
the final rewriting.

###### Example 5

Consider the TGD $\sigma:t(X),s(Y)\rightarrow\exists Z\,p(Y,Z)$, the NC
$\nu:r(X,Y),s(Y)\rightarrow\bot$, and the BCQ $q()\leftarrow r(A,B),p(B,C)$.
Clearly, due to the rewriting step, the query $p:q()\leftarrow
r(A,B),t(V^{1}),s(B)$ is obtained during the rewriting process. However, this
query is not really needed since, for any database $D$ for $\mathcal{R}$,
$D\not\models p$; otherwise, $D$ violates the NC $\nu$ which is a
contradiction since we always assume that the theory $D\cup\\{\sigma,\nu\\}$
is consistent.

It is not difficult to show that, given a BCQ $q$, and a set $\Sigma$ of TGDs,
if a query $p\in q_{\Sigma}$ is not entailed by $\mathit{chase}(D,\Sigma)$,
for an arbitrary database $D$, then any query $p^{\prime}\in q_{\Sigma}$
obtained during the rewriting process starting from $p$, also it is not
entailed by $\mathit{chase}(D,\Sigma)$. Assume now that the set
$\Sigma_{\bot}$ of NCs is part of the input. If we obtain a query $p\in
q_{\Sigma}$ such that there exists a homomorphism that maps
$\mathit{body}(\nu)$, for some NC $\nu\in\Sigma_{\bot}$, to
$\mathit{body}(p)$, then we can safely ignore $p$ since
$\mathit{chase}(D,\Sigma)$ does not entail $p$.

From the above informal discussion, we conclude that we can further reduce the
size of the final rewriting by modifying our algorithm as follows. During the
execution of the rewriting algorithm TGD-rewrite (see Algorithm 1), after the
factorization step (resp., rewriting step) we check whether there exists a
homomorphism that maps $\mathit{body}(\nu)$, for some NC $\nu$ of the given
set of NCs, to the body of the generated query $q^{\prime}$. If there exists
such a homomorphism, then the pair $\langle q^{\prime},0\rangle$ (resp.,
$\langle q^{\prime},1\rangle$) is not added to the set $Q_{\textsc{rew}}$.
Furthermore, the pair $\langle q,1\rangle$ is added to $Q_{\textsc{rew}}$ (see
the first line of the algorithm) only if there is no homomorphism that maps
$\mathit{body}(\nu)$, for some NC $\nu$ of the given set of NCs, to
$\mathit{body}(q)$. If there exists such a homomorphism, then the algorithm
terminates and returns the emptyset, which means that
$\mathit{chase}(D,\Sigma)\not\models q$, for every database $D$ for
$\mathcal{R}$.

##  6 Rewriting Optimization

It is common knowledge that the perfect rewriting obtained by applying a
backward-chaining rewriting algorithm (like TGD-rewrite) is, in general, not
very well-suited for execution by a DB engine due to the large number of
queries to be evaluated. In this section we propose a technique, called _query
elimination_ , aiming at optimizing the obtained rewritten query under the
class of linear TGDs. As we shall see, query elimination (which is an
additional step during the execution of the algorithm TGD-rewrite) reduces
_(i)_ the number of BCQs of the perfect rewriting, _(ii)_ the number of atoms
in each query of the rewriting as well as _(iii)_ the number of joins. Note
that in the rest of the paper we restrict our attention on linear TGDs. Recall
that linear TGDs are TGDs with just one atom in their body. Since we also
assume, as explained in the previous section, TGDs with just one atom in their
head, henceforth, when using the term TGD, we shall refer to TGDs with just
one body-atom and one head-atom.

By exploiting the given set of TGDs, it is possible to identify atoms in the
body of a certain query that are logically implied (w.r.t. the given set of
TGDs) by other atoms in the same query. In particular, for each BCQ $q$
obtained by applying the rewriting step of TGD-rewrite, the atoms of
$\mathit{body}(q)$ that are logically implied (w.r.t. the given set of TGDs)
by some other atom of $\mathit{body}(q)$ are eliminated. Roughly speaking, the
elimination of an atom from the body of a query implies the avoidance of the
construction of redundant queries during the rewriting process. Thus, this
step greatly reduces the number of BCQs in the perfect rewriting. Before going
into the details, let us first introduce some necessary technical notions.

######  Definition 3 (Dependency Graph)

Consider a set $\Sigma$ of TGDs over a schema $\mathcal{R}$. The _dependency
graph_ of $\Sigma$ is a labeled directed multigraph $\langle
N,E,\lambda\rangle$, where $N$ is the node set, $E$ is the edge set, and
$\lambda$ is a labeling function $E\rightarrow\Sigma$. The node set $N$ is the
set of positions of $\mathcal{R}$. If there is a TGD $\sigma\in\Sigma$ such
that the same variable appears at position $\pi_{b}$ in
$\mathit{body}(\sigma)$ and at position $\pi_{h}$ in $\mathit{head}(\sigma)$,
then in $E$ there is an edge $e=(\pi_{b},\pi_{h})$ with $\lambda(e)=\sigma$.

Intuitively speaking, the dependency graph of a set $\Sigma$ of TGDs describes
all the possible ways of propagating a term from a position to some other
position during the construction of the chase under $\Sigma$. More precisely,
the existence of a path $P$ from $\pi_{1}$ to $\pi_{2}$ implies that it is
possible (but not always) to propagate a term from $\pi_{1}$ to $\pi_{2}$. The
existence of $P$ guarantees the propagation of a term from $\pi_{1}$ to
$\pi_{2}$ if, for each pair of consecutive edges $e=(\pi,\pi^{\prime})$ and
$e^{\prime}=(\pi^{\prime},\pi^{\prime\prime})$ of $P$, where $e$ and
$e^{\prime}$ are labeled by the TGDs $\sigma$ and $\sigma^{\prime}$,
respectively, the atom obtained during the chase by applying $\sigma$ triggers
$\sigma^{\prime}$. To verify whether this holds we need an additional piece of
information, the so-called _equality type_ , about the body-atom and the head-
atom of each TGD that occurs in $P$.

######  Definition 4 (Equality Type)

Consider an atom $\underline{a}$ of the form $r(t_{1},\ldots,t_{n})$, where
$n\geq 1$. The _equality type_ of $\underline{a}$ is the set of equalities

$\displaystyle\left\\{r[i]=r[j]~{}|~{}t_{i},t_{j}\not\in\Delta_{c}\textrm{~{}and~{}}t_{i}=t_{j}\right\\}$
$\displaystyle\bigcup$
$\displaystyle\left\\{r[i]=c~{}|~{}c\in\Delta_{c}\textrm{~{}and~{}}t_{i}=c\right\\}.$

We denote the above set as $\mathit{eq}(\underline{a})$.

It is straightforward to see that, given a pair of TGDs $\sigma$ and
$\sigma^{\prime}$, if
$\mathit{eq}(\mathit{body}(\sigma^{\prime}))\subseteq\mathit{eq}(\mathit{head}(\sigma))$,
then there exists a substitution $\mu$ such that
$\mu(\mathit{body}(\sigma^{\prime}))=\mathit{head}(\sigma)$. This allows us to
show that the atom obtained by applying $\sigma$ during the construction of
the chase triggers $\sigma^{\prime}$. Consequently, the existence of a path
$P$ (as above) guarantees the propagation of a term from $\pi_{1}$ to
$\pi_{2}$ if, for each pair of consecutive edges $e$ and $e^{\prime}$ of $P$
which are labeled by $\sigma$ and $\sigma^{\prime}$, respectively,
$\mathit{eq}(\mathit{body}(\sigma^{\prime}))\subseteq\mathit{eq}(\mathit{head}(\sigma))$.

######  Example 6 (Dependency Graph)

Consider the set $\Sigma$ of TGDs

$\begin{array}[]{rcl}\sigma_{1}&:&p(X,Y)\rightarrow\exists Zr(X,Y,Z)\\\
\sigma_{2}&:&r(X,Y,c)\rightarrow s(X,Y,Y)\\\ \sigma_{3}&:&s(X,X,Y)\rightarrow
p(X,Y).\end{array}$

The equality type of the body-atoms and head-atoms of the TGDs of $\Sigma$ are
as follows:

$\begin{array}[]{rcl}\mathit{eq}(\mathit{body}(\sigma_{1}))&=&\varnothing\\\
\mathit{eq}(\mathit{head}(\sigma_{1}))&=&\varnothing\\\
\mathit{eq}(\mathit{body}(\sigma_{2}))&=&\\{r[3]=c\\}\\\
\mathit{eq}(\mathit{head}(\sigma_{2}))&=&\\{s[2]=s[3]\\}\\\
\mathit{eq}(\mathit{body}(\sigma_{3}))&=&\\{s[1]=s[2]\\}\\\
\mathit{eq}(\mathit{head}(\sigma_{3}))&=&\varnothing.\end{array}$

The dependency graph of $\Sigma$ is shown in Figure 2.

We are now ready, by exploiting the dependency graph of a set of TGDs, and the
equality type of an atom, to introduce _atom coverage_.

Figure 2: Dependency graph for Example 6.

######  Definition 5 (Atom Coverage)

Consider a BCQ $q$ over a schema $\mathcal{R}$, and a set $\Sigma$ of TGDs
over $\mathcal{R}$. Let $\underline{a}$ and $\underline{b}$ be atoms of
$\mathit{body}(q)$, where $\\{t_{1},\ldots,t_{n}\\}$, for $n\geq 0$, is the
set of shared variables and constants that occur in $\underline{b}$. Also, let
$G_{\Sigma}$ be the dependency graph of $\Sigma$. We say that $\underline{a}$
_covers_ $\underline{b}$ w.r.t. $q$ and $\Sigma$, written as
$\underline{a}\prec_{\Sigma}^{q}\underline{b}$, if for each $i\in[n]$:  (i)
the term $t_{i}$ occurs also in $\underline{a}$, and  (ii) if $t_{i}$ occurs
in $\underline{a}$ and $\underline{b}$ at positions $\Pi_{\underline{a},i}$
and $\Pi_{\underline{b},i}$, respectively, then, there exists an integer
$k\geq 2$ and a set of TGDs
$\\{\sigma_{1},\ldots,\sigma_{k-1}\\}\subseteq\Sigma$, where
$\mathit{eq}(\mathit{body}(\sigma_{1}))\subseteq\mathit{eq}(\underline{a})$
and, for each $j\in[k-2]$,
$\mathit{eq}(\mathit{body}(\sigma_{j+1}))\subseteq\mathit{eq}(\mathit{head}(\sigma_{j}))$,
such that, for each $\pi\in\Pi_{\underline{b},i}$, in $G_{\Sigma}$ there
exists a path $\pi_{i_{1}}\pi_{i_{2}}\ldots\pi_{i_{k}}$, where
$\pi_{i_{1}}\in\Pi_{\underline{a},i}$, $\pi_{i_{k}}=\pi$, and
$\lambda((\pi_{i_{j}},\pi_{i_{j+1}}))=\sigma_{j}$, for each $j\in[k-1]$.

Condition _(i)_ ensures that by removing $\underline{b}$ from $q$ we do not
loose any constant, and also all the joins between $\underline{b}$ and the
other atoms of $\mathit{body}(q)$, except $\underline{a}$, are preserved.
Condition _(ii)_ guarantees that the atom $\underline{b}$ is logically implied
(w.r.t. $\Sigma$) by the atom $\underline{a}$, and therefore can be
eliminated.

###### Lemma 8

Consider a BCQ $q$ over a schema $\mathcal{R}$, and a set $\Sigma$ of linear
TGDs over $\mathcal{R}$. Suppose that
$\underline{a}\prec_{\Sigma}^{q}\underline{b}$, where
$\underline{a},\underline{b}\in\mathit{body}(q)$, and $q^{\prime}$ is the BCQ
obtained from $q$ by eliminating the atom $\underline{b}$. Then, $I\models q$
iff $I\models q^{\prime}$, for each instance $I$ that satisfies $\Sigma$.

Proof (Sketch). ($\Rightarrow$) By hypothesis, there exists a homomorphism $h$
such that $h(\mathit{body}(q))\subseteq I$. Since, by definition of
$q^{\prime}$, $\mathit{body}(q^{\prime})\subset\mathit{body}(q)$, we
immediately get that $h(\mathit{body}(q^{\prime}))\subseteq I$, which implies
that $I\models q^{\prime}$.

($\Leftarrow$) Conversely, there exists a homomorphism $h$ such that
$h(\mathit{body}(q^{\prime}))\subseteq I$, and thus
$h(\mathit{body}(q)\setminus\\{\underline{b}\\})\subseteq I$. It suffices to
show that there exists an extension of $h$ which maps $\underline{b}$ to $I$.
Since $\underline{a}\prec_{\Sigma}^{q}\underline{b}$, it is not difficult to
verify that there exists an atom $\underline{c}\in I$ such that
$\mathit{eq}(\underline{b})=\mathit{eq}(\underline{c})$, which implies that
there exists a substitution $\mu$ such that
$\mu(\underline{b})=\underline{c}$, and also $\mu$ is compatible with $h$.
Consequently, $(h\cup\mu)(\mathit{body}(q))\subseteq I$, and thus $I\models
q$.

An _atom elimination strategy_ for a BCQ is a permutation of its body-atoms.
Given a BCQ $q$ and a set $\Sigma$ of linear TGDs, the set of atoms of
$\mathit{body}(q)$ that cover $\underline{a}\in\mathit{body}(q)$ w.r.t.
$\Sigma$, denoted as $\mathit{cover}(\underline{a},q,\Sigma)$, is the set
$\\{\underline{b}~{}|~{}\underline{b}\in\mathit{body}(q)\textrm{~{}and~{}}\underline{b}\prec_{\Sigma}^{q}\underline{a}\\}$;
when $q$ and $\Sigma$ are obvious from the context, we shall denote the above
set as $\mathit{cover}(\underline{a})$. By exploiting the cover set of the
atoms of $\mathit{body}(q)$, we associate to each atom elimination strategy
$S$ for $q$ a subset of $\mathit{body}(q)$, denoted
$\mathit{eliminate}(q,S,\Sigma)$, which is the set of atoms of
$\mathit{body}(q)$ that can be safely eliminated (according to $S$) in order
to obtain a logically equivalent query (w.r.t. $\Sigma$) with less atoms in
its body. Formally, $\mathit{eliminate}(q,S,\Sigma)$ is computed by applying
the following procedure; in the sequel, let
$S=[\underline{a}_{1},\ldots,\underline{a}_{n}]$, where
$\\{\underline{a}_{1},\ldots,\underline{a}_{n}\\}=\mathit{body}(q)$:

  * $A:=\varnothing$;

  * foreach $i:=1$ to $n$ do

  * $\underline{a}:=S[i]$;

  * if $\mathit{cover}(\underline{a})\neq\varnothing$ then

  * $A:=A\cup\\{\underline{a}\\}$;

  * foreach $\underline{b}\in\mathit{body}(q)\setminus A$ do

  * $\mathit{cover}(\underline{b}):=\mathit{cover}(\underline{b})\setminus\\{\underline{a}\\}$;

  * return $A$.

By exploiting the fact that the binary relation $\prec_{\Sigma}^{q}$ is
transitive, it is possible to establish the uniqueness (w.r.t. the number of
the eliminated atoms) of the atom elimination strategy for a BCQ. In
particular, the following lemma can be shown.

###### Lemma 9

Consider a BCQ $q$ over a schema $\mathcal{R}$, and a set $\Sigma$ of linear
TGDs over $\mathcal{R}$. Let $S_{1}$ and $S_{2}$ be arbitrary elimination
strategies for $q$. It holds that,
$|\mathit{eliminate}(q,S_{1},\Sigma)|=|\mathit{eliminate}(q,S_{2},\Sigma)|$.

Since the elimination strategy for a query is unique (w.r.t. the number of the
eliminated atoms), in the rest of this section we refer to the set of atoms
that can be safely eliminated from a query $q$ (w.r.t. a set $\Sigma$ of
linear TGDs) by $\mathit{eliminate}(q,\Sigma)$.

We are now ready to describe how query elimination works. During the execution
of the rewriting algorithm TGD-rewrite (see Algorithm 1), after the
factorization step and the rewriting step the so-called _elimination_ step is
applied. In particular, the factorized query $q^{\prime}$ obtained during the
factorization step is the query
$\mathit{eliminate}(\mathit{factorize}(q,\sigma),\Sigma)$, while the rewritten
query obtained during the rewriting step is the query
$\mathit{eliminate}(\gamma_{A\cup\\{\mathit{head}(\sigma)\\}}(q[A/\mathit{body}(\sigma)]),\Sigma)$.
Moreover, instead of adding the given query $q$ in $Q_{\textsc{rew}}$, we add
the eliminated query. In particular, the first line of the algorithm is
replaced by $Q_{\textsc{rew}}:=\langle\mathit{eliminate}(q),1\rangle$. An
example of query elimination follows.

######  Example 7 (Query Elimination)

Consider the set $\Sigma$ of TGDs of Example 6, and the BCQ

$\begin{array}[]{rcl}q()&\leftarrow&\underbrace{p(A,B)}_{\underline{a}},\underbrace{r(A,B,C)}_{\underline{b}},\underbrace{s(A,A,D)}_{\underline{c}}.\end{array}$

Based on the Definition 5, it is an easy task to verify that
$\mathit{cover}(\underline{a})=\varnothing$,
$\mathit{cover}(\underline{b})=\\{\underline{a}\\}$ and
$\mathit{cover}(\underline{c})=\varnothing$. Therefore, the output of the
function $\mathit{eliminate}(q,\Sigma)$ is the singleton set
$\\{\underline{b}\\}$. Consequently, by applying the elimination step we get
the BCQ $q()\leftarrow p(A,B),s(A,A,D)$.

As already mentioned, the fact that an atom $\underline{a}$ covers some atom
$\underline{b}$, means that $\underline{b}$ is logically implied (w.r.t. the
given set of TGDs) by $\underline{a}$. However, as shown by the following
example, this fact is not also necessary for the implication of
$\underline{b}$ by $\underline{a}$.

######  Example 8 (Atom Implication)

Consider the set $\Sigma$ of TGDs of Example 6, and the BCQ $q$

$\begin{array}[]{rcl}q()&\leftarrow&\underbrace{r(A,A,c)}_{\underline{a}},\underbrace{p(A,A)}_{\underline{b}},\end{array}$

where $c$ is a constant of $\Delta_{c}$. Observe that $\underline{a}$ does not
cover $\underline{b}$ since, despite the existence of the paths $r[1]s[1]p[1]$
and $r[2]s[3]p[2]$ in the dependency graph of $\Sigma$,
$\mathit{eq}(\mathit{body}(\sigma_{3}))\not\subseteq\mathit{eq}(\mathit{head}(\sigma_{2}))$.
However, $\underline{b}$ is logically implied (w.r.t. $\Sigma$) by
$\underline{a}$. In particular, for every instance $I$ that satisfies
$\Sigma$, if $I\models\underline{a}$, which implies that an atom of the from
$r(V,V,c)$ exists in $I$, then due to the TGDs $\sigma_{2}$ and $\sigma_{3}$
there exists also an atom $p(V,V)$, and thus $I\models\underline{b}$. Note
that such cases are identified by the C&B algorithm [15]. Nevertheless, as
already criticized in Section 2, this requires to pay a price in the number of
queries in the rewritten query.

It is not difficult to see that the function eliminate runs in quadratic time
in the number of atoms of $\mathit{body}(q)$ (by considering the given set of
TGDs as fixed). In particular, to compute the cover set of each body-atom of
$q$ we need to consider all the pairs of atoms of $\mathit{body}(q)$. Note
that the problem whether a certain atom $\underline{a}$ covers some other atom
$\underline{b}$ is feasible in constant time since the given set of TGDs (and
thus its dependency graph) is fixed.

The following result implies that the rewriting algorithm $\textsf{TGD-
rewrite}^{\star}$, obtained from TGD-rewrite by applying the additional step
of elimination, is still sound and complete.

###### Theorem 10

Consider a BCQ $q$ over a schema $\mathcal{R}$, a database $D$ for
$\mathcal{R}$, and a set $\Sigma$ of linear TGDs over $\mathcal{R}$. Then,
$D\models\textsf{TGD-rewrite}^{\star}(\mathcal{R},\Sigma,q)$ iff
$D\cup\Sigma\models q$.

Proof (Sketch). This result follows from the fact that the algorithm TGD-
rewrite is sound and complete under linear TGDs (see Theorem 6) and Lemma 8.

It is important to clarify that the above result does not hold if we consider
arbitrary TGDs (as in Theorem 6). This is because the proof of Lemma 8, which
states that atom coverage implies logical implication (w.r.t. the given set of
TGDs), is based heavily on the linearity of TGDs. Termination of $\textsf{TGD-
rewrite}^{\star}$ follows immediately from the fact that TGD-rewrite
terminates under linear TGDs (see Theorem 7).

##  7 Implementation and Experimental Setting

TGD-rewrite (without the additional check described in Subsection 5.1) and the
query elimination technique presented in Section 6 have been implemented in
the prototype system Nyaya [36] available at
http://mais.dia.uniroma3.it/Nyaya. The reasoning and query answering engine is
based on the IRIS Datalog engine888http://www.iris-reasoner.org/. extended to
support the FO-rewritable fragments of the Datalog± family. In particular, we
extended IRIS to natively support existential variables in the head without
introducing function symbols and to support the constant $\mathit{false}$ as
head of a rule (used to represent negative constraints). Both IRIS and our
extension are implemented in Java.

Since TGD-rewrite is designed for reasoning over ontologies with large ABoxes,
we put ourselves in a similar experimental setting such that of [19]. Thus, we
use DL-LiteR ontologies with a varying number of axioms. The queries under
consideration are based on canonical examples used in the research projects
where these ontologies have been developed. VICODI (V) is an ontology of
European history, and developed in the EU-funded VICODI
project999http://www.vicodi.org.. STOCKEXCHANGE (S) is an ontology for
representing the domain of financial institutions of the European Union.
UNIVERSITY (U) is a DL-LiteR version of the LUBM
Benchmark101010http://swat.cse.lehigh.edu/projects/lubm/., developed at Lehigh
University, and describes the organizational structure of universities.
ADOLENA (A) (Abilities and Disabilities OntoLogy for ENhancing Accessibility)
is an ontology developed for the South African National Accessibility Portal,
and describes abilities, disabilities and devices. The Path5 (P5) ontology is
a synthetic ontology encoding graph structures and used to generate an
exponential-blowup of the size of the rewritten queries. Recall that the
transformation of a set of TGDs into an equivalent set of single-head TGDs
with a single existential variable can introduce auxiliary predicates and
rules (see Lemmas 1 and 2). The ontologies UX, AX and P5X are equivalent
ontologies to U, A and P5 where the auxiliary predicates are considered part
of the schema. These ontologies allow to study the impact of such
transformations on the size of the rewriting.

We compared our implementation with two other rewriting-based query answering
systems for FO-rewritable ontologies:
QuOnto111111http://www.dis.uniroma1.it/quonto/., based on [5] and developed by
the University of Rome La Sapienza, and
Requiem121212http://www.comlab.ox.ac.uk/projects/requiem/home.html., based on
[19] and developed by the Knowledge Representation group of the University of
Oxford.

Table 1: Evaluation of Nyaya System. |  | Size | Length | Width
---|---|---|---|---
|  | QO | RQ | NY |  NY⋆ | QO | RQ | NY |  NY⋆ | QO | RQ | NY |  NY⋆
V | $q_{1}$ | 15 | 15 | 15 | 15 | 15 | 15 | 15 | 15 | 0 | 0 | 0 | 0
$q_{2}$ | 11 | 10 | 10 | 10 | 32 | 30 | 30 | 30 | 31 | 30 | 30 | 30
$q_{3}$ | 72 | 72 | 72 | 72 | 216 | 216 | 216 | 216 | 144 | 144 | 144 | 144
$q_{4}$ | 185 | 185 | 185 | 185 | 555 | 555 | 555 | 555 | 370 | 370 | 370 | 370
$q_{5}$ | 150 | 30 | 30 | 30 | 900 | 210 | 210 | 210 | 1,110 | 270 | 270 | 270
S | $q_{1}$ | 6 | 6 | 6 | 6 | 6 | 6 | 6 | 6 | 0 | 0 | 0 | 0
$q_{2}$ | 204 | 160 | 160 | 2 | 566 | 480 | 480 | 2 | 362 | 320 | 320 | 0
$q_{3}$ | 1,194 | 480 | 480 | 4 | 5,026 | 2,400 | 2,400 | 8 | 4,778 | 2,400 | 2,400 | 4
$q_{4}$ | 1,632 | 960 | 960 | 4 | 7,384 | 4,800 | 4,800 | 8 | 7,112 | 4,800 | 4,800 | 4
$q_{5}$ | 11,487 | 2,880 | 2,880 | 8 | 67,664 | 20,160 | 20,160 | 24 | 84,064 | 25,920 | 25,920 | 24
U | $q_{1}$ | 5 | 2 | 2 | 2 | 10 | 4 | 4 | 4 | 5 | 2 | 2 | 2
$q_{2}$ | 287 | 148 | 148 | 1 | 813 | 444 | 444 | 1 | 526 | 296 | 296 | 0
$q_{3}$ | 1,260 | 224 | 224 | 4 | 7,296 | 1,344 | 1,344 | 16 | 10,812 | 2,016 | 2,016 | 20
$q_{4}$ | 5,364 | 1,628 | 1,628 | 2 | 15,723 | 4,884 | 4,884 | 2 | 10,393 | 3,256 | 3,256 | 0
$q_{5}$ | 9,245 | 2,960 | 2,960 | 10 | 35,710 | 11,840 | 11,840 | 20 | 52,970 | 17,760 | 17,760 | 20
A | $q_{1}$ | 783 | 402 | 402 | 247 | 1,540 | 779 | 779 | 197 | 757 | 377 | 377 | 86
$q_{2}$ | 1,812 | 103 | 103 | 92 | 5,350 | 256 | 256 | 234 | 3,538 | 153 | 153 | 142
$q_{3}$ | 4,763 | 104 | 104 | 104 | 23,804 | 520 | 520 | 520 | 23,804 | 520 | 520 | 520
$q_{4}$ | 7,251 | 492 | 492 | 454 | 21,406 | 1,288 | 1,288 | 1,212 | 14,155 | 796 | 796 | 758
$q_{5}$ | 66,068 | 624 | 624 | 624 | 195,042 | 3,120 | 3,120 | 3,120 | 128,974 | 3,120 | 3,120 | 3,120
P5 | $q_{1}$ | 14 | 6 | 6 | 6 | 14 | 6 | 6 | 6 | 0 | 0 | 0 | 0
$q_{2}$ | 86 | 10 | 10 | 10 | 156 | 16 | 16 | 16 | 70 | 6 | 6 | 6
$q_{3}$ | 538 | 13 | 13 | 13 | 1,413 | 29 | 29 | 29 | 900 | 16 | 16 | 16
$q_{4}$ | 3,620 | 15 | 15 | 15 | 14,430 | 44 | 44 | 44 | 10,260 | 29 | 29 | 29
$q_{5}$ | 25,256 | 16 | 16 | 16 | 107,484 | 60 | 60 | 60 | 103,361 | 44 | 44 | 44
UX | $q_{1}$ | 5 | 5 | 5 | 5 | 10 | 10 | 10 | 10 | 5 | 5 | 5 | 5
$q_{2}$ | 286 | 240 | 240 | 1 | 156 | 147 | 147 | 1 | 70 | 70 | 70 | 0
$q_{3}$ | 1,248 | 1,008 | 1,008 | 12 | 1,397 | 1,125 | 1,125 | 48 | 892 | 735 | 735 | 60
$q_{4}$ | 5,358 | 5,000 | 5,000 | 5 | 12,006 | 7,578 | 7,578 | 5 | 9,828 | 5,625 | 5,625 | 0
$q_{5}$ | 9,220 | 8,000 | 8,000 | 25 | 101,652 | 47,656 | 47,656 | 50 | 96,677 | 37,890 | 37,890 | 50
AX | $q_{1}$ | 783 | 782 | 782 | 555 | 1,543 | 1,541 | 1,541 | 1,084 | 763 | 761 | 761 | 529
$q_{2}$ | 1,812 | 1,781 | 1,781 | 1,737 | 3,589 | 3,528 | 3,528 | 3,514 | 3,576 | 3,516 | 3,516 | 3,401
$q_{3}$ | 4,763 | 4,752 | 4,752 | 4,741 | 27,705 | 23,760 | 23,760 | 23,760 | 23,824 | 23,815 | 23,815 | 23,694
$q_{4}$ | 7,251 | 7,100 | 7,100 | 6,564 | 7,739 | 7,578 | 7,578 | 6,178 | 5,744 | 5,625 | 5,625 | 5,201
$q_{5}$ | - | - | 76,032 | 76,032 | - | - | 81,173 | 81,173 | - | - | 95,942 | 95,942
P5X | $q_{1}$ | 14 | 14 | 14 | 14 | 14 | 14 | 14 | 14 | 0 | 0 | 0 | 0
$q_{2}$ | 86 | 77 | 77 | 66 | 156 | 147 | 147 | 121 | 70 | 70 | 70 | 55
$q_{3}$ | 530 | 390 | 390 | 329 | 1,397 | 1,125 | 1,125 | 925 | 892 | 735 | 735 | 596
$q_{4}$ | 3,476 | 1,953 | 1,953 | 1,644 | 12,006 | 7,578 | 7,578 | 6,263 | 9,828 | 5,625 | 5,625 | 4,619
$q_{5}$ | 23,744 | 9,766 | 9,766 | 8,219 | 101,652 | 47,656 | 47,656 | 39,531 | 96,677 | 37,890 | 37,890 | 31,312

Since TGD-rewrite, as well as the algorithms presented in [5] and [19], are
proven to be sound and complete, the most relevant way of judging the quality
of the rewriting is the _size_ of the perfect rewriting, i.e., the number of
CQs in the perfect UCQ rewriting. In addition, we use two additional metrics,
namely, the _length_ of the rewriting, i.e., the number of atoms in the
perfect rewriting, and the _width_ , i.e., the number of joins to be performed
when the rewritten query is executed. We believe these metrics to be more
appropriate than the number of symbols in the rewritten query used, for
example, in [19], since they allow to establish in a more precise way the cost
of executing the rewriting on a database system. Table 1 reports the results
of our experiments131313Additional data can be found on the Nyaya’s Web site.
while Table 2 shows the queries used in the experiments. We use the symbol “-”
to denote those cases where the tool did not complete the rewriting within 15
minutes. By QO and RQ we refer to the QuOnto and Requiem systems,
respectively, while NY and NY⋆ refer to Nyaya with factorisation and Nyaya
with both factorisation and query elimination, respectively. All the tests
have been performed on an Intel Core 2 Duo Processor at 2.50 GHz and 4GB of
RAM. The OS is Ubuntu Linux 9.10 carrying a Sun JVM Standard Edition with
maximum heap size set at 2GB of RAM.

Table 2: Test Queries TBox | Queries
---|---
V | $q_{1}(A)\leftarrow\mathit{Location(A).}$
$q_{2}(A,B)\leftarrow\mathit{Military\\_Person(A),hasRole(B,A),related(A,C).}$
$q_{3}(A,B)\leftarrow\mathit{Time\\_Dependant\\_Relation(A),hasRelationMember(A,B),Event(B).}$
$q_{4}(A,B)\leftarrow\mathit{Object(A),hasRole(A,B),Symbol(B).}$
$q_{5}(A)\leftarrow\mathit{Individual(A),hasRole(A,B),Scientist(B),hasRole(A,C),Discoverer(C),hasRole(A,D),Inventor(D).}$
S | $q_{1}(A)\leftarrow\mathit{StockExchangeMember(A).}$
$q_{2}(A,B)\leftarrow\mathit{Person(A),hasStock(A,B),Stock(B).}$
$q_{3}(A,B,C)\leftarrow\mathit{FinantialInstrument(A),belongsToCompany(A,B),Company(B),hasStock(B,C),Stock(C).}$
$q_{4}(A,B,C)\leftarrow\mathit{Person(A),hasStock(A,B),Stock(B),isListedIn(B,C),StockExchangeList(C).}$
$q_{5}(A,B,C,D)\leftarrow\mathit{FinantialInstrument(A),belongsToCompany(A,B),Company(B),hasStock(B,C),Stock(C),}$
| $\mathit{isListedIn(B,D),StockExchangeList(D).}$
U(X) | $q_{1}(A)\leftarrow\mathit{worksFor(A,B),affiliatedOrganizationOf(B,C).}$
$q_{2}(A,B)\leftarrow\mathit{Person(A),teacherOf(A,B),Course(B).}$
$q_{3}(A,B,C)\leftarrow\mathit{Student(A),advisor(A,B),FacultyStaff(B),takesCourse(A,C),teacherOf(B,C),Course(C).}$
$q_{4}(A,B)\leftarrow\mathit{Person(A),worksFor(A,B),Organization(B).}$
$q_{5}(A)\leftarrow\mathit{Person(A),worksFor(A,B),University(B),hasAlumnus(B,A).}$
A(X) | $q_{1}(A)\leftarrow\mathit{Device(A),assistsWith(A,B).}$
$q_{2}(A)\leftarrow\mathit{Device(A),assistsWith(A,B),UpperLimbMobility(B).}$
$q_{3}(A)\leftarrow\mathit{Device(A),assistsWith(A,B),Hear(B),affects(C,B),Autism(C).}$
$q_{4}(A)\leftarrow\mathit{Device(A),assistsWith(A,B),PhysicalAbility(B).}$
$q_{5}(A)\leftarrow\mathit{Device(A),assistsWith(A,B),PhysicalAbility(B),affects(C,B),Quadriplegia(C).}$
P5(X) | $q_{1}(A)\leftarrow\mathit{edge(A,B).}$
$q_{2}(A)\leftarrow\mathit{edge(A,B),edge(B,C).}$
$q_{3}(A)\leftarrow\mathit{edge(A,B),edge(B,C),edge(C,D).}$
$q_{4}(A)\leftarrow\mathit{edge(A,B),edge(B,C),edge(C,D),edge(D,E).}$
$q_{4}(A)\leftarrow\mathit{edge(A,B),edge(B,C),edge(C,D),edge(D,E),edge(E,F).}$

As it can be seen, query elimination provides a substantial advantage in terms
of the size of the perfect rewriting for the real-world ontologies A, U and S.
In particular, for the queries denoted as Q2 in U and S, our procedure
eliminates all the redundant atoms in the input query, and drastically reduces
the number of queries in the final rewriting. On the other side, query
elimination is not particularly effective in the synthetic test case P5 and
P5X, since these cases have been intentionally created in order to generate
perfect rewritings of exponential size.

##  8 Future Work

We plan to investigate rewriting and optimization techniques for sticky-join
sets of TGDs, and alternative forms of rewriting such as positive-existential
queries. We also plan to develop improved techniques for rewriting an
ontological query into a non-recursive Datalog program, rather than into a
union of conjunctive queries (recall the discussion in Section 2). While the
current approaches yield exponentially large non-recursive Datalog programs,
it is possible to rewrite queries and TBoxes into non-recursive Datalog
programs whose size is simultaneously polynomial in the query and the TBox.
This will be dealt in a forthcoming paper.

## Acknowledgments

G. Gottlob’s work was funded by the European Research Council under the
European Community’s Seventh Framework Programme (FP7/2007-2013)/ERC grant no.
246858 – DIADEM. Gottlob gratefully acknowledges a Royal Society Wolfson
Research Merit Award. G. Orsi and G. Gottlob also acknowledge the Oxford
Martin School - Institute for the Future of Computing. A. Pieris’ work was
funded by the EPSRC project “Schema Mappings and Automated Services for Data
Integration and Exchange” (EP/E010865/1). We thank Michaël Thomazo for his
useful and constructive comments on the conference version of this paper.

## References

  * [1] G. Gottlob, G. Orsi, and A. Pieris, “Ontological queries: Rewriting and optimization,” in _Proc. of the 27th Intl Conf. on Data Engineering (ICDE)_ , 2011, pp. 2–13.
  * [2] T. R. Gruber, “A translation approach to portable ontology specifications,” _Knowledge Acquisition_ , vol. 5, no. 2, pp. 199–220, 1993.
  * [3] Wikipedia, “Ontology (information science),” 2010. [Online]. Available: –http://en.wikipedia.org/wiki/Ontology“˙(information“˙science)˝.
  * [4] D. McComb, “The enterprise ontology,” 2006. [Online]. Available: –http://www.tdan.com/view-articles/5016˝.
  * [5] D. Calvanese, G. de Giacomo, D. Lembo, M. Lenzerini, and R. Rosati, “Tractable reasoning and efficient query answering in description logics: The DL-Lite Family,” _Journal of Automated Reasoning_ , vol. 39, no. 3, pp. 385–429, 2007.
  * [6] F. Baader, “Terminological cycles in a description logic with existential restrictions,” in _Proc. of 18th Intl Joint Conf. on Artificial Intelligence (IJCAI)_ , 2003, pp. 325–330.
  * [7] A. Calì, G. Gottlob, and T. Lukasiewicz, “A general Datalog-based framework for tractable query answering over ontologies,” in _Proc. of the 28th Symp. on Principles of Database Systems (PODS)_ , 2009, pp. 77–86.
  * [8] ——, “Datalog${}^{\mbox{$\pm$}}$: A unified approach to ontologies and integrity constraints,” in _Proc. of the 12th Intl Conf. on Database Theory (ICDT)_ , 2009, pp. 14–30.
  * [9] A. Calì, G. Gottlob, and A. Pieris, “Advanced processing for ontological queries,” in _Proc. of the 36th Intl Conf. on Very Large Databases (VLDB)_ , 2010, pp. 554–565.
  * [10] ——, “Query answering under non-guarded rules in Datalog±,” in _Proc. of the 4th Intl conf. on Web Reasoning and Rule Systems (RR)_ , 2010, pp. 1–17.
  * [11] S. Ceri, G. Gottlob, and L. Tanca, “What you always wanted to know about Datalog (and never dared to ask),” _IEEE Transactions on Knowledge and Data Engineering_ , vol. 1, no. 1, pp. 146–166, 1989.
  * [12] C. Beeri and M. Y. Vardi, “A proof procedure for data dependencies,” _Journal of the ACM_ , vol. 31, no. 4, pp. 718–741, 1984.
  * [13] M. Y. Vardi, “On the complexity of bounded-variable queries,” in _Proc. of the 14th Symp. on Principles of Database Systems (PODS)_ , 1995, pp. 266–276.
  * [14] A. Calì, G. Gottlob, and A. Pieris, “Query rewriting under non-guarded rules,” in _Proc. of the 4th Alberto Mendelzon Intl Work. on Foundations of Data Management (AMW)_ , 2010.
  * [15] A. Deutsch, L. Popa, and V. Tannen, “Query reformulation with constraints,” _SIGMOD Record_ , vol. 35, pp. 65–73, 2006.
  * [16] S. Alexaki, V. Christophides, G. Karvounarakis, D. Plexousakis, and K. Tolle, “The ICS-FORTH RDFSuite: Managing voluminous RDF description bases,” in _Proc. of the 2nd Intl Workshop on the Semantic Web (SemWeb)_ , 2001, pp. 109–113.
  * [17] E. Chong, S. Das, G. Eadon, and J. Srinivasan, “An efficient SQL-based RDF querying scheme,” in _Proc. of the 31th Intl Conf. on Very Large Data Bases (VLDB)_ , 2005, pp. 1216–1227.
  * [18] G. Gottlob, N. Leone, and F. Scarcello, “Hypertree decompositions and tractable queries,” in _In Proc. of the 18th Symp. on Principles of database systems (PODS)_ , 1999, pp. 21–32.
  * [19] H. Pérez-Urbina, B. Motik, and I. Horrocks, “Efficient query answering for OWL 2,” in _Proc. of the 8th Intl Semantic Web Conf. (ESWC)_ , 2009, pp. 489–504.
  * [20] R. Rosati and A. Almatelli, “Improving query answering over DL-Lite ontologies,” in _In Proc. of the 20th Intl Conf. on Principles of Knowledge Representation (KR)_ , 2010.
  * [21] A. K. Chandra and P. M. Merlin, “Optimal implementation of conjunctive queries in relational data bases,” in _Proc. of the 9th ACM Symp. on Theory of Computing (STOC)_ , 1977, pp. 77–90.
  * [22] A. Halevy, “Answering queries using views: A survey,” _The VLDB Journal_ , vol. 10, pp. 270–294, 2001.
  * [23] A. Deutsch and V. Tannen, “Mars: A system for publishing XML from mixed and redundant storage,” in _In Proc. of the 29th Intl Conf. on Very large data bases (VLDB)_ , 2003, pp. 201–212.
  * [24] C. Beeri and M. Y. Vardi, “The implication problem for data dependencies,” in _Proc. of the 8th Colloquim on Automata, Languages and Programming (ICALP)_ , 1981, pp. 73–85.
  * [25] A. Calı, G. Gottlob, and M. Kifer, “Taming the infinite chase: Query answering under expressive relational constraints,” in _Proc. of the 11th Intl Joint Conf. on Principles of Knowledge Representation and Reasoning (KR)_ , 2008, pp. 70–80.
  * [26] A. Deutsch, A. Nash, and J. Remmel, “The chase revisited,” in _Proc. of the 27th Symp. on Principles of Database Systems (PODS)_ , 2008, pp. 149–158.
  * [27] D. Maier, A. O. Mendelzon, and Y. Sagiv, “Testing implications of data dependencies,” _ACM Trans. on Database Systems_ , vol. 4, no. 4, pp. 455–469, 1979.
  * [28] D. S. Johnson and A. C. Klug, “Testing containment of conjunctive queries under functional and inclusion dependencies,” _Journal of Computer and System Sciences_ , vol. 28, no. 1, pp. 167–189, 1984.
  * [29] R. Fagin, P. Kolaitis, R. Miller, and L. Popa, “Data exchange: Semantics and query answering,” _Theoretical Computer Science_ , vol. 336, no. 1, pp. 89–124, 2005.
  * [30] B. Marnette, “Generalized schema-mappings: From termination to tractability,” in _In Proc. of the 28th Symp. on Principles of Database Systems (PODS)_ , 2009, pp. 13–22.
  * [31] A. Calì, G. Gottlob, and A. Pieris, “Tractable query answering over conceptual schemata,” in _Proc. of the 28th Intl Conf. on Conceptual Modeling (ER)_ , 2009, pp. 175–190.
  * [32] ——, “Query answering under expressive Entity-Relationship schemata,” in _Proc. of the 29th Intl Conf. on Conceptual Modeling (ER)_ , 2010, pp. 347–361.
  * [33] A. K. Chandra and M. Y. Vardi, “The implication problem for functional and inclusion dependencies is undecidable,” _SIAM Journal of Computing_ , vol. 14, no. 3, pp. 671–677, 1985.
  * [34] S. Abiteboul, R. Hull, and V. Vianu, _Foundations of Databases_. Addison-Wesley, 1995.
  * [35] A. Calì, D. Lembo, and R. Rosati, “On the decidability and complexity of query answering over inconsistent and incomplete databases,” in _Proc. of the 22nd Symp. on Principles of Database Systems (PODS)_ , 2003, pp. 260–271.
  * [36] R. de Virgilio, G. Orsi, L. Tanca, and R. Torlone, “Semantic data markets: a flexible environment for knowledge management,” in _Proc. of 20th Intl Conf. on Information and Knowledge Management (CIKM)_ , 2011, pp. 1559–1564.