Inline evaluation of hybrid knowledge bases

Abstract

The deployment of knowledge representation formalisms to the Web has created the need for hybrid formalisms that combine heterogeneous knowledge bases (KBs). There are many formalisms proposed by the knowledge representation community for modeling knowledge bases, among which two families are of great importance, in particular in the context of semantic Web. One family is Description Logics (DLs) based ontologies, and the other is rule-based logic programming. The challenge of formalisms of combining ontologies and rules has been drawing a lot of attentions in recent years. Among several proposed approaches, loose coupling of rules and on- tologies aims at combining respective knowledge bases by means of a clean interfacing semantics, in which roughly speaking inferences are mutually exchanged such that the one KB takes the imported information into account, and exports in turn conclusions to the other KB. This approach is fostered by non-monotonic description logic (dl-) programs, where this exchange is handled by a generalization of the answer set semantics of non-monotonic logic programs. Because of the loose coupling nature of dl-programs, one can build engines for dl-programs on top of legacy reasoners. For instance, the DLVHEX system with dl-plugin, which is a state- of-the-art system for dl-programs, is built on top of the ASP reasoner DLV and the DL reasoner RacerPro. Although this architecture is very elegant, the performance of this implementation is suboptimal. We observe that the overhead of calling external reasoners in the classical approach can be the bottleneck of the performance. The aim of this thesis is to improve the reasoning efficiency over hybrid KBs. We propose a new strategy, called inline evaluation, which compiles the whole hybrid KB into a new KB using only one single formalism. Hence we can use a single reasoner to do the reasoning tasks, and improve the efficiency of hybrid reasoning. In case of dl-programs, we design an abstract framework rewriting dl-programs to Datalog program with negation, by compiling every com- ponents carefully and combine them together into a single program. The reduction is sound and complete when the DL ontologies are "Datalog-rewritable". We show that many DLs are Datalog-rewritable by introducing concrete rewriting algorithms. Furthermore, we show that inline evaluation can be used in hybrid KBs of other formalisms. To confirm the hypothesis that the inline evaluation is superior to the classical approach of "ASP + external DL reasoner", we implement the inline evaluation method in the novel DReW system for dl-programs. We conduct extensive evaluations on several benchmark suites and show that DReW system outperforms the classical approach in general, especially for dl-programs of complex structures or with large instances.