{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,1]],"date-time":"2026-06-01T20:39:15Z","timestamp":1780346355646,"version":"3.54.1"},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2024,5,10]],"date-time":"2024-05-10T00:00:00Z","timestamp":1715299200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Flanders AI Research programme"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2024,5,10]]},"abstract":"<jats:p>Instance-based provenance is an explanation for a query result in the form of a subinstance of the database. We investigate different desiderata one may want to impose on these subinstances. Concretely we consider seven basic postulates for provenance. Six of them relate subinstances to provenance polynomials, three-valued semantics, and Halpern-Pearl causality. Determinism of the provenance mechanism is the seventh basic postulate. Moreover, we consider the postulate of minimality, which can be imposed with respect to any set of basic postulates. Our main technical contribution is an analysis and characterisation of which combinations of postulates are jointly satisfiable. Our main conceptual contribution is an approach to instance-based provenance through three-valued instances, which makes it applicable to first-order logic queries involving negation.<\/jats:p>","DOI":"10.1145\/3651596","type":"journal-article","created":{"date-parts":[[2024,5,14]],"date-time":"2024-05-14T08:32:13Z","timestamp":1715675533000},"page":"1-16","source":"Crossref","is-referenced-by-count":3,"title":["Postulates for Provenance: Instance-based provenance for first-order logic"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3460-4251","authenticated-orcid":false,"given":"Bart","family":"Bogaerts","sequence":"first","affiliation":[{"name":"Vrije Universiteit Brussel, Brussels, Belgium"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7420-1337","authenticated-orcid":false,"given":"Maxime","family":"Jakubowski","sequence":"additional","affiliation":[{"name":"Universiteit Hasselt, Hasselt, Belgium"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0072-3252","authenticated-orcid":false,"given":"Jan","family":"Van den Bussche","sequence":"additional","affiliation":[{"name":"Universiteit Hasselt, Hasselt, Belgium"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,5,14]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"S. Abiteboul R. Hull and V. Vianu. 1995. Foundations of Databases. Addison-Wesley."},{"key":"e_1_2_1_2_1","volume-title":"Proceedings 28th AAAI Conference, , C.E. Brodley and P. Stone (Eds.). 974--980","author":"Aleksandrowicz G.","unstructured":"G. Aleksandrowicz, H. Chockler, J.Y. Halpern, and A. Ivrii. 2014. The computational complexity of structure-based causality. In Proceedings 28th AAAI Conference, , C.E. Brodley and P. Stone (Eds.). 974--980."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.14778\/2095686.2095693"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings 19th International Conference on Principles of Knowledge Representation and Reasoning, , G. Kern-Isberner, G. Lakemeyer, and T. Meyer (Eds.). IJACI Organization, 91--101","author":"Bourgaux C.","unstructured":"C. Bourgaux, P. Bourhis, L. Peterfreund, and M. Thomazo. 2022. Revisiting semiring provenance for Datalog. In Proceedings 19th International Conference on Principles of Knowledge Representation and Reasoning, , G. Kern-Isberner, G. Lakemeyer, and T. Meyer (Eds.). IJACI Organization, 91--101."},{"key":"e_1_2_1_5_1","volume-title":"Database Theory--ICDT 2001 (Lecture Notes in Computer Science","author":"Buneman P.","unstructured":"P. Buneman, S. Khanna, and W.C. Tan. 2001. Why and where: A characterization of data provenance. In Database Theory--ICDT 2001 (Lecture Notes in Computer Science, Vol. 1973), J. Van den Bussche and V. Vianu (Eds.). Springer, 316--330."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.4204\/EPTCS.26.6"},{"key":"e_1_2_1_7_1","volume-title":"Lecture Notes in Computer Science","volume":"8000","author":"Cheney J.","unstructured":"J. Cheney, U.A. Acar, and R. Perera. 2013. Toward a theory of self-explaining computation. In In Search of Elegance in the Theory and Practice of Computation, V. Tannen, L. Wong, et al. (Eds.). Lecture Notes in Computer Science, Vol. 8000. Springer, 193--216."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1561\/1900000006"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/357775.357777"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings 26th International Conference on Extending Database Technology, , J. Stoyanovich, J. Teubner, et al. (Eds.). OpenProceedings.org, 285--297","author":"Delva T.","unstructured":"T. Delva, A. Dimou, M. Jakubowski, and J. Van den Bussche. 2023. Data provenance for SHACL. In Proceedings 26th International Conference on Extending Database Technology, , J. Stoyanovich, J. Teubner, et al. (Eds.). OpenProceedings.org, 285--297."},{"key":"e_1_2_1_11_1","volume-title":"Proceedings 17th International Conference on Database Theory, N. Schweikardt et al. (Eds.). OpenProceedings.org, 201--212","author":"Deutch D.","unstructured":"D. Deutch, T. Milo, S. Roy, and V. Tannen. 2014. Circuits for Datalog provenance. In Proceedings 17th International Conference on Database Theory, N. Schweikardt et al. (Eds.). OpenProceedings.org, 201--212."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(02)00271-0"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0743-1066(85)80005-4"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1561\/1900000068"},{"key":"e_1_2_1_15_1","unstructured":"E. Gr\"adel and V. Tannen. 2017. Semiring provenance for first-order model checking. arXiv:1712.01980."},{"key":"e_1_2_1_16_1","volume-title":"Proceedings 26th ACM Symposium on Principles of Database Systems. ACM, 31--40","author":"Green T.J.","unstructured":"T.J. Green, G. Karvounarakis, and V. Tannen. 2007. Provenance semirings. In Proceedings 26th ACM Symposium on Principles of Database Systems. ACM, 31--40."},{"key":"e_1_2_1_17_1","volume-title":"Proceedings 24th International Joint Conference on Artificial Intelligence, , Q. Yang and M.J. Wooldridge (Eds.). AAAI Press, 3022--3033","author":"Halpern J.Y.","year":"2015","unstructured":"J.Y. Halpern. 2015. A modification of the Halpern-Pearl definition of causality. In Proceedings 24th International Joint Conference on Artificial Intelligence, , Q. Yang and M.J. Wooldridge (Eds.). AAAI Press, 3022--3033."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1093\/bjps\/axi147"},{"key":"e_1_2_1_19_1","volume-title":"Artificial Intelligence","volume":"52","author":"Katsuno H.","year":"1991","unstructured":"H. Katsuno and A.O. Mendelzon. 1991. Propositional knowledge base revision and minimal change. Artificial Intelligence , Vol. 52, 3 (1991)."},{"key":"e_1_2_1_20_1","volume-title":"Proceedings 2002 Neural Information Processing Systems Conference, S. Becker, S. Thrun, and K. Obermayer (Eds.). MIT Press, 446--453","author":"Kleinberg J.M.","year":"2003","unstructured":"J.M. Kleinberg. 2003. An impossibility theorem for clustering. In Proceedings 2002 Neural Information Processing Systems Conference, S. Becker, S. Thrun, and K. Obermayer (Eds.). MIT Press, 446--453."},{"key":"e_1_2_1_21_1","volume-title":"8th Innovations in Theoretical Computer Science Conference (Leibniz International Proceedings in Informatics","volume":"23","author":"Kleinberg J.M.","unstructured":"J.M. Kleinberg, S. Mullainathan, and M. Raghavan. 2017. Inherent trade-offs in the fair determination of risk scores. In 8th Innovations in Theoretical Computer Science Conference (Leibniz International Proceedings in Informatics, Vol. 67), , Ch.H. Papadimitriou (Ed.). Schloss Dagstuhl--Leibniz Center for Informatics, 43:1--43:23."},{"key":"e_1_2_1_22_1","unstructured":"J.E. Labra Gayo. 2021. Creating knowledge graph subsets using shape expressions. arXiv:2110.11709."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-018-0518-5"},{"key":"e_1_2_1_24_1","volume-title":"Proceedings 2021 International Conference on Management of Data. ACM, 1051--1063","author":"Li C.","unstructured":"C. Li, Z. Miao, Q. Zeng, B. Glavic, and S. Roy. 2021. Putting things into context: Rich explanations for query answers using join graphs. In Proceedings 2021 International Conference on Management of Data. ACM, 1051--1063."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2877206"},{"key":"e_1_2_1_26_1","volume-title":"Proceedings 7th International Conference on Business Process Management (Lecture Notes in Computer Science","volume":"47","author":"B.","year":"2009","unstructured":"B. Lud\"ascher, M. Weske, et al. 2009. Scientific workflows: Business as usual?. In Proceedings 7th International Conference on Business Process Management (Lecture Notes in Computer Science, Vol. 5701), , U. Dayal, J. Eder, J. Koehler, and H.A. Reijers (Eds.). Springer, 31--47."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.14778\/1880172.1880176"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1561\/1800000010"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511803161"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068406002973"},{"key":"e_1_2_1_31_1","volume-title":"An Introduction to Non-Classical Logic: From If to Is","author":"Priest G.","unstructured":"G. Priest. 2008. An Introduction to Non-Classical Logic: From If to Is. Cambridge University Press."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3051528.3051533"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3651596","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3651596","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T21:40:31Z","timestamp":1755898831000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3651596"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5,10]]},"references-count":32,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,5,10]]}},"alternative-id":["10.1145\/3651596"],"URL":"https:\/\/doi.org\/10.1145\/3651596","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,5,10]]}}}