{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,24]],"date-time":"2026-04-24T06:51:51Z","timestamp":1777013511965,"version":"3.51.4"},"reference-count":43,"publisher":"Association for Computing Machinery (ACM)","issue":"6","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2025,2]]},"abstract":"<jats:p>SQL\/PGQ and GQL are very recent international standards for querying property graphs: SQL\/PGQ specifies how to query relational representations of property graphs in SQL, while GQL is a standalone language for graph databases. The rapid industrial development of these standards left the academic community trailing in its wake. While digests of the languages have appeared, we do not yet have concise foundational models like relational algebra and calculus for relational databases that enable the formal study of languages, including their expressiveness and limitations. At the same time, work on the next versions of the standards has already begun, to address the perceived limitations of their first versions.<\/jats:p>\n          <jats:p>Motivated by this, we initiate a formal study of SQL\/PGQ and GQL, concentrating on their concise formal model and expressiveness. For the former, we define simple core languages - Core PGQ and Core GQL - that capture the essence of the new standards, are amenable to theoretical analysis, and clarify the difference between PGQ's bottom up evaluation versus GQL's linear, or pipelined approach. Equipped with these models, we both confirm the necessity to extend the language to fill in the expressiveness gaps and identify the source of these deficiencies. We complement our theoretical analysis with an experimental study, demonstrating that existing workarounds in full GQL and PGQ are impractical, further underscoring the necessity to correct deficiencies in language design.<\/jats:p>","DOI":"10.14778\/3725688.3725707","type":"journal-article","created":{"date-parts":[[2025,8,29]],"date-time":"2025-08-29T14:19:21Z","timestamp":1756477161000},"page":"1798-1810","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["GQL and SQL\/PGQ: Theoretical Models and Expressive Power"],"prefix":"10.14778","volume":"18","author":[{"given":"Am\u00e9lie","family":"Gheerbrant","sequence":"first","affiliation":[{"name":"Universit\u00e9 Paris Cit\u00e9, Paris, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Leonid","family":"Libkin","sequence":"additional","affiliation":[{"name":"RelationalAI &amp; University of Edinburgh, Paris &amp; Edinburgh, UK &amp; France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Liat","family":"Peterfreund","sequence":"additional","affiliation":[{"name":"School of CS, Hebrew University, Jerusalem, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alexandra","family":"Rogova","sequence":"additional","affiliation":[{"name":"Universit\u00e9 Paris Cit\u00e9, Paris, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,8,29]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1025"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/3241691.3241694"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00730-2"},{"key":"e_1_2_1_4_1","first-page":"120","volume-title":"Conference Record of the Sixth Annual ACM Symposium on Principles of Programming Languages","author":"Aho A. V.","year":"1979","unstructured":"A. V. Aho and J. D. Ullman. The universality of data retrieval languages. In A. V. Aho, S. N. Zilles, and B. K. Rosen, editors, Conference Record of the Sixth Annual ACM Symposium on Principles of Programming Languages, San Antonio, Texas, USA, January 1979, pages 110\u2013120. ACM Press, 1979."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3104031"},{"key":"e_1_2_1_6_1","volume-title":"Database Theory. Open source at https:\/\/github.com\/pdm-book\/community","author":"Arenas M.","year":"2022","unstructured":"M. Arenas, P. Barcel\u00f3, L. Libkin, W. Martens, and A. Pieris. Database Theory. Open source at https:\/\/github.com\/pdm-book\/community, 2022."},{"key":"e_1_2_1_7_1","first-page":"188","volume-title":"Principles of Database Systems (PODS)","author":"Barcel\u00f3 P.","year":"2013","unstructured":"P. Barcel\u00f3. Querying graph databases. In Principles of Database Systems (PODS), pages 175\u2013188, 2013."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2389241.2389250"},{"key":"e_1_2_1_9_1","series-title":"CEUR Workshop Proceedings","volume-title":"Proceedings of the ISWC 2018 Posters & Demonstrations, Industry and Blue Sky Ideas Tracks co-located with 17th International Semantic Web Conference (ISWC","author":"Bebee B. R.","year":"2018","unstructured":"B. R. Bebee, D. Choi, A. Gupta, A. Gutmans, A. Khandelwal, Y. Kiran, S. Mallidi, B. McGaughy, M. Personick, K. Rajan, S. Rondelli, A. Ryazanov, M. Schmidt, K. Sengupta, B. B. Thompson, D. Vaidya, and S. Wang. Amazon Neptune: Graph data management in the cloud. In M. van Erp, M. Atre, V. L\u00f3pez, K. Srinivas, and C. Fortuna, editors, Proceedings of the ISWC 2018 Posters & Demonstrations, Industry and Blue Sky Ideas Tracks co-located with 17th International Semantic Web Conference (ISWC 2018), Monterey, USA, October 8th - to - 12th, 2018, volume 2180 of CEUR Workshop Proceedings. CEUR-WS.org, 2018."},{"key":"e_1_2_1_10_1","volume-title":"Revisiting the expressiveness landscape of data graph queries. CoRR, abs\/2406.17871","author":"Benedikt M.","year":"2024","unstructured":"M. Benedikt, A. W. Lin, and D. Yen. Revisiting the expressiveness landscape of data graph queries. CoRR, abs\/2406.17871, 2024."},{"key":"e_1_2_1_11_1","series-title":"Cambridge Studies in Advanced Mathematics","volume-title":"Random Graphs","author":"Bollob\u00e1s B.","year":"2011","unstructured":"B. Bollob\u00e1s. Random Graphs, volume 73 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, 2011."},{"key":"e_1_2_1_12_1","first-page":"185","volume-title":"KR 2000, Principles of Knowledge Representation and Reasoning Proceedings of the Seventh International Conference","author":"Calvanese D.","year":"2000","unstructured":"D. Calvanese, G. D. Giacomo, M. Lenzerini, and M. Y. Vardi. Containment of conjunctive regular path queries with inverse. In KR 2000, Principles of Knowledge Representation and Reasoning Proceedings of the Seventh International Conference, Breckenridge, Colorado, USA, April 11\u201315, 2000, pages 176\u2013185, 2000."},{"key":"e_1_2_1_13_1","first-page":"416","volume-title":"Proceedings of the Ninth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS)","author":"Consens M. P.","unstructured":"M. P. Consens and A. O. Mendelzon. GraphLog: a visual formalism for real life recursion. In Proceedings of the Ninth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS), pages 404\u2013416. ACM Press, 1990."},{"key":"e_1_2_1_14_1","first-page":"330","volume-title":"Proceedings of the Association for Computing Machinery Special Interest Group on Management of Data 1987 Annual Conference","author":"Cruz I. F.","year":"1987","unstructured":"I. F. Cruz, A. O. Mendelzon, and P. T. Wood. A graphical query language supporting recursion. In U. Dayal and I. L. Traiger, editors, Proceedings of the Association for Computing Machinery Special Interest Group on Management of Data 1987 Annual Conference, San Francisco, CA, USA, May 27\u201329, 1987, pages 323\u2013330. ACM Press, 1987."},{"key":"e_1_2_1_15_1","first-page":"12","volume-title":"SIGMOD","author":"Deutsch A.","unstructured":"A. Deutsch, N. Francis, A. Green, K. Hare, B. Li, L. Libkin, T. Lindaaker, V. Marsault, W. Martens, J. Michels, F. Murlak, S. Plantikow, P. Selmer, H. Voigt, O. van Rest, D. Vrgo\u010d, M. Wu, and F. Zemke. Graph pattern matching in GQL and SQL\/PGQ. In SIGMOD, pages 1\u201312. ACM, 2022."},{"key":"e_1_2_1_16_1","first-page":"392","volume-title":"Proceedings of the 2020 International Conference on Management of Data, SIGMOD Conference","author":"Deutsch A.","year":"2020","unstructured":"A. Deutsch, Y. Xu, M. Wu, and V. E. Lee. Aggregation support for modern graph analytics in tigergraph. In Proceedings of the 2020 International Conference on Management of Data, SIGMOD Conference 2020, pages 377\u2013392. ACM, 2020."},{"key":"e_1_2_1_17_1","volume-title":"SQL","author":"Eisenberg A.","year":"1999","unstructured":"A. Eisenberg and J. Melton. SQL: 1999, formerly known as SQL 3. SIGMOD Rec., 28(1):131\u2013138, 1999."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19750210112"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/262762.262763"},{"key":"e_1_2_1_20_1","first-page":"250","volume-title":"Proceedings of the 42nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2023","author":"Francis N.","year":"2023","unstructured":"N. Francis, A. Gheerbrant, P. Guagliardo, L. Libkin, V. Marsault, W. Martens, F. Murlak, L. Peterfreund, A. Rogova, and D. Vrgoc. GPC: A pattern calculus for property graphs. In F. Geerts, H. Q. Ngo, and S. Sintos, editors, Proceedings of the 42nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2023, Seattle, WA, USA, June 18\u201323, 2023, pages 241\u2013250. ACM, 2023."},{"key":"e_1_2_1_21_1","first-page":"22","volume-title":"26th International Conference on Database Theory, ICDT 2023, March 28\u201331","volume":"255","author":"Francis N.","year":"2023","unstructured":"N. Francis, A. Gheerbrant, P. Guagliardo, L. Libkin, V. Marsault, W. Martens, F. Murlak, L. Peterfreund, A. Rogova, and D. Vrgoc. A researcher's digest of GQL. In F. Geerts and B. Vandevoort, editors, 26th International Conference on Database Theory, ICDT 2023, March 28\u201331, 2023, Ioannina, Greece, volume 255 of LIPIcs, pages 1:1\u20131:22. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 2023."},{"key":"e_1_2_1_22_1","first-page":"1445","volume-title":"Proceedings of the 2018 International Conference on Management of Data","author":"Francis N.","year":"2018","unstructured":"N. Francis, A. Green, P. Guagliardo, L. Libkin, T. Lindaaker, V. Marsault, S. Plantikow, M. Rydberg, P. Selmer, and A. Taylor. Cypher: An evolving query language for property graphs. In Proceedings of the 2018 International Conference on Management of Data, page 1433\u20131445, New York, NY, USA, 2018. Association for Computing Machinery."},{"key":"e_1_2_1_23_1","first-page":"43","article-title":"A simple proof that connectivity of finite graphs is not first-order definable","volume":"26","author":"Gaifman H.","year":"1985","unstructured":"H. Gaifman and M. Y. Vardi. A simple proof that connectivity of finite graphs is not first-order definable. Bull. EATCS, 26:43\u201344, 1985.","journal-title":"Bull. EATCS"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1964-0181500-1"},{"issue":"3","key":"e_1_2_1_25_1","first-page":"146","article-title":"Implementation strategies for views over property graphs","volume":"2","author":"Han S.","year":"2024","unstructured":"S. Han and Z. G. Ives. Implementation strategies for views over property graphs. Proc. ACM Manag. Data, 2(3):146, 2024.","journal-title":"Proc. ACM Manag. Data"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198528173.001.0001"},{"key":"e_1_2_1_27_1","first-page":"457","volume-title":"Massive Graph Analytics","author":"Hodler A. E.","unstructured":"A. E. Hodler and M. Needham. Graph data science using neo4j. In D. A. Bader, editor, Massive Graph Analytics, pages 433\u2013457. Chapman and Hall\/CRC, 2022."},{"key":"e_1_2_1_28_1","doi-asserted-by":"crossref","unstructured":"N. Immerman. Descriptive complexity. Springer 1999.","DOI":"10.1007\/978-1-4612-0539-5"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/1024196"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2850413"},{"key":"e_1_2_1_31_1","volume-title":"ISO\/IEC JTC1\/SC32 WG3:W26-027","author":"Lindaaker T.","year":"2023","unstructured":"T. Lindaaker. Predicates on sequences of edges. Technical report, ISO\/IEC JTC1\/SC32 WG3:W26-027, 2023."},{"key":"e_1_2_1_32_1","volume-title":"A trichotomy for regular trail queries. Log. Methods Comput. Sci., 19(4)","author":"Martens W.","year":"2023","unstructured":"W. Martens, M. Niewerth, and T. Popp. A trichotomy for regular trail queries. Log. Methods Comput. Sci., 19(4), 2023."},{"key":"e_1_2_1_33_1","unstructured":"PRQL. Pipelined Relational Query Language 2024. https:\/\/prql-lang.org."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-016-9676-2"},{"key":"e_1_2_1_35_1","volume-title":"Existing languages working group: GQL influence graph","author":"Selmer P.","year":"2019","unstructured":"P. Selmer. Existing languages working group: GQL influence graph, 2019. https:\/\/www.gqlstandards.org\/existing-languages."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2021.101816"},{"issue":"12","key":"e_1_2_1_37_1","doi-asserted-by":"crossref","first-page":"4051","DOI":"10.14778\/3685800.3685826","article-title":"SQL has problems. we can fix them: Pipe syntax","volume":"17","author":"Shute J.","year":"2024","unstructured":"J. Shute, S. Bales, M. Brown, J. Browne, B. Dolphin, R. Kudtarkar, A. Litvinov, J. Ma, J. D. Morcos, M. Shen, D. Wilhite, X. Wu, and L. Yu. SQL has problems. we can fix them: Pipe syntax in SQL. Proc. VLDB Endow., 17(12):4051\u20134063, 2024.","journal-title":"SQL. Proc. VLDB Endow."},{"key":"e_1_2_1_38_1","first-page":"1901","volume-title":"Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data","author":"Sun W.","year":"2015","unstructured":"W. Sun, A. Fokoue, K. Srinivas, A. Kementsietsidis, G. Hu, and G. T. Xie. Sqlgraph: An efficient relational-based property graph store. In T. K. Sellis, S. B. Davidson, and Z. G. Ives, editors, Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data, Melbourne, Victoria, Australia, May 31 - June 4, 2015, pages 1887\u20131901. ACM, 2015."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.14778\/3611540.3611614"},{"key":"e_1_2_1_40_1","first-page":"6","volume-title":"Proceedings of the Fourth International Workshop on Graph Data Management Experiences and Systems","author":"van Rest O.","year":"2016","unstructured":"O. van Rest, S. Hong, J. Kim, X. Meng, and H. Chafi. PGQL: a property graph query language. In Proceedings of the Fourth International Workshop on Graph Data Management Experiences and Systems, pages 1\u20136, 2016."},{"key":"e_1_2_1_41_1","volume-title":"dplyr: A Grammar of Data Manipulation","author":"Wickham H.","year":"2023","unstructured":"H. Wickham, R. Fran\u00e7ois, L. Henry, K. M\u00fcller, and D. Vaughan. dplyr: A Grammar of Data Manipulation, 2023. R package version 1.1.4, https:\/\/github.com\/tidyverse\/dplyr."},{"key":"e_1_2_1_42_1","series-title":"CEUR Workshop Proceedings","volume-title":"Proceedings of the 7th Alberto Mendelzon International Workshop on Foundations of Data Management, Puebla\/-Cholula, Mexico, May 21\u201323","author":"Yakovets N.","year":"2013","unstructured":"N. Yakovets, P. Godfrey, and J. Gryz. Evaluation of SPARQL property paths via recursive SQL. In L. Bravo and M. Lenzerini, editors, Proceedings of the 7th Alberto Mendelzon International Workshop on Foundations of Data Management, Puebla\/-Cholula, Mexico, May 21\u201323, 2013, volume 1087 of CEUR Workshop Proceedings. CEUR-WS.org, 2013."},{"key":"e_1_2_1_43_1","volume-title":"ISO\/IEC JTC1\/ SC32 WG3:BGI-022","author":"Zemke F.","year":"2024","unstructured":"F. Zemke. For each segment discussion. Technical report, ISO\/IEC JTC1\/ SC32 WG3:BGI-022, 2024."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3725688.3725707","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,29]],"date-time":"2025-08-29T14:21:14Z","timestamp":1756477274000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3725688.3725707"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,2]]},"references-count":43,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2025,2]]}},"alternative-id":["10.14778\/3725688.3725707"],"URL":"https:\/\/doi.org\/10.14778\/3725688.3725707","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2025,2]]},"assertion":[{"value":"2025-08-29","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}