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: h0b6f87e2ea0e3b78
Venue: VLDB
Year: 2014
Pagerank: 6.5938977e-05
Overall Rank: 4,452 | 70.07%
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,082	Approximate Query Processing: No Silver Bullet	2017	SIGMOD	0.00012122749
1,091	What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another?	2017	PODS	0.00012074152
2,464	Output-optimal Parallel Algorithms for Similarity Joins	2017	PODS	8.4260608e-05
6,954	Querying Big Data by Accessing Small Data	2015	PODS	5.6350266e-05
7,661	CYADB: A Database that Covers Your Ask	2018	VLDB	5.4772833e-05
8,846	Data Driven Approximation with Bounded Resources	2017	VLDB	5.2649328e-05
9,152	An Effective Syntax for Bounded Relational Queries	2016	SIGMOD	5.2177821e-05
12,288	BEAS: Bounded Evaluation of SQL Queries	2017	SIGMOD	4.9793485e-05
12,324	Bounded Query Rewriting Using Views	2016	PODS	4.9793485e-05
12,327	Logical Aspects of Massively Parallel and Distributed Systems	2016	PODS	4.9793485e-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
138	Join Synopses for Approximate Query Answering	1999	SIGMOD	0.00029627449
448	Histogram-Based Approximation of Set-Valued Query Answers	1999	VLDB	0.00018129161
931	Dynamic Sample Selection for Approximate Query Processing	2003	SIGMOD	0.00013011667
1,173	Wavelet Synopses with Error Guarantees	2002	SIGMOD	0.00011686985
1,638	SCADS: Scale-Independent Storage for Social Computing Applications	2009	CIDR	0.00010012154
2,008	PIQL: Success-Tolerant Query Processing in the Cloud	2012	VLDB	9.1988831e-05
4,321	Generalized Scale Independence Through Incremental Precomputation	2013	SIGMOD	6.6660222e-05
6,043	Size and Treewidth Bounds for Conjunctive Queries	2009	PODS	5.9060629e-05
7,610	On Scale Independence for Querying Big Data	2014	PODS	5.4844912e-05
12,585	Making Queries Tractable on Big Data with Preprocessing (through the eyes of complexity theory)	2013	VLDB	4.9793485e-05

Semantically Similar Papers

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