Optimized Backward Chaining Reasoning System for a Semantic Web
Hui Shi, Kurt J. Maly, Steven J. Zeil · 2014
In this paper we consider knowledge bases that organize information using ontologies. Specifically, we investigate reasoning over a semantic web where the underlying knowledgebase covers linked data about science research that are being harvested from the Web and are supplemented and edited by community members. In the semantic web over which we want to reason, frequent changes occur in the underlying knowledge base, and less frequent changes occur in the underlying ontology or the rule set that governs the reasoning. Queries may be composed of mixtures of clauses answerable directly by access to the knowledge base or indirectly via reasoning applied to that base. Two common methods of reasoning over a knowledge base using first order logic are forward chaining and backward chaining. Forward chaining is suitable for frequent computation of answers with data that are relatively static whereas backward chaining is suitable when frequent changes occur in the underlying knowledge base. We introduce new optimization techniques to the backward-chaining algorithm. We show that these techniques together with the query-optimization reported on earlier, will allow us to actually outperform forward-chaining reasoners in scenarios where the knowledge base is subject to frequent change.