{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,23]],"date-time":"2026-10-23T08:21:22Z","timestamp":1792743682451,"version":"4.5.0"},"reference-count":43,"publisher":"Association for Computing Machinery (ACM)","issue":"3","funder":[{"DOI":"10.13039\/501100006374","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-21-CE48-0015"],"award-info":[{"award-number":["ANR-21-CE48-0015"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2025,6,17]]},"abstract":"<jats:p>The workhorse of property graph query languages such as Cypher and GQL is pattern matching. The result of pattern matching is a collection of paths and mappings of variables to graph elements. To increase expressiveness of post-processing of pattern matching results, languages such as Cypher introduce the capability of creating lists of nodes and edges from matched paths, and provide users with standard list processing tools such as reduce. We show that on the one hand, this makes it possible to capture useful classes of queries that pattern matching alone cannot do. On the other hand, we show that this opens backdoor to very high and unexpected expressiveness. In particular one can very easily express several classical NP-hard problems by simple queries that use reduce. This level of expressiveness appears to be beyond what query optimizers can handle, and indeed this is confirmed by an experimental evaluation, showing that such queries time out already on very small graphs. We conclude our analysis with a suggestion on the use of list processing in queries that while retaining its usefulness, avoids the above pitfalls and prevents highly intractable queries.<\/jats:p>","DOI":"10.1145\/3725281","type":"journal-article","created":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T21:23:29Z","timestamp":1750281809000},"page":"1-25","source":"Crossref","is-referenced-by-count":5,"title":["Dangers of List Processing in Querying Property Graphs"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8936-9829","authenticated-orcid":false,"given":"Am\u00e9lie","family":"Gheerbrant","sequence":"first","affiliation":[{"name":"Universit\u00e9 Paris Cit\u00e9, CNRS, IRIF, Paris, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6698-2735","authenticated-orcid":false,"given":"Leonid","family":"Libkin","sequence":"additional","affiliation":[{"name":"RelationalAI, Paris, France and University of Edinburgh, Edinburgh, United Kingdom"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3824-445X","authenticated-orcid":false,"given":"Alexandra","family":"Rogova","sequence":"additional","affiliation":[{"name":"Universit\u00e9 Paris Cit\u00e9, IRIF, Paris, France"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,6,18]]},"reference":[{"key":"e_1_2_2_1_1","first-page":"1421","article-title":"G-CORE","author":"Angles Renzo","year":"2018","unstructured":"Renzo Angles, Marcelo Arenas, Pablo Barcel\u00f3, Peter A. Boncz, George H. L. Fletcher, Claudio Gutierrez, Tobias Lindaaker, Marcus Paradies, Stefan Plantikow, Juan F. Sequeda, Oskar van Rest, and Hannes Voigt. 2018. G-CORE: A Core for Future Graph Query Languages. In SIGMOD. 1421-1432.","journal-title":"A Core for Future Graph Query Languages. In SIGMOD."},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3104031"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2484425.2484440"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/775152.775249"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2187836.2187922"},{"key":"e_1_2_2_6_1","unstructured":"AWS. 2024. Rewriting Cypher queries to run in openCypher on Neptune. https:\/\/docs.aws.amazon.com\/neptune\/latest\/userguide\/migration-opencypher-rewrites.html."},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2389241.2389250"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539798337716"},{"key":"e_1_2_2_9_1","unstructured":"Vlad Batushkov. 2019. Neo4j Reduce in Action. https:\/\/vladbatushkov.medium.com\/one-month-graph-challenge-radio-3591d01674b8."},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.14778\/3149193.3149196"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/298514.298591"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/38713.38749"},{"key":"e_1_2_2_13_1","first-page":"2246","volume-title":"Graph Pattern Matching in GQL and SQL\/PGQ. In SIGMOD '22: International Conference on Management of Data","author":"Deutsch Alin","year":"2022","unstructured":"Alin Deutsch, Nadime Francis, Alastair Green, Keith Hare, Bei Li, Leonid Libkin, Tobias Lindaaker, Victor Marsault, Wim Martens, Jan Michels, Filip Murlak, Stefan Plantikow, Petra Selmer, Oskar van Rest, Hannes Voigt, Domagoj Vrgoc, Mingxi Wu, and Fred Zemke. 2022. Graph Pattern Matching in GQL and SQL\/PGQ. In SIGMOD '22: International Conference on Management of Data, Philadelphia, PA, USA, June 12 - 17, 2022, Zachary G. Ives, Angela Bonifati, and Amr El Abbadi, (Eds.). ACM, 2246-2258."},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3386144"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.21"},{"key":"e_1_2_2_16_1","volume-title":"Adalbert Gerald Soosai Raj, and Jignesh M. Patel","author":"Fan Jing","year":"2015","unstructured":"Jing Fan, Adalbert Gerald Soosai Raj, and Jignesh M. Patel. 2015. The Case Against Specialized Graph Analytics Engines. In Seventh Biennial Conference on Innovative Data Systems Research, CIDR 2015, Asilomar, CA, USA, January 4--7, 2015, Online Proceedings. www.cidrdb.org."},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3584372.3588662"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICDT.2023.1"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3190657"},{"key":"e_1_2_2_20_1","volume-title":"Johnson","author":"Garey Michael R.","year":"1990","unstructured":"Michael R. Garey and David S. Johnson. 1990. Computers and Intractability; A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., USA."},{"key":"e_1_2_2_21_1","volume-title":"Bull. EATCS","volume":"133","author":"Gasarch William","year":"2021","unstructured":"William Gasarch. 2021. Hilbert's Tenth Problem for Fixed d and n. Bull. EATCS, Vol. 133 (2021). http:\/\/eatcs.org\/beatcs\/index.php\/beatcs\/article\/view\/643"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.14778\/3725688.3725707"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978--3--540--24627--5_8"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1006\/JCSS.1996.0042"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.3390\/app12136490"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2850413"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1006\/JCSS.1997.1523"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2494529"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/96709.96748"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536616.1536637"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.46298\/LMCS-19(4:20)2023"},{"key":"e_1_2_2_32_1","volume-title":"Proceedings of the Fifteenth International Conference on Very Large Data Bases (VLDB), Peter M. G. Apers and Gio Wiederhold, (Eds.). Morgan Kaufmann, 185-193","author":"Alberto","year":"1989","unstructured":"Alberto O. Mendelzon and Peter T. Wood. 1989. Finding Regular Simple Paths in Graph Databases. In Proceedings of the Fifteenth International Conference on Very Large Data Bases (VLDB), Peter M. G. Apers and Gio Wiederhold, (Eds.). Morgan Kaufmann, 185-193. http:\/\/www.vldb.org\/conf\/1989\/P185.PDF"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2124295.2124310"},{"key":"e_1_2_2_34_1","unstructured":"Mark Needham. 2013. Neo4j\/Cypher: Getting the hang of the WITH statement. https:\/\/www.markhneedham.com\/blog\/2013\/03\/20\/neo4jcypher-getting-the-hang-of-the-with-statement\/."},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3078447.3078459"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-016--9676--2"},{"key":"e_1_2_2_37_1","unstructured":"Ian Robinson James Webber and Emil Efrem. 2013. O'Reilly Media."},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3186728.3164139"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.5555\/1629683"},{"key":"e_1_2_2_40_1","unstructured":"Cristian Scutaru. 2024. 10 Brilliant or Atrocious Neo4j Cypher Hacks. https:\/\/data-xtractor.com\/blog\/databases\/neo4j-cypher-hacks\/."},{"key":"e_1_2_2_41_1","unstructured":"Petra Selmer. 2019. Existing Languages Working Group: GQL influence graph. https:\/\/www.gqlstandards.org\/existing-languages."},{"key":"e_1_2_2_42_1","doi-asserted-by":"crossref","unstructured":"Oskar van Rest Sungpack Hong Jinha Kim Xuming Meng and Hassan Chafi. 2016. PGQL: a property graph query language. In GRADES. ACM 7.","DOI":"10.1145\/2960414.2960421"},{"key":"e_1_2_2_43_1","volume-title":"Graph databases","author":"Webber Jim","unstructured":"Jim Webber, Emil Eifrem, and Ian Robinson. 2013. Graph databases. O'Reilly Media, Incorporated."}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3725281","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T18:52:47Z","timestamp":1774983167000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3725281"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,17]]},"references-count":43,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,6,17]]}},"alternative-id":["10.1145\/3725281"],"URL":"https:\/\/doi.org\/10.1145\/3725281","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,6,17]]}}}