{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T01:21:31Z","timestamp":1760059291896,"version":"build-2065373602"},"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>Graph databases have become an important data management technology across various domains, including biology, sociology, industry (e.g. 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 could have great benefits for users in writing correct queries, especially when handling large datasets.  \nTo 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 emptiness (detecting empty queries due to type mismatches) and type safety (guaranteeing that well-typed queries do not fail at runtime). Additionally, we prove a gradual guarantee, 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.<\/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":0,"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"}]},{"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"}]},{"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"}]},{"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"}]},{"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"}]},{"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"}]},{"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"}]}],"member":"320","published-online":{"date-parts":[[2025,10,9]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_2_1_1_1","DOI":"10.1145\/3589778"},{"doi-asserted-by":"publisher","key":"e_1_2_1_2_1","DOI":"10.1145\/1322432.1322433"},{"doi-asserted-by":"publisher","key":"e_1_2_1_3_1","DOI":"10.1145\/3627673.3679220"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the ACM on Programming Languages, 5, POPL","author":"Schwerter Felipe Ba\u00f1ados","year":"2021","unstructured":"Felipe Ba\u00f1ados Schwerter, Alison M Clark, Khurram A Jafery, and Ronald Garcia. 2021. Abstracting gradual typing moving forward: Precise and space-efficient. Proceedings of the ACM on Programming Languages, 5, POPL (2021), 1\u201328."},{"doi-asserted-by":"publisher","key":"e_1_2_1_5_1","DOI":"10.1145\/2559905"},{"doi-asserted-by":"publisher","key":"e_1_2_1_6_1","DOI":"10.1145\/2463664.2465216"},{"doi-asserted-by":"publisher","key":"e_1_2_1_7_1","DOI":"10.1016\/j.jss.2005.06.028"},{"doi-asserted-by":"publisher","key":"e_1_2_1_8_1","DOI":"10.1145\/3110285"},{"doi-asserted-by":"publisher","key":"e_1_2_1_9_1","DOI":"10.1145\/3290329"},{"unstructured":"Richard Cyganiak David Wood and Markus Lanthaler. 2014. RDF 1.1 Concepts and Abstract Syntax. W3C Recommendation. https:\/\/www.w3.org\/TR\/rdf11-concepts\/","key":"e_1_2_1_10_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_11_1","DOI":"10.1145\/3514221.3526057"},{"doi-asserted-by":"publisher","key":"e_1_2_1_12_1","DOI":"10.1145\/3584372.3588662"},{"key":"e_1_2_1_13_1","volume-title":"Digest of GQL. In The 26th International Conference on Database Theory","author":"Francis Nadime","year":"2023","unstructured":"Nadime Francis, Am\u00e9lie Gheerbrant, Paolo Guagliardo, Leonid Libkin, Victor Marsault, Wim Martens, Filip Murlak, Liat Peterfreund, Alexandra Rogova, and Domagoj Vrgoc. 2023. A Researcher\u2019s Digest of GQL. In The 26th International Conference on Database Theory, 2023. 1\u20131."},{"doi-asserted-by":"publisher","key":"e_1_2_1_14_1","DOI":"10.1145\/2837614.2837670"},{"unstructured":"Steve Harris Andy Seaborne and Eric Prud\u2019hommeaux. 2013. SPARQL 1.1 Query Language. W3C Recommendation. https:\/\/www.w3.org\/TR\/sparql11-query\/","key":"e_1_2_1_15_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_16_1","DOI":"10.2200\/S01125ED1V01Y202109DSK022"},{"volume-title":"Intersection and Refinement Types and Reasoning About Type Disjointness for Security Protocol Analysis. Ph. D. Dissertation","author":"Hri\u0163cu C\u0103t\u0103lin","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_2_1_17_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_2_1_18_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_19_1","DOI":"10.1145\/3597503.3623307"},{"doi-asserted-by":"publisher","key":"e_1_2_1_20_1","DOI":"10.1145\/3527325"},{"doi-asserted-by":"publisher","key":"e_1_2_1_21_1","DOI":"10.1145\/2850413"},{"doi-asserted-by":"publisher","key":"e_1_2_1_22_1","DOI":"10.1145\/1140335.1140356"},{"unstructured":"Memgraph Team. 2023. Memgraph. https:\/\/memgraph.com\/","key":"e_1_2_1_23_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_24_1","DOI":"10.1145\/3371078"},{"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 1\u20131.","key":"e_1_2_1_25_1","DOI":"10.1038\/npre.2009.3193"},{"doi-asserted-by":"publisher","key":"e_1_2_1_26_1","DOI":"10.1007\/S00224-016-9676-2"},{"doi-asserted-by":"publisher","key":"e_1_2_1_27_1","DOI":"10.1145\/3022670.2951915"},{"doi-asserted-by":"crossref","unstructured":"Jeremy Siek and Walid Taha. 2006. Gradual typing for functional languages. Scheme and Functional Programming.","key":"e_1_2_1_28_1","DOI":"10.1007\/978-3-540-73589-2_2"},{"doi-asserted-by":"publisher","key":"e_1_2_1_29_1","DOI":"10.4230\/LIPIcs.SNAPL.2015.274"},{"unstructured":"TigerGraph Team. 2021. TigerGraph Documentation \u2013 version 3.1. https:\/\/docs.tigergraph.com\/","key":"e_1_2_1_30_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_31_1","DOI":"10.1007\/978-3-319-66706-5_19"},{"unstructured":"Vesoft Inc\/Nebula. 2023. NebulaGraph. https:\/\/www.nebula-graph.io\/","key":"e_1_2_1_32_1"},{"doi-asserted-by":"publisher","unstructured":"Jim Webber. 2012. A programmatic introduction to Neo4j. In SPLASH. https:\/\/doi.org\/10.1145\/2384716.2384777 10.1145\/2384716.2384777","key":"e_1_2_1_33_1","DOI":"10.1145\/2384716.2384777"},{"doi-asserted-by":"publisher","key":"e_1_2_1_34_1","DOI":"10.1145\/3689734"},{"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 Vrgo\u010d. 2025. Flexible and Expressive Typed Path Patterns for GQL (Artifact). https:\/\/doi.org\/10.5281\/zenodo.16909264 10.5281\/zenodo.16909264","key":"e_1_2_1_35_1","DOI":"10.5281\/zenodo.16909264"},{"doi-asserted-by":"publisher","key":"e_1_2_1_36_1","DOI":"10.1145\/3586036"},{"doi-asserted-by":"publisher","key":"e_1_2_1_37_1","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":[[2025,10,9]],"date-time":"2025-10-09T17:46:37Z","timestamp":1760031997000},"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":[{"type":"electronic","value":"2475-1421"}],"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"}}]}}