2020/03/09 by Diego Figueira, Adwait Godbole, Figueira, Diego +9
Computer Science · #Advanced Database Systems and Queries #Artificial Intelligence (cs.AI) #Data Management and Algorithms #Databases (cs.DB) #FOS: Computer and information sciences #Semantic Web and Ontologies
paper · pdf · doi:10.48550/arxiv.2003.04411
openalex publication_date 2020/03/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Testing containment of queries is a fundamental reasoning task in knowledge\nrepresentation. We study here the containment problem for Conjunctive Regular\nPath Queries (CRPQs), a navigational query language extensively used in\nontology and graph database querying. While it is known that containment of\nCRPQs is expspace-complete in general, we focus here on severely restricted\nfragments, which are known to be highly relevant in practice according to\nseveral recent studies. We obtain a detailed overview of the complexity of the\ncontainment problem, depending on the features used in the regular expressions\nof the queries, with completeness results for np, pitwo, pspace or expspace.\n