# Tighter bounds for query answering
with Guarded TGDs

Antoine Amarilli  LTCI, Télécom Paris, Institut Polytechnique de Paris, FR
<EMAIL_ADDRESS>and  Michael Benedikt  Department of
Computer Science, Oxford University, Parks Rd, Oxford OX1 3QD, UK
<EMAIL_ADDRESS>
###### Abstract.

We consider the complexity of the open-world query answering problem, where we
wish to determine certain answers to conjunctive queries over incomplete
datasets specified by an initial set of facts and a set of Guarded TGDs. This
problem has been well-studied in the literature and is decidable but with a
high complexity, namely, it is ${\mathsf{2EXPTIME}}$ complete. Further, the
complexity shrinks by one exponential when the arity is fixed.

We show in this paper how we can obtain better complexity bounds when
considering separately the arity of the guard atom and that of the additional
atoms, called the _side signature_. Our results make use of the technique of
linearizing Guarded TGDs, introduced in [14]. Specifically, we present a
variant of the linearization process, making use of a restricted version of
the chase that we recently introduced [2]. Our results imply that open-world
query answering can be solved in ${\mathsf{EXPTIME}}$ with arbitrary-arity
guard relations if we simply bound the arity of the side signature; and that
the complexity drops to ${\mathsf{NP}}$ if we fix the side signature and bound
the head arity and width of the dependencies.

##  1\. Introduction

The _(open-world) query answering_ problem is concerned with evaluating a
query $Q$ on an incomplete dataset $.Wespecify$ as a set of possible
completions of an initial set of facts $I$, constrained by a set of integrity
constraints $\Sigma$: formally, we evaluate $Q$ over all completions of $I$
satisfying $\Sigma$. Typically $Q$ is a conjunctive query (CQ), equivalent to
a basic SQL query; the rules $\Sigma$ limit the possible completions to
consider, and are typically expressed in restricted logical formalisms.
Research has therefore sought to explore the tradeoff between the
expressiveness of the constraint language, and the complexity of open-world
query answering.

In the last decades, one notable focus of research on query answering is the
${\mathsf{Datalog}}^{\pm}$ family of constraints, which includes _guarded
tuple-generating dependencies_ (GTGDs). A _tuple-generating dependency_ (TGD)
is a universally-quantified implication, where the left hand side – the body –
is a conjunction of atoms, and the right hand side of the implication – the
head – is a CQ. Up to rewriting TGDs, we can ensure that their right-hand side
is always a single atom: these are called _single-headed_ TGDs and we only
study such TGDs in this paper.

TGDs are a common constraint language to express that some patterns in the
data must imply the existence of other patterns; it subsumes, e.g., _inclusion
dependencies_ which are common in relational databases. The formalism of GTGDs
restricts TGDs by enforcing that there is one atom in the body containing all
the variables used in the body: such an atom is called a _guard atom_. This
ensures that GTGDs are expressible in the guarded fragment of first-order
logic. Query answering is known to be decidable in ${\mathsf{2EXPTIME}}$ for
this class, and better bounds are known in some special cases: for example,
when the arity of the signature is bounded, the complexity drops to
${\mathsf{EXPTIME}}$. Similarly, it is known that for linear TGDs (of
unbounded arity), the complexity of query answering drops to
${\mathsf{PSPACE}}$ [16, 18].

Our goal in this paper is to show finer bounds on query answering. Our
approach to do so is to distinguish between the relations allowed for the
guard atoms in TGDs and the signature used for the remaining atoms.
Specifically, we allow each GTGD to have an unrestricted guard atom, but
restrict the other atoms, e.g., by bounding their maximal arity or fixing the
_side signature_ from which they are taken. Roughly speaking, our results show
that the first limitation brings the complexity of query answering down to
${\mathsf{EXPTIME}}$, while the latter further lowers it to ${\mathsf{NP}}$.
Formally, the main complexity results that we show in this paper are the
following:

######  Result 1.

The query answering problem is in ${\mathsf{EXPTIME}}$ for GTGDs on a side
signature of bounded arity. Further, it is in ${\mathsf{NP}}$ if the
constraints consist of non-full IDs of bounded width along with full GTGDs of
bounded head arity on a fixed side signature.

Note how this result recaptures the ${\mathsf{EXPTIME}}$ membership of query
answering with guarded TGDs of bounded arity, and the lower complexity of
linear TGDs (though we do not achieve a ${\mathsf{PSPACE}}$ but
${\mathsf{EXPTIME}}$ bound), within a single unifying language. The first
result is tight in the sense that there are GTGDs with a fixed side signature
of arity $1$ for which ${\mathsf{OWQA}}$ is ${\mathsf{EXPTIME}}$-complete [4].

The finer-grained bounds presented in this paper were first announced in the
context of our earlier work on access patterns [1]. Research on access
patterns typically relies on encoding problems with GTGDs that capture the
semantics of access methods. For each access method, these TGDs will have a
body consisting of a single high-arity guard atom, and multiple unary atoms
over a particular predicate ${\mathsf{accessible}}$, intuitively denoting that
some instance element can be retrieved using the access patterns.
Specifically, the conference version of our work [1] claimed a number of
bounds on query answering with access patterns, using side-signature-based
techniques. These results were only sketched in the conference version (for
which unpublished appendixes claim our main result, Theorem 2). The results
were omitted from the later journal version [2]. These techniques are also
used in a later conference paper [5] about data disclosure, by the second
author and other authors.

The goal of the present work is to fill this gap, and give a self-contained
presentation of our complexity results on query answering for GTGDs with a
side signature. This makes it possible to understand these TGD complexity
results independently from the application to access methods that motivated
it. Indeed, we believe these results to be interesting in their own right, and
hope that they can be useful to show complexity bounds on query answering in
different contexts.

Our key proof technique is that of _linearization_ , introduced in [14]. The
idea is to reduce to the analysis of _linear TGDs_ , where the rule bodies
have only a single atom. Indeed, query answering for such TGDs is known to be
quite well-behaved [16], in ${\mathsf{PSPACE}}$ in general and in
${\mathsf{NP}}$ when the width is bounded. Restricting the side signature
intuitively make GTGDs “translatable” to linear TGDs in an auxiliary
signature, where a body atom in the auxiliary signature represents a guard
atom in the original signature along with a specific choice of additional
atoms from the restricted side signature.

While this basic idea is quite natural, the linearization process turns out to
be rather involved. In particular, we need to reason with a _saturation
procedure_ to translate the GTGDs to linear TGDs which accurately reflect the
effect of the side signature atoms, in particular the atoms that can be
deduced from them, e.g., by the application of full GTGDs (i.e., with no
existential quantifier). To establish the correctness of the saturation
procedure, we use the standard tool of the _chase_ , but we need to restrict
it to a specialized version called the _one-pass chase_. While the notion of
one-pass chase is from [6], and some other techniques are adapted from the
unpublished appendixes of [1], the only published work using these techniques
is [2] – but there the analysis is restricted to a special case in which the
side signature consists of a single unary atom.

#### Paper structure.

We first give preliminaries in Section 2, reviewing in particular the notion
of _semi-width_ from [2]. We then define the notion of side signature in
Section 3 and state our main result (Theorem 2), which describes the
complexity of translating GTGDs to linear TGDs of bounded semi-width,
depending on bounds on the side signature. This result together with the
results on semi-width directly implies Result 1 above. We then give the proof
of Theorem 2. We start in Section 4 by introducing the necessary notion of a
_tree-like chase proof_ from [3] and _one-pass tree-like chase proofs_ from
[6], modified to our needs. Then we prove the main result in Section 5. We
conclude in Section 6.

##  2\. Preliminaries

#### Data and queries.

We consider a _relational signature_ ${\mathcal{S}}$ that consists of a set of
_relations_ with an associated _arity_ (a positive integer). The _arity_ of
${\mathcal{S}}$ is the maximal arity of a relation in ${\mathcal{S}}$. We
always assume that the arity is at least two. The _positions_ of a relation
$R$ of ${\mathcal{S}}$ are $\\{1\ldots n\\}$ where $n$ is the arity of $R$. An
_instance_ of $R$ is a (finite or infinite) set of $n$-tuples of values from
some infinite set of values. An _instance_ $I$ of ${\mathcal{S}}$ consists of
instances for each relation of ${\mathcal{S}}$. The _active domain_
${\mathsf{Adom}}(I)$ of $I$ is the set of the values that occur in tuples of
$I$.

We can equivalently see $I$ as a set of _facts_ $R(a_{1}\ldots a_{n})$ for
each tuple $(a_{1}\ldots a_{n})$ in the instance of each relation $R$. A
_subinstance_ $I^{\prime}$ of $I$ is an instance that contains a subset of the
facts of $I$, we equivalently say that $I$ is a _superinstance_ of
$I^{\prime}$.

A _relational atom_ over a set $X$ of variables is of the form $R(x_{1}\ldots
x_{n})$, with $R$ being a relation of arity $n$ and $x_{1}\ldots x_{n}$ being
variables from $X$. A _unifier_ from a set of atoms $A_{1},\ldots,A_{n}$ to a
set of atoms $B_{1},\ldots,B_{m}$ is a substitution $\sigma$ of the variables
occurring in the $A_{i}$ such that, for each atom $A_{i}$, writing
$\sigma(A_{i})$ the result of substituting its elements according to $\sigma$,
then the result is one of the $B_{1},\ldots,B_{m}$.

We will study _conjunctive queries_ (CQs), which are logical expressions of
the form $\exists x_{1}\ldots x_{k}~{}(A_{1}\wedge\cdots\wedge A_{m})$, where
the $A_{i}$ are relational atoms over $x_{1}\ldots x_{k}$. A CQ is _Boolean_
if it has no free variables. Because our emphasis in this paper will be
Boolean CQs, _by default when we say a CQ we mean a Boolean one throughout the
paper_. A _match_ of a (Boolean) CQ $Q$ in an instance $I$ is a homomorphism
of $Q$ to $I$, i.e., a mapping $h$ from the variables of $Q$ to
${\mathsf{Adom}}(I)$ which ensures that, for every atom $R(t_{1}\ldots t_{n})$
in $Q$, the atom $R(h(t_{1})\ldots h(t_{n}))$ is a fact of $I$. We say that
$Q$ _holds_ in $I$ if there is a match of $Q$ in $I$. We let $Q(I)$ be the
_output_ of $Q$ on $I$, defined in the usual way: if $Q$ is Boolean, the
output is true if the query holds and false otherwise.

#### Integrity constraints.

An _integrity constraint_ is a restriction on instances: that is, a function
mapping every instance of a given schema to a Boolean. When we say that an
instance _satisfies_ a constraint, we just mean that the function evaluates to
true. As concrete syntax for constraints we use fragments of first-order logic
(FO), with the active-domain semantics, and disallowing constants. The active-
domain semantics can be enforced syntactically, e.g., by restricting first-
order logic formulas to always quantify over elements that appear in some
relation. In the few cases in this paper where we talk about FO integrity
constraints, we will always mean a constraint in such a restricted fragment.
With such a restriction, the truth value of an FO integrity constraint on an
instance is well-defined. We focus on a specific fragment of FO under this
restriction, called _tuple-generating dependencies_ (TGDs) which we now
review.

