Containment of Simple Conjunctive Regular Path Queries

被引：0

作者：

Figueira, Diego ^{[1
]}

Godbole, Adwait ^{[2
]}

Krishna, S. ^{[2
]}

Martens, Wim ^{[3
]}

Niewerth, Matthias ^{[3
]}

Trautner, Tina ^{[3
]}

机构：

[1] Univ Bordeaux, CNRS, Bordeaux INP, LaBRI,UMR 5800, Talence, France

[2] Indian Inst Technol, Mumbai, Maharashtra, India

[3] Univ Bayreuth, Bayreuth, Germany

来源：

KR2020: PROCEEDINGS OF THE 17TH INTERNATIONAL CONFERENCE ON PRINCIPLES OF KNOWLEDGE REPRESENTATION AND REASONING | 2020年

关键词：

LANGUAGE;

D O I：

暂无

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

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, Pi(p)(2), PSPACE or EXPSPACE.

引用

页码：371 / 380

页数：10

共 29 条

[1] The Homomorphism Property in Query Containment and Data Integration
Afrati, Foto N.
[J]. IDEAS '19: PROCEEDINGS OF THE 23RD INTERNATIONAL DATABASE APPLICATIONS & ENGINEERING SYMPOSIUM (IDEAS 2019), 2019, : 2 - 13
[2] Baeza P. Barcelo, 2013, ACM S PRINC DAT SYST, P175
[3] Barcelo P., 2019, LIPICS, V132
[4] Querying Regular Graph Patterns
Barcelo, Pablo
Libkin, Leonid
Reutter, Juan L.
[J]. JOURNAL OF THE ACM, 2014, 61 (01)
[5] Conjunctive query containment over trees
Bjoerklund, Henrik
Martens, Wim
Schwentick, Thomas
[J]. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2011, 77 (03) : 450 - 472
[6] Björklund H, 2013, LECT NOTES COMPUT SC, V8087, P171, DOI 10.1007/978-3-642-40313-2_17
[7] An analytical study of large SPARQL query logs
Bonifati, Angela
Martens, Wim
Timm, Thomas
[J]. VLDB JOURNAL, 2020, 29 (2-3) : 655 - 679
[8] Navigating the Maze of Wikidata Query Logs
Bonifati, Angela
Martens, Wim
Timm, Thomas
[J]. WEB CONFERENCE 2019: PROCEEDINGS OF THE WORLD WIDE WEB CONFERENCE (WWW 2019), 2019, : 127 - 138
[9] Calvanese D, 2002, LECT NOTES COMPUT SC, V2397, P40
[10] Calvanese D., 2000, Proceedings of the Seventh International Conference on Principles of Knowledge Representation and Reasoning. KR'00, P176

← 1 2 3 →