As applications based on semantic web technologies enter the mainstream, there is a need to provide highly efficient ontology reasoning over large Aboxes. However, achieving sufficient scalability is still a challenge. DL reasoning is intractable in the worst case. In [1], we reported on the use of expressive reasoning for matching patient records to clinical trial criteria. While the system was able to successfully reason on 240,269 patient records, a knowledge base with 59 million Abox and 33,561 Tbox assertions, the execution time was prohibitive. In some cases, the system took hours to respond.
The expressivity of the patient knowledge base was ALCH, so expensive reasoning was needed to be complete. However, most typical queries were simple, and could have been answered faster with a less expensive reasoner. A high cost was paid by all queries to support rarer complex queries. In this paper, we present a hybrid approach, that combines a fast, incomplete reasoning algorithm with a slower complete reasoning algorithm to handle the more expressive features of DL. In this way, we were able to dramatically lower the cost of typical simple queries, without losing the ability to answer more complex queries.
An interesting feature of our technique is that any sound and incomplete algorithm may be used in the first phase to quickly find as many solutions as possible to the query. The key novelty in the approach is a mechanism to incorporate these solutions into a slower, complete reasoning algorithm for SHIN , providing much better performance characteristics overall, without sacrificing completeness or expressivity. This approach can be described as self-adjusting, since the reasoner dynamically defaults to the expensive complete algorithm only when deeper inferencing is actually required. On large datasets (30-60 million assertions), this hybrid approach provides significant performance gains (an average of 15 mins per query on the 60 million dataset compared to 100 mins) without sacrificing completeness or expressivity.
At its core, this hybrid approach builds on the summarization and refinement techniques we described earlier to perform sound and complete reasoning on large Aboxes in relational databases [2] [3]. Briefly, this technique applies a standard tableaux algorithm on a summary Abox A rather than the original Abox A to answer queries. A summary Abox is created by aggregating individuals which are members of the same concepts, so when any given individual is tested in the summary Abox, all individuals mapped to the summary individual are effectively tested at the same time. For a tested individual s in A , if the summary is found to be consistent, then we know that all individuals mapped to that summary individual s are not solutions. But if the summary is found to be inconsistent, it is possible that either (a) a subset of individuals mapped to the summarized individual s are instances of the query or (b) the inconsistency is a spurious effect of the summarization. We determine the answer through refinement, which selectively expands the summary Abox to make it more precise. Refinement is an iterative process that partitions the set of individuals mapped to a single summary individual based on the common edges they have in the original Abox, and remaps each partition to a new summary individual. The iteration ends when either the expanded summary is consistent, or it can be shown that all individuals mapped to the tested summary individual are solutions. Significantly, convergence on the solution is based only on the structure of the refined summary, without testing individuals in A. In practice, the scalability of this algorithm is limited by the number of refinement steps that are needed. Refinement is performed by database join operations, which become expensive when the database is large.
The key insight of our hybrid approach is that the solutions from the sound and incomplete reasoner can be used as a partitioning function for refinement instead of partitioning based on common edges, as described in our earlier work. This effectively removes the obvious solutions from the summary Abox. If the sound and incomplete reasoning algorithm finds all solutions, there will be no solutions left in the summary Abox after this first refinement, so the algorithm will converge very quickly. Any remaining inconsistencies are spurious, and can be resolved in one or a few refinement steps. If the sound and incomplete algorithm finds only some of the solutions, then the refinement process will find the rest of the solutions with fewer refinement steps.
Our key contributions in this paper are as follows: (a) we develop a fast, sound but incomplete algorithm based on query expansion, and describe how to incorporate solutions from this and other such techniques into a sound and complete hybrid algorithm for reasoning over large expressive Aboxes, and (b) we demonstrate its effectiveness in providing performance gains (from 100 minutes per query to 15 minutes per query) on expressive Aboxes with 60 million assertions.
There have been efforts in the semantic web community to define less expressive subsets of OWL-DL for which reasoning is tractable. The EL-family of languages [4] is one such example, for which classification can be done in polynomial time.
To take advantage of this fact, various query answering algorithms for EL have been proposed (e.g. [5]). Another example is the DL-Lite family [6], for which conjunctive query answering is expressible as a first-order logic formula (and hence an SQL query) over the Abox stored in a relational database. The QuOnto algorithm [6] is a sound and complete query expansion algorithm for DL-Lite.
Our query expansion algorithm described in Section 6 is not significantly novel. It is similar in spirit to the EL and DL-Lite query expansion approaches, with some differences, namely: (i) instead of using an EL reasoner to compute additional subclasses during the normalization process (as in [5]), we use a sound and complete OWL-DL reasoner (Pellet) which enables us to discover more entailments outside of EL; (ii) we use a datalog reasoner to compute same-asindividual inferences (considering functional properties) and transitive closure for transitive properties that exist in the ABox.
Furthermore, a key point is that any query answering algorithm for a subset of OWL can be plugged into our sound and complete hybrid OWL-DL reasoning system. When it is known that the optimization is complete based on the underlying logic of the KB4 and the manner in which it is implemented, fallback to our refinement strategy is not necessary. Otherwise, the refinement process will find any remaining solutions.
Query answering in expressive DLs can be reduced to consistency detection. For instance, assume that we want to find all instances of the concept C. To answer this query, each individual a is tested by adding the assertion a : ¬C to the Abox, and checking the new Abox for consistency. If the Abox is inconsistent, then a is an instance of C. For large Aboxes, this approach will clearly not scale. Therefore, in our previous work [3], [7], we modify this approach to perform tableau reasoning on a summarized version of the Abox rather than the original Abox. Formally, an Abox A is a summary Abox of a SHIN Abox A if there is a mapping function f that satisfies the following constraints5 :
If the summary Abox A obtained by applying the mapping function f to A is consistent w.r.t. a given Tbox T and a Rbox R, then A is consistent w.r.t. T and R. However, the converse does not hold. In the case of an inconsistent summary, we use a process of iterative refinement to make the summary more precise, to the point where we can conclude that an inconsistent summary A reflects a real inconsistency in the actual Abox A. Refinement is a process by which only the part of the summary that gives rise to the inconsistency is made more precise, while preserving the summary Abox properties (1)-(3). To pinpoint the portion of the summary that gives rise to the inconsistency, we focus on the justification for the inconsistency, where a justification is a minimal set of assertions which, when taken together, imply a logical contradiction.
We define refinement for a summary individual s in a justification J as a partition where individuals mapped to s are partitioned based on which edges in J each individual actually has. More specifically:
Since an individual may be mapped to a summary individual that is in multiple overlapping justifications, we define:
In a refinement step that refines s in A , new individuals s 1 ...s k replace s in A , where there are k unique key sets key * (a), for all a in A such that f (a) = s. Individuals a and b in A mapped to s in A are partitioned correspondingly, that is, f (a) = f (b) after the refinement step iff key * (a) = key * (b) before the refinement step.
In principle, in the presence of many justifications involving overlapping sets of nodes, the union of the keys could become very large. In practice, we have not observed this across the various knowledge bases we have evaluated, even for ones that do contain overlapping justifications.
If all individuals in A mapped to a summary individual s have the same key w.r.t. J , then it must be the case that they have all the edges in the justification and hence s is precise w.r.t. J . If a justification is precise, we can conclude that all individuals in A mapped to the tested individual in the justification are solutions to the query. In the worst case, iterative refinement can expand a summary Abox into the original Abox, but in practice, we conclude on precise justifications with many individuals mapped to each summary node in the justification.
Our implementation of summarization and refinement in a system called SHER is in terms of RDBMS operations to allow the system to scale to large data sets. However, the iterative process of summarization and refinement is expensive, because (a) it requires expensive join operations on all role assertions in the Abox A to define the key(a), as well as expensive join operations of role assertions with type assertions to rebuild the summary, and (b) it requires several consistency checks to find the many sources of inconsistencies for each summary that gets built. For large knowledge bases with multiple ways in which one can derive a solution to the query, this becomes a serious performance bottleneck.
We illustrate our techniques with the sample knowledge base (Tbox T , the Rbox R and the Abox A) in Figures 1 and 2. This example is a small subset of the UOBM [8] benchmark that we use in our evaluation. To form the summary Abox for Figure 2, the individuals a and b are mapped to a single summary individual w with a concept set of W oman, and the individuals f , g and j are mapped to another summary individual p with a concept set of P erson. The summary Abox is shown in the Figure 3.
T assertions:
(1) W omanCollege ∀hasStudent.W oman (2) ≤ 1isT aughtBy R assertions:
(1) loves likes
Consider the query W omanW ithHobby, which is defined as W oman ≥ 1likes. There are three solutions. The individual b is a solution because loves likes. The individual f is a solution because the course d can be taught by only one P erson, and so f and b will be identified with each other during reasoning. Finally, g is a solution, since isStudentOf (g, W omenCollege) implies that g is a W oman.
Figure 3 shows the entire refinement process for answering this query: We explain these steps in more detail. First, ¬W omanW ithHobby is added to a tested summary individual w. The resulting Abox is inconsistent, and a justification J contains the assertions: w : W oman, loves likes, and loves(w, c). For refinement, we target the summary individuals in J , which are w and c. Refinement makes a justification J precise, that is, it partitions the individuals mapped to the summary node w into a new set of summary nodes to reflect the fact that not all individuals in A mapped to w have the loves(w, c) in J . The summary individual w is therefore split into two new summary nodes, w that has individuals with no loves(w, c) mapped to it (e.g., a), and w that has individuals with loves(w, c) mapped to it (e.g., b). This new refined Abox is still inconsistent, with a new justification J which contains the individuals w and c. Refinement of w or c however is no longer possible, because every individual in A that is mapped to w also has the loves(c, ,) and every individual mapped to c has the same edge (here c is the same as the summary node c). At this point, the justification J is precise, in that it cannot be refined further, and we conclude that all individuals in A mapped to w are solutions to the query.
For the second step, ¬W omanW ithHobby is added to a tested summary individual p. The resulting Abox is inconsistent, and this time there is the jus- tification: isStudentOf (p, i), loves likes, and loves(p, h), combined with the axiom W omanCollege ∀hasStudent.W oman. The result of the second refinement is shown in Figure 3. After this refinement, the subgraph containing p is still inconsistent, and p is not refinable. Therefore, all individuals in A mapped to p , namely g, are solutions.
There is one final justification which is refinable: teacherOf (p , d), teacherOf (w , d), w : W oman, loves likes, loves(w , c), and ≤ 1isT aughtBy. After the third refinement step, we conclude that f mapped to P 1 is a solution.
On large knowledge bases, the cost of each additional refinement is significant, so it is critical to reduce the number of refinements. We show in the next sections how our hybrid reasoning approach can reduce the number of refinements for this example.
The key idea to reducing refinement iterations is to (a) quickly find solutions to the query, (b) refine the summary to isolate these solutions into new summary individuals, and (c) ignore these individuals for the rest of the refinement process. We find solutions quickly by using a sound and incomplete reasoning algorithm which does a form of query expansion described in Section 6. We point out that other reasoner implementations (such as QuOnto) for less expressive logics may also be plugged into this technique.
To illustrate the overall idea in terms of our example in Figure 2, we expand our query W omanW ithHobby into the query W omanW ithHobby(x) (W oman(x) likes(x, y)) (W oman(x) loves(x, y)). This query matches all pairs of individuals in the Abox bound to both x and y, namely the pair (b, c), and this constitutes our set of known bindings. Our next step is to refine the summary Abox, so that the individuals in the solution, namely b and c, are mapped to distinct new summary individuals. We do this by a refining the summary Abox in a manner similar to that described in Section 3; the only difference is that we now partition the Abox individuals according to whether they were bound to any variable in the query or not, rather than according to key sets. That is, f (a) = f (b) after the refinement step iff a and b are mapped to the same summary node before the refinement step and either both or neither a and b are individuals in the set of known bindings. Our algorithm keeps track of the subset of known bindings that actually are answers to the query, which is just b in this case. Next, consistency checking is applied to this refined summary, and any remaining inconsistencies are resolved using the standard iterative refinement and summarization process described in [3].
This approach has a nice property: in cases where the incomplete step actually does find all solutions and the summary itself is consistent, the complete reasoning step may simply be a single consistency check on the refined summary. Since there are no more solutions to be found, the only possible causes of inconsistency are spurious inconsistencies, which are the result of our summarization technique. In practice, we find that the incomplete step captures all solutions on most complex queries on most realistic datasets. This optimization therefore significantly reduces the number of refinements and makes query answering practical for large Aboxes.
One non-obvious part of the hybrid algorithm is that it is important to partition out all individuals that are bound to any variable in the query, and not just the individuals that are are actual solutions to the query. To illustrate why this is the case, consider a simple Abox shown in Figure 4 with 3 patients (q, r, s) who each have an associated lab event (l, m, n), and each event indicates a presence of organisms of different types, where x, y, and z indicate individuals with organisms of type X, Y and Z, respectively. The summary Abox, as shown in the Figure will contain one patient individual p, which has q, r and s mapped to it, one lab event individual e which has l, m and n mapped to it, and 3 individual nodes for organisms x, y, and z. Consider a realistic query, which is to find all patients who have a laboratory event which shows the presence of the organism X. As shown in the Figure 4, if a summary is built with only the solution individual q partitioned out, then it will contain spurious inconsistencies which will cause unnecessary refinement. To avoid this issue, we should not only partition out the solution individual q from p, but also other individuals bound to other variables in the query, which in our example would be l and x. The pseudo-code for our overall algorithm is shown in the function Conjunc-tiveQuery in Figure 5.
Our sound but incomplete reasoning algorithm is based on the well-known recursive query expansion technique suggested in the EL [5] and DL-Lite [6] solutions. As discussed earlier, our approach differs in the following ways: (a) we refer to an OWL-DL reasoner (Pellet) for computing subclasses of a concept when performing the expansion, (b) we have an ABox pre-processing step that uses a datalog reasoner to compute transitive relations in the Abox and same-as inferences between ABox individuals due to functional property assertions. The same individuals are used to expand query solutions, i.e, if individual a is found to be a solution to the SQL query generated by query expansion, and sameAs(a,b) is inferred by the datalog reasoner, we add b to the solution set.
For any given query a : C, we recursively traverse the definitions and subclasses of the concept C. For our sample query x : W omanW ithHobby, we first generate a union of SQL select statements which signify all the possible ways in which this query can be expanded. The first disjunct in the union matches individuals of W omanW ithHobby directly, rdf : type(x, W omanW ithHobby). In this case, however, the W omanW ithHobby type does not appear in the Abox, and so we drop this disjunct. Next we would generate disjuncts to match individuals that are in subclasses of W omanW ithHobby, but in this case there are no subclasses (checked by calling a standard DL reasoner). We then add any complex subclasses of W omanW ithHobby which can be inferred syntactically. In our example, we have one such obvious subclass because W omanW ithHobby is defined as equivalent to W oman ≥ 1likes. The expansion process now recursively continues and we expand this complex concept into a select statement which is a disjunction of conjuncts; i.e., the selection must satisfy the two conditions rdf : type(x, W oman) and likes(x, y), or alternatively, satisfy the two conditions rdf : type(x, W oman) and loves(x, y), since likes has a subproperty loves. These queries are applied against an Abox that has been processed to include all edges materialized from the application of all deterministic merger and transitivity rules.
One technical challenge in query expansion in general is keeping the query relatively simple, especially when given very large Tboxes with deep subclass and subproperty hierarchies. Our approach to this problem was to eliminate forms of query expansion if the concept or role did not appear in the ABox. We therefore maintained a simple cache of all roles and concepts that appeared in the ABox, and limited our expansion to only these concepts and roles.
We evaluated our technique on two knowledge bases: the first is a real-world knowledge base, and real queries of clinical data that we had used in previ-ous work [1], and the second is the UOBM benchmark [8]. Our experiments were conducted on a 2-way 2.4GHz AMD Dual Core Opteron system with 16GB of memory running Linux, and we used IBM DB2 V9.1 as our database. Our Java processes were given a maximum heap size of 8GB for clinical data, and 4GB for UOBM.
In prior work [1], we reported on the use of expressive reasoning for matching of patient records on clinical trials. The 1 year anonymized patient dataset we used contained electronic medical records from Columbia University for 240,269 patients with 22,561 Tbox subclass assertions, 26 million type assertions, and 33 million role assertions. The 22,561 Tbox subclass assertions are a subset of the a larger Tbox which combines SNOMED with Columbia's local taxonomy called MED for a total of 523,368 concepts. For details of the partitioning algorithm used to define the subset see [1]. Although the expressivity of the SNOMED version we used falls in the EL fragment of DL, the expressivity needed to reason on the knowledge base is ALCH. This is because we have type assertions in the Abox which includes assertions of the type ∀R.¬C, where the concept C is itself defined in terms of a subclass or equivalence axiom. As a concrete example, for a given patient, and a specific radiology episode for the patient, the presence of ColonN eoplasm may be ruled out. ColonN eoplasm has complex definitions in SNOMED (e.g., ColonN eoplasm ≡ ∃AssociatedM orphology.N eoplasm ∃F indingSite.Colon ColonDisorder). We selected the 9 clinical trials we evaluated in our earlier work which are shown Table 1. Table 2 shows the DL version of the queries, in the order shown in Table 1. For query N CT 00001162, the results shown are for the union of 7 different disorders, only 4 of which are illustrated in Table 2 approach (HTime), the time in minutes for our previous approach (Time), the number of refinements with our hybrid approach (HRefinements) and the number of refinements with our previous approach (Refinements). As can be seen from the table, the hybrid approach reduced the number of refinements to 1 in all cases, which reflects the refinement needed to check that there are no additional solutions after the incomplete algorithm has completed (The one case where 0 refinements occurred was because for that specific query, our expressivity checker decided that no refinement was needed given the specific filtered Abox that was built for the query and the Tbox.) The hybrid approach improved our overall query times from 100.4 mins on average with a standard deviation of 113.7, to 15.6, with a standard deviation of 3.5. This is not surprising, given that the entire variability in query answering in our previous approach was due to the number of refinements.
We evaluated our approach on the UOBM benchmark, modified to SHIN expressivity. This was done by adding a new concept to correspond to each of the nominals in the dataset (e.g. SwimmingClass for Swimming), adding a type assertion for each nominal (e.g., Swimming : SwimmingClass), and changing any of the references to nominals in the Tbox to point to the class. Currently, we have evaluated membership query answering, and we tested one membership query for each concept in the benchmark 6 , comparing the hybrid approach with our prior techniques. We report results for UOBM size 100-with roughly 7.8 million type assertions and 22.4 million role assertions-and UOBM size 150with about 11.7 million type assertions and 33.5 million role assertions. The queries naturally fall into three categories:
empty Concepts that have no instances in the Abox. simple Concepts that have only simple solutions (i.e. reasoning does not require iterative refinement because the justification viewed as a graph does not have path lengths greater than 1). complex Concepts that have complex solutions (i.e. reasoning requires iterative refinement because the justification viewed as a graph has path lengths greater than 1).
We expect the hybrid approach to benefit only the third category of queries. One complication is that the summary Abox for the UOBM benchmark has a spurious inconsistency induced by the summarization process, so all membership query answering require 2 passes of refinement in order to make the summary consistent. Table 4 shows results for the 3 query categories for UOBM sizes 100 and 150. The first three columns list the UOBM dataset size, the category of query, and how many such queries there are. For both sizes and each query category, we report the average and standard deviation for the query time and the number of passes of refinement. For both datasets, we timed out queries that took longer than 30 minutes to complete; the timeouts occured on both the 100 size (1 timeout) and the 150 size (6 timeouts) for the original approach. Hence, those averages and standard deviations are significant underestimates, and so are marked with a * in the table.
As one might expect, there is some overhead for executing the incomplete query, and so the simpler queries actually show some slowdown in the hybrid approach. However, the results do indicate that our hybrid approach greatly reduces the time for the complex queries, which were the most expensive ones with our previous approach. In fact, for all but one query, the incomplete reasoning algorithm found all the solutions. The one query which was the outlier, GraduateCourse, required propagation from a universal restriction for reasoning, which was not accounted for by our incomplete algorithm. In this case, we proceeded to find the answer through our prior complete reasoning algorithm.
We have developed an efficient, scalable query answering system for large expressive ABoxes. The hybrid approach proposed in this paper combines our novel summarization and refinement technology to do sound and complete OWL-DL reasoning with any incomplete reasoning implementation (possibly for a subset of OWL).
We have used our hybrid solution to build a web-based semantic search engine for biomedical literature, known as Anatomy Lens, details of which can be found in [9]. Anatomy Lens has indexed 300 million RDF triples dealing with PubMed data, and utilizes ontological information from three large biomedical ontologies (Gene ontology, Foundational Model of Anatomy, and MeSH), doing query answering in a few seconds. Performing web-time reasoning for such a large expressive dataset would not have been possible without our approach.
We plan to further optimize our query expansion algorithm by pruning irrelevant queries considering the summary ABox, and to continue to explore the use of SHER in real world semantic web applications.