Answering Regular Path Queries Under Approximate Semantics in Lightweight Description Logics

Authors

  • Oliver Fernández Gil TU Dresden
  • Anni-Yasmin Turhan TU Dresden

Keywords:

Description Logics, Computational Complexity of Reasoning

Abstract

Classical regular path queries (RPQs) can be too restrictive for some applications and answering such queries under approximate semantics to relax the query is desirable. While for answering regular path queries over graph databases under approximate semantics algorithms are available, such algorithms are scarce for the ontology-mediated setting. In this paper we extend an approach for answering RPQs over graph databases that uses weighted transducers to approximate paths from the query in two ways. The first extension is to answering approximate conjunctive 2-way regular path queries (C2RPQs) over graph databases and the second is to answering C2RPQs over ELH and DL-Lite_R ontologies. We provide results on the computational complexity of the underlying reasoning problems and devise approximate query answering algorithms.

Downloads

Published

2021-05-18

How to Cite

Fernández Gil, O., & Turhan, A.-Y. (2021). Answering Regular Path Queries Under Approximate Semantics in Lightweight Description Logics. Proceedings of the AAAI Conference on Artificial Intelligence, 35(7), 6340-6348. Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/16787

Issue

Section

AAAI Technical Track on Knowledge Representation and Reasoning