Enhancing Ontological Query-Rewriting via Parallelization

Ontological databases have become the distinguished knowledge bases for today's systems, which consist of an extensional database and an ontology. Several ontological languages have been proposed to model domain knowledge such as Datalog[∃] which extends Datalog with existential quantification. This addition has enriched the language capabilities in capturing complex domain knowledge, however, it makes reasoning tasks, such as query answering, undecidable. Identifying decidable fragments of Datalog[∃] is an important approach to deal with the above issues, where prominent examples are fragments supporting so-called query rewritability. Several rewriting algorithms have been introduced; however, these algorithms are executed in a sequential fashion. In this paper we discuss a methodology that allows existing rewriting algorithms to exploit multi-core architectures, and show how to employ this methodology to implement a parallel version of an existing query rewriting algorithm.