KR2020Proceedings of the 17th International Conference on Principles of Knowledge Representation and ReasoningProceedings of the 17th International Conference on Principles of Knowledge Representation and Reasoning

Rhodes, Greece. September 12-18, 2020.

Edited by
  1. Diego Calvanese
  2. Esra Erdem
  3. Michael Thielscher

ISSN: 2334-1033
ISBN: 978-0-9992411-7-2

Sponsored by
Published by

Copyright © 2020 International Joint Conferences on Artificial Intelligence Organization

Containment of Simple Conjunctive Regular Path Queries

  1. Diego Figueira(Univ. Bordeaux, CNRS, Bordeaux INP, LaBRI)
  2. Adwait Godbole(IIT Bombay)
  3. S. Krishna(IIT Bombay)
  4. Wim Martens(University of Bayreuth)
  5. Matthias Niewerth(University of Bayreuth)
  6. Tina Trautner(University of Bayreuth)
PDF
BibTeX
https://doi.org/10.24963/kr.2020/38

Keywords

  1. Computational aspects of knowledge representation-General
  2. KR and the Web, Semantic Web-General
  3. Knowledge graphs, virtual knowledge graphs, and open linked data-General

Abstract

Testing containment of queries is a fundamental reasoning task in knowledge representation. We study here the containment problem for Conjunctive Regular Path Queries (CRPQs), a navigational query language extensively used in ontology and graph database querying. While it is known that containment of CRPQs is EXPSPACE-complete in general, we focus here on severely restricted fragments, which are known to be highly relevant in practice according to several recent studies. We obtain a detailed overview of the complexity of the containment problem, depending on the features used in the regular expressions of the queries, with completeness results for NP, Pi2p, PSPACE or EXPSPACE.