An Integrated Framework for Comparing Forward and Backward Chaining Algorithms

Abstract

The fields of data integration/exchange (DI/DE) and Ontology-Based Data Access (OBDA) have been extensively studied across various communities, especially those of the database and the semantic web. The underlying problem is common: using several 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 known as ontology materialisation or 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, 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 comparisons. However, there has not been a principled methodology to compare solutions across both areas. In this thesis, we provide an experimental infrastructure – a set of test scenarios, generator and translator tools, and an automated experiments framework – 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. We perform a series of experiments under a wide range of assumptions shedding light to the advantages and disadvantages of both approaches.