{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,8]],"date-time":"2026-10-08T11:34:48Z","timestamp":1791459288698,"version":"4.3.4"},"reference-count":46,"publisher":"Association for Computing Machinery (ACM)","issue":"OOPSLA","license":[{"start":{"date-parts":[[2018,10,24]],"date-time":"2018-10-24T00:00:00Z","timestamp":1540339200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc-sa\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2018,10,24]]},"abstract":"<jats:p>Program analyses detect errors in code, but when code changes frequently as in an IDE, repeated re-analysis from-scratch is unnecessary: It leads to poor performance unless we give up on precision and recall. Incremental program analysis promises to deliver fast feedback without giving up on precision or recall by deriving a new analysis result from the previous one. However, Datalog and other existing frameworks for incremental program analysis are limited in expressive power: They only support the powerset lattice as representation of analysis results, whereas many practically relevant analyses require custom lattices and aggregation over lattice values. To this end, we present a novel algorithm called DRedL that supports incremental maintenance of recursive lattice-value aggregation in Datalog. The key insight of DRedL is to dynamically recognize increasing replacements of old lattice values by new ones, which allows us to avoid the expensive deletion of the old value. We integrate DRedL into the analysis framework IncA and use IncA to realize incremental implementations of strong-update points-to analysis and string analysis for Java. As our performance evaluation demonstrates, both analyses react to code changes within milliseconds.<\/jats:p>","DOI":"10.1145\/3276509","type":"journal-article","created":{"date-parts":[[2018,10,24]],"date-time":"2018-10-24T07:57:18Z","timestamp":1540367838000},"page":"1-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":47,"title":["Incrementalizing lattice-based program analyses in Datalog"],"prefix":"10.1145","volume":"2","author":[{"given":"Tam\u00e1s","family":"Szab\u00f3","sequence":"first","affiliation":[{"name":"itemis, Germany \/ Delft University of Technology, Netherlands"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"G\u00e1bor","family":"Bergmann","sequence":"additional","affiliation":[{"name":"Budapest University of Technology and Economics, Hungary \/ MTA-BME Lend\u00fclet Research Group on Cyber-Physical Systems, Hungary"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sebastian","family":"Erdweg","sequence":"additional","affiliation":[{"name":"Delft University of Technology, Netherlands"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Markus","family":"Voelter","sequence":"additional","affiliation":[{"name":"itemis, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2018,10,24]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2568225.2568243"},{"key":"e_1_2_2_2_1","volume-title":"Introduction to commutative algebra","author":"Atiyah Michael Francis","unstructured":"Michael Francis Atiyah and Ian Grant Macdonald . 1994. Introduction to commutative algebra . Westview press . Michael Francis Atiyah and Ian Grant Macdonald. 1994. Introduction to commutative algebra. Westview press."},{"key":"e_1_2_2_3_1","volume-title":"QL: Object-oriented Queries on Relational Data. In LIPIcs-Leibniz International Proceedings in Informatics","volume":"56","author":"Avgustinov Pavel","year":"2016","unstructured":"Pavel Avgustinov , Oege de Moor , Michael Peyton Jones , and Max Sch\u00e4fer . 2016 . QL: Object-oriented Queries on Relational Data. In LIPIcs-Leibniz International Proceedings in Informatics , Vol. 56 . Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. Pavel Avgustinov, Oege de Moor, Michael Peyton Jones, and Max Sch\u00e4fer. 2016. QL: Object-oriented Queries on Relational Data. In LIPIcs-Leibniz International Proceedings in Informatics, Vol. 56. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik."},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2038916.2038923"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/69.43410"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2391229.2391230"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/502874.502898"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/2075089.2075132"},{"key":"e_1_2_2_9_1","volume-title":"Basic Concepts of Abstract Interpretation","author":"Cousot Patrick","unstructured":"Patrick Cousot and Radhia Cousot . 2004. Basic Concepts of Abstract Interpretation . Springer US , Boston, MA , 359\u2013366. Patrick Cousot and Radhia Cousot. 2004. Basic Concepts of Abstract Interpretation. Springer US, Boston, MA, 359\u2013366."},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2970276.2970315"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-69611-7_7"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(82)90020-0"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1561\/1900000017"},{"key":"e_1_2_2_14_1","first-page":"3","article-title":"Maintenance of Materialized Views: Problems, Techniques, and Applications","volume":"18","author":"Gupta Ashish","year":"1995","unstructured":"Ashish Gupta and Inderpal Singh Mumick . 1995 . Maintenance of Materialized Views: Problems, Techniques, and Applications . IEEE Data Eng. Bull. 18 , 2 (1995), 3 \u2013 18 . http:\/\/sites.computer.org\/debull\/95JUN- CD.pdf Ashish Gupta and Inderpal Singh Mumick. 1995. Maintenance of Materialized Views: Problems, Techniques, and Applications. IEEE Data Eng. Bull. 18, 2 (1995), 3\u201318. http:\/\/sites.computer.org\/debull\/95JUN- CD.pdf","journal-title":"IEEE Data Eng. Bull."},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/170035.170066"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/349214.349216"},{"key":"e_1_2_2_20_1","volume-title":"Cetus Users and Compiler Infastructure Workshop (CETUS","volume":"15","author":"Lam Patrick","year":"2011","unstructured":"Patrick Lam , Eric Bodden , Ondrej Lhot\u00e1k , and Laurie Hendren . 2011 . The Soot framework for Java program analysis: a retrospective . In Cetus Users and Compiler Infastructure Workshop (CETUS 2011), Vol. 15 . 35. Patrick Lam, Eric Bodden, Ondrej Lhot\u00e1k, and Laurie Hendren. 2011. The Soot framework for Java program analysis: a retrospective. In Cetus Users and Compiler Infastructure Workshop (CETUS 2011), Vol. 15. 35."},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1926385.1926389"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.36"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-37051-9_4"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2908080.2908096"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-012-0299-1"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/899610"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2660193.2660242"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/2886521.2886537"},{"key":"e_1_2_2_29_1","volume-title":"Principles of Program Analysis","author":"Nielson Flemming","unstructured":"Flemming Nielson , Hanne R. Nielson , and Chris Hankin . 2010. Principles of Program Analysis . Springer Publishing Company, Inc orporated. Flemming Nielson, Hanne R. Nielson, and Chris Hankin. 2010. Principles of Program Analysis. Springer Publishing Company, Incorporated."},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/32.58766"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.5555\/647165.717845"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/158511.158710"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/199448.199462"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/137097.137852"},{"key":"e_1_2_2_35_1","volume-title":"Graph Transformation","author":"Rozenberg Grzegorz","year":"1997","unstructured":"Grzegorz Rozenberg (Ed.). 1997 . Handbook of Graph Grammars and Computing by Graph Transformation : Volume I . Foundations. World Scientific Publishing Co. , Inc., River Edge, NJ, USA. Grzegorz Rozenberg (Ed.). 1997. Handbook of Graph Grammars and Computing by Graph Transformation: Volume I. Foundations. World Scientific Publishing Co., Inc., River Edge, NJ, USA."},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1069774.1069785"},{"key":"e_1_2_2_37_1","volume-title":"Algorithms","author":"Sedgewick Robert","unstructured":"Robert Sedgewick and Kevin Wayne . 2011. Algorithms ( 4 th ed.). Addison-Wesley Professional . Robert Sedgewick and Kevin Wayne. 2011. Algorithms (4th ed.). Addison-Wesley Professional.","edition":"4"},{"key":"e_1_2_2_38_1","volume-title":"2015 IEEE 31st International Conference on Data Engineering. 867\u2013878","author":"Shkapsky A.","unstructured":"A. Shkapsky , M. Yang , and C. Zaniolo . 2015. Optimizing recursive queries with monotonic aggregates in DeALS . In 2015 IEEE 31st International Conference on Data Engineering. 867\u2013878 . A. Shkapsky, M. Yang, and C. Zaniolo. 2015. Optimizing recursive queries with monotonic aggregates in DeALS. In 2015 IEEE 31st International Conference on Data Engineering. 867\u2013878."},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-24206-9_14"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICSM.2001.972787"},{"key":"e_1_2_2_41_1","volume-title":"Karim Ali, and Eric Bodden.","author":"Sp\u00e4th Johannes","year":"2016","unstructured":"Johannes Sp\u00e4th , Lisa Nguyen Quang Do , Karim Ali, and Eric Bodden. 2016 . Boomerang : Demand-Driven Flow- and Context-Sensitive Pointer Analysis for Java. In 30th European Conference on Object-Oriented Programming (ECOOP 2016) (Leibniz International Proceedings in Informatics (LIPIcs)), Shriram Krishnamurthi and Benjamin S. Lerner (Eds.), Vol. 56 . Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany , 22:1\u201322:26. Johannes Sp\u00e4th, Lisa Nguyen Quang Do, Karim Ali, and Eric Bodden. 2016. Boomerang: Demand-Driven Flow- and Context-Sensitive Pointer Analysis for Java. In 30th European Conference on Object-Oriented Programming (ECOOP 2016) (Leibniz International Proceedings in Informatics (LIPIcs)), Shriram Krishnamurthi and Benjamin S. Lerner (Eds.), Vol. 56. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 22:1\u201322:26."},{"key":"e_1_2_2_42_1","unstructured":"Ozgur Sumer Umut Acar Alexander T Ihler and Ramgopal R Mettu. 2008. Efficient bayesian inference for dynamically changing graphs. In Advances in Neural Information Processing Systems. 1441\u20131448.  Ozgur Sumer Umut Acar Alexander T Ihler and Ramgopal R Mettu. 2008. Efficient bayesian inference for dynamically changing graphs. In Advances in Neural Information Processing Systems. 1441\u20131448."},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/2970276.2970298"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.scico.2014.01.004"},{"key":"e_1_2_2_45_1","volume-title":"Towards User-Friendly Projectional Editors","author":"Voelter Markus","unstructured":"Markus Voelter , Janet Siegmund , Thorsten Berger , and Bernd Kolb . 2014. Towards User-Friendly Projectional Editors . In Software Language Engineering, Beno\u00eet Combemale , DavidJ. Pearce, Olivier Barais, and JurgenJ. Vinju (Eds.). Lecture Notes in Computer Science, Vol. 8706 . Springer International Publishing , 41\u201361. Markus Voelter, Janet Siegmund, Thorsten Berger, and Bernd Kolb. 2014. Towards User-Friendly Projectional Editors. In Software Language Engineering, Beno\u00eet Combemale, DavidJ. Pearce, Olivier Barais, and JurgenJ. Vinju (Eds.). Lecture Notes in Computer Science, Vol. 8706. Springer International Publishing, 41\u201361."},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/2997364.2997365"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/996841.996859"},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/302405.302676"},{"key":"e_1_2_2_49_1","volume-title":"Incremental data flow analysis in a structured program editor","author":"Zadeck Frank Kenneth","unstructured":"Frank Kenneth Zadeck . 1984. Incremental data flow analysis in a structured program editor . Vol. 19 . ACM. Frank Kenneth Zadeck. 1984. Incremental data flow analysis in a structured program editor. Vol. 19. ACM."}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3276509","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3276509","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T15:03:39Z","timestamp":1750259019000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3276509"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,10,24]]},"references-count":46,"journal-issue":{"issue":"OOPSLA","published-print":{"date-parts":[[2018,10,24]]}},"alternative-id":["10.1145\/3276509"],"URL":"https:\/\/doi.org\/10.1145\/3276509","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,10,24]]},"assertion":[{"value":"2018-10-24","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}