Assertion Absorption in Object Queries over Knowledge Bases

eral DL reasoner will include far more instances of assertion membership tasks than of knowledge base consistency tasks. Thus, this separation of concerns can enable technology that is far more efficient for such workloads, particularly so in the case of “non-Horn” DLs that preclude the possibility of computing so-called canonical ABoxes (such as DLs that include disjunction). In this paper, we contribute to this development by introducing a novel absorption technique for knowledge bases and demonstrate that the technique is efficacious for workloads that contain many thousands of assertion membership tasks. To date, work on absorption has focused on the concept satisfaction problem, a simple case of the assertion membership problem for knowledge bases with an ABox consisting of a single assertion a: >. Indeed, it has been known for some time in this case that lazy unfolding is an important optimization technique in model building algorithms for satisfiability (Baader et al. 1994). It is also imperative for a large TBox to be manipulated by an absorption generation process to maximize the benefits of lazy unfolding in such algorithms, thereby reducing the combinatorial effects of disjunction in underlying chase procedures (Horrocks 1998). We build on earlier work reported at the description logics workshop (Hudek and Weddell 2006) that proposed a generalization of the absorption theory and algorithms developed in (Horrocks and Tobies 2000a; 2000b) for the problem of concept satisfaction. The generalization makes it possible for lazy unfolding to be used for parts of terminologies not handled by earlier absorption algorithms and theory. Binary absorption combines two key ideas. The first is the possibility of avoiding the need to internalize (at least some of the) terminological axioms of the form (A1 uA2) v C, where the Ai denote primitive concepts and C a general concept. The second is an idea relating to role absorptions developed by Tsarkov and Horrocks (Tsarkov and Horrocks 2004). These ideas, in combination and when coupled with standard equivalences, make it possible for an algorithm to completely absorb, e. g., the TBox definition. GOODCLIENT = CLIENT u (∃Recommend−. BANK) (∃Buy. (COSTLY t PROFITABLE)) We develop a novel absorption technique for large collections of factual assertions about individual objects. These assertions are commonly accompanied by implicit background knowledge and form a knowledge base. Both the assertions and the background knowledge are expressed in a suitable language of Description Logic and queries over such knowledge bases can be expressed as assertion retrieval queries. The proposed absorption technique significantly improves the performance of such queries, in particular in cases where a large number of object features are known for the objects represented in such a knowledge base. In addition to the absorption technique we present the results of a preliminary experimental evaluation that validates the efficacy of the proposed optimization.

Authors

• Jiewen Wu
• Alexander Hudek
• David Toman
• Grant Weddell

Keywords

No keywords are indexed for this paper.