{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,5]],"date-time":"2026-02-05T11:59:30Z","timestamp":1770292770637,"version":"3.49.0"},"reference-count":82,"publisher":"Association for Computing Machinery (ACM)","issue":"OOPSLA2","license":[{"start":{"date-parts":[[2022,10,31]],"date-time":"2022-10-31T00:00:00Z","timestamp":1667174400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"NSF","award":["CCF-1815949"],"award-info":[{"award-number":["CCF-1815949"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2022,10,31]]},"abstract":"<jats:p>Data processing systems are a fundamental component of the modern computing stack. These systems are routinely deployed online: they continuously receive the requests of data processing operations, and continuously return the results to end users or client applications. Online data processing systems have unique features beyond conventional data processing, and the optimizations designed for them are complex, especially when data themselves are structured and dynamic. This paper describes DON Calculus, the first rigorous foundation for online data processing. It captures the essential behavior of both the backend data processing engine and the frontend application, with the focus on two design dimensions essential yet unique to online data processing systems: incremental operation processing (IOP) and temporal locality optimization (TLO). A novel design insight is that the operations continuously applied to the data can be defined as an operation stream flowing through the data structure, and this abstraction unifies diverse designs of IOP and TLO in one calculus. DON Calculus is endowed with a mechanized metatheory centering around a key observable equivalence property: despite the significant non-deterministic executions introduced by IOP and TLO, the observable result of DON Calculus data processing is identical to that of conventional data processing without IOP and TLO. Broadly, DON Calculus is a novel instance in the active pursuit of providing rigorous guarantees to the software system stack. The specification and mechanization of DON Calculus provide a sound base for the designers of future data processing systems to build upon, helping them embrace rigorous semantic engineering without the need of developing from scratch.<\/jats:p>","DOI":"10.1145\/3563320","type":"journal-article","created":{"date-parts":[[2022,10,31]],"date-time":"2022-10-31T20:23:35Z","timestamp":1667247815000},"page":"899-928","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["The essence of online data processing"],"prefix":"10.1145","volume":"6","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5920-7442","authenticated-orcid":false,"given":"Philip","family":"Dexter","sequence":"first","affiliation":[{"name":"SUNY Binghamton, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2768-3898","authenticated-orcid":false,"given":"Yu David","family":"Liu","sequence":"additional","affiliation":[{"name":"SUNY Binghamton, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5643-1043","authenticated-orcid":false,"given":"Kenneth","family":"Chiu","sequence":"additional","affiliation":[{"name":"SUNY Binghamton, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,10,31]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"2010. Neo4j Graph Database. http:\/\/www.neo4j.org \t\t\t\t  2010. Neo4j Graph Database. http:\/\/www.neo4j.org"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1186632.1186634"},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","unstructured":"Andrew W. Appel Lennart Beringer Adam Chlipala Benjamin C. Pierce Zhong Shao Stephanie Weirich and Steve Zdancewic. 2016. The DeepSpec Project: The Science of Deep Specification . https:\/\/deepspec.org\/ \t\t\t\t  Andrew W. Appel Lennart Beringer Adam Chlipala Benjamin C. Pierce Zhong Shao Stephanie Weirich and Steve Zdancewic. 2016. The DeepSpec Project: The Science of Deep Specification . https:\/\/deepspec.org\/","DOI":"10.1098\/rsta.2016.0331"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1031570.1031572"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/359636.359715"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2660193.2660225"},{"key":"e_1_2_1_7_1","unstructured":"Dimitri P Bertsekas and John N Tsitsiklis. 1989. Parallel and distributed computation: numerical methods. 23 Prentice hall Englewood Cliffs NJ. \t\t\t\t  Dimitri P Bertsekas and John N Tsitsiklis. 1989. Parallel and distributed computation: numerical methods. 23 Prentice hall Englewood Cliffs NJ."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0169-7552(98)00110-X"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/233269.233368"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-39815-8_4"},{"key":"e_1_2_1_11_1","unstructured":"Luca Cardelli. 1988. Phase Distinctions in Type Theory. \t\t\t\t  Luca Cardelli. 1988. Phase Distinctions in Type Theory."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/41625.41641"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2168836.2168846"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2168836.2168854"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1111320.1111054"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1327452.1327492"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3241625.2976014"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5281\/zenodo.7051651"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3314221.3314598"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/HPEC.2012.6408680"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICPADS.2010.116"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2951913.2951938"},{"key":"e_1_2_1_23_1","volume-title":"The Second Workshop on Incremental Computing (IC\u201919)","author":"Eymer Jeffrey","year":"2019","unstructured":"Jeffrey Eymer , Philip Dexter , and Yu David Liu . 2019 . Toward Lazy Evaluation in a Graph Database . In The Second Workshop on Incremental Computing (IC\u201919) . Jeffrey Eymer, Philip Dexter, and Yu David Liu. 2019. Toward Lazy Evaluation in a Graph Database. In The Second Workshop on Incremental Computing (IC\u201919)."},{"key":"e_1_2_1_24_1","unstructured":"Jeff Eymer Philip Dexter Joseph Raskind and Yu David Liu. 2022. The PitStop System online at. https:\/\/github.com\/PitStop-Github\/PitStop \t\t\t\t  Jeff Eymer Philip Dexter Joseph Raskind and Yu David Liu. 2022. The PitStop System online at. https:\/\/github.com\/PitStop-Github\/PitStop"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/199448.199484"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796899003329"},{"key":"e_1_2_1_27_1","volume-title":"Presented as part of the 10th USENIX Symposium on Operating Systems Design and Implementation (OSDI 12)","author":"Gonzalez Joseph E.","year":"1971","unstructured":"Joseph E. Gonzalez , Yucheng Low , Haijie Gu , Danny Bickson , and Carlos Guestrin . 2012. PowerGraph: Distributed Graph-Parallel Computation on Natural Graphs . In Presented as part of the 10th USENIX Symposium on Operating Systems Design and Implementation (OSDI 12) . USENIX , Hollywood, CA . 17\u201330. isbn:978-1-93 1971 -96-6 Joseph E. Gonzalez, Yucheng Low, Haijie Gu, Danny Bickson, and Carlos Guestrin. 2012. PowerGraph: Distributed Graph-Parallel Computation on Natural Graphs. In Presented as part of the 10th USENIX Symposium on Operating Systems Design and Implementation (OSDI 12). USENIX, Hollywood, CA. 17\u201330. isbn:978-1-931971-96-6"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3200691.3178506"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-75987-4_11"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jlamp.2019.03.002"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796818000035"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/4472.4478"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2666356.2594324"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2592798.2592799"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ECOOP.2016.11"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ECOOP.2017.14"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/96709.96744"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2528412"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/322217.322230"},{"key":"e_1_2_1_40_1","first-page":"30","volume-title":"Version Traveler: Fast and Memory-Efficient Version Switching in Graph Processing Systems. In 2016 USENIX Annual Technical Conference (USENIX ATC 16)","author":"Ju Xiaoen","year":"1971","unstructured":"Xiaoen Ju , Dan Williams , Hani Jamjoom , and Kang G. Shin . 2016 . Version Traveler: Fast and Memory-Efficient Version Switching in Graph Processing Systems. In 2016 USENIX Annual Technical Conference (USENIX ATC 16) . USENIX Association, Denver, CO. 523\u2013536. isbn:978-1-93 1971 - 30 - 30 Xiaoen Ju, Dan Williams, Hani Jamjoom, and Kang G. Shin. 2016. Version Traveler: Fast and Memory-Efficient Version Switching in Graph Processing Systems. In 2016 USENIX Annual Technical Conference (USENIX ATC 16). USENIX Association, Denver, CO. 523\u2013536. isbn:978-1-931971-30-0"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3364180"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2012.37"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/PROC.1987.13876"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/1596614.1596622"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.14778\/2212351.2212354"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807184"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/3447786.3456230"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/3302424.3303974"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/1640089.1640091"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/2660193.2660242"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522738"},{"key":"e_1_2_1_52_1","volume-title":"Proc. 8th ACM\/USENIX Symposium on Networked Systems Design and Implementation. 113\u2013126","author":"Murray Derek G","year":"2011","unstructured":"Derek G Murray , Malte Schwarzkopf , Christopher Smowton , Steven Smith , Anil Madhavapeddy , and Steven Hand . 2011 . CIEL: a universal execution engine for distributed data-flow computing . In Proc. 8th ACM\/USENIX Symposium on Networked Systems Design and Implementation. 113\u2013126 . Derek G Murray, Malte Schwarzkopf, Christopher Smowton, Steven Smith, Anil Madhavapeddy, and Steven Hand. 2011. CIEL: a universal execution engine for distributed data-flow computing. In Proc. 8th ACM\/USENIX Symposium on Networked Systems Design and Implementation. 113\u2013126."},{"key":"e_1_2_1_53_1","volume-title":"Making Sense of Performance in Data Analytics Frameworks. In 12th USENIX Symposium on Networked Systems Design and Implementation (NSDI 15)","author":"Ousterhout Kay","year":"2015","unstructured":"Kay Ousterhout , Ryan Rasti , Sylvia Ratnasamy , Scott Shenker , and Byung-Gon Chun . 2015 . Making Sense of Performance in Data Analytics Frameworks. In 12th USENIX Symposium on Networked Systems Design and Implementation (NSDI 15) . USENIX Association, Oakland, CA. 293\u2013307. isbn:978-1-93 1971-218 Kay Ousterhout, Ryan Rasti, Sylvia Ratnasamy, Scott Shenker, and Byung-Gon Chun. 2015. Making Sense of Performance in Data Analytics Frameworks. In 12th USENIX Symposium on Networked Systems Design and Implementation (NSDI 15). USENIX Association, Oakland, CA. 293\u2013307. isbn:978-1-931971-218"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.1995.380386"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.1988.105474"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/75277.75305"},{"key":"e_1_2_1_57_1","first-page":"1247","volume-title":"Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data (SIGMOD \u201912)","author":"Ramachandra Karthik","unstructured":"Karthik Ramachandra and S. Sudarshan . 2012. Holistic Optimization by Prefetching Query Results . In Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data (SIGMOD \u201912) . 133\u2013144. isbn:978-1-4503- 1247 - 1249 Karthik Ramachandra and S. Sudarshan. 2012. Holistic Optimization by Prefetching Query Results. In Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data (SIGMOD \u201912). 133\u2013144. isbn:978-1-4503-1247-9"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.14778\/3021924.3021929"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522740"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/3009837.3009891"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/42201.42203"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/971699.318993"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1145\/3267809.3267811"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2882950"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/2442516.2442530"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-11957-6_27"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1145\/2666356.2594305"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1145\/1297027.1297043"},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1145\/3486609.3487203"},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1145\/2567948.2580051"},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1145\/258993.259019"},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.14778\/2752939.2752940"},{"key":"e_1_2_1_73_1","volume-title":"StreamIt: A Language for Streaming Applications","author":"Thies William","unstructured":"William Thies , Michal Karczmarek , and Saman Amarasinghe . 2002. StreamIt: A Language for Streaming Applications . In Compiler Construction, R. Nigel Horspool (Ed.). 2304, Springer Berlin Heidelberg , Berlin, Heidelberg . 179\u2013196. isbn:978-3-540-45937-8 William Thies, Michal Karczmarek, and Saman Amarasinghe. 2002. StreamIt: A Language for Streaming Applications. In Compiler Construction, R. Nigel Horspool (Ed.). 2304, Springer Berlin Heidelberg, Berlin, Heidelberg. 179\u2013196. isbn:978-3-540-45937-8"},{"key":"e_1_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-44202-9_15"},{"key":"e_1_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213957"},{"key":"e_1_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.1145\/3037697.3037748"},{"key":"e_1_2_1_77_1","first-page":"3","article-title":"Asynchronous Large-Scale Graph Processing Made Easy","volume":"13","author":"Wang Guozhang","year":"2013","unstructured":"Guozhang Wang , Wenlei Xie , Alan J Demers , and Johannes Gehrke . 2013 . Asynchronous Large-Scale Graph Processing Made Easy .. In CIDR. 13 , 3 \u2013 6 . Guozhang Wang, Wenlei Xie, Alan J Demers, and Johannes Gehrke. 2013. Asynchronous Large-Scale Graph Processing Made Easy.. In CIDR. 13, 3\u20136.","journal-title":"CIDR."},{"key":"e_1_2_1_78_1","volume-title":"2015 USENIX Annual Technical Conference (USENIX ATC 15)","author":"Wang Kai","year":"2015","unstructured":"Kai Wang , Guoqing Xu , Zhendong Su , and Yu David Liu . 2015 . GraphQ: Graph Query Processing with Abstraction Refinement\u2014 Scalable and Programmable Analytics over Very Large Graphs on a Single PC . In 2015 USENIX Annual Technical Conference (USENIX ATC 15) . USENIX Association, Santa Clara, CA. 387\u2013401. isbn:978-1-93 1971-225 Kai Wang, Guoqing Xu, Zhendong Su, and Yu David Liu. 2015. GraphQ: Graph Query Processing with Abstraction Refinement\u2014 Scalable and Programmable Analytics over Very Large Graphs on a Single PC. In 2015 USENIX Annual Technical Conference (USENIX ATC 15). USENIX Association, Santa Clara, CA. 387\u2013401. isbn:978-1-931971-225"},{"key":"e_1_2_1_79_1","doi-asserted-by":"publisher","DOI":"10.1145\/2851141.2851145"},{"key":"e_1_2_1_80_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522737"},{"key":"e_1_2_1_81_1","doi-asserted-by":"publisher","DOI":"10.1145\/2934664"},{"key":"e_1_2_1_82_1","doi-asserted-by":"publisher","DOI":"10.1145\/2688500.2688507"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3563320","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3563320","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:38:10Z","timestamp":1750178290000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3563320"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,10,31]]},"references-count":82,"journal-issue":{"issue":"OOPSLA2","published-print":{"date-parts":[[2022,10,31]]}},"alternative-id":["10.1145\/3563320"],"URL":"https:\/\/doi.org\/10.1145\/3563320","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,10,31]]},"assertion":[{"value":"2022-10-31","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}