In ontology-mediated queries (OMQs), a database query is enriched with an ontology, providing knowledge to obtain more complete answers from incomplete data. OMQs are the focus of intensive research, particularly when the ontology is expressed in Description Logics (DLs) or in rule-based formalisms like existential rules and Datalog , see e.g., [5, 4, 10] and their references. The open-world semantics of these formalisms makes them suitable for handling incomplete knowledge, but viewing all data as incomplete can result in too few certain answers. For this reason, closed predicates have been advocated as a powerful tool to combine complete and incomplete knowledge, by explicitly specifying predicates assumed complete, thus given a closed-world semantics [8, 13]. For example, take the following self-explanatory ontology T (formally, a DL TBox ): BScStud v Student; Student v 9attends:Course; BScStud v 8attends::GradCourse and the following set of facts A (an ABox ): Course(c1), Course(c2), GradCourse(c2), BScStud(a) The instance query q(x; y) = attends(x; y) mediated by T does not retrieve (a; c1) as a certain answer, but if c1 and c2 are known to be the only courses, then we can declare Course a closed predicate, and then (a; c1) becomes a certain answer. We investigate the relative expressiveness of OMQs in terms of more traditional query languages like Datalog. More precisely, we are interested in the following problem: given an OMQ Q (speci ed by a query and a TBox, possibly with closed predicates), obtain a Datalog query Q0|in a suitable fragment|such that, for any ABox A, the certain answers to Q and Q0 coincide. The existence of such a Q0 and its size are crucial for understanding the expressive power and succinctness of di erent families of OMQs. It is also very relevant in practice, since it allows to reuse existing database technologies to support OMQ answering. For example, the research into OMQs that can be rewritten into rst-order (FO) queries has produced the successful DL-Lite family [6], which has been extensively studied, and laid the base for developing other FO-rewritable query languages, e.g., [9, 11]. Many DLs are not FO-rewritable, but can be rewritten into monotonic Datalog queries, leading to implemented systems, e.g., [17, 7, 19]. The pioneering work in [12] showed that instance queries in an expressive extension of ALC (without closed predicates) can be rewritten into a disjunctive Datalog program, using a constant number of variables per rule, but exponentially many rules. For union ? This work was supported by the Austrian Science Fund (FWF) projects P25207, T515 and W1255.
of conjunctive queries in ALC, the existence of exponential Datalog rewritings
was shown recently [
We consider OMQs of the form (T ; ; q), where q is an instance query and T
is a TBox in the very expressive DL ALCHIO with closed predicates . Observe
that these queries are non-monotonic: if = fCourseg are the closed predicates
in the above example, then (a; c1) is a certain answer to (T ; ; q) over A, but it
is not a certain answer over A0 = A [ fCourse(c3)g. This shows that these queries
cannot be rewritten into monotonic variants of Datalog, like positive Datalog
(with or without disjunction). The main contribution of this paper is a polynomial
time translation of queries in Q into disjunctive Datalog extended with negation
as failure Datalog_: . Our translation is modular: if no closed predicates are
present|i.e., for regular instance queries in ALCHIO|our translation yields
a positive disjunctive Datalog program of polynomial size. To our knowledge,
this is the rst polynomial time translation of an expressive (non-Horn) DL into
Datalog. The full version of this abstract can be found in [
We assume familiarity with DLs [
t Bk (N2) A1 v 9r:A2 (N3) A1 v 8r:A2 (N4) r v s where B(i) are concept names or nominals fag, and r and s are roles of the form p or p ; the ABox A is a set of assertions of the forms A(a) and p(a; b). Models of axioms, assertions, TBoxes and ABoxes are de ned as usual. For an ABox A and a set of closed predicates , we write I j= A if: (a) I j= A, (b) for all concept names A 2 , if e 2 AI , then A(e) 2 A, and (c) for all role names r 2 , if (e1; e2) 2 rI , then r(e1; e2) 2 A. For a KB K, we write I j= K if the following hold:1 (i) a 2 I and aI = a for each a 2 NI occurring in K, (ii) I j= T , and (iii) I j= A. For an assertion , we write K j= if I j= for all I such that I j= K. Finally, an (ontology mediated) instance query is a triple Q = (T ; ; q), where q 2 NC [ NR. Let a 2 NI in case q 2 NC, and a 2 NI2 otherwise. Then a is a certain answer to Q over an ABox A if (T ; ; A) j= q(a); note that if = ;, this boils down to the usual DL instance checking problem. 1 We make the standard name assumption (SNA)for the individuals occurring in K.
Assume a KB K = (T ; ; A) and an assertion q. Deciding K 6j= q amounts to deciding whether there exists a counterexample (for the entailment of q from K), which is an I with I j= K and I 6j= q. In this section we give a brief explanation of how this can be decided, and reduced to evaluating a Datalog_: query.
Below, a core interpretation for K is an interpretation I with domain NI(K)
such that I j= A, and which satis es some additional conditions (e.g., it models
the TBox axioms of the forms (N1), (N3), (N4), and also (N2) when the role is
closed); see [
To decide the existence of a counterexample, we proceed in two steps: (1) Guess a core interpretation I for K, such that I 6j= q. (2) Check that I can be extended to satisfy all axioms in T . Since the extension coincides with I on the assertions they entail, this preserves the non-entailment of q.
Given T , and q, de ning Datalog_: rules that do (1) for any input A is not so hard. For example, rules like the following `guess' how individuals participate in concepts and roles: A(x) _ A(x) ind(x) A(x); A(x) r(x; y) _ r(x; y) ind(x); ind(y) r(x; y); r(x; y) and other rules then verify the additional conditions in the de nition of core interpretation. The latter simulate the TBox axioms in a rather direct way (e.g., an axiom r v s becomes s(x; y) r(x; y)). Their only interesting feature is that, to ensure that no instances are added to closed predicates in the extension of I, we use constraints with negative body atoms. For example, we use r(x; y); not s(x; y) instead of the rule above if s is closed.
Now, step (2) is harder: given T , , and I, verifying whether I can be extended into a full model of T while respecting is ExpTime-hard already for fragments of ALCHOI (as it is a generalization of consistency testing ). In order to obtain a polynomial set of rules that solves this ExpTime-hard problem, we characterize it as a game, revealing a simple algorithm that admits an elegant implementation in Datalog_: .
The game is played over a set LC(T ; ; I) of locally consistent types, which are sets of atomic concepts satisfying conditions such as having no explicit inconsistencies and satisfying all axioms of type (N1) in T . Additionally, a type that contains a nominal fag must be the type realized by a in A, that is, is exactly the set of all B such that a 2 BI . Moreover, must be realized in I by some individual whenever it contains a closed concept, or a concept occurring on the left-hand-side of an axiom (N2) that has closed role on the right.
We now describe the game, which is played by Bob (the builder), who wants to extend I into a model, and Sam (the spoiler), who wants to spoil all Bob's attempts. The game on I starts by Sam choosing an individual a 2 I , and = type(a; I) is set to be the current type. Then: ( ) If 62 LC(T ; ; I), then Sam is declared winner. Otherwise, Sam chooses an inclusion A v 9r:A0 2 T with A 2 ; if there is no such inclusion, Bob wins the game. Otherwise, Bob chooses a new type 0 such that: (C1) A0 2 0, and (C2) for all inclusions A1 v 8s:A2 2 T : if r v s 2 T and A1 2 then A2 2 0, if r v s 2 T and A1 2 0 then A2 2 .
0 is set as current type is and we go back to to continue with a new round.
It can be proved that a core I can be extended into a model i Bob has a non-losing strategy for the game played on I. To decide the existence of a non-losing strategy, we implement in Datalog_: a procedure to mark all types from which there is no non-winning strategy. The rules that do this can be found in the full version. Here we discuss a few sample rules. For example, a rule
Marked(x) Type(x); B1 2 x; : : : ; Bn 2 x; B10 62 x; : : : ; Bn0 62 x marks types that violate axioms of type (N1), where Type is a k-ary relation that contains (bit vectors denoting) the di erent combinations of the k concepts occurring in T , and B 2 x (resp. B 62 x) is shortcut for the atom testing if B is (not) in this type. For testing the local consistency conditions that involve realized types, we use a k-ary predicate RealizedType that gathers all types realized in I. Then, for example, a rule Marked(x) Type(x); A 2 x; not RealizedType(x) marks all non-realized types that contain a closed A, and similar rules handled enforces s-neighbors with closed s and nominals f g a . The most interesting part is to go beyond the local consistency, propagating the markings to types that don't allow Bob to pick an unmarked successor type. We need to mark a type if A 2 for some = A v 9r:A0 2 T , and each type 0 has either been marked, or violates one of (C1) and (C2). We use an auxiliary (2k + 1) relation MarkedOne to collect all such 0: MarkedOne(x; a ; y) Type(x); Marked(y) and similar rules for collecting types that violate (C1) or (C2). We now want to ensure that Marked(t) in case MarkedOne(t; a ; v) is true for all types v. This needs a set of rules that generate a linear order over types, and use it to iterate over all types. If we manage to reach the last type, the current type is marked. To this end, we need another (2k +1)-ary relation MarkedUntil. We add: MarkedUntil(x; a ; z) MarkedOne(x; a ; z); rst(z) MarkedUntil(x; a ; u) MarkedUntil(x; a ; z); next(z; u); MarkedOne(x; a ; u)
Marked(x) MarkedUntil(x; a ; z); A 2 x; last(z) Finally, there is a set of rules that check that all types realized in the core are not marked. Putting all the rules together, we can show the following: Theorem 1. For an instance query (T ; ; q), where T is an ALCHIO TBox, we can build in polynomial time a Datalog_: program P such that: (i) The certain answers to (T ; ; q) and (P; q) coincide for any given ABox A over the signature of T . (ii) If = ;, then P is a positive program. (iii) If = ; and T is an ALCHI TBox, then P is a positive program with no occurrences of the 6= predicate.