{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,24]],"date-time":"2025-07-24T11:25:51Z","timestamp":1753356351236},"reference-count":93,"publisher":"Association for Computing Machinery (ACM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2021,11]]},"abstract":"<jats:p>Database systems use static analysis to determine upfront which data is needed for answering a query and use indexes and other physical design techniques to speed-up access to that data. However, for important classes of queries, e.g., HAVING and top-k queries, it is impossible to determine up-front what data is<jats:italic>relevant.<\/jats:italic>To overcome this limitation, we develop provenance-based data skipping (PBDS), a novel approach that generates provenance sketches to concisely encode what data is relevant for a query. Once a provenance sketch has been captured it is used to speed up subsequent queries. PBDS can exploit physical design artifacts such as indexes and zone maps.<\/jats:p>","DOI":"10.14778\/3494124.3494130","type":"journal-article","created":{"date-parts":[[2022,2,5]],"date-time":"2022-02-05T00:31:46Z","timestamp":1644021106000},"page":"451-464","source":"Crossref","is-referenced-by-count":4,"title":["Provenance-based data skipping"],"prefix":"10.14778","volume":"15","author":[{"given":"Xing","family":"Niu","sequence":"first","affiliation":[{"name":"Illinois Institute of Technology"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Boris","family":"Glavic","sequence":"additional","affiliation":[{"name":"Illinois Institute of Technology"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ziyu","family":"Liu","sequence":"additional","affiliation":[{"name":"Illinois Institute of Technology"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pengyuan","family":"Li","sequence":"additional","affiliation":[{"name":"Illinois Institute of Technology"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dieter","family":"Gawlick","sequence":"additional","affiliation":[{"name":"Oracle"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vasudha","family":"Krishnaswamy","sequence":"additional","affiliation":[{"name":"Oracle"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhen Hua","family":"Liu","sequence":"additional","affiliation":[{"name":"Oracle"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Danica","family":"Porobic","sequence":"additional","affiliation":[{"name":"Oracle"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,2,4]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"[n.d.]. http:\/\/www.tpc.org\/tpch\/ (visited on 10\/28\/2021). [n.d.]. http:\/\/www.tpc.org\/tpch\/ (visited on 10\/28\/2021)."},{"key":"e_1_2_1_2_1","unstructured":"Serge Abiteboul and Olivier Duschka. 2013. Complexity of Answering Queries Using Materialized Views. (2013). Serge Abiteboul and Olivier Duschka. 2013. Complexity of Answering Queries Using Materialized Views. (2013)."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/275487.275516"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.14778\/2556549.2556566"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/645926.671701"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007609"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453922"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.14778\/2336664.2336670"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2806416.2806429"},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","unstructured":"Khalil Amiri Sanghyun Park Renu Tewari and Sriram Padmanabhan. 2003. Scalable template-based query containment checking for web semantic caches. In ICDE. 493--504. Khalil Amiri Sanghyun Park Renu Tewari and Sriram Padmanabhan. 2003. Scalable template-based query containment checking for web semantic caches. In ICDE. 493--504.","DOI":"10.1109\/ICDE.2003.1260816"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989284.1989302"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1516360.1516470"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/11546849_7"},{"key":"e_1_2_1_14_1","first-page":"51","article-title":"GProM - A Swiss Army Knife for Your Provenance Needs","volume":"41","author":"Arab Bahareh Sadat","year":"2018","unstructured":"Bahareh Sadat Arab , Su Feng , Boris Glavic , Seokki Lee , Xing Niu , and Qitian Zeng . 2018 . GProM - A Swiss Army Knife for Your Provenance Needs . Data Eng. Bull. 41 , 1 (2018), 51 -- 62 . Bahareh Sadat Arab, Su Feng, Boris Glavic, Seokki Lee, Xing Niu, and Qitian Zeng. 2018. GProM - A Swiss Army Knife for Your Provenance Needs. Data Eng. Bull. 41, 1 (2018), 51--62.","journal-title":"Data Eng. Bull."},{"key":"e_1_2_1_15_1","first-page":"1","article-title":"Algorithms for Provisioning Queries and Analytics","volume":"18","author":"Assadi Sepehr","year":"2016","unstructured":"Sepehr Assadi , Sanjeev Khanna , Yang Li , and Val Tannen . 2016 . Algorithms for Provisioning Queries and Analytics . In ICDT. 18 : 1 -- 18 :18. Sepehr Assadi, Sanjeev Khanna, Yang Li, and Val Tannen. 2016. Algorithms for Provisioning Queries and Analytics. In ICDT. 18:1--18:18.","journal-title":"ICDT."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-005-0156-6"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008729828172"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/582353.582376"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/800105.803397"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376715"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2004.75"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/645480.655434"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/1325851.1325856"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3035926"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1561\/1900000006"},{"key":"e_1_2_1_26_1","doi-asserted-by":"crossref","unstructured":"John Clarke. 2013. Storage indexes. In Oracle Exadata Recipes. 553--576. John Clarke. 2013. Storage indexes. In Oracle Exadata Recipes. 553--576.","DOI":"10.1007\/978-1-4302-4915-3_19"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/357775.357777"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/1792734.1792766"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/1792734.1792766"},{"key":"e_1_2_1_30_1","volume-title":"Caravan: Provisioning for What-If Analysis. CIDR","author":"Deutch D.","year":"2013","unstructured":"D. Deutch , Z. Ives , T. Milo , and V. Tannen . 2013 . Caravan: Provisioning for What-If Analysis. CIDR (2013). D. Deutch, Z. Ives, T. Milo, and V. Tannen. 2013. Caravan: Provisioning for What-If Analysis. CIDR (2013)."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3300084"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536274.2536301"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2483574.2483578"},{"key":"e_1_2_1_34_1","volume-title":"Miller","author":"Du Jiang","year":"2017","unstructured":"Jiang Du , Boris Glavic , Wei Tan , and Ren\u00e9e J . Miller . 2017 . DeepSea: Adaptive Workload-Aware Partitioning of Materialized Views in Scalable Data Analytics. In EDBT. 198--209. Jiang Du, Boris Glavic, Wei Tan, and Ren\u00e9e J. Miller. 2017. DeepSea: Adaptive Workload-Aware Partitioning of Materialized Views in Scalable Data Analytics. In EDBT. 198--209."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3035957"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735461.2735467"},{"key":"e_1_2_1_37_1","first-page":"14","article-title":"Explanation Tables","volume":"5","author":"Gebaly Kareem El","year":"2018","unstructured":"Kareem El Gebaly , Guoyao Feng , Lukasz Golab , Flip Korn , and Divesh Srivastava . 2018 . Explanation Tables . Sat 5 (2018), 14 . Kareem El Gebaly, Guoyao Feng, Lukasz Golab, Flip Korn, and Divesh Srivastava. 2018. Explanation Tables. Sat 5 (2018), 14.","journal-title":"Sat"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.scico.2017.08.009"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jal.2009.09.001"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1561\/1900000068"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.5555\/2814579.2814592"},{"key":"e_1_2_1_42_1","doi-asserted-by":"crossref","unstructured":"Boris Glavic Ren\u00e9e J Miller and Gustavo Alonso. 2013. Using SQL for Efficient Generation and Querying of Provenance Information. In In Search of Elegance in the Theory and Practice of Computation. 291--320. Boris Glavic Ren\u00e9e J Miller and Gustavo Alonso. 2013. Using SQL for Efficient Generation and Querying of Provenance Information. In In Search of Elegance in the Theory and Practice of Computation. 291--320.","DOI":"10.1007\/978-3-642-41660-6_16"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/376284.375706"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/1121995.1122002"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/1739041.1739087"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-32925-8_1"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/1265530.1265535"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/3034786.3056125"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.5555\/310709"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1007\/s007780100054"},{"key":"e_1_2_1_51_1","unstructured":"S\u00e1ndor H\u00e9man Niels J Nes Marcin \u017bukowski and Peter Alexander Boncz. 2008. Positional Delta Trees to reconcile updates with read-optimized data storage. CWI. Information Systems [INS]. S\u00e1ndor H\u00e9man Niels J Nes Marcin \u017bukowski and Peter Alexander Boncz. 2008. Positional Delta Trees to reconcile updates with read-optimized data storage. CWI. Information Systems [INS]."},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.14778\/2002938.2002944"},{"key":"e_1_2_1_53_1","doi-asserted-by":"crossref","unstructured":"Robert Ikeda Semih Salihoglu and Jennifer Widom. 2010. Provenance-Based Refresh in Data-Oriented Workflows. technical report. Robert Ikeda Semih Salihoglu and Jennifer Widom. 2010. Provenance-Based Refresh in Data-Oriented Workflows. technical report.","DOI":"10.1145\/2063576.2063816"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.5555\/1855795.1855800"},{"key":"e_1_2_1_55_1","doi-asserted-by":"crossref","unstructured":"Alekh Jindal and Jens Dittrich. 2012. Relax and let the database do the partitioning online. In Enabling Real-Time Business Intelligence. 65--80. Alekh Jindal and Jens Dittrich. 2012. Relax and let the database do the partitioning online. In Enabling Real-Time Business Intelligence. 65--80.","DOI":"10.1007\/978-3-642-33500-6_5"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/2380776.2380778"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/42267.42273"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-32925-8_12"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.14778\/3229863.3236233"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.14778\/3380750.3380760"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544812"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2594536"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544834"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/212433.220198"},{"key":"e_1_2_1_65_1","doi-asserted-by":"crossref","unstructured":"Xiang Li Xiaoyang Xu and Tanu Malik. 2016. Interactive provenance summaries for reproducible science. In eScience. 355--360. Xiang Li Xiaoyang Xu and Tanu Malik. 2016. Interactive provenance summaries for reproducible science. In eScience. 355--360.","DOI":"10.1109\/eScience.2016.7870920"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1007\/s007780050071"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1109\/eScience.2010.51"},{"key":"e_1_2_1_68_1","unstructured":"Guido Moerkotte. 1998. Small materialized aggregates: A light weight index structure for data warehousing. (1998). Guido Moerkotte. 1998. Small materialized aggregates: A light weight index structure for data warehousing. (1998)."},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.14778\/3236187.3236204"},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1145\/67544.66966"},{"key":"e_1_2_1_71_1","volume-title":"Vasudha Krishnaswamy, and Venkatesh Radhakrishnan.","author":"Niu Xing","year":"2017","unstructured":"Xing Niu , Raghav Kapoor , Boris Glavic , Dieter Gawlick , Zhen Hua Liu , Vasudha Krishnaswamy, and Venkatesh Radhakrishnan. 2017 . Provenance-aware Query Optimization. In ICDE. 473--484. Xing Niu, Raghav Kapoor, Boris Glavic, Dieter Gawlick, Zhen Hua Liu, Vasudha Krishnaswamy, and Venkatesh Radhakrishnan. 2017. Provenance-aware Query Optimization. In ICDE. 473--484."},{"key":"e_1_2_1_72_1","first-page":"1267","article-title":"Heuristic and Cost-based Optimization for Diverse Provenance Tasks","volume":"31","author":"Niu Xing","year":"2018","unstructured":"Xing Niu , Raghav Kapoor , Boris Glavic , Dieter Gawlick , Zhen Hua Liu , Vasudha Krishnaswamy , and Venkatesh Radhakrishnan . 2018 . Heuristic and Cost-based Optimization for Diverse Provenance Tasks . TKDE 31 , 7 (2018), 1267 -- 1280 . Xing Niu, Raghav Kapoor, Boris Glavic, Dieter Gawlick, Zhen Hua Liu, Vasudha Krishnaswamy, and Venkatesh Radhakrishnan. 2018. Heuristic and Cost-based Optimization for Diverse Provenance Tasks. TKDE 31, 7 (2018), 1267--1280.","journal-title":"TKDE"},{"key":"e_1_2_1_73_1","unstructured":"Xing Niu Ziyu Liu Pengyuan Li and Boris Glavic. 2021. Provenance-based Data Skipping (extended version). (2021). arXiv:2104.12815 Xing Niu Ziyu Liu Pengyuan Li and Boris Glavic. 2021. Provenance-based Data Skipping (extended version). (2021). arXiv:2104.12815"},{"key":"e_1_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1145\/3003665.3003667"},{"key":"e_1_2_1_75_1","unstructured":"Dan Olteanu and Jakub Z\u00e1vodn\u00fd. 2011. On Factorisation of Provenance Polynomials. In TaPP. Dan Olteanu and Jakub Z\u00e1vodn\u00fd. 2011. On Factorisation of Provenance Polynomials. In TaPP."},{"key":"e_1_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.1145\/211990.212001"},{"key":"e_1_2_1_77_1","volume-title":"Autopart: Automating schema design for large scientific databases using data partitioning.","author":"Papadomanolakis S.","year":"2004","unstructured":"S. Papadomanolakis and A. Ailamaki . 2004 . Autopart: Automating schema design for large scientific databases using data partitioning. (2004). S. Papadomanolakis and A. Ailamaki. 2004. Autopart: Automating schema design for large scientific databases using data partitioning. (2004)."},{"key":"e_1_2_1_78_1","volume-title":"Jermaine","author":"Perez Luis L.","year":"2014","unstructured":"Luis L. Perez and Christopher M . Jermaine . 2014 . History-aware Query Optimization with Materialized Intermediate Views. In ICDE. Luis L. Perez and Christopher M. Jermaine. 2014. History-aware Query Optimization with Materialized Intermediate Views. In ICDE."},{"key":"e_1_2_1_79_1","doi-asserted-by":"publisher","DOI":"10.5555\/3199517.3199522"},{"key":"e_1_2_1_80_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3064052"},{"key":"e_1_2_1_81_1","doi-asserted-by":"publisher","DOI":"10.14778\/2856318.2856329"},{"key":"e_1_2_1_82_1","unstructured":"Sudeepa Roy and Dan Suciu. 2014. A formal approach to finding explanations for database queries. Sudeepa Roy and Dan Suciu. 2014. A formal approach to finding explanations for database queries."},{"key":"e_1_2_1_83_1","doi-asserted-by":"publisher","DOI":"10.1145\/322217.322221"},{"key":"e_1_2_1_84_1","doi-asserted-by":"publisher","DOI":"10.5555\/645914.671636"},{"key":"e_1_2_1_85_1","doi-asserted-by":"publisher","DOI":"10.14778\/3229863.3236253"},{"key":"e_1_2_1_86_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465306"},{"key":"e_1_2_1_87_1","doi-asserted-by":"publisher","DOI":"10.14778\/3025111.3025123"},{"key":"e_1_2_1_88_1","doi-asserted-by":"publisher","DOI":"10.5555\/3522802.3522955"},{"key":"e_1_2_1_89_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536354.2536356"},{"key":"e_1_2_1_90_1","doi-asserted-by":"publisher","DOI":"10.14778\/3025111.3025120"},{"key":"e_1_2_1_91_1","doi-asserted-by":"crossref","unstructured":"Jingren Zhou Per-Ake Larson and Ronnie Chaiken. 2010. Incorporating partitioning and parallel plans into the SCOPE optimizer. In ICDE. 1060--1071. Jingren Zhou Per-Ake Larson and Ronnie Chaiken. 2010. Incorporating partitioning and parallel plans into the SCOPE optimizer. In ICDE. 1060--1071.","DOI":"10.1109\/ICDE.2010.5447802"},{"key":"e_1_2_1_92_1","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342267"},{"key":"e_1_2_1_93_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807234"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3494124.3494130","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,17]],"date-time":"2024-09-17T22:35:08Z","timestamp":1726612508000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3494124.3494130"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,11]]},"references-count":93,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,11]]}},"alternative-id":["10.14778\/3494124.3494130"],"URL":"https:\/\/doi.org\/10.14778\/3494124.3494130","relation":{},"ISSN":["2150-8097"],"issn-type":[{"type":"print","value":"2150-8097"}],"subject":[],"published":{"date-parts":[[2021,11]]}}}