Bounded Query Rewriting Using Views

Summary: Decide if Q has a bounded rewriting via views V under access constraints A — Q answerable from cached views plus fragment D_Q whose size and lookup are independent of |D|. Results: Σp^3-complete for CQs (even acyclic), undecidable for FO/RA; PTIME cases identified and a PTIME-checkable FO core syntax provided. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1688
Venue: PODS
Year: 2016
Pagerank: 5.093636e-05
Overall Rank: 12,029 | 17.48%
DOI: 10.1145/2902251.2902294

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Yang Cao (Beihang University; University of Edinburgh)
2. Wenfei Fan (Beihang University; University of Edinburgh)
3. Floris Geerts (University of Antwerp)
4. Ping Lu (Beihang University)

BibTeX Citation

@inproceedings{cao_pods16,
        address = {New York, NY, USA},
        series = {{PODS} '16},
        title = {{Bounded Query Rewriting Using Views}},
        url = {https://dl.acm.org/doi/10.1145/2902251.2902294},
        doi = {10.1145/2902251.2902294},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Cao, Yang and Fan, Wenfei and Geerts, Floris and Lu, Ping},
        year = {2016}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
8,701	Data Driven Approximation with Bounded Resources	2017	VLDB	5.3828806e-05
11,990	BEAS: Bounded Evaluation of SQL Queries	2017	SIGMOD	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 15 of 15 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
22	Data Integration: A Theoretical Perspective	2002	PODS	0.00056204792
69	Answering Queries Using Views (Extended Abstract)	1995	PODS	0.00038090878
298	Answering Queries Using Templates With Binding Patterns (Extended Abstract)	1995	PODS	0.00022138018
763	On the Complexity of Bounded-Variable Queries	1995	PODS	0.00014230134
869	Rewriting Aggregate Queries Using Views	1999	PODS	0.00013503594
1,635	SCADS: Scale-Independent Storage for Social Computing Applications	2009	CIDR	0.00010158805
1,969	PIQL: Success-Tolerant Query Processing in the Cloud	2012	VLDB	9.3749819e-05
2,330	Hypertree Decompositions and Tractable Queries	1999	PODS	8.7447066e-05
2,733	Processing First-Order Queries under Limited Access Patterns	2004	PODS	8.1927747e-05
4,250	Generalized Scale Independence Through Incremental Precomputation	2013	SIGMOD	6.8031294e-05
4,393	Bounded Conjunctive Queries	2014	VLDB	6.7280426e-05
6,286	Finite Queries do not Have Effective Syntax	1995	PODS	5.9269746e-05
6,841	Querying Big Data by Accessing Small Data	2015	PODS	5.7574257e-05
7,484	On Scale Independence for Querying Big Data	2014	PODS	5.6074278e-05
9,002	An Effective Syntax for Bounded Relational Queries	2016	SIGMOD	5.3346995e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,121	Query Evaluation using Overlapping Views: Completeness and Efficiency	2006	SIGMOD
2	9,002	An Effective Syntax for Bounded Relational Queries	2016	SIGMOD
3	5,146	Query Containment and Rewriting Using Views for Regular Path Queries Under Constraints	2003	PODS
4	5,361	Answering Queries Using Views with Arithmetic Comparisons	2002	PODS
5	69	Answering Queries Using Views (Extended Abstract)	1995	PODS
6	4,445	View-Based Query Containment	2003	PODS
7	6,624	Queries Determined by Views: Pack Your Views	2007	PODS
8	1,991	Views and Queries: Determinacy and Rewriting	2005	PODS
9	2,527	Rewriting Queries Using Views in Description Logics	1997	PODS
10	869	Rewriting Aggregate Queries Using Views	1999	PODS