How to provide scalable and quality guaranteed approximation for query answering over expressive description logics (DLs) is an important problem in knowledge representation (KR). This is a pressing issue, in particular due to the fact that, for the widely used standard Web Ontology Language OWL, whether conjunctive query answering is decidable is still an open problem. Pan and Thomas propose a soundness guaranteed approximation, which transforms an ontology in a more expressive DL to its least upper bound approximation in a tractable DL. In this paper, we investigate a completeness guaranteed approximation, based on transformations of both the source ontology and input queries. We have implemented both soundness guaranteed and completeness guaranteed approximations in our TrOWL ontology reasoning infrastructure.
The growing availability of semantic annotated data requires scalable query
answering in description logics. How to provide efficient querying answering service for
expressive DLs has been an important open problem in KR. In fact, whether query
answering in OWL DL is decidable is still an open problem. The closest available
complexity results are about the SHIQ DL, which is OWL DL without nominals and
datatypes, but allowing qualified number restrictions. Ortiz et al. [
Approximation has been identified as a potential way to reduce the complexity
of reasoning over OWL DL ontologies. Many existing approaches [
In this paper, we investigate a completeness guaranteed approximation for
nonboolean query answering, based on transformations of both the source ontology and
input queries It turns out that the semantic approximation constructed for soundness
guaranteed query service can also be exploited to provide completeness guaranteed
query service. We then provide a more fine grained approximation, which can provide
potentially much smaller but still completeness guaranteed, which can be used to
provide anytime querying answering for OWL DL. We have implemented both soundness
guaranteed and completeness guaranteed approximations in our TrOWL ontology
reasoning infrastructure. Accordingly, for each query, we provide two answer sets: one is
soundness guaranteed and the other is completeness guaranteed. To evaluate our
approach, we use the ontologies that Motik et al [
A conjunctive query is of the form q(X) 9U:'(X; U ), or simply q(X) '(X; U ), where X and U are vectors of distinguished variables (DVs) and non-distinguished variables (NDVs) resp., and ' is a conjunction of atoms of the form A(v), R(v1; v2), where A; R are named concepts and named roles resp., v; v1 and v2 are variables in X and U , or individual names in the given ontology. If v; v1 and v2 are not in U , then A(v) and R(v1; v2) are non-distinguished variable free atoms. If X is an empty set, we say q is a boolean query; otherwise, we say q is a non-boolean query. Theoretically, allowing only named concepts and roles in atoms is not a restriction, as we can always define such named concepts and roles in ontologies. Practically, this should not be an issue as querying against named relations is a usual practice when people query over relational databases. In this paper, although we consider input queries with only named concepts and roles in atoms, it is still possible to have concept descriptions in atoms due to query rewriting (see Section 3). As usual, an interpretation I satisfies an ontology O if it satisfies all the axioms in O; in this case, we say I is a model of O. Given an evaluation [X 7! S], where S is a vector of individual names, if every model I of O satisfies q[X7!S], we say O entails q[X7!S]; in this case, S is called a solution of q.
We could consider a conjunctive query as a directed graph [
A non-distinguished variable sub-graph (or NDV sub-graph) of a query q is a sub-graph of q with all its nodes being non-distinguished variables. For example, q1 has one NDV sub-graph (containing the node u). 2.2
Selman and Kautz illustrated the idea of knowledge compilation in [
Let be a set of clauses (the original theory), the sets lb and ub of Horn clauses are respectively a Horn lower-bound and a Horn upper-bound of iff M( lb) M( ) M( ub), or, equivalently, lb j= j= ub. This says the Horn lowerbound is logically stronger than the original theory and the Horn upper-bound is logically weaker than it. A Horn lower-bound glb is a greatest Horn lower-bound iff there is no set 0 of Horn clauses such that M( lb) M( 0) M( ). A Horn upperbound lub is a least Horn upper-bound iff there is no set 0 of Horn clauses such that M( ) M( 0) M( lub). 2.3
Pan and Thomas [
The following definition provides the notion of least upper-bound in their setting; i.e., they consider all Lt axioms that are entailed by Os.
Definition 1. (Entailment Set) Let NC , NP and NI be the finite set of named concepts, named roles and named individuals, respectively, used in Os. The entailment set of Os w.r.t. Lt, denoted as ES(Os; Lt), is the set which contains all Lt axioms (constructed by using only vocabulary in NC , NP and NI ) that are entailed by Os. Lemma 1. ES(Os; Lt) is the least upper bound compilation of Os in Lt. In order to use ES(Os; Lt) as the target approximation ontology Ot, we need to find some lightweight language Lt such that ES(Os; Lt) is finite.
Lemma 2. Given an OWL DL ontology Os, ES(Os; LDL-LiteR) is a finite set.
Accordingly, we can use DL-LiteR as a lightweight language Lt for approximating
OWL DL ontologies in order to provide scalable query answering service. See [
Given an OWL DL ontology Os and an arbitrary query q, we denote the set of solutions of q over Os as Sq;Os and the set of solutions of q over ES(Os; DL-LiteR) as Sq;ES(Os;DL-LiteR). The following theorem shows that query answering based on the DL-LiteR entailment set is soundness guaranteed. In this section, we will first show how to make use of entailment sets (introduced in Section 2.3) to provide a completeness guaranteed approximation for OWL DL query answering. Secondly, we will show how to provide smaller completeness guaranteed approximations by using some enriched entailment sets. In order to provide a completeness guaranteed approximation based on entailment sets, we first introduce the approximate function FC0, and then show that, given an OWL DL ontology Os and a query q, querying FC0(q) over ES(Os; DL-LiteR) is completeness guaranteed, i.e. Sq;Os SFC0(q);ES(Os;DL-LiteR).
Definition 2. (Approximation Function FC0) Let q be an input non-boolean conjunctive query of the form q(X) '(X; U ), the approximation function FC0 returns qC0(X) '0(X; ;), where '0(X; ;) is a non-distinguished variable free conjunction that only contains all the non-distinguished variable free atoms in '(X; U ). From the query graph point of view, this amounts to removing all NDV sub-graphs of an input query q and all edges connecting to these sub-graphs from q.
Example 1. Let us revisit the query q1(x) C(x) ^ R1(x; u) ^ R2(x; Rome), FC0(q1) is q1C0(x) C(x) ^ R2(x; Rome), which corresponds to the following graph. Theorem 3. Given an OWL DL ontology Os and an arbitrary non-boolean query q, Sq;Os SFC0(q);ES(Os;DL-LiteR).
of FC0, and (ii) SFC0(q);Os = SFC0(q);ES(Os;DL-LiteR), due to Theorem 2.
Theorems 1 and 3 suggest that, given an OWL DL ontology Os and a non-boolean query q, we could now provide both a soundness guaranteed answer set Sq;ES(Os;DL-LiteR) and a completeness guaranteed answer set SFC0(q);ES(Os;DL-LiteR). 3.2
The approximation function FC0 removes all the non-distinguished atoms from the input query q, which could potentially introduce many unsound answers in the completeness guaranteed answer set.
Example 2. Consider the cyclic query q2 of the form q2(x1; x2) C(x1)^R1(x1; u1)^ R2(x1; Rome) ^ R3(u1; u2) ^ R4(Rome; u2) ^ D(u2) ^ R5(u2; x2), which corresponds to the following graph: FC0(q2) is q2C0(x1; x2) graph:
FC0(q2) has two disconnected components that do not share any variables: R2(x1; Rome) and >(x2). The latter one binds all named individuals to x2, thus the answer set potentially could be large and contain many unsound answers.
In this section, we investigate how to improve FC0 by keeping more information
from the non-distinguished atoms. We develop a query rewriting technique based on
the rolling up technique that has been used [
Let us revisit the query q1 (with an acyclic query graph) before providing formal analysis.
Example 3. The query q1 is to retrieve all named individuals (x), which are instances of C, related by role R1 to an (possibly unnamed) individual (u) and related by role R2 to the individual Rome. The query can be paraphrased as the query q10(x) C(x) ^ 9R1:>(x) ^ R2(x; Rome), which corresponds to the following graph.
It should be noted that the intuition from the above example is substantiated by the fact q1 corresponds to the first order logic formula 8x(9u(C(x)^R1(x; u)^R2(x; Rome))), which can be translated to the first order logic formula 8x(C(x)^9R1:>(x)^R2(x; Rome)). Accordingly, we have the the following lemma for rolling-up a path of non-distinguished variables.
Lemma 3. Let Os be an OWL DL ontology, C1; :::Cm concepts, R1; :::Rm named roles and o a named individual in Os, x; u1; :::; um variables. Given the following input query q and corresponding rolled up query q0: – q(x) R(x; u1)^S(o; u1)^C1(u1)^R2(u1; u2)^C2(u2)^:::^Rm(um 1; um)^
Cm(um) – q0(x) 9R:(C1u9R2:(:::9Rm 1:(Cm 1u9Rm:Cm)))(x)^9S:(C1u9R2:(:::9Rm 1:(Cm 1u 9Rm:Cm)))(o) ^ 9R:9S :fog(x) ^ 9S:9R :>(o)
A few remarks for the above lemma: (i) If we have Ai;1(ui) ^ ::: ^ Ai;n(ui) in the query q, we could first combine them into one atom Ai;1 u:::uAi;n(ui), before applying the lemma. Hence, Ci can be either a named concept or a conjunction of named concepts Ai;1 u ::: u Ai;n. (ii) The lemma shows that rolling up non-distinguished variables to distinguished variables (x) is the similar to rolling up to individuals (o). For example, we could roll up q3(x) R1(x; u1) ^ R3(u1; u2) into q30(x) 9R1:(9R3:>)(x).
In order to apply Lemma 3 for completeness guaranteed approximations of potentially cyclic non-boolean queries, we introduce the notion of proxy nodes. Intuitively speaking, proxy nodes are nodes to which we roll up paths of non-distinguished variable.
Definition 3. (Proxy Node) Given a non-boolean query q, a proxy node of q is a node in the query graph of q that (i) corresponds to a distinguished variable or an individual and (ii) directly connects via a role to a non-distinguished variable.
For example, in the query graph of q2, proxy nodes include x1; x2 and Rome.
Given a non-boolean query q, a proxy node p of q, we call the acyclic path p; n1; :::nh (where n1; :::; nh are nodes in q) a proxy path w.r.t. p. Note that the above definition does not take into account the direction of edges, since R(ui; uj ) is equivalent to R (uj ; ui). We use Path(p; n) to denote all proxy paths from the proxy node p to the node n. For example, in the query graph of q2, Path(x1; Rome) contains one path: x1; u1; u2; Rome w.r.t. x1.
The following lemma deals with enriching the labels of proxy nodes based on their non-distinguished variable paths.
Lemma 4. Let Os be an OWL DL ontology, C1; :::Cm concepts and R1; :::Rm named roles in Os, X the set of distinguished variables, p a proxy node in q and n1; :::; nm nodes in q. Given the following input query q and corresponding enriched query q0 based on the rolling up of the proxy path p; n1; :::; nm: – q(X) D(p)^R1(p; n1)^C1(n1)^R2(n1; n2)^C2(n2)^:::^Rm(nm 1; nm)^
Cm(nm) – q0(X) D(p)^R1(p; n1)^C1(n1)^R2(n1; n2)^C2(n2)^:::^Rm(nm 1; nm)^
Cm(nm) ^ 9R1:(C1 u 9R2:(:::9Rm 1:(Cm 1 u 9Rm:Cm)))(p)
It should be noted that q0 contains all atoms of q, while adding an atom for p based on the rolling up.
Definition 4. (Proxy Node Based Rolling Up Function FR) Let q be an input nonboolean query of the form q(X) '(X; U ), p1; :::; pn proxy nodes in q, the proxy node based rolling up function FR rewrite q as follows: 1. Normalise q into q0: transform concept atoms of the form A1(i) ^ ::: ^ Ak(i) into
A1 u ::: u Ak(i). 2. Enrich q0 into q00: For each NDV-subgraph g of q0, – if g weakly connects to at least two proxy nodes p1; :::pk(k 2), then for each pair hpi; pj i (1 i < j k) of the weakly connected proxy nodes, enrich q0 based on all paths in Path(pi; pj ) according to Lemma 4; – if there is only one proxy node p connected to g, let n1; :::ns be the set of nodes in g that has the lowest weak connectivity degree. For each nh (1 h s), enrich q0 based on all paths in Path(p; nh) according to Lemma 4. 3. Returns FC0(q00).
Example 4. q2 contains only one NDV sub-graph, which connects to three proxy nodes. FR(q2) is q2R(x1; x2) C(x1) ^ R2(x1; Rome) ^ 9R1:(9R3:(D u 9R5:>))(x1) ^ 9R5 :(D u 9R3 :(9R1 :C))(x2) ^ 9R1:(9R3:(D u 9R4 :>))(x1) ^ 9R4:(D u 9R3 :(9R1 :C))(Rome) ^ 9R5 :(D u 9R4 :>)(x2) ^ 9R4:(D u 9R5 :>)(Rome), which corresponds to the following graph.
Theorem 4. Given an OWL DL ontology Os and an arbitrary non-boolean query q, Sq;Os SFR(q);Os SFC0(q);ES(Os;DL-LiteR).
Theorem 4 shows that SFR(q);Os is a more fine grained completeness guaranteed answer set. Given an OWL DL ontology Os and a non-boolean query q, this sub-section investigates how to to answer FR(q) over Os. In particular, we will show this can be done based on enriched entailment sets of Os.
According to Def 4, these descriptions are of the form 9R1:(C1 u 9R2:(:::9Rm 1:(Cm 1 u 9Rm:Cm))) (1) where C1; :::Cm are conjunctions of named concepts, and R1; :::Rm are either named roles or their inverse. Intuitively, we first introduce fresh named concepts to represent concept descriptions in the labels of proxy nodes, then query against the extended ontology. Formally, given an ontology Os and a non-boolean query q, we can extend Os to q-enriched ontology Osq as follows: for each proxy node concept description P of the form (1) in FR(q), add an axiom AP P into Os, where AP is a fresh named concept. We use FN (FR(q)) to denote the resulted query of rewriting FR(q) by replacing all concept descriptions P of the form (1) with the corresponding named concepts AP . Lemma 5. Let Os be an ontology, q a non-boolean query. SFR(q);Os = SFN (FR(q));Osq = SFN (FR(q));ES(Osq;DL-LiteR).
Proof: (Sketch) The first equivalence is trivial. The second equivalence is due to Theorem 2 and the fact that FR(q) does not contain any non-distinguished variables.
We call ES(Osq; DL-LiteR) an enriched entailment set of Os w.r.t. the query q. In the next section, we will investigate query independent enriched entailment sets. 4
A9R4:>(Rome).
In this section, we introduce a strategy to incrementally construct enriched entailment sets. For a concept description P of the form (1), we use depth(P ) to denote the maximal number of serial existential quantifiers in it; e.g., depth(9R1:(C1 u 9R2:>)) = 2. We define the depth of a query q as the maximal length of proxy paths in it.
For an OWL DL ontology Os, let Ei = fei1; ; eikg (i 1) be the set of DLLiteR axioms that a) contain some of the representative named concepts for the concept descriptions of the form (1) that are with depth i, and b) are entailed by Os. Accordingly, a serial of i-entailment set i (i 1), are defined as followings: 0 = ES(Os; DL-LiteR), 1 = 0 [ E1, ..., i = i 1 [ Ei. Let 0 i m be an integer, we define the function Fi to rewrite FR(q) by a) replacing all concept descriptions 9R1:(C1 u 9R2:(:::9Rm 1:(Cm 1 u 9Rm:Cm))) with the representative named concept (of depth i) for 9R1:(C1 u 9R2:(:::9Ri 1:(Ci 1 u 9Ri:>))). For example, F1(FR(q2)) is q2R(x1; x2) C(x1) ^ R2(x1; Rome) ^ A9R1:>(x1) ^ A9R5 :>(x2) ^ Theorem 5. Given an OWL DL ontology Os and a query q over Os. Let j have: i 0, we
It should be noted that the above theorems are for arbitrary queries. For OWL DL ontology Os and a query q, an anytime reasoning for query answering is a set of computing jobs fSF0(FR(q)); 0 ; ; SFi(FR(q)); i ; g. Fig. 1 shows the intuitive hierarchy of the set of solutions in anytime reasoning for query q on Os. We note when i increases, the curve is approaching to the middle red line, which is Sq;Os .
We have implemented both soundness guaranteed and completeness guaranteed approximations in our TrOWL ontology reasoning infrastructure, which is based on the infrastructure used in the ONTOSEARCH2 system. As Theorem 5 indicates, soundness guaranteed and completeness guaranteed semantic approximations can be implemented in a similar manner. The main difference is that, the form one is based on 0, while the latter one is based on i( 1). All these (i-)entailment sets are stored in the database. As it could be quite time consuming to compute i( 1), we apply some optimisations and produce some relaxed completeness guaranteed approximations Ci (instead of i). All the tests were done on an Apple Macbook, with 2.0 Ghz Dual Core and 2Gb ram.
In [
Table 3 presents the average completeness degrees (cd, with cd = 1:0 indicating being the exact answer set) and average time (ms) spent on querying each set of queries (one with zero NDVs, three with one, and three with two) of over 0; C1; :::; C3. Completeness degree is defined as jjetaajj , where ta is the total answers returned, while ea is the exact answer set. Since all the queries were tree-shape queries, the exact result set was calculated semi-automatically. For comparison, we also list the average completeness degrees and average time (querying over the original ontology) spent for Pellet, which treats all variables in the query as distinguished when query answering over ontologies.
Our evaluation shows (see also Table 3): (1) Query with Pellet and over 0 are both soundness preserving; moveover, our soundness preserving approximation based on 0 is more complete than Pellet. (2) Querying over 0 is much more efficient than Pellet. (3) Querying over C1; C2; C3 is also more efficient than over Pellet, while slightly less efficient than over 0. (4) The refinement from of the completeness preserving approximations is effective. The completeness preserving answer sets over C3 are much smaller than those over C2, which in turn are much smaller than those over C1. In fact, for all the tested queries, answer sets over C3 are both sound and complete. Figure 2 shows the convergence of each complete entailment set, as the complexity of the set increases. This shows the result for each query using two non-distinguished variables. It can clearly be seen how using anytime reasoning over increasingly large entailment sets can improve the precision of a query, as the additional entailment sets are calculated from the source ontology. 6
In this paper, we investigate a completeness guaranteed approximation, based on
transformations of both the source ontology and input queries. Based on this approach and
the results from [
From the literature, the closest approach is SCREECH-ALL [
One immediate future work is to further test this approach on variant application ontologies. Study more optimization techniques in order to build more efficient systems will be one of the important future works.