of Invited Talk Query rewriting has become a very prominent tool for e ciently implementing ontology-mediated querying in practice. The technique was originally introduced in the context of DL-Lite [4], but is now increasingly being used also for more expressive DLs. While rewritings are not guaranteed to exist beyond DL-Lite, the simple structure of ontologies that emerge from practical applications gives hope that non-existence of rewritings is a rare case. The aim of the talk is to survey FO- and Datalog-rewriting of ontologymediated queries in description logics beyond DL-Lite. It is structured into three parts. The rst part is concerned with FO-rewritings in Horn-DLs such as EL, E LI, and Horn-SHI, the second part considers FO-rewritings in non-Horn-DLs such as ALC and ALCI, and the third part is about Datalog-rewritings in nonHorn DLs. In all three parts, I will try to emphasize useful characterizations of FO-rewritability, practically e cient algorithms for constructing rewritings, and relevant computational complexity results. The presentation is based on joint work with Meghyn Bienvenu, Balder ten Cate, Peter Hansen, I_nanc Seylan, and Frank Wolter. The subsequent section provides some supplementary material that is featured in the talk, but has not yet been published elsewhere. It establishes a link between the rst and the second part of the talk.
In [
An ontology-mediated query (OMQ) is a triple Q = (T ; ; q) with T a TBox, an ABox signature (set of concept and role names), and q a query. An OBDA language is a set of OMQs. We use (ALCI; BAQ) to denote the OBDA language that consists of all OMQs (T ; ; q) with T an ALCI-TBox and q a BAQ, and likewise for other combinations of a DL and a query language. An OMQ Q = (T ; ; q) is FO-rewritable if there is an FO-sentence ' such that for every ABox A that is consistent w.r.t. T , we have A j= Q i A j= '.
As usual in OBDA, an ABox is a nite set of assertions of the form A(a) or r(a; b) with A a concept name and r a role name. We write r (a; b) 2 A to mean r(b; a) 2 A and use Ind(A) to denote the set of individuals used in A. An ABox A is tree-shaped if the undirected graph (Ind(A); ffa; bg j r(a; b) 2 Ag) is a tree and whenever r(a; b) 2 A, then (i) s(a; b) 2 A implies r = s and (ii) A contains no assertion of the form s(b; a). Tree-shapedness of conjunctive queries (CQs) is de ned accordingly. Note that, in both cases, our trees allow upwardsand downwards-directed edges, but no multi-edges.
We now introduce unravelings of ABoxes and the notion of unraveling
tolerance [
It can be shown as in [
Theorem 1 ([
Using a pumping argument, it can be shown that if there is any bound k as
Theorem 1, then we can choose k = 22jT j. Based on this, worst-case optimal
(ExpTime) decision procedures for FO-rewritability in (Horn-ALCI; AQ) can
be devised using automata methods. E ciently computing rewritings in practice
requires further algorithm engineering [
We will now establish a characterization of FO-rewritability in the
nonHorn OBDA language (ALCI; BAQ). It is shown in [
It is easy to see that an OMQ Q is FO-rewritable if and only if the
complement of TQ is FO-de nable, and likewise for rewritability into monadic Datalog.
In [
Theorem 2 ([
This approach is also capable of producing actual rewritings, but unfortunately it is best-case exponential. This calls for a better understanding of FO-rewritability in (ALCI; BAQ) and related languages, as a basis for more practical (yet complete) approaches.
As a preliminary, we show that unraveling tolerance is equivalent to rewritability into monadic Datalog. This actually follows straightforwardly from known results about CSPs.
Theorem 3. An OMQ from (ALCI; BAQ) is unraveling tolerant i it is rewritable into monadic Datalog.
Proof. A CSP template T over signature has tree duality i there is a set O
of tree-shaped -structures (called obstructions and where tree-shapedness is
de ned as for ABoxes and CQs above) such that for all nite -structures S,
we have T S i S 6 O for all O 2 O. It was shown in [
\if". Assume that Q = (T ; ; q) is unraveling tolerant. Let O be the set of all
tree-shaped -ABoxes A with A j= Q. Then O witnesses tree duality: if TQ A
for some -ABox A, then A 6j= Q; since B j= Q and B ! A implies A j= Q [
\only if". Assume that TQ has tree duality with set of obstructions O. Let A be a -ABox with A j= Q. Then TQ 6 A and thus A B for some B 2 O. Since B is tree-shaped, A B implies Aau B for some a 2 Ind(A). Consequently TQ 6 Aau which yields Aau j= Q as required. tu We now establish the announced characterization.
Theorem 4. Let Q = (T ; q; ) be an OMQ from (ALCI; BAQ). Then Q is FO-rewritable i 1. Q is FO-rewritable on tree-shaped ABoxes and 2. Q is unraveling tolerant.
Proof. \if". Assume that Q is unraveling tolerant and FO-rewritable on treeshaped ABoxes. By Theorem 3, the complement of the template TQ is de nable by a monadic Datalog program Q. Let Q0 be obtained from Q by identifying the variables in rule bodies in all possible ways and then retaining only those rules whose bodies are a tree-shaped CQ. It can be veri ed that Q0 is a rewriting of Q: A j= Q implies Aau j= Q for some a 2 Ind(A) (since Q is unraveling tolerant) implies Aau j= Q (since Q is a rewriting of Q) implies Aau j= Q0 (since Aau is tree-shaped) implies A j= Q0 (since AuA ! A). Conversely, A j= Q0 implies A j= Q (by construction of Q0) implies A j= Q. It is easy to further modify
Q0 so that in addition to being tree shaped, every role body contains at most one EDB atom.
We now use the existence of Q0 to argue that Q has an FO-rewriting ' on tree-shaped ABoxes that takes the form of a union of tree-shaped CQs. Let be an FO-rewriting of Q on tree-shaped ABoxes. By Gaifman's locality theorem, there is a number d 0 such that for every -ABox A, we have A j= i Ad j= where Ad is obtained by taking the disjoint union of all d-neighborhoods in A; here, the d-neighborhood in A around a 2 Ind(A) is the restriction of A to all individuals that can be reached from a on a role path in A of length at most d. Note that is a rewriting of Q and every OMQ from (ALCI; BAQ) satis es the property that if a -ABox A is the disjoint union of ABoxes A1; : : : ; Ak, then A j= Q i Ai j= Q for at least one Ai. We can thus strengthen the above obervation as follows: for every -ABox A, we have A j= i there is some dneighborhood N in A such that N j= . Since both and Q0 are rewritings of the same query Q, the same applies to the monadic Datalog program Q0 instead of to . Moreover, we can nd an ` 0 such that for every -ABox A with A j= Q0, there is an A0 A with A0 j= Q0 and in which every individual has degree at most `|due to the special shape of Q0, we can in fact simply choose for ` the number of IDB relations in Q0. Combining these two observations, we get the following: for every tree-shaped -ABox A with A j= Q, there is a tree-shaped ABox A0 A of depth at most d and degree at most ` such that 0 = Q. We can thus choose as the desired rewriting ' the UCQ that consists A j of all tree-shaped ABoxes A (viewed as a CQ) that satisfy A j= Q and are of depth at most d and of degree at most `.
It remains to note that, due to its syntactic shape, ' is an FO-rewriting not only on tree-shaped ABoxes, but also on unrestricted ones. First assume that A is a -ABox with A j= Q. Since Q is unraveling tolerant, there then is an a 2 Ind(A) with Aau j= Q. Since ' is an FO-rewriting on tree-shaped ABoxes, we get Aau j= '. Since ' is a UCQ and Aau ! A, we obtain A j= '. Conversely, assume A j= '. Since ' is a union of tree-shaped CQs, this yields Aau j= ' for some a 2 Ind(A), thus Aau j= Q and A j= Q.
\only if". Assume that Q is FO-rewritable. Then it is clearly also FOrewritable on tree-shaped ABoxes (the same rewriting works). It thus remains to show that Q is unraveling tolerant.
It is proved in [
Now back to our OMQ Q. Since Q is FO-rewritable, so is TQ. By the above
result on nite duality in terms of nite trees, there is thus a nite set of
tree-shaped ABoxes such that for all -ABoxes A, we have A j= Q i B ! A
for some B 2 . Consequently, the UCQ qb = WB2 qB is an FO-rewriting of
Q, where qB is B viewed as a Boolean CQ in the obvious way. Note that qb is a
disjunction of tree-shaped CQs. It is thus straightforward to show that for all
-ABoxes A, we have A j= qb i Aau j= qb for some a 2 Ind(A). The unraveling
tolerance of Q follows. tu
The proof of Theorem 4 also yields the following corollary, which strengthens the
observation from [
Corollary 1. If an OMQ in (ALCI; BAQ) is FO-rewritable, then it is rewritable into a union of tree-shaped conjunctive queries.
We remark that, even when switching to the OBDA language (ALC; BAQ), it is not possible to replace the undirected trees in Corollary 1 with directed trees.
We close with some discussion of Theorem 4. As future work, we plan to adapt the result from (ALCI; BAQ) to (ALCI; AQ) and to use them as a basis for developing practically feasible algorithms that construct FO-rewritings. Dealing with (ALCI; AQ) seems to require more liberal de nitions of tree-shaped ABoxes and of unraveling tolerance which allow for back-edges to the root as in the tree-model property for DLs with nominals. To obtain a rst impression of the e ect of answer variables, the reader might want to consider the following OMQ Q = (T ; ; q) from (ALCI; BAQ):
T = fP u 9r:P v A; :P u 9r::P v Ag = frg q = 9x A(x) and its variation Q0 from (ALCI; BAQ) obtained by replacing q with the AQ q0 = A(x). Q is not unraveling tolerant as witnessed by the ABox A = fr(a; a)g which satis es A j= Q, but Aau 6j= Q. The same is true for Q0 if the notion of unraveling tolerance is adapted in a naive way to non-Boolean OMQs. However, while Q is not FO-rewritable (by Theorem 4), it is not too hard to prove that the FO-formula r(x; x) is an FO-rewriting of Q0.
Another interesting question concerns the complexity of deciding
FO-rewritability in (ALCI; BAQ) (and of course also (ALCI; AQ)) via Theorem 4.
It is shown in [