ForBackBench: A Benchmark for Chasing vs. Query-Rewriting

Download PDF

Abstract

The fields of Data Integration/Exchange (DE) and Ontology Based Data Access (OBDA) have been extensively studied across different communities. The underlying problem is common: using a number of different structured data-sources mapped to a common mediating schema/ontology/knowledge-graph, answer a query posed on the latter. In DE, forward-chaining algorithms collectively known as the Chase, are used to transform source data to a new materialised instance that satisfies the ontology and can be directly used for query answering. In OBDA, backward-chaining algorithms rewrite the query over the source schema, taking the ontology into account, in order to execute the rewriting directly on the source instances. These two families of reasoning approaches have seen an individual rise in algorithms, practical implementations, and benchmarks. However, there has not been a principled methodology to compare solutions across both areas. In this paper, we provide a benchmark infrastructure --- a set of test scenarios, a set of generator and translator tools, and an experimental infrastructure --- to allow the translation and execution of a DE/OBDA scenario across areas and among different chase and query-rewriting systems. We provide an original methodology and standards to perform cross-approach comparisons and enable a deeper analysis of the interplay between forward- and backward-chaining. In the process, we also present a syntactic restriction of linear Tuple Generating Dependencies that precisely captures DL-Lite_R, a correspondence previously un-investigated. We perform a series of experiments under a wide range of assumptions shedding light to the advantages and disadvantages of both approaches.