{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,11]],"date-time":"2026-04-11T02:15:02Z","timestamp":1775873702329,"version":"3.50.1"},"reference-count":48,"publisher":"Association for Computing Machinery (ACM)","issue":"7","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2023,3]]},"abstract":"<jats:p>Incremental view maintenance (IVM) has long been a central problem in database theory. Many solutions have been proposed for restricted classes of database languages, such as the relational algebra, or Datalog. These techniques do not naturally generalize to richer languages. In this paper we give a general, heuristic-free solution to this problem in 3 steps: (1) we describe a simple but expressive language called DBSP for describing computations over data streams; (2) we give a new mathematical definition of IVM and a general algorithm for solving IVM for arbitrary DBSP programs, and (3) we show how to model many rich database query languages using DBSP (including the full relational algebra, queries over sets and multisets, arbitrarily nested relations, aggregation, flatmap (unnest), monotonic and non-monotonic recursion, streaming aggregation, and arbitrary compositions of all of these). SQL and Datalog can both be implemented in DBSP. As a consequence, we obtain efficient incremental view maintenance algorithms for queries written in all these languages.<\/jats:p>","DOI":"10.14778\/3587136.3587137","type":"journal-article","created":{"date-parts":[[2023,5,8]],"date-time":"2023-05-08T23:11:35Z","timestamp":1683587495000},"page":"1601-1614","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":22,"title":["DBSP: Automatic Incremental View Maintenance for Rich Query Languages"],"prefix":"10.14778","volume":"16","author":[{"given":"Mihai","family":"Budiu","sequence":"first","affiliation":[{"name":"VMware Research"}]},{"given":"Tej","family":"Chajed","sequence":"additional","affiliation":[{"name":"VMware Research"}]},{"given":"Frank","family":"McSherry","sequence":"additional","affiliation":[{"name":"Materialize Inc."}]},{"given":"Leonid","family":"Ryzhyk","sequence":"additional","affiliation":[{"name":"VMware Research"}]},{"given":"Val","family":"Tannen","sequence":"additional","affiliation":[{"name":"University of Pennsylvania"}]}],"member":"320","published-online":{"date-parts":[[2023,5,8]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"[n.d.]. The Aurora Project. http:\/\/cs.brown.edu\/research\/aurora\/. Last accessed November 2022.  [n.d.]. The Aurora Project. http:\/\/cs.brown.edu\/research\/aurora\/. Last accessed November 2022."},{"key":"e_1_2_1_2_1","volume-title":"sqllogictest. https:\/\/www.sqlite.org\/sqllogictest\/doc\/trunk\/about.wiki. Last accessed","year":"2023","unstructured":"[n.d.]. sqllogictest. https:\/\/www.sqlite.org\/sqllogictest\/doc\/trunk\/about.wiki. Last accessed March 2023 . [n.d.]. sqllogictest. https:\/\/www.sqlite.org\/sqllogictest\/doc\/trunk\/about.wiki. Last accessed March 2023."},{"key":"e_1_2_1_3_1","volume-title":"Foundations of Software Science and Computation Structures (FoSSaCS).","author":"Abadi Mart\u00edn","unstructured":"Mart\u00edn Abadi , Frank McSherry , and Gordon Plotkin . 2015. Foundations of Differential Dataflow . In Foundations of Software Science and Computation Structures (FoSSaCS). London, UK . http:\/\/homepages.inf.ed.ac.uk\/gdp\/publications\/differentialweb.pdf Mart\u00edn Abadi, Frank McSherry, and Gordon Plotkin. 2015. Foundations of Differential Dataflow. In Foundations of Software Science and Computation Structures (FoSSaCS). London, UK. http:\/\/homepages.inf.ed.ac.uk\/gdp\/publications\/differentialweb.pdf"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3517889"},{"key":"e_1_2_1_5_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\/ Serge Abiteboul, Richard Hull, and Victor Vianu. 1995. Foundations of Databases. Addison-Wesley. http:\/\/webdam.inria.fr\/Alice\/"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687553.1687592"},{"key":"e_1_2_1_7_1","volume-title":"Fixing Incremental Computation. In European Symposium on Programming Languages and Systems (ESOP). Prague, Czech Republic, 525--552","author":"Alvarez-Picallo Mario","year":"2019","unstructured":"Mario Alvarez-Picallo , Alex Eyers-Taylor , Michael Peyton Jones , and C.-H. Luke Ong . 2019 . Fixing Incremental Computation. In European Symposium on Programming Languages and Systems (ESOP). Prague, Czech Republic, 525--552 . https:\/\/link.springer.com\/chapter\/10.1007\/978-3-030-17184-1_19 Mario Alvarez-Picallo, Alex Eyers-Taylor, Michael Peyton Jones, and C.-H. Luke Ong. 2019. Fixing Incremental Computation. In European Symposium on Programming Languages and Systems (ESOP). Prague, Czech Republic, 525--552. https:\/\/link.springer.com\/chapter\/10.1007\/978-3-030-17184-1_19"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/28659.28674"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3190662"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068418000224"},{"key":"e_1_2_1_12_1","volume-title":"DBSP: A Language for Expressing Incremental View Maintenance for Rich Query Languages. https:\/\/github.com\/vmware\/database-stream-processor\/blob\/main\/doc\/spec.pdf.","author":"Budiu Mihai","year":"2022","unstructured":"Mihai Budiu , Frank McSherry , Leonid Ryzhyk , and Val Tannen . 2022 . DBSP: A Language for Expressing Incremental View Maintenance for Rich Query Languages. https:\/\/github.com\/vmware\/database-stream-processor\/blob\/main\/doc\/spec.pdf. Mihai Budiu, Frank McSherry, Leonid Ryzhyk, and Val Tannen. 2022. DBSP: A Language for Expressing Incremental View Maintenance for Rich Query Languages. https:\/\/github.com\/vmware\/database-stream-processor\/blob\/main\/doc\/spec.pdf."},{"key":"e_1_2_1_13_1","volume-title":"Deriving Production Rules for Incremental View Maintenance. In International Conference of Very Large Data Bases (VLDB)","author":"Ceri Stefano","year":"1991","unstructured":"Stefano Ceri and Jennifer Widom . 1991 . Deriving Production Rules for Incremental View Maintenance. In International Conference of Very Large Data Bases (VLDB) . Barcelona, Spain, 577--589. http:\/\/www.vldb.org\/conf\/ 1991\/P577.PDF Stefano Ceri and Jennifer Widom. 1991. Deriving Production Rules for Incremental View Maintenance. In International Conference of Very Large Data Bases (VLDB). Barcelona, Spain, 577--589. http:\/\/www.vldb.org\/conf\/1991\/P577.PDF"},{"key":"e_1_2_1_14_1","unstructured":"Tej Chajed. 2022. DBSP formalization. https:\/\/github.com\/tchajed\/dbsp-theory  Tej Chajed. 2022. DBSP formalization. https:\/\/github.com\/tchajed\/dbsp-theory"},{"key":"e_1_2_1_15_1","volume-title":"Optimizing Queries with Materialized Views. In International Conference on Data Engineering (ICDE). 190--200","author":"Chaudhuri Surajit","year":"1995","unstructured":"Surajit Chaudhuri , Ravi Krishnamurthy , Spyros Potamianos , and Kyuseok Shim . 1995 . Optimizing Queries with Materialized Views. In International Conference on Data Engineering (ICDE). 190--200 . Surajit Chaudhuri, Ravi Krishnamurthy, Spyros Potamianos, and Kyuseok Shim. 1995. Optimizing Queries with Materialized Views. In International Conference on Data Engineering (ICDE). 190--200."},{"key":"e_1_2_1_16_1","volume-title":"Now Publishers Inc","author":"Chirkova Rada","unstructured":"Rada Chirkova and Jun Yang . 2012. Materialized Views . Now Publishers Inc ., Hanover, MA, USA . Rada Chirkova and Jun Yang. 2012. Materialized Views. Now Publishers Inc., Hanover, MA, USA."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.14778\/2994509.2994530"},{"key":"e_1_2_1_18_1","volume-title":"The Lean Theorem Prover. In International Conference on Automated Deduction (CADE-25)","author":"de Moura Leonardo","year":"2015","unstructured":"Leonardo de Moura , Soonho Kong , Jeremy Avigad , Floris van Doorn , and Jakob von Raumer . 2015 . The Lean Theorem Prover. In International Conference on Automated Deduction (CADE-25) . Berlin, Germany. Leonardo de Moura, Soonho Kong, Jeremy Avigad, Floris van Doorn, and Jakob von Raumer. 2015. The Lean Theorem Prover. In International Conference on Automated Deduction (CADE-25). Berlin, Germany."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00962282"},{"key":"e_1_2_1_20_1","volume-title":"ACM SIGPLAN Workshop on Programming Languages Technologies for XML","author":"Foster J. Nathan","year":"2008","unstructured":"J. Nathan Foster , Ravi Konuru , Jerome Simeon , and Lionel Villard . 2008 . An Algebraic Approach to XQuery View Maintenance . In ACM SIGPLAN Workshop on Programming Languages Technologies for XML . San Francisco, CA. J. Nathan Foster, Ravi Konuru, Jerome Simeon, and Lionel Villard. 2008. An Algebraic Approach to XQuery View Maintenance. In ACM SIGPLAN Workshop on Programming Languages Technologies for XML. San Francisco, CA."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.2200\/S00648ED1V01Y201505DTM041"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-011-9323-x"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1265530.1265535"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/223784.223849"},{"key":"e_1_2_1_25_1","first-page":"3","article-title":"Maintenance of materialized views: Problems, techniques, and applications","volume":"18","author":"Gupta Ashish","year":"1995","unstructured":"Ashish Gupta , Inderpal Singh Mumick , 1995 . Maintenance of materialized views: Problems, techniques, and applications . IEEE Data Eng. Bull. 18 , 2 (1995), 3 -- 18 . Ashish Gupta, Inderpal Singh Mumick, et al. 1995. Maintenance of materialized views: Problems, techniques, and applications. IEEE Data Eng. Bull. 18, 2 (1995), 3--18.","journal-title":"IEEE Data Eng. Bull."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/170035.170066"},{"key":"e_1_2_1_27_1","volume-title":"Workshop on Deductive Databases (Technical Report). Washington, D.C., 56--65","author":"John","unstructured":"John V. Harrison and Suzanne W. Dietrich. 1992. Maintenance of Materialized Views in a Deductive Database: An Update Propagation Approach . In Workshop on Deductive Databases (Technical Report). Washington, D.C., 56--65 . John V. Harrison and Suzanne W. Dietrich. 1992. Maintenance of Materialized Views in a Deductive Database: An Update Propagation Approach. In Workshop on Deductive Databases (Technical Report). Washington, D.C., 56--65."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3064027"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.14778\/3192965.3192966"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3371316.3371325"},{"key":"e_1_2_1_31_1","volume-title":"KSQL: Streaming SQL Engine for Apache Kafka. In International Conference on Extending Database Technology (EDBT)","author":"Jafarpour Hojjat","year":"2019","unstructured":"Hojjat Jafarpour , Rohan Desai , and Damian Guy . 2019 . KSQL: Streaming SQL Engine for Apache Kafka. In International Conference on Extending Database Technology (EDBT) . Lisbon, Portugal, 524--533. http:\/\/openproceedings.org\/ 2019\/conf\/edbt\/EDBT19_paper_329.pdf Hojjat Jafarpour, Rohan Desai, and Damian Guy. 2019. KSQL: Streaming SQL Engine for Apache Kafka. In International Conference on Extending Database Technology (EDBT). Lisbon, Portugal, 524--533. http:\/\/openproceedings.org\/2019\/conf\/edbt\/EDBT19_paper_329.pdf"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3396375"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807085.1807100"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902286"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-23580-1_11"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/223784.223850"},{"key":"e_1_2_1_37_1","volume-title":"Proceedings of the 9th ACM SIGPLAN International Conference on Certified Programs and Proofs","author":"Community The","year":"2020","unstructured":"The mathlib Community . 2020 . The Lean Mathematical Library . In Proceedings of the 9th ACM SIGPLAN International Conference on Certified Programs and Proofs ( New Orleans, LA, USA) (CPP 2020). Association for Computing Machinery, New York, NY, USA, 367--381. 10.1145\/3372885.3373824 The mathlib Community. 2020. The Lean Mathematical Library. In Proceedings of the 9th ACM SIGPLAN International Conference on Certified Programs and Proofs (New Orleans, LA, USA) (CPP 2020). Association for Computing Machinery, New York, NY, USA, 367--381. 10.1145\/3372885.3373824"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.14778\/3401960.3401974"},{"key":"e_1_2_1_39_1","volume-title":"Differential Dataflow. In Conference on Innovative Data Systems Research (CIDR)","author":"McSherry Frank","year":"2013","unstructured":"Frank McSherry , Derek Gordon Murray , Rebecca Isaacs , and Michael Isard . 2013 . Differential Dataflow. In Conference on Innovative Data Systems Research (CIDR) . Asilomar, CA, 12 pages. https:\/\/www.cidrdb.org\/cidr 2013\/Papers\/CIDR13_Paper111.pdf Frank McSherry, Derek Gordon Murray, Rebecca Isaacs, and Michael Isard. 2013. Differential Dataflow. In Conference on Innovative Data Systems Research (CIDR). Asilomar, CA, 12 pages. https:\/\/www.cidrdb.org\/cidr2013\/Papers\/CIDR13_Paper111.pdf"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2018.12.004"},{"key":"e_1_2_1_41_1","volume-title":"Incremental Update of Datalog Materialisation: the Backward\/Forward Algorithm. In Conference on Artificial Intelligence (AAAI)","author":"Motik Boris","year":"2015","unstructured":"Boris Motik , Yavor Nenov , Robert Edgar Felix Piro , and Ian Horrocks . 2015 . Incremental Update of Datalog Materialisation: the Backward\/Forward Algorithm. In Conference on Artificial Intelligence (AAAI) . Austin, Texas, 1560--1568. http:\/\/www.aaai.org\/ocs\/index.php\/AAAI\/AAAI15\/paper\/view\/9660 Boris Motik, Yavor Nenov, Robert Edgar Felix Piro, and Ian Horrocks. 2015. Incremental Update of Datalog Materialisation: the Backward\/Forward Algorithm. In Conference on Artificial Intelligence (AAAI). Austin, Texas, 1560--1568. http:\/\/www.aaai.org\/ocs\/index.php\/AAAI\/AAAI15\/paper\/view\/9660"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522738"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3183758"},{"key":"e_1_2_1_44_1","unstructured":"L. R. Rabiner and B. Gold (Eds.). 1975. Theory and Application of Digital Signal Processing. Prentice-Hall.  L. R. Rabiner and B. Gold (Eds.). 1975. Theory and Application of Digital Signal Processing. Prentice-Hall."},{"key":"e_1_2_1_45_1","volume-title":"Datalog 2.0.","author":"Ryzhyk Leonid","unstructured":"Leonid Ryzhyk and Mihai Budiu . 2019. Differential Datalog . In Datalog 2.0. Philadelphia, PA , 12 pages. http:\/\/budiu.info\/work\/ddlog.pdf Leonid Ryzhyk and Mihai Budiu. 2019. Differential Datalog. In Datalog 2.0. Philadelphia, PA, 12 pages. http:\/\/budiu.info\/work\/ddlog.pdf"},{"key":"e_1_2_1_46_1","volume-title":"Incremental Maintenance of Externally Materialized Views. In International Conference of Very Large Data Bases (VLDB). Mumbai (Bombay), India, 75--86","author":"Staudt Martin","year":"1996","unstructured":"Martin Staudt and Matthias Jarke . 1996 . Incremental Maintenance of Externally Materialized Views. In International Conference of Very Large Data Bases (VLDB). Mumbai (Bombay), India, 75--86 . http:\/\/www.vldb.org\/conf\/1996\/P075.PDF Martin Staudt and Matthias Jarke. 1996. Incremental Maintenance of Externally Materialized Views. In International Conference of Very Large Data Bases (VLDB). Mumbai (Bombay), India, 75--86. http:\/\/www.vldb.org\/conf\/1996\/P075.PDF"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.14778\/2752939.2752940"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3380586"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/115790.115799"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3587136.3587137","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,8]],"date-time":"2023-05-08T23:17:02Z","timestamp":1683587822000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3587136.3587137"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,3]]},"references-count":48,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2023,3]]}},"alternative-id":["10.14778\/3587136.3587137"],"URL":"https:\/\/doi.org\/10.14778\/3587136.3587137","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2023,3]]},"assertion":[{"value":"2023-05-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}