Benchmarking Ontology-Based Query Rewriting Systems

Authors

  • Martha Imprialou University of Oxford
  • Giorgos Stoilos National Technical University of Athens
  • Bernardo Cuenca Grau University of Oxford

DOI:

https://doi.org/10.1609/aaai.v26i1.8215

Keywords:

Description Logics, Query Rewriting, Query Generation, Benchmarking

Abstract

Query rewriting is a prominent reasoning technique in ontology-based data access applications. A wide variety of query rewriting algorithms have been proposed in recent years and implemented in highly optimised reasoning systems. Query rewriting systems are complex software programs; even if based on provably correct algorithms, sophisticated optimisations make the systems more complex and errors become more likely to happen. In this paper, we present an algorithm that, given an ontology as input, synthetically generates ``relevant'' test queries. Intuitively, each of these queries can be used to verify whether the system correctly performs a certain set of ``inferences'', each of which can be traced back to axioms in the input ontology. Furthermore, we present techniques that allow us to determine whether a system is unsound and/or incomplete for a given test query and ontology. Our evaluation shows that most publicly available query rewriting systems are unsound and/or incomplete, even on commonly used benchmark ontologies; more importantly, our techniques revealed the precise causes of their correctness issues and the systems were then corrected based on our feedback. Finally, since our evaluation is based on a larger set of test queries than existing benchmarks, which are based on hand-crafted queries, it also provides a better understanding of the scalability behaviour of each system.

Downloads

Published

2021-09-20

How to Cite

Imprialou, M., Stoilos, G., & Cuenca Grau, B. (2021). Benchmarking Ontology-Based Query Rewriting Systems. Proceedings of the AAAI Conference on Artificial Intelligence, 26(1), 779-785. https://doi.org/10.1609/aaai.v26i1.8215

Issue

Section

AAAI Technical Track: Knowledge Representation and Reasoning