{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:25:03Z","timestamp":1750307103736,"version":"3.41.0"},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2012,12,1]],"date-time":"2012-12-01T00:00:00Z","timestamp":1354320000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2012,12]]},"abstract":"<jats:p>Provenance information has been proved to be very effective in capturing the computational process performed by queries, and has been used extensively as the input to many advanced data management tools (e.g., view maintenance, trust assessment, or query answering in probabilistic databases).<\/jats:p>\n          <jats:p>\n            We observe here that while different (set-)equivalent queries may admit different provenance expressions when evaluated on the same database, there is always some part of these expressions that is common to all. We refer to this part as the\n            <jats:italic>core<\/jats:italic>\n            provenance. In addition to being informative, the core provenance is also useful as a compact input to the aforementioned data management tools. We formally define the notion of core provenance. We study algorithms that, given a query, compute an equivalent (called p-minimal) query that for every input database, the provenance of every result tuple is the core provenance. We study such algorithms for queries of varying expressive power (namely conjunctive queries with disequalities and unions thereof). Finally, we observe that, in general, one would not want to require database systems to execute a specific p-minimal query, but instead to be able to find, possibly off-line, the core provenance of a given tuple in the output (computed by an arbitrary equivalent query), without reevaluating the query. We provide algorithms for such direct computation of the core provenance.\n          <\/jats:p>","DOI":"10.1145\/2389241.2389249","type":"journal-article","created":{"date-parts":[[2013,1,2]],"date-time":"2013-01-02T13:23:15Z","timestamp":1357132995000},"page":"1-36","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":11,"title":["On Provenance Minimization"],"prefix":"10.1145","volume":"37","author":[{"given":"Yael","family":"Amsterdamer","sequence":"first","affiliation":[{"name":"Tel Aviv University and University of Pennsylvania"}]},{"given":"Daniel","family":"Deutch","sequence":"additional","affiliation":[{"name":"Ben Gurion University and University of Pennsylvania"}]},{"given":"Tova","family":"Milo","sequence":"additional","affiliation":[{"name":"Tel Aviv University"}]},{"given":"Val","family":"Tannen","sequence":"additional","affiliation":[{"name":"University of Pennsylvania"}]}],"member":"320","published-online":{"date-parts":[[2012,12]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Abiteboul S. Hull R. and Vianu V. 1995. Foundations of Databases. Addison-Wesley. Abiteboul S. Hull R. and Vianu V. 1995. Foundations of Databases . Addison-Wesley."},{"volume-title":"Proceedings of the International Conference on Extending Database Technology.","author":"Afrati F. N.","key":"e_1_2_1_2_1"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989284.1989303"},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","unstructured":"Arenas M. Barcel\u00f3 P. Libkin L. and Murlak F. 2010. Relational and XML Data Exchange. Synthesis Lectures on Data Management. Morgan & Claypool Publishers. Arenas M. Barcel\u00f3 P. Libkin L. and Murlak F. 2010. Relational and XML Data Exchange . Synthesis Lectures on Data Management. Morgan & Claypool Publishers.","DOI":"10.1007\/978-3-031-01840-4"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-007-0080-z"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-005-0156-6"},{"volume-title":"Proceedings of the International Conference on Database Theory.","author":"Buneman P.","key":"e_1_2_1_7_1"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1412331.1412340"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/275487.275504"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/800105.803397"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376715"},{"volume-title":"Proceedings of the International Conference on Database Theory.","author":"Chekuri C.","key":"e_1_2_1_12_1"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1639950.1640064"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142351.1142362"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1138394.1138400"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1265530.1265549"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1061318.1061323"},{"key":"e_1_2_1_18_1","unstructured":"Gatterbauer W. Meliou A. and Suciu D. 2011. Default-all is dangerous! In Proceedings of the 3rd USENIX Workshop on the Theory and Practice of Provenance. Gatterbauer W. Meliou A. and Suciu D. 2011. Default-all is dangerous! In Proceedings of the 3rd USENIX Workshop on the Theory and Practice of Provenance ."},{"volume-title":"Proceedings of the 3rd USENIX Workshop on the Theory and Practice of Provenance.","author":"Glavic B.","key":"e_1_2_1_19_1"},{"key":"e_1_2_1_20_1","unstructured":"Gottlob G. 2010. Private communication. Gottlob G. 2010. Private communication."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1514894.1514930"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-011-9327-6"},{"volume-title":"Proceedings of the International Conference on Very Large Databases.","author":"Green T. J.","key":"e_1_2_1_23_1"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1265530.1265535"},{"key":"e_1_2_1_25_1","unstructured":"Karvounarakis G. and Tannen V. 2008. Conjunctive queries and mappings with unequalities. Tech. rep. University of Pennsylvania. Karvounarakis G. and Tannen V. 2008. Conjunctive queries and mappings with unequalities. Tech. rep. University of Pennsylvania."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/42267.42273"},{"key":"e_1_2_1_27_1","doi-asserted-by":"crossref","unstructured":"Kuich W. 1997. Semirings and formal power series. In Handbook of Formal Languages. Kuich W. 1997. Semirings and formal power series. In Handbook of Formal Languages .","DOI":"10.1007\/978-3-642-59136-5_9"},{"volume":"477","volume-title":"Description Logics. CEUR Workshop Proceedings","author":"Libkin L.","key":"e_1_2_1_28_1"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.14778\/1880172.1880176"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453943"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/322217.322221"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1084805.1084812"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007629"},{"key":"e_1_2_1_34_1","first-page":"4","article-title":"Recording provenance for SQL queries and updates","volume":"30","author":"Vansummeren S.","year":"2007","journal-title":"IEEE Data Engin. Bull."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807234"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2389241.2389249","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2389241.2389249","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T09:34:58Z","timestamp":1750239298000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2389241.2389249"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,12]]},"references-count":35,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2012,12]]}},"alternative-id":["10.1145\/2389241.2389249"],"URL":"https:\/\/doi.org\/10.1145\/2389241.2389249","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"type":"print","value":"0362-5915"},{"type":"electronic","value":"1557-4644"}],"subject":[],"published":{"date-parts":[[2012,12]]},"assertion":[{"value":"2011-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-12-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}