{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T11:10:05Z","timestamp":1750677005106,"version":"3.41.0"},"reference-count":53,"publisher":"Cambridge University Press (CUP)","issue":"3","license":[{"start":{"date-parts":[[2025,4,25]],"date-time":"2025-04-25T00:00:00Z","timestamp":1745539200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Theory and Practice of Logic Programming"],"published-print":{"date-parts":[[2025,5]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Advances in incremental Datalog evaluation strategies have made Datalog popular among use cases with constantly evolving inputs such as static analysis in continuous integration and deployment pipelines. As a result, new logic programming debugging techniques are needed to support these emerging use cases.<\/jats:p><jats:p>This paper introduces an incremental debugging technique for Datalog, which determines the failing changes for a <jats:italic>rollback<\/jats:italic> in an incremental setup. Our debugging technique leverages a novel incremental provenance method. We have implemented our technique using an incremental version of the Souffl\u00e9 Datalog engine and evaluated its effectiveness on the DaCapo Java program benchmarks analyzed by the Doop static analysis library. Compared to state-of-the-art techniques, we can localize faults and suggest rollbacks with an overall speedup of over 26.9<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S147106842500002X_inline1.png\"\/><jats:tex-math>\n$\\times$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> while providing higher quality results.<\/jats:p>","DOI":"10.1017\/s147106842500002x","type":"journal-article","created":{"date-parts":[[2025,4,25]],"date-time":"2025-04-25T08:36:28Z","timestamp":1745570188000},"page":"256-280","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":0,"title":["Provenance Guided Rollback Suggestions"],"prefix":"10.1017","volume":"25","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3857-5016","authenticated-orcid":false,"given":"DAVID","family":"ZHAO","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"PAVLE","family":"SUBOTI\u0106","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"MUKUND","family":"RAGHOTHAMAN","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"BERNHARD","family":"SCHOLZ","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2025,4,25]]},"reference":[{"key":"S147106842500002X_ref44","unstructured":"Sch\u00e4fer, M. , Avgustinov, P. and De moor, O. (2017). Algebraic data types for object-oriented datalog [online]."},{"key":"S147106842500002X_ref31","doi-asserted-by":"crossref","unstructured":"Kakas, A. C. , Kowalski, R. A. and Toni, F. (1993). Abductive logic programming. Journal of logic and computation, 2(6), pp. 719\u2013770.","DOI":"10.1093\/logcom\/2.6.719"},{"key":"S147106842500002X_ref39","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2018.12.004"},{"key":"S147106842500002X_ref13","first-page":"1","volume-title":"Branch and Bound Algorithms-Principles and Examples","author":"Clausen","year":"1999"},{"key":"S147106842500002X_ref17","first-page":"1","article-title":"Locating faults with program slicing: An empirical analysis","volume":"26","author":"Ezekiel","year":"2021","journal-title":"Empirical Software Engineering"},{"key":"S147106842500002X_ref6","doi-asserted-by":"publisher","DOI":"10.1016\/S0065-2458(08)60641-5"},{"key":"S147106842500002X_ref9","doi-asserted-by":"publisher","DOI":"10.1145\/1639949.1640108"},{"key":"S147106842500002X_ref34","doi-asserted-by":"crossref","unstructured":"Li, X. , Bundy, A. and Smaill, A. 2018. Abc repair system for datalog-like theories. In 10th International Conference on Knowledge Engineering and Ontology Development, SCITEPRESS, 335\u2013342.","DOI":"10.5220\/0006959703350342"},{"key":"S147106842500002X_ref35","doi-asserted-by":"publisher","DOI":"10.1145\/3611643.3616363"},{"key":"S147106842500002X_ref18","first-page":"458","volume-title":"Constraint-Driven Database Repair","author":"Fan","year":"2009"},{"key":"S147106842500002X_ref28","doi-asserted-by":"publisher","DOI":"10.1007\/BF01531033"},{"key":"S147106842500002X_ref43","first-page":"4","article-title":"Differential datalog","volume":"2","author":"Ryzhyk","year":"2019","journal-title":"Datalog"},{"key":"S147106842500002X_ref26","doi-asserted-by":"publisher","DOI":"10.1145\/170036.170066"},{"key":"S147106842500002X_ref49","doi-asserted-by":"publisher","DOI":"10.1007\/s10664-019-09688-8"},{"key":"S147106842500002X_ref25","first-page":"87","volume-title":"Communications of the ACM","volume":"63","author":"Grech","year":"2018"},{"key":"S147106842500002X_ref29","doi-asserted-by":"crossref","unstructured":"Huang, S. S. , Green, T. J. and Loo, B. T. 2011. Datalog and emerging applications: An interactive tutorial. In Proceedings of the 2011 ACM SIGMOD International Conference on Management of Data. SIGMOD \u201911, ACM, 1213\u20131216.","DOI":"10.1145\/1989323.1989456"},{"key":"S147106842500002X_ref36","unstructured":"Mcsherry, F. , Murray, D. G. , Isaacs, R. and Isard, M. 2013. Differential dataflow. In 6th Biennial Conference on Innovative Data Systems Research."},{"key":"S147106842500002X_ref47","doi-asserted-by":"publisher","DOI":"10.1145\/1925805.1925818"},{"key":"S147106842500002X_ref19","doi-asserted-by":"publisher","DOI":"10.14778\/1454159.1454200"},{"key":"S147106842500002X_ref3","doi-asserted-by":"publisher","DOI":"10.14778\/3352063.3352131"},{"key":"S147106842500002X_ref21","first-page":"1070","volume-title":"The Stable Model Semantics for Logic Programming","author":"Gelfond","year":"1988"},{"key":"S147106842500002X_ref30","doi-asserted-by":"crossref","unstructured":"Jordan, H. , Scholz, B. and Suboti\u0107, P. 2016. Souffl\u00e9: On synthesis of program analyzers. In International Conference on Computer Aided Verification, Springer, 422\u2013430.","DOI":"10.1007\/978-3-319-41540-6_23"},{"key":"S147106842500002X_ref46","doi-asserted-by":"publisher","DOI":"10.1109\/ICSME.2016.83"},{"key":"S147106842500002X_ref48","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.1984.5010248"},{"key":"S147106842500002X_ref5","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-25543-5_14"},{"key":"S147106842500002X_ref7","doi-asserted-by":"crossref","unstructured":"Blackburn, S. M. , Garner, R. , Hoffman, C. , Khan, A. M. , Mckinley, K. S. , Bentzur, R. , Diwan, A. , Feinberg, D. , Frampton, D. , Guyer, S. Z. , Hirzel, M. , Hosking, A. , Jump, M. , Lee, H. , Moss, J. E. B. , Phansalkar, A. , Stefanovi\u0107, D. , Vandrunen, T. , Von dincklage, D. and Wiedermann, B. 2006. The DaCapo benchmarks: Java benchmarking development and analysis. In OOPSLA \u201906: Proceedings of the 21st annual ACM SIGPLAN conference on Object-Oriented Programing, Systems, Languages, and Applications, ACM Press, New York, NY, USA, 169\u2013190.","DOI":"10.1145\/1167473.1167488"},{"key":"S147106842500002X_ref52","first-page":"253","volume-title":"Why? ACM SIGSOFT Software Engineering Notes 24","volume":"6","author":"Zeller","year":"1999"},{"key":"S147106842500002X_ref54","doi-asserted-by":"crossref","unstructured":"Zhao, D. , Subotic, P. , Raghothaman, M. and Scholz, B. 2021. Towards elastic incrementalization for datalog. In 23rd International Symposium on Principles and Practice of Declarative Programming, 1\u201316.","DOI":"10.1145\/3479394.3479415"},{"key":"S147106842500002X_ref37","doi-asserted-by":"publisher","DOI":"10.1002\/bltj.2229"},{"key":"S147106842500002X_ref4","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068403001832"},{"key":"S147106842500002X_ref24","doi-asserted-by":"publisher","DOI":"10.1109\/ICSE.2019.00120"},{"key":"S147106842500002X_ref12","first-page":"22","article-title":"Program slicing and data provenance","volume":"30","author":"Cheney","year":"2007","journal-title":"IEEE Data Engineering Bulletin"},{"key":"S147106842500002X_ref16","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-63390-9_14"},{"key":"S147106842500002X_ref33","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.2007.70773"},{"key":"S147106842500002X_ref51","doi-asserted-by":"crossref","unstructured":"Yoon, Y. and Myers, B. A. 2012. An exploratory study of backtracking strategies used by developers. In Proceedings of the 5th International Workshop on Co-Operative and Human Aspects of Software Engineering. CHASE \u201912, IEEE Press, 138\u2013144.","DOI":"10.1109\/CHASE.2012.6223012"},{"key":"S147106842500002X_ref40","unstructured":"Oracle rollback. 2023. https:\/\/docs.oracle.com\/cd\/B10500_01\/server.920\/a96533\/instreco.htm#429546"},{"key":"S147106842500002X_ref38","doi-asserted-by":"publisher","DOI":"10.1145\/128765.128770"},{"key":"S147106842500002X_ref10","unstructured":"Bravo, L. and Bertossi, L. E. 2004. Consistent query answering under inclusion dependencies. In Proceedings of the 2004 conference of the Centre for Advanced Studies on Collaborative research, October 5\u20137, 2004. Lutfiyya, H. , Singer, J. and Stewart, D. A. , Eds.Markham, Ontario, Canada, 202\u2013216."},{"volume-title":"Theory of Linear and Integer Programming","year":"1998","author":"Schrijver","key":"S147106842500002X_ref45"},{"key":"S147106842500002X_ref14","doi-asserted-by":"crossref","unstructured":"Coburn, J. , Bunker, T. , Schwarz, M. , Gupta, R. and Swanson, S. 2013. From aries to mars: Transaction support for next-generation, solid-state drives. In Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles. SOSP \u201913, Association for Computing Machinery, New York, NY, USA, 197\u2013212.","DOI":"10.1145\/2517349.2522724"},{"key":"S147106842500002X_ref27","doi-asserted-by":"publisher","DOI":"10.1002\/swf.41"},{"key":"S147106842500002X_ref23","unstructured":"GLPK (gnu linear programming kit). 2012. https:\/\/www.gnu.org\/software\/glpk\/glpk.html"},{"key":"S147106842500002X_ref56","doi-asserted-by":"crossref","unstructured":"Zhou, W. , Sherr, M. , Tao, T. , Li, X. , Loo, B. T. and Mao, Y. 2010. Efficient querying and maintenance of network provenance at internet-scale. In Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data, 615\u2013626.","DOI":"10.1145\/1807167.1807234"},{"key":"S147106842500002X_ref2","first-page":"131","volume-title":"Staged Points-to Analysis for Large Code Bases","author":"Allen","year":"2015"},{"key":"S147106842500002X_ref11","first-page":"60","article-title":"A survey of algorithmic debugging","volume":"50","author":"Caballero","year":"2017","journal-title":"ACM Computing Surveys (CSUR)"},{"key":"S147106842500002X_ref22","unstructured":"Github codeql. 2021. https:\/\/codeql.github.com\/ Accessed: 19-10-2021."},{"key":"S147106842500002X_ref42","doi-asserted-by":"crossref","unstructured":"Rosen, C. , Grawi, B. and Shihab, E. 2015. Commit guru: Analytics and risk prediction of software commits. In Proceedings of the 2015 10th Joint Meeting on Foundations of Software Engineering. ESEC\/FSE 2015, Association for Computing Machinery, New York, NY, USA, 966\u2013969.","DOI":"10.1145\/2786805.2803183"},{"key":"S147106842500002X_ref53","doi-asserted-by":"publisher","DOI":"10.1109\/32.988498"},{"key":"S147106842500002X_ref1","unstructured":"Accelerated database recovery. 2023. https:\/\/docs.microsoft.com\/en-us\/azure\/sql-database\/sql-database-accelerated-database-recovery"},{"key":"S147106842500002X_ref32","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807269"},{"key":"S147106842500002X_ref15","doi-asserted-by":"publisher","DOI":"10.1145\/3338112"},{"key":"S147106842500002X_ref41","doi-asserted-by":"crossref","unstructured":"Raghothaman, M. , Mendelson, J. , Zhao, D. , Naik, M. and Scholz, B. 2019. Provenance-guided synthesis of datalog programs. In Proceedings of the ACM on Programming Languages, Vol. 4, 1\u201327.","DOI":"10.1145\/3371130"},{"key":"S147106842500002X_ref55","doi-asserted-by":"publisher","DOI":"10.1145\/3379446"}],"container-title":["Theory and Practice of Logic Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S147106842500002X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T10:40:52Z","timestamp":1750675252000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S147106842500002X\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,4,25]]},"references-count":53,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,5]]}},"alternative-id":["S147106842500002X"],"URL":"https:\/\/doi.org\/10.1017\/s147106842500002x","relation":{},"ISSN":["1471-0684","1475-3081"],"issn-type":[{"type":"print","value":"1471-0684"},{"type":"electronic","value":"1475-3081"}],"subject":[],"published":{"date-parts":[[2025,4,25]]},"assertion":[{"value":"\u00a9 The Author(s), 2025. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (https:\/\/creativecommons.org\/licenses\/by\/4.0\/), which permits unrestricted re-use, distribution and reproduction, provided the original article is properly cited.","name":"license","label":"License","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}