Containment of Simple Regular Path Queries
This work addresses query containment for practical graph database applications, but it is incremental as it builds on known complexity results for restricted fragments.
The paper tackles the containment problem for Conjunctive Regular Path Queries (CRPQs) in graph databases, focusing on restricted fragments to map complexity results across classes like NP, PITWO, PSPACE, and EXPSPACE.
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, pitwo, pspace or expspace.