{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,19]],"date-time":"2026-05-19T07:14:37Z","timestamp":1779174877237,"version":"3.51.4"},"reference-count":61,"publisher":"Association for Computing Machinery (ACM)","issue":"5","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2025,1]]},"abstract":"<jats:p>Optimising queries with many joins is known to be a hard problem. The explosion of intermediate results as opposed to a much smaller final result poses a serious challenge to modern database management systems (DBMSs). This is particularly glaring in case of analytical queries that join many tables but ultimately only output comparatively small aggregate information. Analogous problems are faced by graph database systems when processing analytical queries with aggregates on top of complex path queries.<\/jats:p>\n          <jats:p>\n            In this work, we propose novel optimisation techniques, both on the logical, and physical level, that allow us to avoid the materialisation of join results for certain types of aggregate queries. The key to these optimisations is the notion of\n            <jats:italic toggle=\"yes\">guardedness<\/jats:italic>\n            , by which we impose restrictions on the occurrence of attributes in GROUP BY clauses and in aggregate expressions. The efficacy of our optimisations is validated through their implementation in Spark SQL and extensive empirical evaluation on various standard benchmarks.\n          <\/jats:p>","DOI":"10.14778\/3718057.3718068","type":"journal-article","created":{"date-parts":[[2025,8,27]],"date-time":"2025-08-27T18:11:49Z","timestamp":1756318309000},"page":"1398-1411","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Avoiding Materialisation for Guarded Aggregate Queries"],"prefix":"10.14778","volume":"18","author":[{"given":"Matthias","family":"Lanzinger","sequence":"first","affiliation":[{"name":"TU Wien, Vienna, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Reinhard","family":"Pichler","sequence":"additional","affiliation":[{"name":"TU Wien, Vienna, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alexander","family":"Selzer","sequence":"additional","affiliation":[{"name":"TU Wien, Vienna, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,8,27]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3129246"},{"key":"e_1_2_1_2_1","volume-title":"Foundations of Databases","author":"Abiteboul Serge","unstructured":"Serge Abiteboul, Richard Hull, and Victor Vianu. 1995. Foundations of Databases. Addison-Wesley. http:\/\/webdam.inria.fr\/Alice\/"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2007.04.013"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICDT.2017.4"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2742797"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/110859440"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.14778\/2556549.2556579"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2018.2850339"},{"key":"e_1_2_1_9_1","unstructured":"Linus Bao Emily Jin Michael Bronstein \u0130smail \u0130lkan Ceylan and Matthias Lanzinger. 2024. Homomorphism Counts as Structural Encodings for Graph Learning. arXiv:2410.18676 [cs.LG] https:\/\/arxiv.org\/abs\/2410.18676"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings NeurIPS. 25280\u201325293","author":"Barcel\u00f3 Pablo","year":"2021","unstructured":"Pablo Barcel\u00f3, Floris Geerts, Juan L. Reutter, and Maksimilian Ryschkov. 2021. Graph Neural Networks with Local Graph Parameters. In Proceedings NeurIPS. 25280\u201325293. https:\/\/proceedings.neurips.cc\/paper\/2021\/hash\/d4d8d1ac7e00e9105775a6b660dd3cbb-Abstract.html"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2012.31"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3555041.3589715"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/S00224-014-9543-Y"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings AMW (CEUR Workshop Proceedings)","volume":"3409","author":"Gottlob Georg","year":"2023","unstructured":"Georg Gottlob, Matthias Lanzinger, Davide Mario Longo, Cem Okulmus, Reinhard Pichler, and Alexander Selzer. 2023. Reaching Back to Move Forward: Using Old Ideas to Achieve a New Level of Query Optimization (short paper). In Proceedings AMW (CEUR Workshop Proceedings), Vol. 3409. CEUR-WS.org. https:\/\/ceur-ws.org\/Vol-3409\/paper6.pdf"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.2303.02723"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/382780.382783"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1809"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1006\/JCSS.2001.1809"},{"key":"e_1_2_1_19_1","unstructured":"Marc H. Graham. 1979. On The Universal Relation. Technical Report. University of Toronto."},{"key":"e_1_2_1_20_1","unstructured":"GraphDB. (accessed July 2024). https:\/\/graphdb.ontotext.com\/."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1265530.1265535"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2636918"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.14778\/3503585.3503586"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3589298"},{"key":"e_1_2_1_25_1","volume-title":"Miranker","author":"Hu Zeyuan","year":"2024","unstructured":"Zeyuan Hu and Daniel P. Miranker. 2024. TreeTracker Join: Turning the Tide When a Tuple Fails to Join. CoRR abs\/2403.01631 (2024). arXiv:2403.01631 http:\/\/arxiv.org\/abs\/2403.01631"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3064027"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-019-00590-9"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1155\/2020\/6364752"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.48550\/ARXIV.2402.08595"},{"key":"e_1_2_1_30_1","volume-title":"K\u00d9ZU Graph Database Management System. In 13th Conference on Innovative Data Systems Research, CIDR 2023","author":"Jin Guodong","year":"2023","unstructured":"Guodong Jin, Xiyang Feng, Ziyi Chen, Chang Liu, and Semih Salihoglu. 2023. K\u00d9ZU Graph Database Management System. In 13th Conference on Innovative Data Systems Research, CIDR 2023, Amsterdam, The Netherlands, January 8\u201311, 2023. www.cidrdb.org. https:\/\/www.cidrdb.org\/cidr2023\/papers\/p48-jin.pdf"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902293"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902280"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.14778\/2831360.2831362"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/S00778-013-0348-4"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.48550\/ARXIV.2406.17076"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850583.2850594"},{"key":"e_1_2_1_37_1","unstructured":"Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. http:\/\/snap.stanford.edu\/data."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3517871"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3461837.3464516"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3548785.3548800"},{"key":"e_1_2_1_41_1","unstructured":"Neo4J. (accessed July 2024). https:\/\/neo4j.com\/."},{"key":"e_1_2_1_42_1","volume-title":"Proceedings ICML (Proceedings of Machine Learning Research)","volume":"119","author":"Nguyen Hoang","year":"2020","unstructured":"Hoang Nguyen and Takanori Maehara. 2020. Graph Homomorphism Convolution. In Proceedings ICML (Proceedings of Machine Learning Research), Vol. 119. PMLR, 7306\u20137316. http:\/\/proceedings.mlr.press\/v119\/nguyen20c.html"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3183758"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3003665.3003667"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/2656335"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2764945"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2013.01.012"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3324961"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.1996.492194"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/3527333"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/3580305.3599953"},{"key":"e_1_2_1_52_1","unstructured":"TPC-DS. [n.d.]. TPC-DS Benchmark. https:\/\/www.tpc.org\/tpcds\/."},{"key":"e_1_2_1_53_1","unstructured":"TPC-H. [n.d.]. TPC-H Benchmark. https:\/\/www.tpc.org\/tpch\/."},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2764946"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.2301.04003"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3517830"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3452808"},{"key":"e_1_2_1_58_1","volume-title":"Proceedings VLDB. VLDB, 82\u201394","author":"Yannakakis Mihalis","year":"1981","unstructured":"Mihalis Yannakakis. 1981. Algorithms for Acyclic Database Schemes. In Proceedings VLDB. VLDB, 82\u201394."},{"key":"e_1_2_1_59_1","volume-title":"COMPSAC","author":"Yu C. T.","year":"1979","unstructured":"C. T. Yu and M. Z. \u00d6zsoyo\u011flu. 1979. An algorithm for tree-query membership of a distributed query. In The IEEE Computer Society's Third International Computer Software and Applications Conference, COMPSAC 1979. 306\u2013312."},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPCCC47392.2019.8958719"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.14778\/3407790.3407840"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3718057.3718068","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,27]],"date-time":"2025-08-27T18:12:54Z","timestamp":1756318374000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3718057.3718068"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1]]},"references-count":61,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2025,1]]}},"alternative-id":["10.14778\/3718057.3718068"],"URL":"https:\/\/doi.org\/10.14778\/3718057.3718068","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2025,1]]},"assertion":[{"value":"2025-08-27","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}