A _tuple-generating dependency_ (TGD) is an FO sentence $\tau$ of the form:
$\forall\vec{x}~{}(\beta(\vec{x})\rightarrow\exists\vec{y}~{}A(\vec{x},\vec{y}))$
where $\beta$ is a conjunction of relational atoms called the _body_ , and $A$
is an atom called the _head_. We will always make the assumption that TGDs are
_single-headed_ , in the sense that their head is a single atom: see for
instance [15] for an example of work investigating the impact of this choice.

For brevity, in the sequel, we will omit outermost universal quantifications
in TGDs. The _exported variables_ of $\tau$ are the variables of $\vec{x}$
which occur in the head. A _full TGD_ is one with no existential quantifiers
in the head. A _guarded TGD_ (GTGD) is a TGD $\tau$ whose body $\beta$
contains some relational atom $A$ which contains all variables occurring in
$\beta$. We call $A$ a _guard_ of $\beta$, and of $\tau$: note that it is not
necessarily unique. When decomposing $\beta$ as
$A(\vec{x})\wedge\beta^{\prime}(\vec{x})$ for one specific choice of $A$, we
call $A$ the _guard atom_ and call $\beta^{\prime}$ the _side atoms_. We will
also say that a fact or set of facts $S$ is _guarded_ by another fact or set
of facts $S^{\prime}$ if the facts of $S$ only use elements occurring in
$S^{\prime}$.

A _frontier-guarded TGD_ is one where there is a relational atom $A$ of
$\beta$ which contains all the exported free variables, in particular a
guarded TGD is always frontier-guarded. A _linear TGD_ is one where the body
and head consist of a single atom: in particular a linear TGD is always
guarded. An _inclusion dependency_ (ID) is a linear TGD where we further
impose that no variable is repeated in the body and no variable is repeated in
the head. The _width_ of a TGD is the number of exported variables. Remember
that we do not allow constants in TGDs.

####  ${\mathsf{OWQA}}$ and TGD implication problems.

We say that a set of first-order sentences $\lambda$ _entails_ a first-order
sentence $\rho$, written $\lambda\models\rho$, if every instance satisfying
$\lambda$ also satisfies $\rho$. In particular, a special case of entailment
is _entailment of a TGD $\tau$ by a set of TGDs $\Sigma$_.

We will in particular study a specific kind of entailment problem, of the
form:

$\bigwedge_{i\leq n}F_{i}\wedge\Sigma\models Q$

where $\Sigma$ is a set consisting of TGDs, each $F_{i}$ is a fact, and $Q$ is
a CQ. This is the problem of _certain answers_ or _(open-world) query
answering_ [13] (${\mathsf{OWQA}}$) under TGDs for CQs. If $I_{0}$ is a finite
instance with facts $F_{1}\ldots F_{n}$, we also write $I_{0},\Sigma\models Q$
to mean $\bigwedge_{i}F_{i}\wedge\Sigma\models Q$. Note that the
${\mathsf{OWQA}}$ problem is closely connected to the problem of _query
containment under constraints_ , which has been independently studied in the
literature, also in connection with access patterns; see, e.g., [12]. We study
the complexity of the ${\mathsf{OWQA}}$ problem in _combined complexity_ ,
i.e., as a function of $|I_{0}|$, $|\Sigma|$, and $|Q|$, where the size
$|\Sigma|$ is taken following, e.g., a string representation, and likewise for
$|I_{0}|$ and $|Q|$.

#### Semi-width.

Our tractability results in this paper will be shown by reducing to the case
of linear TGDs, which we call _linearization_. In particular, we will rely
from ${\mathsf{NP}}$ upper bounds which depend on the _width_ of the
dependencies. The following result was shown by Johnson and Klug [16] in the
case of inclusion dependencies:

######  Proposition 1 ([16]).

For fixed $w$, there is an ${\mathsf{NP}}$ algorithm for ${\mathsf{OWQA}}$
under inclusion dependencies of width at most $w$.

This notion was slightly generalized in [2] to the notion of _semi-width_ ,
which extends width by the addition of acyclic TGDs. We now review the
definition. The _basic position graph_ of a set of TGDs $\Sigma$ is the
directed graph whose nodes are the positions of relations in $\Sigma$, with an
edge from $R[i]$ to $S[j]$ if and only if there is a dependency
$\delta\in\Sigma$ with exported variable $x$ occurring in position $i$ of $R$
in the body of $\delta$ and position $j$ of $S$ in the head of $\delta$. We
say that a collection of TGDs $\Sigma$ has _semi-width_ bounded by $w$ if it
can be decomposed into $\Sigma_{1}\cup\Sigma_{2}$ where $\Sigma_{1}$ has width
bounded by $w$ and the position graph of $\Sigma_{2}$ is acyclic.

We can then show that ${\mathsf{OWQA}}$ is ${\mathsf{NP}}$ for linear TGDs of
bounded semi-width. The result was shown in [2, Appendix C] for inclusion
dependencies ([2, Proposition 6.5]), and we must slightly modify the proof to
apply more generally to linear TGDs:

######  Proposition 1.

For fixed $w$, there is an ${\mathsf{NP}}$ algorithm for OWQA under linear
TGDs of semi-width at most $w$.

To avoid distracting from the main results of the paper, we give a self-
contained proof of this result in Appendix A, most of which is identical to
[2, Appendix C].

##  3\. Result statements

Having defined the preliminaries, we are now ready to formally state the
results of this paper. We first contrast them with existing results, then
introduce the notion of _side signature_ through which they are phrased, and
finally state them, together with the main technical linearization result that
we show.

#### Earlier results.

Our focus is on complexity bounds for the ${\mathsf{OWQA}}$ problem with
Guarded TGDs. The following bounds on this problem represent the prior state
of the art [8]:

[[8]] Given a set of guarded TGDs $\Sigma$, an instance $I$, and a query $Q$,
the ${\mathsf{OWQA}}$ problem for $\Sigma$, $I$, and $Q$ is
${\mathsf{2EXPTIME}}$-complete.

Further, if we fix the arity of ${\mathcal{S}}$, then the problem is
${\mathsf{EXPTIME}}$-complete. Last, if we fix the guarded TGDs $\Sigma$, the
problem is ${\mathsf{NP}}$-complete.

Our goal in this paper is to refine the first two results, i.e., the
${\mathsf{2EXPTIME}}$ and ${\mathsf{EXPTIME}}$ bounds, by showing that they
hold for more general constraint languages, defined via the notion of _side
signature_.

#### Side signature.

The _side signature_ intuitively consists of relations that cannot be used as
guards, i.e., each TGD is guarded with a relation which is not part of the
side signature: Let $\gamma$ be a GTGD on signature ${\mathcal{S}}$. Given a
sub-signature ${\mathcal{S}}^{\prime}\subseteq{\mathcal{S}}$, we say that
$\gamma$ has _side signature ${\mathcal{S}}^{\prime}$_ if there is a choice of
guard atom in the body of $\gamma$ such that all other body atoms are
relations of ${\mathcal{S}}^{\prime}$. A set of GTGDs $\Sigma$ has _side
signature ${\mathcal{S}}^{\prime}$_ if all GTGDs of $\Sigma$ do.

Our bounds will also rely on the notion of _head arity_ : The _head arity_ of
$\gamma$ is the number of variables used in the head of $\gamma$. The _head
arity_ of a set $\Sigma$ of GTGDs is the maximal head arity of a GTGD in
$\Sigma$.

We can now re-state Result 1 from the introduction:

See 1

In other words, we show that, for the ${\mathsf{OWQA}}$ problem to be in
${\mathsf{EXPTIME}}$, we can allow arbitrary-arity guarded TGDs, and we just
need to bound the arity of the side signature. In particular, our result
recaptures and extends the ${\mathsf{EXPTIME}}$ bound on the combined
complexity of ${\mathsf{OWQA}}$ for linear TGDs [10].

We further show that, to achieve ${\mathsf{NP}}$ complexity, we do not need to
fix the dependencies – it suffices to fix the width of non-full GTGDs, and the
head arity of full GTGDs. This extends the ${\mathsf{NP}}$ upper bound on
${\mathsf{OWQA}}$ for bounded-width IDs by Johnson and Klug [16].

#### Linearization result.

All of our complexity bounds are shown by reducing the ${\mathsf{GTGD}}$ case
to the case of reasoning over linear TGDs. We say that a set $\Sigma^{\prime}$
of constraints and an instance $I_{0}^{\prime}$ _emulate_ another set of
constraints $\Sigma$ and instance $I_{0}$ if they are equivalent for
${\mathsf{OWQA}}$, i.e., entail the same CQs: formally, for any CQ $Q$ we have
$I_{0},\Sigma\models Q$ iff $I_{0}^{\prime},\Sigma^{\prime}\models Q$. We then
show:

######  Theorem 2.

For any fixed side signature arity $a^{\prime}\in\mathbb{N}$, there is a
polynomial $P$ satisfying the following. Given:

  * •

A signature ${\mathcal{S}}$ of arity $a$;

  * •

A subsignature ${\mathcal{S}}^{\prime}\subseteq{\mathcal{S}}$ with
$n^{\prime}$ relations and arity $\leq a^{\prime}$;

  * •

An instance $I_{0}$ on ${\mathcal{S}}$;

  * •

A set $\Sigma$ of non-full IDs of width $w$ and of full GTGDs with side
signature ${\mathcal{S}}^{\prime}$ and head arity $h$;

We can compute in time $(\left|\Sigma\right|\times
a\times\left|I_{0}\right|)^{P(w,h,n^{\prime})})$ a set $\Sigma^{\prime}$ of
linear TGDs of semi-width $\leq w$ and arity $\leq a$, and an instance
$I_{0}^{\mathsf{Lin}}$, such that $\Sigma^{\prime}$ and $I_{0}^{\mathsf{Lin}}$
emulate $\Sigma$ and $I_{0}$.

Note that we assume that IDs are _non-full_ , i.e., they must create at least
one null. Of course, full IDs can be seen as full GTGDs with empty side
signature, so they are also covered by this result – but their head arity is
then counted in the bound $h$. Note also that the head arity for full GTGDs
serves as a bound on the width of the full GTGDs. So we can replace $h$ and
$w$ in this formula by a bound on the width of any TGD in $\Sigma$, full or
non-full.

Theorem 2 will be proven in the next sections. Before this, we show how to
prove Result 1 from Theorem 2.

#### Proving Result 1 from Theorem 2.

With Theorem 2, we are able to prove our main complexity result (Result 1).
Indeed, we can show:

######  Corollary 3.

There is an ${\mathsf{EXPTIME}}$ algorithm for ${\mathsf{OWQA}}$ under GTGDs
on a bounded arity side signature.

######  Proof 3.1.

One can simulate GTGDs by non-full IDs and full GTGDs, via additional
relations. More precisely, we see every full ID as a full GTGD, and we rewrite
every non-full GTGD
$\forall\vec{x}~{}(\beta(\vec{x})\rightarrow\exists\vec{y}~{}A(\vec{x},\vec{y}))$
to:

  * •

