Bounded Conjunctive Queries

Summary: Characterizes effectively bounded SPC queries under access schemas, where answers require only a dataset-size-independent fragment. Decides boundedness and parameter instantiation (quadratic-time to NP-complete), and synthesizes bounded-access plans with demonstrated cost reductions. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 10971
Venue: VLDB
Year: 2014
Pagerank: 6.7280426e-05
Overall Rank: 4,393 | 69.87%
DOI: 10.14778/2732977.2732996

Incoming Non-self Citations Over Time

Authors

1. Yang Cao (Beihang University; University of Edinburgh)
2. Wenfei Fan (Beihang University; University of Edinburgh)
3. Tianyu Wo (Beihang University)
4. Wenyuan Yu (Meta)

BibTeX Citation

@article{cao_vldb14,
        title = {{Bounded Conjunctive Queries}},
        author = {Cao, Yang and Fan, Wenfei and Wo, Tianyu and Yu, Wenyuan},
        journal = {PVLDB},
        series = {{VLDB} '14},
        volume = {7},
        number = {12},
        pages = {1231},
        doi = {10.14778/2732977.2732996},
        url = {https://doi.org/10.14778/2732977.2732996},
        year = {2014}
}

Incoming Citations (Sorted by Pagerank)

Showing 10 of 10 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,108	Approximate Query Processing: No Silver Bullet	2017	SIGMOD	0.00012145154
1,109	What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another?	2017	PODS	0.00012142685
2,462	Output-optimal Parallel Algorithms for Similarity Joins	2017	PODS	8.5487602e-05
6,841	Querying Big Data by Accessing Small Data	2015	PODS	5.7574257e-05
7,515	CYADB: A Database that Covers Your Ask	2018	VLDB	5.6029996e-05
8,701	Data Driven Approximation with Bounded Resources	2017	VLDB	5.3828806e-05
9,002	An Effective Syntax for Bounded Relational Queries	2016	SIGMOD	5.3346995e-05
11,990	BEAS: Bounded Evaluation of SQL Queries	2017	SIGMOD	5.093636e-05
12,029	Bounded Query Rewriting Using Views	2016	PODS	5.093636e-05
12,032	Logical Aspects of Massively Parallel and Distributed Systems	2016	PODS	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 10 of 10 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
136	Join Synopses for Approximate Query Answering	1999	SIGMOD	0.00030123303
435	Histogram-Based Approximation of Set-Valued Query Answers	1999	VLDB	0.000185063
909	Dynamic Sample Selection for Approximate Query Processing	2003	SIGMOD	0.00013291205
1,156	Wavelet Synopses with Error Guarantees	2002	SIGMOD	0.00011929041
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
4,250	Generalized Scale Independence Through Incremental Precomputation	2013	SIGMOD	6.8031294e-05
5,982	Size and Treewidth Bounds for Conjunctive Queries	2009	PODS	6.0207284e-05
7,484	On Scale Independence for Querying Big Data	2014	PODS	5.6074278e-05
12,294	Making Queries Tractable on Big Data with Preprocessing (through the eyes of complexity theory)	2013	VLDB	5.093636e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,029	Bounded Query Rewriting Using Views	2016	PODS
2	5,383	Compressed Representations of Conjunctive Query Results	2018	PODS
3	763	On the Complexity of Bounded-Variable Queries	1995	PODS
4	851	Query Optimization in the Presence of Limited Access Patterns	1999	SIGMOD
5	12,229	The Fine Classification of Conjunctive Queries and Parameterized Logarithmic Space Complexity	2013	PODS
6	9,994	Efficient Algorithms for Cardinality Estimation and Conjunctive Query Evaluation With Simple Degree Constraints	2025	PODS
7	10,182	The Space-Time Complexity of Sum-Product Queries	2026	PODS
8	9,009	Efficient Approximations of Conjunctive Queries	2012	PODS
9	6,841	Querying Big Data by Accessing Small Data	2015	PODS
10	9,002	An Effective Syntax for Bounded Relational Queries	2016	SIGMOD