A Scalable Backward Chaining-based Reasoner for a Semantic Web

Abstract — In this paper we consider knowledge bases that organize information using ontologies. Specifically, we investi-gate reasoning over a semantic web where the underlying knowledge base 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 under-lying knowledge base, and less frequent changes occur in the underlying ontology or the rule set that governs the reasoning. Interposing a backward chaining reasoner between a knowledge base and a query manager yields an architecture that can support reasoning in the face of frequent chang-es. However, such an interposition of the reasoning introduces uncertainty regarding the size and effort measurements typi-cally exploited during query optimization. We present an algo-rithm for dynamic query optimization in such an architecture. We also introduce new optimization techniques to the back-ward-chaining algorithm. We show that these techniques to-gether 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. Finally, we analyze the impact of these techniques on a large knowledge base that requires external storage. Keywords-semantic web; ontology; reasoning; query optimization; backward chaining. I