Memory-Saving Evaluation Plans for Datalog

Ontology-based query answering (OBQA), without any doubt, represents one of the fundamental reasoning services in Semantic Web applications. Specifically, OBQA is the task of evaluating a (conjunctive) query over a knowledge base (KB) consisting of an extensional dataset paired with an ontology. A number of effective practical approaches proposed in the literature rewrite the query and the ontology into an equivalent Datalog program. In case of very large datasets, however, classical approaches for evaluating such programs tend to be memory consuming, and may even slow down the computation. In this paper, we explain how to compute a memory-saving evaluation plan consisting of an optimal indexing schema for the dataset together with a suitable body-ordering for each Datalog rule. To evaluate the quality of our approach, we compare our plans with the classical approach used by DLV over widely used ontological benchmarks. The results confirm the memory usage can be significantly reduced without paying any cost in efficiency.