Provenance-based Data Skipping

Summary: Proposes provenance-based data skipping (PBDS) that builds compact provenance sketches encoding data relevance for a query, e.g., HAVING and top-k. These sketches speed up subsequent queries and can leverage physical design artifacts like indexes and zone maps. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 12921
Venue: VLDB
Year: 2022
Pagerank: 4.4279829e-05
Overall Rank: 8,886 | 38.19%
DOI: 10.14778/3494124.3494130

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
8,415	Pruning in Snowflake: Working Smarter, Not Harder	2025	SIGMOD	4.5197687e-05
10,886	FaDE: More Than a Million What-ifs Per Second	2025	VLDB	4.1945683e-05
10,895	Towards an Objective Metric for Data Value Through Relevance	2024	CIDR	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 37 of 37 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
24	The R+-Tree: A Dynamic Index For Multi-Dimensional Objects	1987	VLDB	0.00083378538
31	Provenance Semirings	2007	PODS	0.0007857786
158	Automated Selection of Materialized Views and Indexes for SQL Databases	2000	VLDB	0.00040071492
214	Scorpion: Explaining Away Outliers in Aggregate Queries	2013	VLDB	0.0003363692
286	Integrating Vertical and Horizontal Partitioning into Automated Physical Database Design	2004	SIGMOD	0.00028990057
297	Complexity of Answering Queries Using Materialized Views	1998	PODS	0.00028596715
368	Small Materialized Aggregates: A Light Weight Index Structure for Data Warehousing	1998	VLDB	0.000254931
561	An Annotation Management System for Relational Databases	2004	VLDB	0.00020115419
586	DBToaster: Higher-order Delta Processing for Dynamic, Frequently Fresh Views	2012	VLDB	0.00019685374
731	Optimizing Queries Using Materialized Views: A Practical, Scalable Solution	2001	SIGMOD	0.00017468889
942	A Formal Approach to Finding Explanations for Database Queries	2014	SIGMOD	0.00015155714
1,099	Interpretable and Informative Explanations of Outcomes	2015	VLDB	0.00014096312
1,106	Provenance for Aggregate Queries	2011	PODS	0.0001398766
1,646	Caravan: Provisioning for What-If Analysis	2013	CIDR	0.00011036992
1,861	Efficient Provenance Storage	2008	SIGMOD	0.00010287053
1,985	A Practical Scalable Distributed B-Tree	2008	VLDB	9.8569956e-05
1,989	Column Imprints: A Secondary Index Structure	2013	SIGMOD	9.8478437e-05
2,256	ProvSQL: Provenance and Probability Management in PostgreSQL	2018	VLDB	9.1879032e-05
2,280	SMOKE: Fine-grained Lineage at Interactive Speed	2018	VLDB	9.1111033e-05
2,363	Merging What’s Cracked, Cracking What’s Merged: Adaptive Indexing in Main-Memory Column-Stores	2011	VLDB	8.9580928e-05
2,649	Explaining Query Answers with Explanation-Ready Databases	2016	VLDB	8.3719123e-05
2,729	Vertical Partitioning for Database Design: A Graphical Algorithm	1989	SIGMOD	8.2167214e-05
2,764	The Semiring Framework for Database Provenance	2017	PODS	8.1574444e-05
3,153	Horizontal Data Partitioning In Database Design	1982	SIGMOD	7.4707022e-05
3,584	Efficient Querying and Maintenance of Network Provenance at Internet-Scale	2010	SIGMOD	6.9460423e-05
3,737	Skipping-oriented Partitioning for Columnar Layouts	2017	VLDB	6.8033227e-05
3,912	Two Birds, One Stone: A Fast, yet Lightweight, Indexing Scheme for Modern Database Systems	2017	VLDB	6.6354964e-05
4,386	Indexing on Modern Hardware: Hekaton and Beyond	2014	SIGMOD	6.2320098e-05
6,084	Distributed Provenance Compression	2017	SIGMOD	5.2196728e-05
6,696	Approximate Summaries for Why and Why-not Provenance	2020	VLDB	4.9581958e-05
6,777	Revisiting Reuse in Main Memory Database Systems	2017	SIGMOD	4.9288776e-05
7,208	Efficient Bulk Updates on Multiversion B-trees	2013	VLDB	4.7998295e-05
7,715	Query Centric Partitioning and Allocation for Partially Replicated Database Systems	2017	SIGMOD	4.6699261e-05
8,230	You Say 'What', I Hear 'Where' and 'Why' - (Mis-)Interpreting SQL to Derive Fine-Grained Provenance	2018	VLDB	4.5541444e-05
8,394	Hypothetical Reasoning via Provenance Abstraction	2019	SIGMOD	4.527807e-05
9,907	PROPOLIS: Provisioned Analysis of Data-Centric Processes	2013	VLDB	4.2577164e-05
11,733	Provenance Summaries for Answers and Non-Answers	2018	VLDB	4.1945683e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
9,029	Provenance for SQL through Abstract Interpretation: Value-less, but Worthwhile	2015	VLDB	4.4040532e-05
10,546	Evaluating Continuous Queries with Inconsistency Annotations	2025	VLDB	4.1945683e-05
11,993	A Partitioning Framework for Aggressive Data Skipping	2014	VLDB	4.1945683e-05
6,809	Adaptive Data Skipping in Main-Memory Systems	2016	SIGMOD	4.9206606e-05
8,729	OneProvenance: Efficient Extraction of Dynamic Coarse-Grained Provenance From Database Query Event Logs	2023	VLDB	4.4582221e-05
8,394	Hypothetical Reasoning via Provenance Abstraction	2019	SIGMOD	4.527807e-05
6,186	On Provenance Minimization	2011	PODS	5.166082e-05
6,466	Pando: Enhanced Data Skipping with Logical Data Partitioning	2023	VLDB	5.0528281e-05
2,173	Querying Data Provenance	2010	SIGMOD	9.3676609e-05
3,922	Pushing Data-Induced Predicates Through Joins in Big-Data Clusters	2020	VLDB	6.6291079e-05