{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,19]],"date-time":"2026-03-19T16:52:45Z","timestamp":1773939165287,"version":"3.50.1"},"reference-count":34,"publisher":"Association for Computing Machinery (ACM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2020,2]]},"abstract":"<jats:p>\n            Why and why-not provenance have been studied extensively in recent years. However, why-not provenance and --- to a lesser degree --- why provenance can be very large, resulting in severe scalability and usability challenges. We introduce a novel\n            <jats:italic>approximate summarization<\/jats:italic>\n            technique for provenance to address these challenges. Our approach uses patterns to encode why and why-not provenance concisely. We develop techniques for efficiently computing provenance summaries that balance informativeness, conciseness, and completeness. To achieve scalability, we integrate sampling techniques into provenance capture and summarization. Our approach is the first to both scale to large datasets and generate comprehensive and meaningful summaries.\n          <\/jats:p>","DOI":"10.14778\/3380750.3380760","type":"journal-article","created":{"date-parts":[[2020,3,11]],"date-time":"2020-03-11T21:49:08Z","timestamp":1583963348000},"page":"912-924","source":"Crossref","is-referenced-by-count":18,"title":["Approximate summaries for why and why-not provenance"],"prefix":"10.14778","volume":"13","author":[{"given":"Seokki","family":"Lee","sequence":"first","affiliation":[{"name":"Illinois Institute of Technology"}]},{"given":"Bertram","family":"Lud\u00e4scher","sequence":"additional","affiliation":[{"name":"University of Illinois"}]},{"given":"Boris","family":"Glavic","sequence":"additional","affiliation":[{"name":"Illinois Institute of Technology"}]}],"member":"320","published-online":{"date-parts":[[2020,3,11]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Handbook of mathematical functions: with formulas, graphs, and mathematical tables","author":"Abramowitz M.","year":"1965","unstructured":"M. Abramowitz and I. A. Stegun . Handbook of mathematical functions: with formulas, graphs, and mathematical tables , volume 55 . Courier Corporation , 1965 . M. Abramowitz and I. A. Stegun. Handbook of mathematical functions: with formulas, graphs, and mathematical tables, volume 55. Courier Corporation, 1965."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2806416.2806429"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1516360.1516470"},{"key":"e_1_2_1_4_1","volume-title":"TaPP","author":"Bidoit N.","year":"2014","unstructured":"N. Bidoit , M. Herschel , and K. Tzompanaki . Immutably answering why-not questions for equivalent conjunctive queries . In TaPP , 2014 . N. Bidoit, M. Herschel, and K. Tzompanaki. Immutably answering why-not questions for equivalent conjunctive queries. In TaPP, 2014."},{"key":"e_1_2_1_5_1","first-page":"145","volume-title":"EDBT","author":"Bidoit N.","year":"2014","unstructured":"N. Bidoit , M. Herschel , K. Tzompanaki , Query-Based Why-Not Provenance with NedExplain . In EDBT , pages 145 -- 156 , 2014 . N. Bidoit, M. Herschel, K. Tzompanaki, et al. Query-Based Why-Not Provenance with NedExplain. In EDBT, pages 145--156, 2014."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559901"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376715"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735461.2735467"},{"issue":"3","key":"e_1_2_1_9_1","first-page":"43","article-title":"Explanation tables","volume":"41","author":"Gebaly K. E.","year":"2018","unstructured":"K. E. Gebaly , G. Feng , L. Golab , F. Korn , and D. Srivastava . Explanation tables . IEEE Data Eng. Bull. , 41 ( 3 ): 43 -- 51 , 2018 . K. E. Gebaly, G. Feng, L. Golab, F. Korn, and D. Srivastava. Explanation tables. IEEE Data Eng. Bull., 41(3):43--51, 2018.","journal-title":"IEEE Data Eng. Bull."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1265530.1265535"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-017-0486-1"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920869"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453936"},{"issue":"4","key":"e_1_2_1_14_1","first-page":"761","article-title":"Incomplete Information","volume":"31","author":"Imieli\u0144ski T.","year":"1984","unstructured":"T. Imieli\u0144ski and W. Lipski Jr . Incomplete Information in Relational Databases. JACM , 31 ( 4 ): 761 -- 791 , 1984 . T. Imieli\u0144ski and W. Lipski Jr. Incomplete Information in Relational Databases. JACM, 31(4):761--791, 1984.","journal-title":"Relational Databases. JACM"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/1315451.1315455"},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","first-page":"382","DOI":"10.1007\/978-3-642-41660-6_20","volume-title":"Search of Elegance in the Theory and Practice of Computation","author":"K\u00f6hler S.","year":"2013","unstructured":"S. K\u00f6hler , B. Lud\u00e4scher , and D. Zinn . First-order provenance games . In In Search of Elegance in the Theory and Practice of Computation , pages 382 -- 399 . Springer , 2013 . S. K\u00f6hler, B. Lud\u00e4scher, and D. Zinn. First-order provenance games. In In Search of Elegance in the Theory and Practice of Computation, pages 382--399. Springer, 2013."},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-04031-7","volume-title":"Constraint Databases","author":"Kuper G. M.","year":"2000","unstructured":"G. M. Kuper , L. Libkin , and J. Paredaens , editors . Constraint Databases . Springer , 2000 . G. M. Kuper, L. Libkin, and J. Paredaens, editors. Constraint Databases. Springer, 2000."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2017.105"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.14778\/3229863.3236233"},{"key":"e_1_2_1_20_1","first-page":"1","volume-title":"VLDB J.","author":"Lee S.","year":"2018","unstructured":"S. Lee , B. Lud\u00e4scher , and B. Glavic . Pug: a framework and practical implementation for why and why-not provenance . VLDB J. , pages 1 -- 25 , 2018 . S. Lee, B. Lud\u00e4scher, and B. Glavic. Pug: a framework and practical implementation for why and why-not provenance. VLDB J., pages 1--25, 2018."},{"key":"e_1_2_1_21_1","volume-title":"Approximate summaries for why and why-not provenance (extended version). Technical report, https:\/\/arxiv.org\/abs\/2002.00084","author":"Lee S.","year":"2020","unstructured":"S. Lee , B. Lud\u00e4scher , and B. Glavic . Approximate summaries for why and why-not provenance (extended version). Technical report, https:\/\/arxiv.org\/abs\/2002.00084 , 2020 . S. Lee, B. Lud\u00e4scher, and B. Glavic. Approximate summaries for why and why-not provenance (extended version). Technical report, https:\/\/arxiv.org\/abs\/2002.00084, 2020."},{"key":"e_1_2_1_22_1","first-page":"2","volume-title":"TaPP","author":"Lee S.","year":"2017","unstructured":"S. Lee , X. Niu , B. Lud\u00e4scher , and B. Glavic . Integrating approximate summarization with provenance capture . In TaPP , pages 2 -- 2 , 2017 . S. Lee, X. Niu, B. Lud\u00e4scher, and B. Glavic. Integrating approximate summarization with provenance capture. In TaPP, pages 2--2, 2017."},{"key":"e_1_2_1_23_1","volume-title":"TaPP","author":"Olteanu D.","year":"2011","unstructured":"D. Olteanu and J. Z\u00e1vodn\u00fd . On factorisation of provenance polynomials . In TaPP , 2011 . D. Olteanu and J. Z\u00e1vodn\u00fd. On factorisation of provenance polynomials. In TaPP, 2011."},{"key":"e_1_2_1_24_1","volume-title":"TaPP","author":"Riddle S.","year":"2014","unstructured":"S. Riddle , S. K\u00f6hler , and B. Lud\u00e4scher . Towards constraint provenance games . In TaPP , 2014 . S. Riddle, S. K\u00f6hler, and B. Lud\u00e4scher. Towards constraint provenance games. In TaPP, 2014."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2588578"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3051528.3051533"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2745754.2745765"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807172"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0215-8"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2750549"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536354.2536356"},{"key":"e_1_2_1_32_1","first-page":"3","volume-title":"Proceedings of the Twelfth ACM Workshop on Hot Topics in Networks","author":"Wu Y.","unstructured":"Y. Wu , A. Haeberlen , W. Zhou , and B. T. Loo . Answering why-not queries in software-defined networks with negative provenance . In Proceedings of the Twelfth ACM Workshop on Hot Topics in Networks , page 3 . ACM, 2013. Y. Wu, A. Haeberlen, W. Zhou, and B. T. Loo. Answering why-not queries in software-defined networks with negative provenance. In Proceedings of the Twelfth ACM Workshop on Hot Topics in Networks, page 3. ACM, 2013."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2619239.2626335"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2610501"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3380750.3380760","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T09:31:50Z","timestamp":1672219910000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3380750.3380760"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,2]]},"references-count":34,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2020,2]]}},"alternative-id":["10.14778\/3380750.3380760"],"URL":"https:\/\/doi.org\/10.14778\/3380750.3380760","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2020,2]]}}}