{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,15]],"date-time":"2026-05-15T01:18:37Z","timestamp":1778807917748,"version":"3.51.4"},"reference-count":34,"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":[[2023,1]]},"abstract":"<jats:p>We revisit the classical change propagation framework for query evaluation under updates. The standard framework takes a query plan and materializes the intermediate views, which incurs high polynomial costs in both space and time, with the join operator being the culprit. In this paper, we propose a new change propagation framework without joins, thus naturally avoiding this polynomial blowup. Meanwhile, we show that the new framework still supports constant-delay enumeration of both the deltas and the full query results, the same as in the standard framework. Furthermore, we provide a quantitative analysis of its update cost, which not only recovers many recent theoretical results on the problem, but also yields an effective approach to optimizing the query plan. The new framework is also easy to be integrated into an existing streaming database system. Experimental results show that our system prototype, implemented using Flink DataStream API, significantly outperforms other systems in terms of space, time, and latency.<\/jats:p>","DOI":"10.14778\/3579075.3579080","type":"journal-article","created":{"date-parts":[[2023,3,6]],"date-time":"2023-03-06T17:10:26Z","timestamp":1678122626000},"page":"1046-1058","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":16,"title":["Change Propagation Without Joins"],"prefix":"10.14778","volume":"16","author":[{"given":"Qichen","family":"Wang","sequence":"first","affiliation":[{"name":"Hong Kong Baptist University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiao","family":"Hu","sequence":"additional","affiliation":[{"name":"University of Waterloo"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Binyang","family":"Dai","sequence":"additional","affiliation":[{"name":"Hong Kong University of Science and Technology"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ke","family":"Yi","sequence":"additional","affiliation":[{"name":"Hong Kong University of Science and Technology"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,3,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/2015836.2015849"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.14778\/2336664.2336670"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/110859440"},{"key":"e_1_2_1_4_1","volume-title":"Computer Science Logic","author":"Bagan Guillaume","unstructured":"Guillaume Bagan , Arnaud Durand , and Etienne Grandjean . 2007. On Acyclic Conjunctive Queries and Constant Delay Enumeration . In Computer Science Logic . Springer Berlin Heidelberg , Berlin, Heidelberg , 208--222. Guillaume Bagan, Arnaud Durand, and Etienne Grandjean. 2007. On Acyclic Conjunctive Queries and Constant Delay Enumeration. In Computer Science Logic. Springer Berlin Heidelberg, Berlin, Heidelberg, 208--222."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3125644"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3034786.3034789"},{"key":"e_1_2_1_7_1","first-page":"28","article-title":"Apache Flink: Stream and Batch Processing in a Single Engine","volume":"38","author":"Carbone Paris","year":"2015","unstructured":"Paris Carbone , Asterios Katsifodimos , Stephan Ewen , Volker Markl , Seif Haridi , and Kostas Tzoumas . 2015 . Apache Flink: Stream and Batch Processing in a Single Engine . IEEE Data Engineering Bulletin 38 , 4 (2015), 28 -- 38 . Paris Carbone, Asterios Katsifodimos, Stephan Ewen, Volker Markl, Seif Haridi, and Kostas Tzoumas. 2015. Apache Flink: Stream and Batch Processing in a Single Engine. IEEE Data Engineering Bulletin 38, 4 (2015), 28--38.","journal-title":"IEEE Data Engineering Bulletin"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735496.2735503"},{"key":"e_1_2_1_9_1","volume-title":"Materialized views. Foundations and Trends\u00ae in Databases 4, 4","author":"Chirkova Rada","year":"2012","unstructured":"Rada Chirkova and Jun Yang . 2012. Materialized views. Foundations and Trends\u00ae in Databases 4, 4 ( 2012 ), 295--405. Rada Chirkova and Jun Yang. 2012. Materialized views. Foundations and Trends\u00ae in Databases 4, 4 (2012), 295--405."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3375395.3389130"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732279.2732281"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2742786"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-008-0116-z"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1809"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/290593.290597"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746609"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3064027"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3371316.3371325"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-019-00590-9"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings 19th International Conference on Data Engineering (Cat. No. 03CH37405)","author":"Kang Jaewoo","year":"2003","unstructured":"Jaewoo Kang , Jeffrey F Naughton , and Stratis D Viglas . 2003 . Evaluating window joins over unbounded streams . In Proceedings 19th International Conference on Data Engineering (Cat. No. 03CH37405) . IEEE, 341--352. Jaewoo Kang, Jeffrey F Naughton, and Stratis D Viglas. 2003. Evaluating window joins over unbounded streams. In Proceedings 19th International Conference on Data Engineering (Cat. No. 03CH37405). IEEE, 341--352."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3396375"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3375395.3387646"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/502585.502644"},{"key":"e_1_2_1_24_1","unstructured":"Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. http:\/\/snap.stanford.edu\/data.  Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. http:\/\/snap.stanford.edu\/data."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2746485"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2764947.2764948"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915246"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3183758"},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data. 2773--2776","author":"Nikolic Milos","year":"2020","unstructured":"Milos Nikolic , Haozhe Zhang , Ahmet Kara , and Dan Olteanu . 2020 . F-IVM: learning over fast-evolving relational data . In Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data. 2773--2776 . Milos Nikolic, Haozhe Zhang, Ahmet Kara, and Dan Olteanu. 2020. F-IVM: learning over fast-evolving relational data. In Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data. 2773--2776."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/233269.233361"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732939.2732944"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.2301.04003"},{"key":"e_1_2_1_33_1","volume-title":"Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data. 1225--1239","author":"Wang Qichen","year":"2020","unstructured":"Qichen Wang and Ke Yi . 2020 . Maintaining Acyclic Foreign-Key Joins under Updates . In Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data. 1225--1239 . Qichen Wang and Ke Yi. 2020. Maintaining Acyclic Foreign-Key Joins under Updates. In Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data. 1225--1239."},{"key":"e_1_2_1_34_1","volume-title":"Proc. International Conference on Very Large Data Bases. 82--94","author":"Yannakakis Mihalis","year":"1981","unstructured":"Mihalis Yannakakis . 1981 . Algorithms for acyclic database schemes . In Proc. International Conference on Very Large Data Bases. 82--94 . Mihalis Yannakakis. 1981. Algorithms for acyclic database schemes. In Proc. International Conference on Very Large Data Bases. 82--94."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3579075.3579080","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,3,6]],"date-time":"2023-03-06T17:16:19Z","timestamp":1678122979000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3579075.3579080"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,1]]},"references-count":34,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2023,1]]}},"alternative-id":["10.14778\/3579075.3579080"],"URL":"https:\/\/doi.org\/10.14778\/3579075.3579080","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2023,1]]},"assertion":[{"value":"2023-03-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}