{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,12]],"date-time":"2025-11-12T16:10:37Z","timestamp":1762963837520,"version":"3.45.0"},"reference-count":23,"publisher":"Association for Computing Machinery (ACM)","issue":"5","funder":[{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["2355\/24"],"award-info":[{"award-number":["2355\/24"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2025,11,10]]},"abstract":"<jats:p>SQL\/PGQ is the emerging ISO standard for querying property graphs defined as views over relational data. We formalize its expressive power across three fragments: the read-only core, the read-write extension, and an extended variant with richer view definitions. Our results show that graph creation plays a central role in determining the expressiveness.<\/jats:p>\n                  <jats:p>The read-only fragment is strictly weaker than the read-write fragment, and the latter is still below the complexity class NL. Extending view definitions with arbitrary arity identifiers closes this gap: the extended fragment captures exactly NL. This yields a strict hierarchy of SQL\/PGQ fragments, whose union covers all NL queries. On ordered structures the hierarchy collapses: once arity-2 identifiers are allowed, higher arities add no power, mirroring the classical transitive-closure collapse and underscoring the central role of view construction in property graph querying.<\/jats:p>","DOI":"10.1145\/3767715","type":"journal-article","created":{"date-parts":[[2025,11,12]],"date-time":"2025-11-12T15:06:02Z","timestamp":1762959962000},"page":"1-18","source":"Crossref","is-referenced-by-count":0,"title":["On the Expressiveness of Languages for Querying Property Graphs in Relational Databases"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0009-0000-2230-1734","authenticated-orcid":false,"given":"Hadar","family":"Rotschield","sequence":"first","affiliation":[{"name":"School of Computer Science and Engineering, The Hebrew University of Jerusalem, Jerusalem, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4788-0944","authenticated-orcid":false,"given":"Liat","family":"Peterfreund","sequence":"additional","affiliation":[{"name":"School of Computer Science and Engineering, The Hebrew University of Jerusalem, Jerusalem, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,11,12]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3190654"},{"key":"e_1_2_1_2_1","volume-title":"Foundations of Modern Query Languages for Graph Databases. ACM Comput. Surv. 50, 5","author":"Angles Renzo","year":"2017","unstructured":"Renzo Angles, Marcelo Arenas, Pablo Barcel\u00f3, Aidan Hogan, Juan L. Reutter, and Domagoj Vrgoc. 2017. Foundations of Modern Query Languages for Graph Databases. ACM Comput. Surv. 50, 5 (2017), 68:1--68:40."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2389241.2389250"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2559905"},{"key":"e_1_2_1_5_1","volume-title":"Relative Expressiveness of Nested Regular Expressions. In Proceedings of the 6th Alberto Mendelzon International Workshop on Foundations of Data Management (AMW 2012) (CEUR Workshop Proceedings","volume":"195","author":"Barcel\u00f3 Pablo","unstructured":"Pablo Barcel\u00f3, Jorge P\u00e9rez, and Juan L. Reutter. 2012. Relative Expressiveness of Nested Regular Expressions. In Proceedings of the 6th Alberto Mendelzon International Workshop on Foundations of Data Management (AMW 2012) (CEUR Workshop Proceedings, Vol. 866), Juliana Freire and Dan Suciu (Eds.). CEUR-WS.org, Aachen, Germany, 180--195. https:\/\/ceur-ws.org\/Vol-866\/paper13.pdf"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the Seventh International Conference on Principles of Knowledge Representation and Reasoning (KR 2000","author":"Calvanese Diego","year":"2000","unstructured":"Diego Calvanese, Giuseppe De Giacomo, Maurizio Lenzerini, and Moshe Y. Vardi. 2000. Containment of Conjunctive Regular Path Queries with Inverse. In Proceedings of the Seventh International Conference on Principles of Knowledge Representation and Reasoning (KR 2000), Anthony G. Cohn, Fausto Giunchiglia, and Bart Selman (Eds.). Morgan Kaufmann, San Francisco, CA, USA, 176--185. Breckenridge, CO, USA, April 11--15, 2000."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/38713.38749"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.2407.06766"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3584372.3588662"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ICDT.2023.1"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0049--237X(08)71879--2"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.14778\/3725688.3725707"},{"key":"e_1_2_1_13_1","volume-title":"GQL Standards Website. https:\/\/www.gqlstandards.org\/ Accessed","author":"GQL Standards Committee","year":"2024","unstructured":"GQL Standards Committee. 2024. GQL Standards Website. https:\/\/www.gqlstandards.org\/ Accessed: November 2024."},{"key":"e_1_2_1_14_1","doi-asserted-by":"crossref","unstructured":"Alastair Green Paolo Guagliardo and Leonid Libkin. 2021. Property graphs and paths in GQL: Mathematical definitions. Technical Reports TR-2021-01. Linked Data Benchmark Council (LDBC). doi:10.54285\/ldbc.TZJP7279","DOI":"10.54285\/ldbc.TZJP7279"},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","unstructured":"Neil Immerman. 1999. Descriptive Complexity. Springer New York.","DOI":"10.1007\/978-1-4612-0539-5"},{"key":"e_1_2_1_16_1","unstructured":"ISO\/IEC JTC 1\/SC 32\/WG 3. 2023. ISO\/IEC 9075--16: SQL\/PGQ - Property Graph Queries. https:\/\/www.iso.org\/standard\/79473.html. Working Draft ISO\/IEC JTC 1\/SC 32\/WG 3."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3722234.3725822"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1021819901281"},{"key":"e_1_2_1_19_1","unstructured":"openCypher. 2017. Cypher Query Language Reference Version 9. https:\/\/github.com\/opencypher\/openCypher\/blob\/master\/docs\/openCypher9.pdf"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICDT.2015.177"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10586-022-03540-3"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3685980.3685984"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2960414.2960421"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3767715","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,12]],"date-time":"2025-11-12T16:08:46Z","timestamp":1762963726000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3767715"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,11,10]]},"references-count":23,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2025,11,10]]}},"alternative-id":["10.1145\/3767715"],"URL":"https:\/\/doi.org\/10.1145\/3767715","relation":{},"ISSN":["2836-6573"],"issn-type":[{"type":"electronic","value":"2836-6573"}],"subject":[],"published":{"date-parts":[[2025,11,10]]}}}