TY - GEN

T1 - Conjunctive Regular Path Queries under Injective Semantics

AU - Figueira, Diego

AU - Romero, Miguel

N1 - Funding Information:
Diego Figueira is partially supported by ANR QUID, grant ANR-18-CE400031. Miguel Romero is funded by Fondecyt grant 11200956, the Data Observatory Foundation, and the National Center for Artificial Intelligence CENIA FB210017, Basal ANID.
Publisher Copyright:
© 2023 ACM.

PY - 2023/6/18

Y1 - 2023/6/18

N2 - We introduce injective semantics for Conjunctive Regular Path Queries (CRPQs), and study their fundamental properties. We identify two such semantics: Atom-injective and query-injective semantics, both defined in terms of injective homomorphisms. These semantics are natural generalizations of the well-studied class of RPQs under simple-path semantics to the class of CRPQs. We study their evaluation and containment problems, providing useful characterizations for them, and we pinpoint the complexities of these problems. Perhaps surprisingly, we show that containment for CRPQs becomes undecidable for atom-injective semantics, and PSPACE-complete for query-injective semantics, in contrast to the known EXPSPACE-completeness result for the standard semantics. The techniques used differ significantly from the ones known for the standard semantics, and new tools tailored to injective semantics are needed. We complete the picture of complexity by investigating, for each semantics, the containment problem for the main subclasses of CRPQs, namely Conjunctive Queries and CRPQs with finite languages.

AB - We introduce injective semantics for Conjunctive Regular Path Queries (CRPQs), and study their fundamental properties. We identify two such semantics: Atom-injective and query-injective semantics, both defined in terms of injective homomorphisms. These semantics are natural generalizations of the well-studied class of RPQs under simple-path semantics to the class of CRPQs. We study their evaluation and containment problems, providing useful characterizations for them, and we pinpoint the complexities of these problems. Perhaps surprisingly, we show that containment for CRPQs becomes undecidable for atom-injective semantics, and PSPACE-complete for query-injective semantics, in contrast to the known EXPSPACE-completeness result for the standard semantics. The techniques used differ significantly from the ones known for the standard semantics, and new tools tailored to injective semantics are needed. We complete the picture of complexity by investigating, for each semantics, the containment problem for the main subclasses of CRPQs, namely Conjunctive Queries and CRPQs with finite languages.

KW - containment

KW - evaluation

KW - graph databases

KW - injective homomorphisms

KW - regular path queries (RPQ)

KW - simple paths

UR - http://www.scopus.com/inward/record.url?scp=85164253866&partnerID=8YFLogxK

U2 - 10.1145/3584372.3588664

DO - 10.1145/3584372.3588664

M3 - Conference contribution

AN - SCOPUS:85164253866

T3 - Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems

SP - 231

EP - 240

BT - PODS 2023 - Proceedings of the 42nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems

PB - Association for Computing Machinery

T2 - 42nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2023

Y2 - 18 June 2023 through 23 June 2023

ER -