{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,15]],"date-time":"2026-05-15T01:17:14Z","timestamp":1778807834110,"version":"3.51.4"},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","issue":"2","funder":[{"name":"Hong Kong RGC Grants","award":["12200524, 16205422, 16204223, 16203924, C2004-21GF, and C2003-23Y"],"award-info":[{"award-number":["12200524, 16205422, 16204223, 16203924, C2004-21GF, and C2003-23Y"]}]},{"name":"NTU startup grant","award":["#025714-00001"],"award-info":[{"award-number":["#025714-00001"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2026,6,30]]},"abstract":"<jats:p>Conjunctive queries with predicates in the form of comparisons that span multiple relations have regained interest recently, due to their relevance in OLAP queries, spatiotemporal databases, and machine learning over relational data. The standard technique, predicate pushdown, has limited efficacy on such comparisons. A technique by Willard can be used to process short comparisons that are adjacent in the join tree in time linear in the input size plus output size. In this article, we describe a new algorithm for evaluating conjunctive queries with both short and long comparisons, and identify an acyclic condition under which linear time can be achieved. We have also implemented the new algorithm on top of Spark, and our experimental results demonstrate order-of-magnitude speedups over SparkSQL on a variety of graph pattern and analytical queries.<\/jats:p>","DOI":"10.1145\/3769424","type":"journal-article","created":{"date-parts":[[2025,9,25]],"date-time":"2025-09-25T11:05:04Z","timestamp":1758798304000},"page":"1-37","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Conjunctive Queries with Comparisons"],"prefix":"10.1145","volume":"51","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0959-5536","authenticated-orcid":false,"given":"Qichen","family":"Wang","sequence":"first","affiliation":[{"name":"College of Computing and Data Science, Nanyang Technological University","place":["Singapore, Singapore"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2178-3716","authenticated-orcid":false,"given":"Ke","family":"Yi","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, The Hong Kong University of Science and Technology","place":["Hong Kong, Hong Kong"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2026,3,6]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.53"},{"key":"e_1_3_3_3_2","volume-title":"Foundations of Databases: The Logical Level (1st ed.)","author":"Abiteboul Serge","year":"1995","unstructured":"Serge Abiteboul, Richard Hull, and Victor Vianu. 1995. Foundations of Databases: The Logical Level (1st ed.). Addison-Wesley Longman Publishing Co., Inc., USA."},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/3426865"},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICDT.2019.21"},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902280"},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/3034786.3056105"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2742797"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","unstructured":"Guillaume Bagan Arnaud Durand and Etienne Grandjean. 2007. On acyclic conjunctive queries and constant delay enumeration. In Computer Science Logic 21st International Workshop CSL 2007 16th Annual Conference of the EACSL Lausanne Switzerland September 11-15 2007 Proceedings (Lecture Notes in Computer Science Vol. 4646) Jacques Duparc and Thomas A. Henzinger (Eds.). Springer 208\u2013222. 10.1007\/978-3-540-74915-8_18","DOI":"10.1007\/978-3-540-74915-8_18"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77974-2"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/3450263"},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.1137\/0217026"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","unstructured":"Bernard Chazelle and Leonidas J. Guibas. 1986. Fractional cascading: II. applications. Algorithmica 1 2 (1986) 163\u2013191. 10.1007\/BF01840441","DOI":"10.1007\/BF01840441"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.5555\/1614191"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/3555041.3589715"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1007\/11604686_1"},{"key":"e_1_3_3_17_2","volume-title":"On the Universal Relation","author":"Graham M. H.","year":"1980","unstructured":"M. H. Graham. 1980. On the Universal Relation. Technical Report. University of Toronto. Computer Systems Research Group and Graham, MH."},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","unstructured":"Xiao Hu and Qichen Wang. 2023. Computing the difference of conjunctive queries efficiently. In Proceedings of the ACM on Management of Data (PACMMOD) 1 2 Article 153 (June 2023) 26 pages. 10.1145\/3589298","DOI":"10.1145\/3589298"},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","unstructured":"Muhammad Idris Mart\u00edn Ugarte Stijn Vansummeren Hannes Voigt and Wolfgang Lehner. 2020. General dynamic Yannakakis: conjunctive queries with theta joins under updates. VLDB J. 29 2-3 (2020) 619\u2013653. 10.1007\/S00778-019-00590-9","DOI":"10.1007\/S00778-019-00590-9"},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902293"},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","unstructured":"Paraschos Koutris Tova Milo Sudeepa Roy and Dan Suciu. 2017. Answering conjunctive queries with inequalities. Theory of Computer Systems 61 1 (July 2017) 2\u201330. 10.1007\/s00224-016-9684-2","DOI":"10.1007\/s00224-016-9684-2"},{"key":"e_1_3_3_22_2","unstructured":"Jure Leskovec and Andrej Krevl. 2014. SNAP datasets: Stanford large network dataset collection. http:\/\/snap.stanford.edu\/data"},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.1145\/2535926"},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/2213556.2213565"},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806772"},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.14778\/3476249.3476306"},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1455"},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.1145\/3725423"},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3517830"},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2002.1848"},{"key":"e_1_3_3_31_2","doi-asserted-by":"publisher","DOI":"10.5555\/1286831.1286840"},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.1109\/CMPSAC.1979.762509"},{"key":"e_1_3_3_33_2","unstructured":"Matei Zaharia Mosharaf Chowdhury Tathagata Das Ankur Dave Justin Ma Murphy McCauly Michael J. Franklin Scott Shenker and Ion Stoica. 2012. Resilient distributed datasets: A fault-tolerant abstraction for in-memory cluster computing. In Proceedings of the 9th USENIX Symposium on Networked Systems Design and Implementation NSDI 2012 San Jose CA USA April 25-27 2012 Steven D. Gribble and Dina Katabi (Eds.). USENIX Association 15\u201328. https:\/\/www.usenix.org\/conference\/nsdi12\/technical-sessions\/presentation\/zaharia"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3769424","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,11]],"date-time":"2026-03-11T11:17:11Z","timestamp":1773227831000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3769424"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,3,6]]},"references-count":32,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,6,30]]}},"alternative-id":["10.1145\/3769424"],"URL":"https:\/\/doi.org\/10.1145\/3769424","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,3,6]]},"assertion":[{"value":"2023-04-14","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-08-19","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-03-06","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}