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 条

[21]

Florescu D., 1998, Proceedings of the Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems. PODS 1998, P139, DOI 10.1145/275487.275503

[22] Cypher: An Evolving Query Language for Property Graphs [J].

Francis, Nadime ;

Green, Alastair ;

Guagliardo, Paolo ;

Libkin, Leonid ;

Lindaaker, Tobias ;

Marsault, Victor ;

Plantikow, Stefan ;

Rydberg, Mats ;

Selmer, Petra ;

Taylor, Andres .

SIGMOD'18: PROCEEDINGS OF THE 2018 INTERNATIONAL CONFERENCE ON MANAGEMENT OF DATA, 2018, :1433-1445

[23] Querying Graphs with Data [J].

Libkin, Leonid ;

Martens, Wim ;

Vrgoc, Domagoj .

JOURNAL OF THE ACM, 2016, 63 (02)

[24] Getting the Most Out of Wikidata: Semantic Technology Usage in Wikipedia's Knowledge Graph [J].

Malyshev, Stanislav ;

Kroetzsch, Markus ;

Gonzalez, Larry ;

Gonsior, Julius ;

Bielefeldt, Adrian .

SEMANTIC WEB - ISWC 2018, PT II, 2018, 11137 :376-394

[25] Containment and equivalence for a fragment of XPath [J].

Miklau, G ;

Suciu, D .

JOURNAL OF THE ACM, 2004, 51 (01) :2-45

[26] ON THE COMPLEXITY OF XPATH CONTAINMENT IN THE PRESENCE OF DISJUNCTION, DTDS, AND VARIABLES [J].

Neven, Frank ;

Schwentick, Thomas .

LOGICAL METHODS IN COMPUTER SCIENCE, 2006, 2 (03)

[27] nSPARQL: A navigational language for RDF [J].

Perez, Jorge ;

Arenas, Marcelo ;

Gutierrez, Claudio .

JOURNAL OF WEB SEMANTICS, 2010, 8 (04) :255-270

[28] EQUIVALENCES AMONG RELATIONAL EXPRESSIONS WITH THE UNION AND DIFFERENCE OPERATORS [J].

SAGIV, Y ;

YANNAKAKIS, M .

JOURNAL OF THE ACM, 1980, 27 (04) :633-655

[29]

Wood PT, 2003, LECT NOTES COMPUT SC, V2572, P300

← 1 2 3 →