Complete Yet Practical Search for Minimal Query Reformulations Under Constraints

Summary: ProvC&B preserves completeness for minimal reformulations by adding provenance to link joins to the universal-plan subqueries. From one provenance-enabled chase, reformulations are read directly, yielding speedups over naive chases and commercial rewrites. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 4813
Venue: SIGMOD
Year: 2014
Pagerank: 7.0263584e-05
Overall Rank: 3,509 | 75.59%
DOI: 10.1145/2588555.2593683

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 9 of 9 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,936	Querying with Access Patterns and Integrity Constraints	2015	VLDB	7.8554347e-05
4,293	ESTOCADA: Towards Scalable Polystore Systems	2020	VLDB	6.2885419e-05
4,499	Possible and Certain SQL Keys	2015	VLDB	6.1385333e-05
5,402	Towards Scalable Hybrid Stores: Constraint-Based Rewriting to the Rescue	2019	SIGMOD	5.5278023e-05
6,137	Detecting Metadata-Related Logic Bugs in Database Systems via Raw Database Construction	2024	VLDB	5.1916986e-05
7,557	Invisible Glue: Scalable Self-Tuning Multi-Stores	2015	CIDR	4.7112819e-05
8,961	An Effective Syntax for Bounded Relational Queries	2016	SIGMOD	4.4206115e-05
8,980	HADAD: A Lightweight Approach for Optimizing Hybrid Complex Analytics Queries	2021	SIGMOD	4.4169807e-05
10,603	Detecting Schema-Related Logic Bugs in Relational DBMSs via Equivalent Database Construction	2025	VLDB	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 17 of 17 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
31	Provenance Semirings	2007	PODS	0.0007857786
82	Answering Queries Using Views (Extended Abstract)	1995	PODS	0.00054402763
468	Materialized Views In Oracle	1998	VLDB	0.00022411821
584	Answering Queries with Aggregation Using Views	1996	VLDB	0.0001971526
607	Extending Query Rewriting Techniques for Fine-Grained Access Control	2004	SIGMOD	0.00019266724
731	Optimizing Queries Using Materialized Views: A Practical, Scalable Solution	2001	SIGMOD	0.00017468889
766	MARS: A System for Publishing XML from Mixed and Redundant Storage	2003	VLDB	0.00017014604
870	Query Optimization in the Presence of Limited Access Patterns	1999	SIGMOD	0.00015771912
873	Constraint-Based XML Query Rewriting for Data Integration	2004	SIGMOD	0.00015752865
1,059	Answering Complex SQL Queries Using Automatic Summary Tables	2000	SIGMOD	0.00014382575
2,401	Physical Data Independence, Constraints, and Optimization with Universal Plans	1999	VLDB	8.8954126e-05
3,065	Processing First-Order Queries under Limited Access Patterns	2004	PODS	7.6230903e-05
3,489	On Chase Termination Beyond Stratification	2009	VLDB	7.0468114e-05
4,654	A Chase Too Far?	2000	SIGMOD	6.022356e-05
5,471	Answering Queries Using Views with Arithmetic Comparisons	2002	PODS	5.4888202e-05
6,300	Rewriting Nested XML Queries Using Nested Views	2006	SIGMOD	5.1223169e-05
8,704	Equivalence of Nested Queries with Mixed Semantics	2009	PODS	4.4647149e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
2,861	Pushing Constraint Selections	1992	PODS	7.9919152e-05
6,567	Generating Efficient Plans for Queries Using Views	2001	SIGMOD	5.0069599e-05
6,881	Query Evaluation using Overlapping Views: Completeness and Efficiency	2006	SIGMOD	4.8964953e-05
12,297	Equivalence of SQL Queries In Presence of Embedded Dependencies	2009	PODS	4.1945683e-05
5,685	Exact Cardinality Query Optimization with Bounded Execution Cost	2019	SIGMOD	5.3717535e-05
2,936	Querying with Access Patterns and Integrity Constraints	2015	VLDB	7.8554347e-05
6,186	On Provenance Minimization	2011	PODS	5.166082e-05
2,727	Semantic Query Optimization in the Presence of Types	2010	PODS	8.2216778e-05
2,401	Physical Data Independence, Constraints, and Optimization with Universal Plans	1999	VLDB	8.8954126e-05
4,654	A Chase Too Far?	2000	SIGMOD	6.022356e-05