KR2024Proceedings of the 21st International Conference on Principles of Knowledge Representation and ReasoningProceedings of the 21st International Conference on Principles of Knowledge Representation and Reasoning

Hanoi, Vietnam. November 2-8, 2024.

Edited by

ISSN: 2334-1033
ISBN: 978-1-956792-05-8

Sponsored by
Published by

Copyright © 2024 International Joint Conferences on Artificial Intelligence Organization

Boundedness for Unions of Conjunctive Regular Path Queries over Simple Regular Expressions

  1. Diego Figueira(Université de Bordeaux)
  2. S Krishna(IIT Bombay)
  3. Om Swostik Mishra(IIT Bombay)
  4. Anantha Padmanabha(Indian Institute of Technology Madras)

Keywords

  1. Reasoning in knowledge graphs-General
  2. Ontologies and knowledge-enriched data management-General

Abstract

The problem of whether a recursive query can be rewritten as query without recursion is a fundamental reasoning task, known as the boundedness problem. Here we study the boundedness problem for Unions of Conjunctive Regular Path Queries (UCRPQs), a navigational query language extensively used in ontology and graph database querying. The boundedness problem for UCRPQs is known to be decidable, ExpSpace-complete. Here we focus our analysis on UCRPQs using simple regular expressions, which are of high practical relevance and enjoy a lower reasoning complexity. We show that the complexity for the boundedness problem for this UCRPQs fragment is Pi-p-2-complete, and that an equivalent bounded query can be produced in polynomial time whenever possible.

When the query turns out to be unbounded, we also study the task of finding an equivalent maximally bounded query, which we show to be feasible in Pi-p-2 . As a side result of independent interest stemming from our developments, we study a notion of succinct finite automata and prove that its membership problem is NP-complete.