This paper considers the setting of ontology-based query answering (OBQA). In this setting, Description Logics (DLs) and existential rules (a.k.a. tuple-generating dependencies or Datalog rules) are popular ontology languages, while conjunctive queries (CQs) is the main querying tool. Among KR researchers there is a clear consensus that the required level of scalability in OBQA can only be achieved via query rewriting, which attempts to reduce OBQA into the problem of evaluating a query over a relational database. Two query languages are usually considered: first-order queries (FO) and non-recursive Datalog queries (NDL).
An interesting approach to query rewriting is the polynomial combined approach [
Research Challenges. The problem of applying the polynomial combined approach
to existing DLs and classes of existential rules is relatively understood. Nevertheless,
there are still basic open questions that deserve our attention. Regarding DLs, little is
known about formalisms with n-ary relations such as DLR-LiteR, that is, the
extension of DL-LiteR with n-ary roles. Regarding existential rules, it is open whether the
polynomial combined approach can be applied to the class of linear existential rules (or
simply linear rules), that is, assertions of the form 8X8Y(s(X; Y) ! 9Z p(X; Z)),
where s(X; Y) and p(X; Z) are atomic formulas [
It is not difficult to show that, if linear rules are polynomially combined rewritable,
then also DLR-LiteR is polynomially combined rewritable — this follows from the
fact that query answering under DLR-LiteR can be easily reduced to query answering
under linear rules [
z5 (b) z4
Given a (Boolean) CQ q, a database D, and a set of linear rules, can we rewrite in polynomial time: (i) q and , independently of D, into a Q-query q , where Q 2 fFO; NDLg, and (ii) D and , independently of q, into a database D , such that (D [ ) j= q iff D j= q ?
The answer to the above question is affirmative under the assumption that the arity
of the underlying schema is bounded; implicit in [
We assume the reader is familiar with the chase procedure. Recall that the chase for
a database D and a set of rules, denoted chase(D; ), is a universal model of D
and , and thus (D [ ) j= q iff chase(D; ) j= q, for each CQ q. The instance
chase(D; ) can be naturally seen as a directed labeled graph, called chase graph,
denoted CG (D; ). It is also easy to verify that for linear rules, CG (D; ) is a directed
forest; for details on the chase, see, e.g., [
Example 1. Let D = fp(a; b; c); p(b; c; d)g, and let brevity, the universal quantifiers are omitted): be the set of linear rules (for p(X; Y; Z) ! 9W p(X; W; Y ) p(X; Y; Z) ! 9W p(Y; X; W ) p(X; Y; Z) ! 9W p(Z; W; Y ) p(X; Y; Z) ! p(Y; Z; X): Given the BCQ q = 9A9B9C9D (p(A; a; B) ^ p(C; B; b) ^ p(D; c; b)), as shown in Figure 1(a), there exists a homomorphism h (dashed arrows in the figure) that maps q to an initial segment of the chase graph of D and , and thus (D [ ) j= q. It is interesting to observe that the nulls occurring in h(q), i.e., z1, z3, z4 and z5, form a rooted forest F , depicted in Figure 1(b), with the following properties; for brevity, let (z) be the atom in CG (D; ) where the null z is invented (see shaded atoms in Figure 1(a) for (z1), (z3), (z4) and (z5)): (i) for every root node z, (z) is reachable from D; (ii) for every edge (z; w), (w) is reachable from (z); and (iii) for every atom a 2 h(q), there exists a unique path in F that contains all the nulls in a, and, assuming that the leaf node of is z, a is reachable from (z). Indeed, it is easy to verify that (z1) and (z5) are reachable from D, (z3) and (z4) are reachable from (z1), and finally, h(p(A; a; B)) = p(z3; a; z1) is reachable from (z3), h(p(C; B; b)) = p(z4; z1; b) is reachable from (z4), and h(p(D; c; b)) = p(z5; c; b) is reachable from (z5).
Roughly speaking, the triple consisting of: (1) the homomorphism h, that maps q to the chase; (2) the function , that gives the atoms in the chase where the nulls occurring in h(q) were invented; and (3) the forest F , that encodes how the nulls of h(q) depend on each other, as well as the order of their generation, is what we call a proof generator for q w.r.t. D and . The existence of such a triple, allows us to generate the part of the chase due to which the query is entailed, i.e., the proof of the query (hence the name “proof generator”). Therefore, for query answering purposes under linear rules, we simply need to check if such a proof generator exists.
Lemma 1. (D [
) j= q iff there exists a proof generator for q w.r.t. D and . 3
We give a positive answer to our research question regarding linear rules and the polynomial combined approach. More precisely, we show that: Theorem 1. The class of linear rules is polynomially combined Q-rewritable, where Q 2 fFO; NDLg.
To establish the above theorem, we heavily rely on the notion of the proof generator. Fix a (Boolean) CQ q, a database D, and a set of linear rules. By Lemma 1, it suffices to construct in polynomial time a query q 2 Q (independently of D), and a database D (independently of q), such that D j= q iff a proof generator for q w.r.t. D and exists. Roughly, the query q guesses a triple (h; ; F ) (as described in Example 1), and then verifies that the guessed triple is a proof generator for q w.r.t. D and . The interesting part of q is the component that applies the crucial reachability checks required by the definition of the proof generator. Although the path among two atoms in the chase graph may be of exponential size, its existence can be checked via Q-queries of polynomial size. An immediate consequence of Theorem 1 is that: Corollary 1. The description logic DLR-LiteR is polynomially combined Q-rewritable, where Q 2 fFO; NDLg.
The results of this work are, for the moment, of theoretical nature and we do not claim that they will directly lead to better practical algorithms. We believe that a smart implementation of the proposed techniques can lead to more efficient rewriting procedures; this will be the subject of future research. We are also planning to optimize the proposed rewriting algorithm, with the aim of constructing queries of optimal size.
Acknowledgements. G. Gottlob was supported by the EPSRC Programme Grant EP/M025268/ “VADA: Value Added Data Systems – Principles and Architecture”. M. Manna was supported by the MIUR project “SI-LAB BA2KNOW – Business Analitycs to Know”, and by Regione Calabria, programme POR Calabria FESR 2007-2013, projects “ITravel PLUS” and “KnowRex: Un sistema per il riconoscimento e l’estrazione di conoscenza”. A. Pieris was supported by the Austrian Science Fund (FWF): P25207N23 and Y698.