Introduction
Query rewriting is a widely used technique for e ciently answering
ontologymediated queries (OMQs) using o -the-shelf database systems. In particular, if
an OMQ is rewritable into a rst-order (FO) query, then it can be answered
using a relational database system. It is thus a fundamental problem to design
algorithms that compute an FO-rewriting of a given OMQ. For OMQs based
on expressive DLs such as ALC, nding complete such algorithms turns out to
be a technically very challenging problem; moreover, the desired rewritings are
not always guaranteed to exist. A natural rst step is thus to nd an algorithm
that decides the existence of a rewriting; in fact, any complete and terminating
algorithm for computing rewritings will implicitly also solve the decision problem
and one can expect to learn important lessons already from the latter case.
An OMQ is a triple Q = (T ; ; q) with T a TBox, an ABox signature, and
q a query [
5
]. We use (L; Q) to denote the OMQ language that consists of all OMQs
where T is formulated in the DL L and q in the query language Q. It has been
shown in [
5
] that decidability results and tight NExpTime complexity bounds
for FO-rewritability in (ALC; AQ) and related OMQ languages can be obtained
by translating the input OMQ Q into a constraint satisfaction problem (CSP)
whose complement is equivalent to Q and then applying known algorithms that
decide FO-rewritability of the CSP [
15
]. When atomic queries (AQs) are replaced
with conjunctive queries (CQs) or unions thereof (UCQs), such
equivalencepreserving translation to CSP is no longer possible; instead and as also shown
in [
5
], one can translate Q into a formula ' of the strictly more expressive logical
generalization MMSNP of CSP such that :' is equivalent to Q [
11
]. In contrast
to the CSP case, though, it was not known whether FO-rewritability of MMSNP
formulas is decidable. In this abstract, we show that this is the case and that
the complexity is 2NExpTime-complete, with the lower bounds coming from [
7
].
We then lift this result to FO-rewritability of OMQs formulated in any OMQ
language between (ALCI; UCQ) and (SHI; UCQ). Technically, our approach
consists in a reduction of the MMSNP case to the CSP case. We also analyze
the shape of the rewritings, which we hope will provide guidance for nding
algorithms that compute actual rewritings. One can prove analogous results
for rewritability into monadic Datalog in a very similar way. We do not report
about details here for lack of space. We are currently working on the unrestricted
Datalog case, which is more challenging.
Related work. FO-rewritability was rst studied in an OMQ context for
the inexpressive DL-Lite family of DLs [
1, 9, 14, 17
]. FO-rewritability in OMQ
languages based on more expressive Horn DLs has been investigated in [
3, 4, 12
].
Rewritability of Horn DLs into Datalog was considered in [10, 13, 18{20].
2
Results
Instead of working with MMSNP, we prefer monadic disjunctive Datalog, MDDLog.
It was observed in [
5
] that these have the same expressive power up to
complementation and can be mutually translated in polynomial time. We refer to [
5
]
for full de nitions and notation. An MDDLog program is Boolean if it only
returns yes/no answers. The diameter of is the maximum number of variables
occuring in a rule in . A generalized CSP is de ned by a set of templates S
instead of a single template and asks for a homomorphism from the input I to
at least one template T 2 S (a template is simply a nite relational structure).
With coCSP, we mean the complement of a (potentially generalized) CSP. The
girth of a structure is the length of a smallest cycle in it and 1 if there is no
cycle, see e.g. [
7
] for details.
We start with Boolean MDDLog programs. Our proofs make use of the
classical translation of MMSNP sentences into generalized CSPs rst described
by Feder and Vardi and stated in the following in terms of MDDLog.
Theorem 1 ([
11
]). Given a Boolean MDDLog program over EDB schema
SE of diameter k, one can e ectively construct a set of templates S over a
di erent EDB schema S0E such that
1. every nite SE -structure I can be converted in polytime into an S0E -structure
I0 such that I j= i I0 2= CSP(S );
2. every nite S0E -structure I0 of girth exceeding k can be converted in polytime
into an SE -instance I such that I j= i I0 2= CSP(S ).
Exact size bounds on the set S and its elements are given in [
7
]; although they
are needed for our nal result, we omit them from this abstract for brevity.
We next observe that the reduction described in Theorem 1 preserves
FOrewritability, up to a certain gap related to inputs of small girth. In the following,
we will consider UCQ-rewritability instead of FO-rewritability since for MDDLog,
coCSP, and all other formalisms considered here FO-rewritability implies
UCQrewritability.
Proposition 1. Let be a Boolean MDDLog program of diameter k and let
S be as in Theorem 1. Then
1. every UCQ-rewriting of coCSP(S ) can be converted into a UCQ-rewriting
of in polynomial time;
2. every UCQ-rewriting of can e ectively be converted into a UCQ-rewriting
of coCSP(S ) on structures of girth exceeding k.
Thus, FO-rewritability of is equivalent to FO-rewritability of coCSP(S ) on
structures of su ciently high girth. The `high girth' quali cation is removed by
the following observation.
Lemma 1. Let S be a set of templates over schema SE and g 0. Then, if
coCSP(S) is UCQ-de nable on nite SE -structures of girth exceeding g, it is
UCQ-de nable on (unrestricted) nite SE -structures.
Analyzing the involved blowups and exploiting that FO-rewritability of generalized
CSPs can be decided in NP [
5, 15
] and that FO-rewritability of Boolean MDDLog
programs is 2NExpTime-hard [
7
], we obtain the following.
Theorem 2. FO-rewritability of Boolean MDDLog programs is decidable in
2 NExpTime, thus 2 NExpTime-complete.
The limitation to Boolean programs can be lifted by a simple reduction which
replaces answer variables with fresh monadic relation symbols. Moreover, it
was shown in [
7
] that OMQs formulated in (SHI; UCQ) can be translated into
MDDLog with a blowup that is double exponential, but does not add up with
the blowup caused by the translation of MDDLog programs to generalized CSPs.
Finally, [
7
] also establishes a 2NExpTime lower bound for FO-rewritability in
(ALCI; CQ) and (ALC; UCQ). We can thus extend Theorem 2 as follows.
Theorem 3. FO-rewritability is 2 NExpTime-complete in MMSNP, in MDDLog,
and in OMQ languages between (ALC; UCQ) and (SHI; UCQ) as well as between
(ALCI; CQ) and (SHI; UCQ) (without transitive roles in UCQs).
We now consider the shape of rewritings. For brevity, we concentrate on Boolean
queries. An analysis of the proof of Proposition 1 yields the following.
Proposition 2. Every FO-rewritable Boolean MDDLog program of diameter k
has a rewriting of the form q1 _ _ qn with each qi a CQ of treewidth bounded by
(1; k). The same holds for Boolean OMQs from the OMQ languages in Theorem 3.
See [
6
] for a de nition of treewidth (1; k). We believe that Proposition 2 is
interesting for at least two reasons. Firstly, it says that when constructing
rewritings, it is enough to look for a structurally very restricted type of UCQ
instead of for an unrestricted FO formula. And secondly because it clari es the
shape of obstructions of FO-rewritable MMSNP sentences in the spirit of CSP
obstructions [
8
]. In particular, it is interesting to contrast Proposition 2 with the
fact that if a CSP is FO-rewritable, then it has a nite set of obstructions that
are nite trees, that is, its complement is rewritable into a UCQ that consists of
tree-shaped CQs [
2, 16
].
Acknowledgements. We thank Manuel Bodirsky and Florent Madelaine for
inspiring discussions and the ERC for funding this work under grant 647289.