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: 4814
Venue: SIGMOD
Year: 2014
Pagerank: 7.0192177e-05
Overall Rank: 3,514 | 75.58%
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,942	Querying with Access Patterns and Integrity Constraints	2015	VLDB	7.8464054e-05
4,285	ESTOCADA: Towards Scalable Polystore Systems	2020	VLDB	6.2824978e-05
4,502	Possible and Certain SQL Keys	2015	VLDB	6.1322784e-05
5,409	Towards Scalable Hybrid Stores: Constraint-Based Rewriting to the Rescue	2019	SIGMOD	5.5224926e-05
6,143	Detecting Metadata-Related Logic Bugs in Database Systems via Raw Database Construction	2024	VLDB	5.1867156e-05
7,557	Invisible Glue: Scalable Self-Tuning Multi-Stores	2015	CIDR	4.7070194e-05
8,963	An Effective Syntax for Bounded Relational Queries	2016	SIGMOD	4.4165156e-05
8,981	HADAD: A Lightweight Approach for Optimizing Hybrid Complex Analytics Queries	2021	SIGMOD	4.4138435e-05
10,611	Detecting Schema-Related Logic Bugs in Relational DBMSs via Equivalent Database Construction	2025	VLDB	4.1905499e-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.00078516827
82	Answering Queries Using Views (Extended Abstract)	1995	PODS	0.00054430106
470	Materialized Views In Oracle	1998	VLDB	0.00022386815
583	Answering Queries with Aggregation Using Views	1996	VLDB	0.00019705383
607	Extending Query Rewriting Techniques for Fine-Grained Access Control	2004	SIGMOD	0.00019248482
728	Optimizing Queries Using Materialized Views: A Practical, Scalable Solution	2001	SIGMOD	0.00017459654
761	MARS: A System for Publishing XML from Mixed and Redundant Storage	2003	VLDB	0.00016998994
867	Query Optimization in the Presence of Limited Access Patterns	1999	SIGMOD	0.00015757737
868	Constraint-Based XML Query Rewriting for Data Integration	2004	SIGMOD	0.00015737664
1,059	Answering Complex SQL Queries Using Automatic Summary Tables	2000	SIGMOD	0.00014370009
2,398	Physical Data Independence, Constraints, and Optimization with Universal Plans	1999	VLDB	8.8871067e-05
3,069	Processing First-Order Queries under Limited Access Patterns	2004	PODS	7.6161135e-05
3,494	On Chase Termination Beyond Stratification	2009	VLDB	7.0401e-05
4,650	A Chase Too Far?	2000	SIGMOD	6.0169723e-05
5,496	Answering Queries Using Views with Arithmetic Comparisons	2002	PODS	5.4741922e-05
6,300	Rewriting Nested XML Queries Using Nested Views	2006	SIGMOD	5.1174095e-05
8,699	Equivalence of Nested Queries with Mixed Semantics	2009	PODS	4.4604187e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
2,870	Pushing Constraint Selections	1992	PODS	7.9840692e-05
6,884	Query Evaluation using Overlapping Views: Completeness and Efficiency	2006	SIGMOD	4.8917858e-05
6,567	Generating Efficient Plans for Queries Using Views	2001	SIGMOD	5.0023017e-05
12,305	Equivalence of SQL Queries In Presence of Embedded Dependencies	2009	PODS	4.1905499e-05
5,696	Exact Cardinality Query Optimization with Bounded Execution Cost	2019	SIGMOD	5.367449e-05
2,942	Querying with Access Patterns and Integrity Constraints	2015	VLDB	7.8464054e-05
6,187	On Provenance Minimization	2011	PODS	5.1611195e-05
2,732	Semantic Query Optimization in the Presence of Types	2010	PODS	8.2137395e-05
2,398	Physical Data Independence, Constraints, and Optimization with Universal Plans	1999	VLDB	8.8871067e-05
4,650	A Chase Too Far?	2000	SIGMOD	6.0169723e-05