a full GTGD $\forall\vec{x}~{}(\beta(\vec{x})\rightarrow A^{\prime}(\vec{x})$
where $A^{\prime}$ is fresh and features no variable repetitions;

  * •

a non-full ID
$\forall\vec{x}~{}(A^{\prime}(\vec{x})\rightarrow\exists\vec{y}~{}A^{\prime\prime}(\vec{x},\vec{y}))$
where again $A^{\prime\prime}$ is fresh and features no variable repetitions;

  * •

a full (linear) GTGD
$\forall\vec{x}~{}(A^{\prime\prime}(\vec{x},\vec{y})\rightarrow
A(\vec{x},\vec{y}))$ where the head (but not the body) may feature variable
repetitions.

Thus we can assume that the constraints $\Sigma$ consist of non-full IDs and
full GTGDs. Further note that this transformation does not change the
signature arity, the side signature, or the width.

Now, apply the reduction of Theorem 2, which computes in ${\mathsf{EXPTIME}}$
a set of linear TGDs $\Sigma^{\prime}$ and rewritten instance
$I_{0}^{\mathsf{Lin}}$ that emulate the original TGDs $\Sigma$ and instance
$I_{0}$. We can solve the ${\mathsf{OWQA}}$ problem for linear TGDs via an
algorithm that takes ${\mathsf{PSPACE}}$ in the maximum arity but polynomial
time in the input instance and the TGDs. This can be done either by the chase-
based argument of [16] or via generating and evaluating on-the-fly a query
rewriting consisting of a union of CQs where each CQ has polynomial size in
the input CQ and maximal arity of the linear TGDs, and the number of such CQs
is polynomial in the number of linear TGDs and exponential in the arity [11].
When we apply this to our exponential set of linear TGDs, we get the desired
${\mathsf{EXPTIME}}$ bound.

We can then use Theorem 2 by fixing the head arity $h$, the width $w$, and the
entire side signature ${\mathcal{S}}^{\prime}$, to deduce the following.

######  Corollary 4.

There is an ${\mathsf{NP}}$ algorithm for ${\mathsf{OWQA}}$ under bounded-
width non-full IDs and full GTGDs of bounded head arity on a fixed side
signature.

The point of this result is that, while the side signature
${\mathcal{S}}^{\prime}$ is constant, the entire signature ${\mathcal{S}}$, in
particular its arity, are _not_ constant. The relations in
${\mathcal{S}}\setminus{\mathcal{S}}^{\prime}$ can be used in two ways: in the
bounded-width IDs, and as guards in the full GTGDs. Note that the bound on
width limits how many variables can be exported in a non-full ID (but this
does not bound the signature arity), and the bound on head arity intuitively
means that relations with a large arity can only be used in the non-full IDs
and in the body (and more specifically as the guard) of full GTGDs.

######  Proof 3.2 (Proof of Corollary 4).

We simply apply the reduction of Theorem 2, which computes in
${\mathsf{PTIME}}$ an equivalent set of linear TGDs of constant semi-width and
a rewriting of the instance which emulate the original instance and
constraints. Then, we conclude by Proposition 2.

#### Constants, multi-headed dependencies, and IDs.

Note that that we have stated our results with dependencies that are assumed
to be _single-headed_ , and which do not feature _constants_.

For the ${\mathsf{EXPTIME}}$ upper bound (Corollary 3), we do not expect that
these restrictions make a difference. Intuitively, constants can be emulated
by adding unary relations to the side signature (so without increasing its
arity), and multi-headed rules can be rewritten to be single-headed.

For the ${\mathsf{NP}}$ upper bound (Corollary 4), rewriting constants and
multi-headed dependencies in this fashion may increase the head arity and/or
side signature, and we do not know if the result holds without disallowing
constants and enforcing dependencies to be single-headed.

We have also stated the ${\mathsf{NP}}$ upper bound in a way that requires the
dependencies to be either _full GTGDs_ , or _non-full IDs_. Of course, full
IDs are in particular full GTGDs, so they are covered (though their arity is
then counted in the head arity). Likewise, non-full GTGDs can be rewritten to
full GTGDs and IDs as in the proof of Corollary 3, but again potentially
increasing the head arity. We do not know if the notion of head arity can be
defined in a different way to strengthen Corollary 4.

#### Inapplicability of hardness results.

We also give a short explanation of why our results do not contradict the
known hardness results of [8] on ${\mathsf{OWQA}}$ with GTGDs.

For Corollary 3, it is shown in [8, Theorem 6.2] that the ${\mathsf{OWQA}}$
problem on a fixed instance for an atomic query under GTGDs is
${\mathsf{2EXPTIME}}$-hard when the arity is unbounded, even when the number
of relations in the signature is bounded. The proof works by devising a GTGD
theory that simulates an ${\mathsf{EXPSPACE}}$ alternating Turing machine, by
coding the state of the Turing machine as facts on tuples of elements:
specifically, a fact $\mathit{zero}(\mathbf{V},X)$ codes that there is a zero
in the cell indexed by the binary vector $\mathbf{V}$ in configuration $X$.
The arity of such relations is unbounded, so they cannot be part of the side
signature ${\mathcal{S}}^{\prime}$. However, in the simulation of the Turing
machine, the GTGDs in the proof use another relation as guard (the $g$
relation), and the bodies contain other high-arity relations, so there is no
choice of ${\mathcal{S}}^{\prime}$ for which the GTGD theory defined in the
hardness proof can satisfy the definition of a side signature.

For Corollary 4, the proof in [8, Theorem 6.2] explicitly writes the state of
the $i$-th tape cell of a configuration $X$ as, e.g., $\mathit{zero_{i}}(X)$.
These relations occur in rule bodies where they are not guards, but as
Corollary 4 assumes that the side signature is fixed, they cannot be part of
the side signature. A variant of the construction of the proof (to show
${\mathsf{EXPTIME}}$-hardness on an unbounded signature arity) would be to
code configurations as tuples of elements $X_{1}\ldots X_{n}$ and write, e.g.,
$\mathit{zero}(X_{i})$. However, the constant-width bound on IDs would then
mean that the proof construction can only look at a constant number of cells
when creating one configuration from the previous one.

Let us now prove Theorem 2 in the rest of this paper.

##  4\. One-pass tree-like chase proofs for Guarded TGDs

To show our linearization result, we review in this section the tool of _one-
pass tree-like chase proofs_ and review the result from [6] that it can be
used for ${\mathsf{OWQA}}$ with GTGDs.

#### Tree-like chase proofs.

We now introduce the chase proofs that we are using. We first review the
general notion of _chase sequences_ [13], which are known to be complete for
${\mathsf{OWQA}}$ with CQs and general TGDs. We specifically focus on _tree-
like chase proofs_ , which are complete for ${\mathsf{OWQA}}$ with frontier-
guarded TGDs [3].

A _chase tree_ $T$ consists of a directed tree and a function mapping each
vertex $v$ in the tree to a finite set of facts $T(v)$. We extend the usual
notion of chase tree by distinguishing one vertex in the chase tree, which is
said to be _recently updated_ ; this notion will be used when defining one-
pass chase proofs. A chase tree $T$ can be transformed to another chase tree
$T^{\prime}$ in the following two ways:

  * •

One can apply a _chase step_ with a GTGD
$\gamma:\forall\vec{x}(\beta(\vec{x})\rightarrow\exists\vec{y}~{}A(\vec{x},\vec{y}))$.
The precondition is that there exists a vertex $v$ in $T$ and a substitution
$\sigma$ with domain $\vec{x}$ such that ${\sigma(\beta)\subseteq T(v)}$. The
image $\sigma(\beta)$ is called a _trigger_ $\psi$ of $\gamma$ in $T$. We say
that the trigger $\psi$ is _active_ if there is no mapping $\sigma^{\prime}$
that extends $\sigma$ and ensures that $\sigma^{\prime}(A)$ occurs in $T$ (not
necessarily in $v$). Applying the chase step is also called _firing_ $\psi$,
and will ensure that $\psi$ is no longer active, as we will add facts to $T$
that define a suitable extension $\sigma^{\prime}$.

The result of the chase step is obtained as follows.

    * –

If $\gamma$ is full, then the chase tree $T^{\prime}$ is obtained from $T$ by
marking $v$ as recently updated in $T^{\prime}$, setting
${T^{\prime}(v)\colonequals T(v)\cup\\{\sigma(A)\\}}$ and defining
$T^{\prime}$ as $T$ on other nodes.

    * –

If $\gamma$ is not full, then $\sigma$ is extended to a substitution
$\sigma^{\prime}$ that maps each variable in $\vec{y}$ to a labeled null not
occurring in $T$, and the chase tree $T^{\prime}$ is obtained from $T$ by
introducing a fresh child $v^{\prime}$ of $v$, marking $v^{\prime}$ as
recently updated in $T^{\prime}$, and defining $T^{\prime}$ by extending $T$
with

${T(v^{\prime})\colonequals\sigma^{\prime}(A)\cup\\{F\in T(v)\mid F\text{ is
guarded by }\sigma^{\prime}(A)\\}}$

In other words, the new node contains $\sigma^{\prime}(A)$ and all facts of
the parent node that are guarded by it, i.e., all facts of $T(v)$ that only
use elements shared with $T(v^{\prime})$.

  * •

One can apply a _propagation step_ from a vertex $v$ to a vertex $v^{\prime}$
in $T$. More precisely, we select a nonempty subset $S\subseteq T(v)$ of the
facts of $v$, and select a vertex $v^{\prime}$ where these facts do not occur
(i.e., $T(v^{\prime})\cap S=\emptyset$) but they are guarded (i.e., the facts
of $S$ only use elements occurring in a fact of $T(v^{\prime})$). Then we set
$T^{\prime}(v^{\prime})\colonequals T(v^{\prime})\cup S$ and mark $v^{\prime}$
as recently updated.

Note that we allow the firing of non-active triggers. If $\gamma$ is full,
firing a non-active trigger simply means that we modify $v$ to add a fact
$\sigma(A)$ which already exists somewhere in the chase tree (and could have
been propagated instead); or it has no effect if the created fact $\sigma(A)$
already exists in $v$. If $\gamma$ is non-full, firing a non-active trigger
means that we create a new child of $v$, with a different choice of labeled
nulls.

A _tree-like chase sequence_ for a base instance $I$ and a finite set of GTGDs
$\Sigma$ is a finite sequence of chase trees ${T_{0},\dots,T_{n}}$ such that
$T_{0}$ contains exactly one _root vertex_ $r$ that is the recently updated
vertex in $T_{0}$ and ${T_{0}(r)=I}$, and each $T_{i}$ with ${0<i\leq n}$ is
obtained from $T_{i-1}$ by one of the two steps above, i.e., a chase step with
some ${\gamma\in\Sigma}$, or a propagation step. For each vertex $v$ in
$T_{n}$ and each fact ${F\in T_{n}(v)}$, this sequence is a _tree-like chase
proof of_ $F$ _from_ $I$ and $\Sigma$. It is well-known (e.g., [9]) that, for
any CQ $Q$, we have ${I,\Sigma\models Q}$ if and only if there is a tree-like
chase sequence $T_{0},\ldots,T_{n}$ for $I$ and $\Sigma$ such that $Q$ has a
_match_ in $T_{n}$, in other words, there is a tree-like chase proof
$T_{0},\ldots,T_{n}$ of each of the facts of $\sigma(Q)$, for $\sigma$ some
substitution mapping the variables of $Q$ to the domain values of $T_{n}$.

#### Tree-like chase proofs.

Our linearization result will rely on the fact that tree-like chase proofs can
be normalized to ensure that we do not jump back and forth in a tree, but
perform our changes to the tree in one single traversal. Versions of this
result have appeared dating back to [1], with refinements in [17] for the
disjunctive case. The result was applied to get rewritings for atomic queries
under GTGD constraints in [6], and we use the formulation from that paper.

[[6]] A tree-like chase sequence ${T_{0},\dots,T_{n}}$ for a base instance $I$
and a finite set of GTGDs $\Sigma$ is _one-pass_ if, for each ${0<i\leq n}$,
the chase tree $T_{i}$ is obtained by applying one of the following two steps
to the recently updated vertex $v$ of $T_{i-1}$:

  * •

if we can perform a propagation step copying exactly one fact from $v$ to its
parent, then we do so;

  * •

otherwise, if no propagation step from $v$ to its parent can be applied, we
perform a chase step with a GTGD from $\Sigma$.

Thus, each step in a tree-like chase sequence is applied to a “focused”
vertex, namely, the recently updated vertex. Steps with non-full TGDs move the
“focus” from parent to child, and steps with full TGDs do not move the focus:
the full steps are followed by propagation which copies the fact upwards as
long as it is possible, possibly moving the “focus” upwards. Moreover, once a
child-to-parent propagation has taken place, the child cannot be revisited in
further steps: this is because existing nodes in the tree that are not
recently updated can only become recently updated again following a
propagation step, which we only allowed from children to parents.

Theorem 5, proven in [7], shows that one-passness can be enforced on chase
proofs for GTGDs: whenever a proof exists, there exists a one-pass proof too.

######  Theorem 5.

For each base instance $I$, each finite set of GTGDs $\Sigma$ and each fact
$F$ such that ${I,\Sigma\models F}$, there exists a one-pass tree-like chase
proof of $F$ from $I$ and $\Sigma$.

##  5\. Proof of the linearization result (Theorem 2)

We can now begin the proof of Theorem 2. The construction we use is a
refinement of the linearization method given in Section 4.2 of Gottlob, Manna,
and Pieris [14].

#### Proof intuition.

Prior to giving the proof, we begin with an overview. There is a pretty
obvious strategy for linearization: introduce a new predicate for each guarded
set of atoms over the side signature, then rewrite the GTGDs into linear ones
over the enhanced signature. The correctness of this transformation is less
evident. We discuss informally what the issue is. Entailment with Guarded TGDs
is captured by the chase process, which forms an instance with a tree-like
shape, as we explained in Section 4. At each chase step we may add new nodes
to the tree, but we may also need to propagate facts up and down the tree.
With linear TGDs, we can use the same process, but _we no longer propagate
facts up and down the tree_ : we simply add on new nodes with a single fact
per node. It could be the case that, in performing this linearization, we are
losing track of the effect of some propagation steps. We need to use the
notion of one-pass chase to justify that this may not happen (specifically,
use Theorem 5), and also need to ensure that the dependencies are _closed_ to
ensure that propagation is unnecessary.

Our proof strategy consists of three steps. First, we explain how to compute a
form of _closure_ of our IDs and full GTGDs, for a bounded domain of side
atoms, which we call bounded _breadth_. This is a kind of query-rewriting
result for atomic query answering (as in [6]), whose correctness is justified
via the one-pass chase. This intuitively ensures that, whenever a full GTGD
generates a fact about earlier elements, then this generation could already
have been performed when these earlier elements had been generated, using an
implied full GTGD. The main difference of our closure with [14] is that we
exploit the width and side signature arity bounds to compute only a portion of
the derived axioms, without bounding the overall signature.

Second, once this closure has been computed, we return to an analysis of the
chase and explain how to structure it further. Specifically, we enforce that
we only fire full GTGDs and their small-breadth closure after having fired a
non-full ID. We call this the _shortcut chase_ , since we shortcut certain
derivations that go up and down the chase tree via the firing of derived
axioms: we thus have a variation of the chase process for GTGDs that is
complete for entailment, but with no propagation steps at all.

Third, with this final normalization result about the chase in hand, we can
turn to linearization. We perform the linearization described informally above
– introduce auxiliary predicates and then rewrite the source GTGDs to use
these predicates. The chase normalization can then be used to argue that the
transformation is correct.

We now give the details.

###  5.1. Bounded breadth closure

The first step of our proof is to show how to compute a closure of the
constraints $\Sigma$. We will now fix the side signature
${\mathcal{S}}^{\prime}$ and its (constant) arity bound $a^{\prime}$, and also
fix the bounds $w,h$ on width and head arity respectively. We will reason
about full GTGDs with side signature ${\mathcal{S}}^{\prime}$ that obey a
certain _breadth_ restriction:

Let $b\in\mathbb{N}$ and let $\gamma$ be a full GTGD on side signature
${\mathcal{S}}^{\prime}$. We say that $\gamma$ has _breadth $\leq b$_ if there
is a choice of guard atom $A$ in the body of $\gamma$ for which all other
atoms are relations of ${\mathcal{S}}^{\prime}$ and there is a choice of a
subset $P$ of at most $b$ positions of $A$ such that, letting $X$ be the
variables that occur in $A$ at positions lying within $P$, the following
_variable occurrences condition_ holds on the body of $\gamma$:

  * •

the body atoms other than $A$ only use variables of $X$;

  * •

the positions of $A$ outside of $P$ use variables that are not in $X$ and
occur only once in the body (i.e., there are no variable repetitions)

In other words, $\gamma$ can then be written:

$A(\vec{x},\vec{y})\wedge\phi(\vec{x})\rightarrow H(\vec{x},\vec{y})$

where $A$ denotes the guard atom, $\phi$ denotes the other body atoms (which
use relations of ${\mathcal{S}}^{\prime}$), $H$ denotes the head atom,
$\vec{x}$ denotes the variables of $X$, the variables of $\vec{y}$ in the body
are not repeated in the body, and the variables $\vec{x}$ occur in at most $b$
positions in $A$.

We compute a bound on the number of GTGDs of a given breadth and head arity.
This bound is why we also need to bound the width, side signature, and head
arity in Corollary 4:

######  Lemma 6.

The number of full GTGDs of breadth $\leq b$ and of head arity $\leq h$ is at
most

$n\cdot(a+1)^{b}\cdot b^{b}\cdot(2^{n^{\prime}\cdot b^{a^{\prime}}})\cdot
n\cdot(a+1)^{h}$

where: $n$ is the number of relations in the full signature ${\mathcal{S}}$,
$a$ is the maximal arity of any relation in ${\mathcal{S}}$, $n^{\prime}$ is
the number of relations in ${\mathcal{S}}^{\prime}$, and $a^{\prime}$ is the
maximal arity of the relations of ${\mathcal{S}}^{\prime}$.

######  Proof 5.1.

To compute this, we illustrate how to choose a full GTGD satisfying the
conditions. Several choices will lead to the same GTGD, but this is not a
problem as we are trying to derive an upper bound.

Here are the choices that we have to make:

  * •

Choose the relation for the guard atom: this gives a factor of $n$.

  * •

Choose the subset $P$ of size $\leq b$: this gives a factor of $(a+1)^{b}$
because an upper bound on this is to choose $b$ positions, with replacement,
and with the option of choosing a dummy position for subsets of size $<b$.

  * •

Choose the pattern of variables on these $P$ positions: this gives a factor of
$b^{b}$, because an upper bound on this is to use a set of $b$ variables and
decide which of these variables to put at each of the (at most) $b$ positions
of $P$.

  * •

Choose the other facts of the body, i.e., a subset of the possible facts: the
corresponding factor is $2^{N}$ where $N$ is the number of possible facts,
which are obtained by choosing a relation of the side signature and choosing a
variable (among the $b$ possible variables) for each position (among
$a^{\prime}$ at most).

  * •

Choose the head atom: this gives a factor of $n$ for the choice of relation,
and a factor $(a+1)^{h}$ to decide, for each of the $\leq h$ positions of this
relation, which body variable to use (of which there are at most $a$).

Hence, the result is indeed the quantity given in the lemma statement.

Observe that, when $b$, $h$, $n^{\prime}$, and $a^{\prime}$ are all constant,
then the above quantity is polynomial in the size of the input signature
${\mathcal{S}}$. Further, when only $a^{\prime}$ is bounded, then the quantity
is singly exponential in the input.

Letting $\Sigma$ be our set of constraints (with non-full IDs of bounded width
and full GTGDs), we say that a full GTGD $\gamma$ is _suitable_ if its head
arity is no greater than the bound $h$ and its breadth is no greater than $w$,
the width bound on the IDs. We say that it is a _derived suitable_ full GTGD
if, further, we have $\Sigma\models\gamma$, that is, any instance that
satisfies $\Sigma$ also satisfies $\gamma$. Note that the derived suitable
GTGDs generally do _not_ include all the full GTGDs that we started with,
because some of them may have breadth larger than $w$.

For our proof of Theorem 2 we will also need to show that the set of derived
suitable full GTGDs can be computed efficiently.

We say that a suitable full GTGD $\gamma$ is _trivial_ if its head atom
already occurs in its body. Given a set of non-full IDs and full GTGDs
$\Sigma$, the _$b$ -closure_ $\widehat{\Sigma}^{b}$ is obtained by starting
with the suitable full GTGDs in $\Sigma$, plus the trivial suitable full
GTGDs, and applying the following inference rules until we reach a fixpoint:

  * •

(Transitivity): Suppose that there is a GTGD body $\beta$ and heads
$B_{1}(\vec{z}_{1})\ldots B_{n}(\vec{z}_{n})$ such that, for each $1\leq j\leq
n$, the full GTGD $\beta\rightarrow B_{j}(\vec{z}_{j})$ has breadth at most
$b$ and is in $\Sigma\cup\widehat{\Sigma}^{b}$. Suppose that there is a full
GTGD $\beta^{\prime}\rightarrow\rho$ in $\Sigma\cup\widehat{\Sigma}^{b}$, and
that there is a unifier $\upsilon$ mapping $\beta^{\prime}$ to
$\beta\wedge\bigwedge_{j}B_{j}(\vec{z}_{j})$. Then add to
$\widehat{\Sigma}^{b}$ the following if it is suitable:

$\beta\rightarrow\upsilon(\rho).$

  * •

(ID): Suppose we have an non-full ID $\delta$ in $\Sigma$ from $R(\vec{x})$ to
$S(\vec{y})$ of width $w^{\prime}\leq b$, which exports $x_{j_{i}}$ to
$y_{k_{i}}$ for $1\leq i\leq w^{\prime}$. Suppose that
$S(\vec{z},\vec{w})\wedge\phi(\vec{w})\rightarrow H(\vec{w})$ is a full GTGD
in $\Sigma\cup\widehat{\Sigma}^{b}$, with the $S$-atom being a guard, such
that the variables of $\vec{w}$ in the $S$-atom occur only at exported
positions of the head of $\delta$, and the variables of the $S$-atom at
positions not exported in the head of $\delta$ contain variables with no
repetitions. Then add to $\widehat{\Sigma}^{b}$ the following:

$R(\vec{z},\vec{w})\wedge\phi(\vec{w})\rightarrow H(\vec{w})$

where the $R$-atom is obtained from the $S$-atom by backwards rewriting via
$\delta$, i.e., its positions at exported positions in the body of $\delta$
contain the variables of the original GTGD at the corresponding exported
position in the head of $\delta$, and the other positions of the $R$-atom
contain fresh variables with no repetitions.

Although $b$ is a parameter of this procedure, we will only consider it with
$b=w$. Clearly, all the GTGDs of $\widehat{\Sigma}^{b}$ are suitable, in
particular the number of variables in their heads are no greater than the
number of variables in the heads of dependencies of $\Sigma$. We claim that in
fact $\widehat{\Sigma}^{b}$ contains all derived suitable full GTGDs:

######  Proposition 7.

For any set $\Sigma$ of non-full IDs of width $\leq w$ and full GTGDs on side
signature ${\mathcal{S}}^{\prime}$ with head arity $\leq h$, then
$\widehat{\Sigma}^{w}$ is the set of derived suitable full GTGDs.

Before we prove this claim, we state and prove that the computation of the
$b$-closure can be performed efficiently:

######  Lemma 8.

There is a polynomial $P$ such that, for any set $\Sigma$ of non-full IDs of
width $\leq w$ and full GTGDs on side signature ${\mathcal{S}}^{\prime}$ with
head arity $\leq h$, letting $b\colonequals w$ and letting $a$ be the arity of
the signature, we can compute $\widehat{\Sigma}^{b}$ in time
$(\left|\Sigma\right|\times a)^{P(w,h)}$.

######  Proof 5.2.

From our bound in Lemma 6, and knowing that the full GTGDs in the closure are
suitable, we know that the maximal size of $\widehat{\Sigma}^{b}$ satisfies
our running time bound. We can compute it by iterating the possible production
of rules until we reach a fixpoint, so it suffices to show that at each
intermediate state of $\widehat{\Sigma}^{b}$, testing every possible rule
application is in PTIME in the current $\widehat{\Sigma}^{b}\cup\Sigma$.

For (ID), this is straightforward: we simply try every ID from $\Sigma$ and
every rule from the current $\widehat{\Sigma}^{b}$ unioned with $\Sigma$, and
we check whether we can perform the backwards rewriting (which is clearly
PTIME), in which case we add the result to $\widehat{\Sigma}^{b}$.

For (Transitivity), we enumerate all possible bodies $\beta$ of suitable
GTGDs: there are polynomially many, up to renaming the variables to have
canonical names. For each $\beta$, we then find all rules in $\Sigma$ and in
$\widehat{\Sigma}^{b}$ that have body $\beta$ up to variable renaming. To do
this, there are two cases. First, if $\beta$ only contains
${\mathcal{S}}^{\prime}$-atoms, then we can just test the homomorphism because
the guard of $\beta$ has constant arity so the domain of $\beta$ has constant
size. Second, if $\beta$ contains an atom not in ${\mathcal{S}}^{\prime}$, by
assumption there is only one and it is a guard, so we can just consider the
GTGDs whose body contains such an atom, try to unify the atom with $\beta$ in
PTIME, and check if the candidate body achieves exactly the side atoms of
$\beta$.

Once we have identified all suitable GTGDs having body $\beta$ up to variable
renaming, clearly we can take $1\leq j\leq n$ to range over all such GTGDs,
and consider the union $H$ of their heads. Now, we enumerate all GTGDs in
$\Sigma\cup\widehat{\Sigma}^{b}$ and we must argue that we can test in PTIME
whether their body $\beta^{\prime}$ unifies to $\beta\cup H$. There are again
two cases. First, if $\beta^{\prime}$ contains only atoms from
${\mathcal{S}}^{\prime}$, we can again test all possible mappings of
$\beta^{\prime}$ because the domain of $\beta^{\prime}$ has constant size so
there are only polynomially many. Second, if $\beta^{\prime}$ contains an atom
$A$ not in ${\mathcal{S}}^{\prime}$, we consider all atoms in $\beta\cup H$
which are not in ${\mathcal{S}}^{\prime}$, and test in PTIME for each of them
whether $A$ unifies with it and if the mapping thus defined is a homomorphism
from $\beta^{\prime}$ to $\beta\cup H$. In both cases, if $\beta^{\prime}$
unifies to $\beta\cup H$, we add the new full GTGD to $\widehat{\Sigma}^{b}$.
This concludes the proof.

Recall that our near-term goal is show that we can compute the derived
suitable full GTGDs within certain bounds. Thus far we have shown that we can
compute the $w$-closure in the required bounds. What remains toward the goal
above is to prove Proposition 7, i.e., to show that the closure captures the
required derived suitable GTGDs. For this, we will need to use the machinery
of the one-pass chase, which we developed in Section 4:

######  Proof 5.3 (Proof of Proposition 7).

One direction is straightforward: we can immediately show by induction on the
derivation that any GTGD produced in the closure is indeed a derived suitable
full GTGD. Hence, we focus on the converse direction.

We prove that every derived suitable full GTGD is produced in the closure, by
induction on the number of chase steps in a one-pass chase proof of its head
from its body. Specifically, let the derived suitable full GTGD be
$\gamma:R(\vec{x},\vec{y})\wedge\left(\bigwedge_{i}A_{i}(\vec{x})\right)\rightarrow\lambda(\vec{z})$,
with $\vec{z}\subseteq\vec{x}\cup\vec{y}$. Let $K_{0}$ be a set of constants,
and $I_{0}$ be the initial instance which consists of the instantiation of the
body of $\gamma$ on $K_{0}$: we let $\vec{a}_{0},\vec{b}_{0},\vec{c}_{0}$ be
the tuples of $K_{0}$ corresponding to $\vec{x}$, $\vec{y}$, $\vec{z}$, let
$\mu$ be the mapping from the variables $\vec{x}\cup\vec{y}$ to
$\vec{a_{0}}\cup\vec{b_{0}}$ defined accordingly, and call
$F_{0}=R(\vec{a_{0}},\vec{b_{0}})$ the instantiation of the guard atom, which
is a fact in the root node of the chase tree and which guards the facts of
this node. We show that $\gamma$ is produced in the closure by induction on
the number of chase steps (not counting propagation steps) required in a one-
pass chase proof to produce $\lambda_{0}\colonequals\lambda(\vec{c}_{0})$ from
$I_{0}$. The fact that we can assume a one-pass chase proof is thanks to
Theorem 5. A fact that was produced by firing an ID will be referred to as an
_ID -fact_: note that it clearly always guards all facts of its node. We also
consider $F_{0}$ to be an ID-fact.

The base case is when there is a one-pass chase proof of length $0$, i.e.,
$\lambda_{0}$ is in $I_{0}$. In this case, $\gamma$ is a trivial suitable
GTGD, so it is in the closure by construction.

We now show the induction case. We consider a one-pass chase proof that adds
$\lambda_{0}$ to $I_{0}$ in as few chase steps as possible. The firing that
produces $\lambda_{0}$ cannot be the firing of an ID, because the IDs are non-
full, so they produce facts that contain some null whereas $\lambda_{0}$ is a
fact on $K_{0}$. Hence, $\lambda_{0}$ is produced by firing a full GTGD
$\gamma^{\prime}$ on a trigger $\psi$ (possibly followed by a succession of
propagation steps, which are not counted). Let $F$ be the ID-fact that guards
$\psi$ and is the topmost one in the chase: note that all facts of $\psi$ are
present in the node of $F$, i.e., in the one-pass chase they have been
propagated to that node once created. Either $F=F_{0}$ or $F$ is a strict
descendant of $F_{0}$.

If $F$ is $F_{0}$, then it means that $F_{0}$ guards this firing. Hence, all
facts of $\psi$ are facts over $K_{0}$. We know that each such fact $\phi$
over the constants $K_{0}$ was derived in the chase from $I_{0}$ (possibly
trivially, i.e., possibly with 0 steps), so that, letting $\phi^{\prime}$ be
obtained from $\phi$ by replacing constants by variables (i.e., the preimage
by $\mu$), the GTGD
$\gamma_{\phi}:R(\vec{x},\vec{y})\wedge\left(\bigwedge_{i}A_{i}(\vec{x})\right)\rightarrow\phi^{\prime}$
is a derived full suitable GTGD. In particular it satisfies the variable
occurrences condition because it has the same body as $\gamma$ which does.
Further, this derived full suitable GTGD is witnessed by a one-pass chase with
strictly less steps. Hence, by induction hypothesis, each $\gamma_{\phi}$ is
in the closure. We can now see that, as $\gamma^{\prime}\in\Gamma$, as the
$\gamma_{\phi}$ are in the closure, we can apply the (Transitivity) rule and
conclude that $\gamma$ is also in the closure.

Now, consider the case where the ID-guard $F$ of the firing is a strict
descendant of $F_{0}$ in the chase tree. In this case we must have performed
propagation steps after the firing. We consider the path in the chase tree
from $F_{0}$ to $F$. Let $F^{\prime}$ be the ID-fact which is the first
element of this path after $F_{0}$: it is a child of $F_{0}$ and an ancestor
of $F$. Let $\vec{c}$ be the elements shared between $F^{\prime}$ and $F_{0}$.
Let $\Phi$ be the set of facts on the elements $\vec{c}$ that were created
when the fact $F^{\prime}$ was created. The fact $\lambda_{0}$ is not part of
$\Phi$ and was created later in the chase. It is, however, a fact on
$\vec{c}$: specifically it is a fact on $K_{0}$ with ID-guard $F$, hence on
the elements shared between $F_{0}$ and $F$, which are a subset of those
shared between $F_{0}$ and $F^{\prime}$. Now, by definition of the one-pass
chase, we know that after the creation of $F^{\prime}$, no new facts on
$\vec{c}$ were created in the subtree rooted at $F^{\prime}$, as these would
have been propagated upwards as long as possible, i.e., until $F$, and the
subtree rooted at $F^{\prime}$ would no longer be active, contradicting the
fact that $\lambda_{0}$ is derived there later.

Thus, if we start the chase with the ID-fact $F^{\prime}$ plus the set $\Phi$,
then we can also deduce $\lambda_{0}$, because all derivations in the one-pass
chase between the creation of $F^{\prime}$ and the propagation of
$\lambda_{0}$ from $F^{\prime}$ to $F_{0}$ must happen in that subtree. Thus,
letting $\beta^{\prime}$ be the result of replacing constants by variables
(i.e., taking the preimage by $\mu$) of $\\{F^{\prime}\\}\cup\Phi$, this shows
that $\gamma^{\prime}:\beta^{\prime}\rightarrow\lambda$ is entailed by
$\Sigma$. Now, this is a GTGD with breadth at most $w$ because the width of
IDs (and hence the cardinality of $\vec{c}$, and hence of the domain of
$\Phi$) is at most $w$. Hence, $\gamma^{\prime}$ is a derived suitable full
GTGD, and the proof for this derived suitable full GTGD is shorter than that
of $\gamma$. By induction hypothesis, we have
$\gamma^{\prime}\in\widehat{\Sigma}^{b}$. We can now apply (ID) to
$\gamma^{\prime}$ with the IDs that generated $F^{\prime}$ from $F_{0}$,
thanks to the fact that $\Phi$ and $\lambda_{0}$ are on $K_{0}$ so they are on
exported positions of the ID, and there cannot be repeated variables in the
atom corresponding to $F^{\prime}$ in $\beta^{\prime}$ except at positions
that were exported between $F^{\prime}$ and $F_{0}$ (because these other
elements are fresh in $F^{\prime}$). The application of rule (ID) yields
$\gamma^{\prime\prime}:R(\vec{x},\vec{y})\wedge\Phi^{\prime}(\vec{z})\rightarrow\lambda(\vec{z})$,
where $\Phi^{\prime}$ is the result of renaming the constants of $\Phi$ to
variables by taking the preimage by $\mu$.

We now argue as in the first case of $F=F_{0}$ that, as each fact of $\Phi$
was derived from $I_{0}$ with a shorter proof than the proof of $\gamma$, by
the induction hypothesis, for each $\phi\in\Phi$, the derived suitable full
GTGD
$R(\vec{x},\vec{y})\wedge\left(\bigwedge_{i}A_{i}(\vec{x})\right)\rightarrow\phi$
is in $\widehat{\Sigma}^{b}$. We conclude, by applying (Transitivity) to
$\gamma^{\prime\prime}$ and these derived suitable full GTGDs, that
$\gamma\in\widehat{\Sigma}^{b}$.

Hence, we have shown that $\gamma$ was derived, which concludes the induction
and finishes the completeness proof.

###  5.2. Making the chase similar to a linear chase

We are now ready for the second stage of our proof. Thus far we have used an
analysis of the tree-like chase to design an algorithm to compute the closure
of a set of GTGDs. If we were interested only in query answering for atomic
queries, it would suffice to take these full TGDs and run them as a Datalog
program, thus replacing the chase completely. For general CQ query answering
it is also possible to reduce the query answering process to applying a set of
full TGDs: see, for example [bbcjsl]. But this would not get us improved
bounds. Instead we will assume that we still use a tree-like chase to do query
answering, but look at the impact of adding all of these derived GTGDs on the
chase process. Recall that in the tree-like chase we have chase steps and
propagation steps. We argue that the chase can be “normalized” so that there
are _no propagation steps at all_. To do that we will add _shortcuts_ which
summarize the impact of chase steps combined with propagation steps.

The _shortcut chase_ works by constructing _bags_ : a _bag_ is a set of facts
consisting of one fact generated by an ID (called an _ID -fact_) and facts on
the domain of the ID-fact (called _full facts_). We will have a tree structure
on bags that corresponds to how they are created.

The shortcut chase then consists of two alternating kinds of steps:

  * •

The _ID steps_, where we fire an ID on an ID-fact $F$ where it is applicable.
Let $g$ be the bag of $F$. The ID step creates a new bag $g^{\prime}$ which is
a child of $g$, which contains the result $F^{\prime}$ of firing the ID, along
with a copy of the full facts of $g$ which only use elements shared between
$F$ and $F^{\prime}$.

  * •

The _full saturation steps_ , which apply to a bag $g$, only once per bag,
precisely at the moment where it is created by an ID step (or on the root
bag). In this step, we apply all the full GTGDs of $\widehat{\Sigma}^{w}$ to
the facts of $g$, and add the consequences to $g$ (they are still on the
domain of $g$ because the rules are full).

Our next goal is to argue that the shortcut chase is as good as the usual
chase in terms of query answering. The shortcut chase consists of chase steps
in the usual sense, so it is still universal. What is not obvious is that the
infinite result of the shortcut chase satisfies $\Sigma$: indeed, we must
argue that all violations would have been addressed by a chase step. This is
not straightforward, because the shortcut chase does not consider all
triggers: specifically, for full GTGDs, it only considers triggers that are
entirely contained in a bag, and only for full GTGDs in $\widehat{\Sigma}^{w}$
(not those in $\Sigma$). So what we must do is argue that the shortcut chase
does not leave any violations. The intuition for this is that, as we are
chasing with the closure $\widehat{\Sigma}^{w}$, all violations can be
witnessed within a bag.

To show this formally, we will rely on the following observation, which uses
the closure $\widehat{\Sigma}^{w}$. In the statement of this lemma, we talk of
the _topmost bag_ that contains a guarded tuple: it is obvious by considering
the domains of the bags that this is well-defined:

######  Lemma 9.

Consider the shortcut chase on an instance $I_{0}$ which is closed under the
full GTGDs of $\Sigma$ and of $\widehat{\Sigma}^{w}$ (we see $I_{0}$ as a root
bag). Assume that a full saturation step on some bag $g$ creates a fact $F$.
Then $g$ is the topmost bag of the chase tree that contains the elements of
$F$.

######  Proof 5.4.

Let $g^{\prime}$ be the topmost bag of the chase tree that contains all
elements of $F$, and let us show that $F$ was created in $g^{\prime}$.
Consider the moment in the chase where $g^{\prime}$ was created in an ID step.
At this moment, $g^{\prime}$ consists of its ID-fact plus full facts copied
over from the parent of $g^{\prime}$ (or none, in the case where $g^{\prime}$
is the root): as the IDs have width $\leq w$, these full facts are on a domain
$\vec{c}$ of size at most $w$. We let $\beta$ be the set of these facts, i.e.,
the ID-facts and the full facts. As the shortcut chase proceeds entirely
downwards in the tree, and it constructs a subset of the usual chase, by
starting the chase with a root bag containing $\beta$, we know that $F$ is
deduced. Hence, letting $\beta^{\prime}$ and $F^{\prime}$ be the result of
renaming the elements of $\beta$ and $F$ to variables, we know that the GTGD
$\gamma:\beta^{\prime}\rightarrow F^{\prime}$ is entailed by
$\widehat{\Sigma}^{w}$. Hence, $\gamma$ is a derived suitable full GTGD, so we
must have $\gamma\in\widehat{\Sigma}^{w}$. Thus, we have also applied $\gamma$
in the full saturation step just after the moment where we created
$g^{\prime}$; or, if $g^{\prime}$ is the root bag, it is closed under $\Sigma$
and under $\widehat{\Sigma}^{w}$ by hypothesis. Hence, we have shown that $F$
was indeed created in $g^{\prime}$, which concludes.

This immediately implies the following:

######  Corollary 10.

For any fact $F$ created in the shortcut chase, for any bag $g$ containing all
elements of $F$, then $F$ appears in the bag $g$.

######  Proof 5.5.

First consider the case where $F$ is an ID-fact, i.e., it was created by
applying a chase step with a non-full ID. In this case, $F$ contains a null,
and the topmost bag $g$ containing all elements of $F$ is the bag where this
null was introduced, so it also contains $F$. Now, the bags that contain the
elements of $F$ form a subtree of the tree on bags rooted at $g$, and $F$ is
copied in all these bags.

If $F$ is a full fact, we use Lemma 9 to argue that $F$ occurs in the topmost
bag containing all its elements, and again $F$ is copied in all other bags.

This allows us to show that the shortcut chase is equivalent to the usual
chase: that is, it is a complete proof system for query answering.
Specifically, let $I_{0}$ be an arbitrary set of facts, which we consider as a
root bag, and which has been closed under the full GTGDs of $\Sigma$ and of
$\widehat{\Sigma}^{w}$. Let $I$ be the result of the shortcut chase of $I_{0}$
by $\widehat{\Sigma}^{w}$. We claim:

######  Lemma 11.

$I$ satisfies $\Sigma$.

######  Proof 5.6.

Consider a trigger $\psi$ in $I$ for a dependency $\gamma$ of $\Sigma$, and
show that it is not active. All rules in $\Sigma$ are guarded, so the domain
of $\psi$ is guarded, and there is a topmost bag $g$ where all elements of
$\psi$ appear. By Corollary 10, all facts of $\psi$ are reflected in all bags
where all their elements appear, in particular they are all reflected in $g$.
Hence, $\psi$ is included in a single bag $g$.

It is clear that any trigger for an ID would have been fired, so we can assume
that $\psi$ is a trigger for a full GTGD of $\Sigma$. Let $\psi^{\prime}$ be
the instantiation of the head of $\gamma$, i.e., the fact that we would create
by firing the trigger $\psi$, and let us show that $\psi^{\prime}$ is already
present in $I$. As we assumed that $I_{0}$ is closed under $\Sigma$, the bag
$g$ cannot be the root bag, and was created by an ID step. At this point, $g$
contained only an ID-fact plus ${\mathcal{S}}^{\prime}$-facts on a domain of
size at most $w$, thanks to the fact that the IDs have width at most $w$. All
further facts created in $g$ are created by the full saturation step. Hence,
all the facts of the trigger $\psi$ are entailed by the initial contents of
$g$, and its head $\psi^{\prime}$ also is. This means that the corresponding
full GTGD $\gamma^{\prime}$ is a derived suitable full GTGD because its
breadth is bounded by $b$. Specifically, the variable occurrences condition is
respected because the elements of the ID-fact of $g$ cannot be repeated
outside of the positions that contain elements exported from the parent fact
of $g$.

Now, as we have applied a full saturation step on $g$, the trigger $\psi$ for
$\gamma^{\prime}$ has been fixed in this step, creating $\psi^{\prime}$ in
$I$. This shows that $\psi$ is not active in $I$ and concludes the proof.

We now know that the result $I$ of the shortcut chase satisfies $\Sigma$, and
as the shortcut chase only applies chase steps, it is actually equivalent to
the chase:

######  Theorem 12.

For any instance $I_{0}$ closed under the full GTGDs of $\Sigma$ and of
$\widehat{\Sigma}^{w}$, for any CQ $Q$, then $Q$ is satisfied in the shortcut
chase of $I_{0}$ iff $I_{0},\Sigma\models Q$.

All that remains now is to translate the shortcut chase to a set of linear
TGDs.

###  5.3. The final stage: Linearization and its justification

We now describe the third and last stage of the proof of Theorem 2. We
describe the translation to a set of linear TGDs, intuitively introducing
predicates for each guarded sets of atoms on the side signature; and also
describe the pre-processing of the instance, intuitively closing under these
dependencies. The correctness of this transformation will then be argued using
the shortcut chase.

Fix a tuple $x_{1},\ldots,x_{n}$ of variables. For every relation $R$ of arity
$l$, for every subset $P=\\{p_{1}\ldots p_{k}\\}$ of its positions of size at
most $w$, for every instance $\chi$ of the relations of
${\mathcal{S}}^{\prime}$ on $x_{p_{1}}\ldots x_{p_{k}}$, we create a copy
$R_{P,\chi}$ of $R$. Observe that this creates a singly exponential number of
relations when the arity $a^{\prime}$ of ${\mathcal{S}}^{\prime}$ is fixed,
and it creates only polynomially many relations when we further fix $w$ and
the full side signature ${\mathcal{S}}^{\prime}$. We let $\Theta$ consist of
the following linear GTGDs:

  * •

Instantiate: for every relation $R_{P,\chi}$, for every homomorphism $h$ from
$x_{1},\ldots,x_{l}$ to itself which maps $P$ to $P$ (not necessarily as the
identity) and is the identity outside of $P$, let $\chi^{\prime}$ be the
instance on $x_{1}\ldots x_{n}$ obtained by starting with $R(h(\vec{x}))\cup
h(\chi)$ and then repeatedly applying the full TGDs of $\widehat{\Sigma}^{w}$
(a full saturation step). Then for every fact $S(\vec{y})$ of $\chi^{\prime}$
(with $\vec{y}\subseteq h(\vec{x})$), we add the full GTGD:

$R_{P,\chi}(h(\vec{x}))\rightarrow S(\vec{y})$

Note that in particular we always have the TGD:

$R_{P,\chi}(h(\vec{x}))\rightarrow R(h(\vec{x}))$

  * •

Lift: for every relation $R_{P,\chi}$, for every homomorphism $h$ as above,
let $\chi^{\prime}$ be as above. For every ID $\delta$
$S(\vec{y})\rightarrow\exists\vec{z}~{}T(\vec{y},\vec{z})$, for every match
$h^{\prime}$ of $S(\vec{y})$ in $\chi^{\prime}$, let
$P^{\prime}=\\{p_{1}^{\prime},\ldots,p_{k^{\prime}}^{\prime}\\}$ be the
exported positions of $\delta$ in $\vec{y}$. Let $\chi^{\prime\prime}$ be the
restriction of $\chi^{\prime}$ to
$h^{\prime}(y_{p_{1}^{\prime}}),\ldots,h^{\prime}(y_{p_{k^{\prime}}^{\prime}})$,
and let $P^{\prime\prime}$ be the corresponding exported positions in the head
of $\delta$. Then we add the linear GTGD:

$R_{P,\chi}(h(\vec{x}))\rightarrow\exists\vec{z}~{}T_{P^{\prime},\chi^{\prime\prime}}(h^{\prime}(\vec{y}),\vec{z})$

######  Example 5.7.

Let $\Sigma$ consist of the ID $R(x,y)\rightarrow\exists z~{}R(y,z)$ and the
Full GTGD $R(x,y)\wedge U(x)\rightarrow U(y)$.

Our side signature here will consist of only $U$. Let $w=1$, so we will be
considering subsets of the positions $\\{1,2\\}$ of $R$ of size $1$. Our sets
$\chi$ will thus include:

  * •

$\chi_{1}$ on position $1$ with fact $U(1)$

  * •

$\chi_{2}$ on position $2$ with fact $U(2)$

as well as several degenerate examples (with empty set of side signature
facts). We will then have auxiliary predicate $R_{\chi_{1}},R_{\chi_{2}}$
$\ldots$, each of arity $2$.

The rule (instantiate) will give us full GTGDs such as:

$\displaystyle R_{\chi_{1}}(x,y)\rightarrow U(y)$ $\displaystyle
R_{\chi_{1}}(x,y)\rightarrow R(x,y)$

The inference rule (Lift) will provide us with full GTGDs such as

$R_{\chi_{2}}(x,y)\rightarrow\exists z~{}R_{\chi_{1}}(y,z)$

The result of this transformation clearly consists of linear TGDs. Further,
they are of semi-width $w$: indeed, the rules produced by the Lift
transformation have width bounded by $w$, and the rules produced by
Instantiate have an acyclic position graph.

Having computed $\widehat{\Sigma}^{w}$, these rules can be computed in
polynomial time in their number, and this number indeed satisfies the bound
required in the statement of Theorem 2. Indeed, let us verify this, similarly
to the bound shown in Lemma 6. Let $n$ be the number of relations of the
signature, $a$ the maximal arity of the signature, $n^{\prime}$ the number of
relations in the side signature, $h$ the head arity, and $a^{\prime}$ the
maximal arity of the side signature. We can then bound the number of relations
$R_{P,\chi}$ by choosing the relation $R$ (a factor of $n$), choosing the
subset $P$ (a factor of at most $(a+1)^{w}$), and choosing the subset $\chi$
(a factor of at most $2^{n^{\prime}\cdot(w+1)^{a^{\prime}}}$). Now, the number
of homomorphisms in Instantiate rules given the choice of $R_{P,\chi}$ is
bounded by $w^{w}$, and their number of possible heads is bounded by
$(a+1)^{h}$ (the number of facts that can be created by the TGDs of
$\widehat{\Sigma}^{w}$ which have head arity $\leq h$) plus one (for the fact
$R(h(\vec{x}))$). Further, the number of Lift rules is bounded by the number
of relations $R_{P,\chi}$ (bounded above), times the number of homomorphisms
(i.e., $w^{w}$), times $(a+1)^{w}$ for the choice of $P^{\prime}$, times the
number of relations $T_{P^{\prime},\chi^{\prime\prime}}$ for the choice of
head. Hence, having fixed the arity $a^{\prime}$ of the side signature, there
are indeed fixed polynomials $P_{1}$ and $P_{2}$ such that the number of
rules, and the time to construct them, is in
$P_{1}(\left|\Sigma\right|,a^{P_{2}(w,h,n^{\prime})})$.

We have described the construction of $\Sigma^{\prime}$. Now, to construct the
rewriting $I_{0}^{\mathsf{Lin}}$ of $I_{0}$, we first construct the instance
$I_{1}$ by closing $I_{0}$ under the full GTGDs of $\Sigma$ and of
$\widehat{\Sigma}^{w}$. To see why $I_{1}$ can be computed in the prescribed
bound, we can assume that we have computed $\widehat{\Sigma}^{w}$ as we
already know that it can be computed in the given time bound (Lemma 8), so we
need only reason about the complexity of applying the rules. Now, note that
the domain size does not increase, and the number of possible new facts is
bounded by $\left|{\mathsf{Adom}}(I_{0})\right|^{h}$. Now, testing each
possible rule application is in PTIME. Indeed, it amounts to homomorphism
testing between the body of a full GTGD and $I_{0}$, for which it suffices to
consider the guard atom, trying to map it to every fact of $I_{0}$, and then
check whether the function that this defines is a homomorphism from the entire
body to $I_{0}$.

Now we construct $I_{0}^{\mathsf{Lin}}$ from $I_{1}$ by considering every fact
$R(\vec{a})$ of $I_{1}$, considering every subset of positions $P$ of
$\vec{a}$ of size at most $w$, and adding the fact $R_{P,\chi}(\vec{a})$,
where $\chi$ is constructed from the restriction of $I_{1}$ to
$a_{p_{1}},\ldots,a_{p_{k}}$ for $P=\\{p_{1},\ldots,p_{k}\\}$. Formally,
remembering that we fixed a tuple of variables $x_{1},\ldots x_{n}$ of
variables, letting $h$ be a homomorphism from $x_{p_{1}},\ldots,x_{p_{k}}$ to
$a_{p_{1}},\ldots,a_{p_{k}}$, we add to $\chi$ every fact $R(\vec{y})$ such
that $R(h(\vec{y}))$ is in $I_{1}$. Note that, if $\vec{a}$ contains duplicate
elements, then $h$ is not injective, so we add multiple copies in $\chi$ for
every fact of $I_{1}$ with domain in $\\{a_{p_{1}},\ldots,a_{p_{k}}\\}$. This
still respects the time bounds, because it is doable in PTIME in
$|I_{1}|^{w}$.

The last thing to show is that, on the resulting $I_{0}^{\mathsf{Lin}}$, the
shortcut chase is equivalent to the chase by $\Theta$. Since the shortcut
chase captures entailment (Theorem 12), showing this is sufficient to
conclude.

To see this, consider the shortcut chase where each bag is annotated by the
relation for the ID-fact that created it, the subset of positions of the
elements that it shared with its parent, and the subinstance that was copied
by the parent; and consider the chase by the rules of the form Lift in
$\Theta$. We can observe by a straightforward induction that the tree
structure on the bags of the shortcut chase with the indicated labels is
isomorphic to the tree of facts of the form $R_{P,\chi}(\vec{x})$ created in
the chase by the Lift rules. Now, the applications of the rules Instantiate
create precisely the facts contained in these bags, so this shows that the
chase by $\Theta$ and the shortcut chase create precisely the same facts.

This shows that $\Theta$ satisfies indeed the hypotheses of Theorem 2, and
concludes the proof.

##  6\. Conclusion

In this work we have given finer bounds on query answering with GTGDs, based
on the notion of side signature. In addition to justifying claims in prior
papers, we believe it is a good example of the use of the linearization
technique from [14], and of the recently-developed notion of the one-pass
chase. We think this combination can be used to get finer-grained bounds for
query answering for other TGD classes, such as frontier-guarded.

When we do not impose any width bound, but merely fix the side signature
arity, we show an ${\mathsf{EXPTIME}}$ bound. Not only is the problem for this
class ${\mathsf{EXPTIME}}$-complete, but there is an
${\mathsf{EXPTIME}}$-hardness result in [4] for the case with the simplest
possible fixed side signature: one unary predicate. In that sense, our result
is optimal. However, we suspect our ${\mathsf{NP}}$ upper bound is not
optimal. The ${\mathsf{NP}}$ upper bound result requires us to fix the side
signature, bound the width of non-full IDs, and also bound the head arity
(hence the width) of the full ${\mathsf{GTGD}}$s. We believe that the same
${\mathsf{NP}}$ bound would hold if we consider single-headed GTGDs with fixed
side signature, bounding the width of both the full and non-full GTGDs. This
would allow the non-full GTGDs to be linear TGDs rather than IDs. A proof
would naturally involve modifying our saturation procedure. We believe that
one can relax the variable occurrence condition in the definition of breadth
to allow guard atoms featuring equality patterns on variables without side
signature atoms, provided that they follow the equalities in the head of some
dependency. We leave the details of this verification for future work.

Our results give new classes where ${\mathsf{OWQA}}$ is in
${\mathsf{EXPTIME}}$ and new cases where it is in ${\mathsf{NP}}$. We do not
provide larger classes where the complexity is in ${\mathsf{PSPACE}}$: this is
a bit surprising, and is one area of particular interest for future work.
Indeed, the canonical example where ${\mathsf{OWQA}}$ is in
${\mathsf{PSPACE}}$ is when TGDs are linear, and our technique works by
reducing to that case.

## References

  * [1] A. Amarilli and M. Benedikt.  When can we answer queries with result-limited methods.  PODS, 2018.
  * [2] A. Amarilli and M. Benedikt.  When can we answer queries with result-limited methods.  LMCS, 2022.
  * [3] J. Baget, M. Leclère, and M. Mugnier.  Walking the decidability line for rules with existential variables.  In KR, 2010.
  * [4] V. Bárány, M. Benedikt, and P. Bourhis.  Access patterns and integrity constraints revisited.  In ICDT, 2013.
  * [5] M. Benedikt, P. Bourhis, L. Jachiet, and M. Thomazo.  Reasoning about disclosure in data integration in the presence of source constraints.  In IJCAI, 2019.
  * [6] M. Benedikt, M. Buron, S. Germano, K. Kappelmann, and B. Motik.  Rewriting the infinite chase.  PVLDB, 2022.
  * [7] M. Benedikt, M. Buron, S. Germano, K. Kappelmann, and B. Motik.  Rewriting the infinite chase, 2022.  https://krr-oxford.github.io/Guarded-saturation/.
  * [8] A. Calì, G. Gottlob, and M. Kifer.  Taming the infinite chase: Query answering under expressive relational constraints.  JAIR, 2013.
  * [9] A. Calì, G. Gottlob, and T. Lukasiewicz.  A general Datalog-based framework for tractable query answering over ontologies.  Journal of Web Semantics, 14, 2012.
  * [10] A. Calì, G. Gottlob, and A. Pieris.  Towards more expressive ontology languages: The query answering problem.  Artif. Intell., 193, 2012.
  * [11] A. Calì, D. Lembo, and R. Rosati.  Query rewriting and answering under constraints in data integration systems.  In IJCAI, 2003.
  * [12] A. Deutsch, B. Ludäscher, and A. Nash.  Rewriting queries using views with access patterns under integrity constraints.  TCS, 371(3), 2007.
  * [13] R. Fagin, P. G. Kolaitis, R. J. Miller, and L. Popa.  Data exchange: Semantics and query answering.  TCS, 336(1), 2005.
  * [14] G. Gottlob, M. Manna, and A. Pieris.  Polynomial combined rewritings for existential rules.  In KR, 2014.
  * [15] G. Gottlob, M. Manna, and A. Pieris.  Multi-head guarded existential rules over fixed signatures.  In Proceedings of the International Conference on Principles of Knowledge Representation and Reasoning, volume 17, pages 445–454, 2020.
  * [16] D. S. Johnson and A. C. Klug.  Testing containment of conjunctive queries under functional and inclusion dependencies.  JCSS, 28(1), 1984.
  * [17] K. Kappelmann.  Decision procedures for guarded logics, 2019.  https://arxiv.org/abs/1911.03679.
  * [18] T. Lukasiewicz, M. V. Martinez, A. Pieris, and G. I. Simari.  From classical to consistent query answering under existential rules.  In Twenty-Ninth AAAI Conference on Artificial Intelligence, 2015\.

##  Appendix A Proof of the Semi-Width Result (Proposition 2)

In this appendix, we prove the ${\mathsf{NP}}$ bound on containment for
bounded semi-width linear TGDs, i.e., Proposition 2. Recall its statement:

See 2

The proof presented here is the same as in [2, Appendix C], except that to go
from IDs to linear TGDs we must change the statement of proof of Lemma 14. The
proof is otherwise identical up to minor changes.

To prove the result, let $\Sigma$ be the collection of linear TGDs. We will
reason about the tree-like sequences (see Section 4) that can be obtained
starting with some instance $I_{0}$. We modify the definition in this appendix
in the following way: we do not perform propagation steps (they are never
needed), and when performing a chase step we will handle the case of full or
non-full TGDs $\tau$ in the same way: we always proceed as in the case of non-
full TGDs, i.e., we always create a new child $v^{\prime}$ of the vertex $v$
to contain the new fact. This ensures that, in the tree-like chase sequences
that we consider, the root node always contain precisely the facts of $I_{0}$,
and the non-root nodes contain precisely one fact and are in one-to-one
correspondence with the facts that we generate. Further, if we fired a trigger
$\psi=\\{F\\}$ to create a fact $F^{\prime}$, then the node $n^{\prime}$
created by applying the chase step so that $T(n^{\prime})=\\{F^{\prime}\\}$ is
a child of the node $n$ such that $T(n)=\\{F\\}$.

Let us now consider a chase tree $T$ within some tree-like chase proof
starting with $I_{0}$. A _generated fact_ in $T$ is a fact which is not a fact
of $I_{0}$. Let us now consider nodes $n$ and $n^{\prime}$ in $T$, with $n$ a
strict ancestor of $n^{\prime}$. We say $n$ and $n^{\prime}$ are _far apart_
if there are distinct generated facts $F_{1}$ and $F_{2}$ such that:

  * •

the node $n_{1}$ corresponding to $F_{1}$ and the node $n_{2}$ corresponding
to $F_{2}$ are both ancestors of $n^{\prime}$ and descendants of $n$;

  * •

$n_{1}$ is an ancestor of $n_{2}$;

  * •

$F_{1}$ and $F_{2}$ were generated by the same rule of $\Sigma$; and

  * •

the equalities between values in positions within $F_{1}$ are exactly the same
as the equalities within $F_{2}$, and any values occurring in both $F_{1}$ and
$F_{2}$ occur in the same positions in $F_{1}$ and $F_{2}$.

If $n$ and $n^{\prime}$ are not far apart, we say that they are _near_.

Given a match $h$ of $Q$ in the chase tree $T$, its _augmented image_ is the
closure of its image under least common ancestors, including by convention the
root node. If $Q$ has size $k$ then this has size $\leq 2k+1$. For any two
nodes $n$ and $n^{\prime}$ in the augmented image, we call $n$ the _image
parent of_ $n^{\prime}$ if $n$ is the lowest ancestor of $n^{\prime}$ in the
augmented image.

######  Lemma 13.

If $Q$ has a match $h$ in the final chase tree $T$ of a tree-like chase
sequence, then there is another tree-like chase sequence with final tree
$T^{\prime}$, and a match $h^{\prime}$ of $Q$ in $T^{\prime}$ with the
property that if $n$ is the image parent of $n^{\prime}$ then $n$ and
$n^{\prime}$ are near.

######  Proof A.1.

We prove that given such an $h$ and $T$, we can construct an $h^{\prime}$ and
$T^{\prime}$ such that we decrease the sum of the depths of the violations.

If $n$ is far apart from $n^{\prime}$, then there are witnesses $F_{1}$ and
$F_{2}$ to this, corresponding to nodes $n_{1}$ and $n_{2}$ respectively.
Informally, we will “pull up” the homomorphism by replacing witnesses below
$F_{2}$ with witnesses below $F_{1}$. Formally, we create $T^{\prime}$ by
first removing each step of the chase proof that generates a node that is a
descendent of $n_{1}$. Letting $T_{1}$ be the nodes in $T$ that do not lie
below $n_{1}$, we will add nodes and the associated proof steps to
$T^{\prime}$. Let $C_{2}$ be the chase steps in $T$ that generate a node below
$n_{2}$, ordered as in $T$, and let $T_{2}$ be the nodes produced by these
steps. We then add chase steps in $T^{\prime}$ for each chase step in $C_{2}$.
More precisely, we expand $T^{\prime}$ by an induction on prefixes of $C_{2}$,
building $T^{\prime}$ and a partial function $m$ from the domains of facts in
$\\{n_{2}\\}\cup T_{2}$ into the domain of facts associated to $n_{1}$ and its
descendants in $T^{\prime}$. The invariant is that $m$ preserves each fact of
$T$ generated by the chase steps in $C_{2}$ we have processed thus far in the
induction, and that $m$ is the identity on any values in $F_{1}$. We
initialize the induction by mapping the elements associated to $n_{1}$ to
elements associated to $n_{2}$. Our assumptions on $n_{1}$ and $n_{2}$ suffice
to guarantee that we can perform such a mapping satisfying the invariant. For
the inductive case, suppose the next chase step $s$ in $C_{2}$ uses ID
$\delta$, firing on the fact associated to $v_{i}$ in $T$, producing node
$v_{i+1}$. Then we perform a step $s^{\prime}$ using $\delta$ and the fact
associated to $m(v_{i})$ in $T^{\prime}$. If $\delta$ was a full ID we do not
modify $m$, while if it is a non-full ID we extend $m$ to map the generated
elements of $s$ to the corresponding elements of $s^{\prime}$. We can thus
form $h^{\prime}$ by revising $h(x)$ when $h(x)$ lies below $n_{1}$, setting
$h^{\prime}(x)$ to $m(h(x))$. Note that there could not have been any elements
in the augmented image of $h$ in $T$ that hang off the path between $n_{1}$
and $n_{2}$, since $n$ and $n^{\prime}$ were assumed to be adjacent in the
augmented image and the augmented image is closed under least common
ancestors.

In moving from $T$ and $h$ to $T^{\prime}$ and $h^{\prime}$ we reduce the sum
of the depths of nodes in the image, while no new violations are created,
since the image-parent relationships are preserved.

Call a match $h$ of $Q$ in the chase _tight_ if it has the property given in
the lemma above. The _depth_ of the match is the depth of the lowest node in
its image. The next observation, also due to Johnson and Klug, is that when
the width is bounded, tight matches can not occur far down in the tree:

######  Lemma 14.

If $\Sigma$ is a set of linear TGDs of width $w$ and the schema has arity
bounded by $m$, then any tight match of size $k$ has all of its nodes at depth
at most $k\cdot\left|\Sigma\right|\cdot(m+w)^{w}$.

######  Proof A.2.

We claim that the length of the path between a node $n$ of the image of the
match and its image parent $n^{\prime}$ must be at most
$\Delta\colonequals\left|\Sigma\right|\cdot(m+w)^{w}$ Indeed, every fact on
the path was created by applying a dependency of $\Sigma$: choosing such a
dependency $\sigma$, the occurrences of variables in the head tell us which of
the elements of facts created by the application of $\sigma$ are necessarily
equal. Specifically, the elements at positions corresponding to existential
variables contain fresh nulls with equalities that are exactly as indicated;
and the elements at exported positions contain at most $w$ distinct values,
with equalities specified by the variable occurrences plus possibly additional
equalities if some of the $w$ values are in fact equal. Thus, considering the
values occurring in the fact of $n^{\prime}$ (at most $m$), the status of a
descendant fact can be characterized by:

  * •

Knowing the last rule used; this corresponds to a factor of $|\Sigma|$

  * •

For each of the exported elements (at most $w$), knowing which are equal to
elements of $n^{\prime}$ or to some different element, i.e., each such
exported element is either one of the $m$ elements of $n^{\prime}$ or some
value in $\\{1,\ldots,w\\}$ used to represent the equality patterns between
the elements that are not in $n^{\prime}$; this corresponds to a factor of
$(m+w)^{w}$

Thus, after $\Delta$ steps, there will be two elements which repeat both the
rule and the configuration of the values, which would contradict tightness.
Since the augmented image contains the root, this implies the bound above.

Johnson and Klug’s result follows from combining the previous two lemmas:
[[16]] For any fixed $w\in\mathbb{N}$, there is an ${\mathsf{NP}}$ algorithm
for query containment under IDs of width at most $w$.

######  Proof A.3.

We know it suffices to determine whether there is a match in a chase proof,
and the previous lemmas tell us that the portion of a chase proof required to
find a match is not large. We thus guess a tree-like chase proof where the
tree consists of $k$ branches of depth at most
$k\cdot\left|\Sigma\right|\cdot(m+w)^{w}$ for $k$ the query size, along with a
match in them, verifying the validity of the branches according to the rules
of $\Sigma$.

We now give the extension of this argument for bounded semi-width. Recall from
the body that a collection of IDs $\Sigma$ has _semi-width_ bounded by $w$ if
it can be decomposed as $\Sigma=\Sigma_{1}\cup\Sigma_{2}$ where $\Sigma_{1}$
has width bounded by $w$ and the basic position graph of $\Sigma_{2}$ is
acyclic. An easy modification of Proposition A.2 now completes the proof of
our semi-width result (Proposition 2):

######  Proof A.4.

We revisit the argument of Lemma 14, claiming a bound with an extra factor of
$\left|\Sigma\right|$ in it. As in that argument, it suffices to show that,
considering the extended image of a tight match of $Q$ in a chase proof, then
the distance between any node $n^{\prime}$ of the extended image and its
closest ancestor $n$ is bounded, i.e., it must be at most
$|\Sigma|^{2}\cdot(m+w)^{w}$. Indeed, as soon as we apply a rule of
$\Sigma_{1}$ along the path, at most $w$ values are exported, and so the
remaining path is bounded as before. Since $\Sigma_{2}$ has an acyclic basic
position graph, a value in $n$ can propagate for at most $|\Sigma_{2}|$ steps
when using rules of $\Sigma_{2}$ only. Thus after at most $|\Sigma_{2}|$ edges
in a path we will either have no values propagated (if we used only rules from
$\Sigma_{2}$) or at most $w$ values (if we used a rule from $\Sigma_{1}$). In
particular, we cannot have a gap of more than
$|\Sigma_{2}|\cdot|\Sigma|\cdot(m+w)^{w}$ in a tight match.