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 -