{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,29]],"date-time":"2026-07-29T02:20:27Z","timestamp":1785291627630,"version":"3.55.0"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"OOPSLA2","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2025,10,9]]},"abstract":"<jats:p>\n                    Graph databases have become an important data management technology across various domains, including biology, sociology, industry (\n                    <jats:italic toggle=\"yes\">e.g<\/jats:italic>\n                    . fraud detection, supply chain management, financial services), and investigative journalism, due to their ability to efficiently store and query large-scale knowledge graphs and networks. Recently, the Graph Query Language (GQL) was introduced as a new ISO standard providing a unified framework for querying graphs. However, this initial specification lacks a formal type system for query validation. As a result, queries can fail at runtime due to type inconsistencies or produce empty results without prior warning. Solving this issue would help users write correct queries, especially on large datasets.\n                  <\/jats:p>\n                  <jats:p>\n                    To address this gap, we introduce a formal type model for a core fragment of GQL extended with property-based filtering and imprecise types both in the schema and the queries. This model, named FPPC, enables static detection of semantically incorrect and stuck queries, improving user feedback. We establish key theoretical properties, including\n                    <jats:italic toggle=\"yes\">emptiness<\/jats:italic>\n                    (detecting empty queries due to type mismatches) and\n                    <jats:italic toggle=\"yes\">type safety<\/jats:italic>\n                    (guaranteeing that well-typed queries do not fail at runtime). Additionally, we prove a\n                    <jats:italic toggle=\"yes\">gradual guarantee<\/jats:italic>\n                    , ensuring that removing type annotations either does not introduce static type errors or only increases the result set. By integrating imprecision into GQL, FPPC offers a flexible solution for handling schema evolution and incomplete type information. This work contributes to making GQL more robust, improving both its usability and its formal foundation.\n                  <\/jats:p>","DOI":"10.1145\/3763061","type":"journal-article","created":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T08:49:50Z","timestamp":1759999790000},"page":"302-328","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Flexible and Expressive Typed Path Patterns for GQL"],"prefix":"10.1145","volume":"9","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3968-6201","authenticated-orcid":false,"given":"Wenjia","family":"Ye","sequence":"first","affiliation":[{"name":"National University of Singapore, Singapore, Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5315-0198","authenticated-orcid":false,"given":"Mat\u00edas","family":"Toro","sequence":"additional","affiliation":[{"name":"University of Chile \/ IMFD, Santiago, Chile"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-4140-1351","authenticated-orcid":false,"given":"Tom\u00e1s","family":"D\u00edaz","sequence":"additional","affiliation":[{"name":"University of Chile, Santiago, Chile"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1846-7210","authenticated-orcid":false,"given":"Bruno C. d. S.","family":"Oliveira","sequence":"additional","affiliation":[{"name":"University of Hong Kong, Hong Kong, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8303-2099","authenticated-orcid":false,"given":"Manuel","family":"Rigger","sequence":"additional","affiliation":[{"name":"National University of Singapore, Singapore, Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4559-6544","authenticated-orcid":false,"given":"Claudio","family":"Gutierrez","sequence":"additional","affiliation":[{"name":"University of Chile, Santiago, Chile"},{"name":"IMFD, Santiago, Chile"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5854-2652","authenticated-orcid":false,"given":"Domagoj","family":"Vrgo\u010d","sequence":"additional","affiliation":[{"name":"Pontificia Universidad Cat\u00f3lica de Chile, Santiago, Chile"},{"name":"IMFD, Santiago, Chile"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,10,9]]},"reference":[{"key":"e_1_3_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3589778"},{"key":"e_1_3_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1322432.1322433"},{"key":"e_1_3_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3627673.3679220"},{"key":"e_1_3_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3434342"},{"key":"e_1_3_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2559905"},{"key":"e_1_3_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463664.2465216"},{"key":"e_1_3_2_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jss.2005.06.028"},{"key":"e_1_3_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3110285"},{"key":"e_1_3_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3290329"},{"key":"e_1_3_2_11_1","unstructured":"Richard Cyganiak David Wood and Markus Lanthaler. 2014. RDF 1.1 Concepts and Abstract Syntax. W3C Recommendation. https:\/\/www.w3.org\/TR\/rdf11-bconcepts\/"},{"key":"e_1_3_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3526057"},{"key":"e_1_3_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3584372.3588662"},{"key":"e_1_3_2_14_1","unstructured":"Nadime Francis Am\u00e9lie Gheerbrant Paolo Guagliardo Leonid Libkin Victor Marsault Wim Martens Filip Murlak Liat Peterfreund Alexandra Rogova and Domagoj Vrgoc. 2023b. A Researcher\u2019s Digest of GQL. In The 26th International Conference on Database Theory 2023. Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik 1\u20131."},{"key":"e_1_3_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2837614.2837670"},{"key":"e_1_3_2_16_1","unstructured":"Steve Harris Andy Seaborne and Eric Prud\u2019hommeaux. 2013. SPARQL 1.1 Query Language. W3C Recommendation. https:\/\/www.w3.org\/TR\/sparql11-bquery\/"},{"key":"e_1_3_2_17_1","doi-asserted-by":"publisher","DOI":"10.2200\/S01125ED1V01Y202109DSK022"},{"key":"e_1_3_2_18_1","volume-title":"Union, Intersection and Refinement Types and Reasoning About Type Disjointness for Security Protocol Analysis","author":"Hri\u0163cu C\u0103t\u0103lin","year":"2011","unstructured":"C\u0103t\u0103lin Hri\u0163cu. 2011. Union, Intersection and Refinement Types and Reasoning About Type Disjointness for Security Protocol Analysis. Ph. D. Dissertation. Saarland University, Saarbr\u00fccken, Germany."},{"key":"e_1_3_2_19_1","unstructured":"ISO\/IEC. 2024. ISO\/IEC 39075:2024 Information technology \u2014 Database languages \u2014 GQL. Available online: https:\/\/www.iso.org\/standard\/76120.html. Accessed: 2024-05-15."},{"key":"e_1_3_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3597503.3623307"},{"key":"e_1_3_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3527325"},{"key":"e_1_3_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2850413"},{"key":"e_1_3_2_23_1","doi-asserted-by":"crossref","unstructured":"Tobias Lindahl and Konstantinos Sagonas. 2006. Practical type inference based on success typings. In Proceedings of the 8th ACM SIGPLAN international conference on Principles and practice of declarative programming. 167\u2013178.","DOI":"10.1145\/1140335.1140356"},{"key":"e_1_3_2_24_1","unstructured":"Memgraph Team. 2023. Memgraph. https:\/\/memgraph.com\/"},{"key":"e_1_3_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3371078"},{"key":"e_1_3_2_26_1","doi-asserted-by":"crossref","unstructured":"Nicole Redaschi and UniProt Consortium. 2009. UniProt in RDF: tackling data integration and distributed annotation with the semantic web. Nature precedings (2009) 1\u20131.","DOI":"10.1038\/npre.2009.3193"},{"key":"e_1_3_2_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/S00224-b016-b9676-b2"},{"key":"e_1_3_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3022670.2951915"},{"key":"e_1_3_2_29_1","article-title":"Gradual typing for functional languages","author":"Siek Jeremy","year":"2006","unstructured":"Jeremy Siek and Walid Taha. 2006. Gradual typing for functional languages. Scheme and Functional Programming.","journal-title":"Scheme and Functional Programming"},{"key":"e_1_3_2_30_1","doi-asserted-by":"publisher","unstructured":"Jeremy G Siek Michael M Vitousek Matteo Cimini and John Tang Boyland. 2015. Refined criteria for gradual typing. In 1st Summit on Advances in Programming Languages (SNAPL 2015). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik 274\u2013293. doi:10.4230\/LIPIcs.SNAPL.2015.274","DOI":"10.4230\/LIPIcs.SNAPL.2015.274"},{"key":"e_1_3_2_31_1","unstructured":"TigerGraph Team. 2021. TigerGraph Documentation - version 3.1. https:\/\/docs.tigergraph.com\/"},{"key":"e_1_3_2_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-b3-b319-b66706-b5_19"},{"key":"e_1_3_2_33_1","unstructured":"Vesoft Inc\/Nebula. 2023. NebulaGraph. https:\/\/www.nebula-bgraph.io\/"},{"key":"e_1_3_2_34_1","doi-asserted-by":"publisher","unstructured":"JimWebber. 2012. Aprogrammatic introduction to Neo4j. In SPLASH. doi:10.1145\/2384716.2384777","DOI":"10.1145\/2384716.2384777"},{"key":"e_1_3_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3689734"},{"key":"e_1_3_2_36_1","doi-asserted-by":"publisher","unstructured":"Wenjia Ye Mat\u00edas Toro Tom\u00e1s D\u00edaz Bruno C. D. S. Oliveira Manuel Rigger Claudio Gutierrez and Domagoj Vrgoc. 2025. Flexible and Expressive Typed Path Patterns for GQL (Artifact). doi:10.5281\/zenodo.16909264","DOI":"10.5281\/zenodo.16909264"},{"key":"e_1_3_2_37_1","doi-asserted-by":"publisher","unstructured":"Wenjia Ye Mat\u00edas Toro and Federico Olmedo. 2023. A Gradual Probabilistic Lambda Calculus. Proceedings of the ACM on Programming Languages 7 OOPSLA1 (Oct. 2023) 256\u2013285. doi:10.1145\/3586036","DOI":"10.1145\/3586036"},{"key":"e_1_3_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3591271"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3763061","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,7,16]],"date-time":"2026-07-16T10:05:51Z","timestamp":1784196351000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3763061"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,9]]},"references-count":37,"journal-issue":{"issue":"OOPSLA2","published-print":{"date-parts":[[2025,10,9]]}},"alternative-id":["10.1145\/3763061"],"URL":"https:\/\/doi.org\/10.1145\/3763061","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,10,9]]},"assertion":[{"value":"2025-03-24","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-08-12","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-10-09","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}