Querying Big Data by Accessing Small Data

Summary: Define bounded evaluability: under index/cardinality access constraints, Q can be answered by inspecting a D_Q whose size and discovery cost depend only on Q and the constraints. Show FO undecidable in general, identify decidable FO fragments with effective syntax, and develop two approximation methods (bounded envelopes, parameter specialization) with decision/complexity results. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: he4a853aa1099b4ee
Venue: PODS
Year: 2015
Pagerank: 5.6350266e-05
Overall Rank: 6,954 | 53.25%
DOI: 10.1145/2745754.2745771

Incoming Non-self Citations Over Time

Authors

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

BibTeX Citation

@inproceedings{fan_pods15,
        address = {New York, NY, USA},
        series = {{PODS} '15},
        title = {{Querying Big Data by Accessing Small Data}},
        url = {https://dl.acm.org/doi/10.1145/2745754.2745771},
        doi = {10.1145/2745754.2745771},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Fan, Wenfei and Geerts, Floris and Cao, Yang and Deng, Ting and Lu, Ping},
        year = {2015}
}

Incoming Citations (Sorted by Pagerank)

Showing 10 of 10 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
784	VerdictDB: Universalizing Approximate Query Processing	2018	SIGMOD	0.00014012614
1,082	Approximate Query Processing: No Silver Bullet	2017	SIGMOD	0.00012122749
2,027	Database Learning: Toward a Database that Becomes Smarter Every Time	2017	SIGMOD	9.1618139e-05
7,015	A Hierarchical Contraction Scheme for Querying Big Graphs	2022	SIGMOD	5.6210836e-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,167	Block as a Value for SQL over NoSQL	2019	VLDB	4.9793485e-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 14 of 14 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
222	Approximate Computation of Multidimensional Aggregates of Sparse Data Using Wavelets	1999	SIGMOD	0.00024218831
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,148	Graph Pattern Matching: From Intractable to Polynomial Time	2010	VLDB	0.00011809728
1,173	Wavelet Synopses with Error Guarantees	2002	SIGMOD	0.00011686985
1,428	Knowing When You’re Wrong: Building Fast and Reliable Approximate Query Processing Systems	2014	SIGMOD	0.00010693831
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
2,790	Processing First-Order Queries under Limited Access Patterns	2004	PODS	8.0100392e-05
3,870	On the Complexity of the Containment Problem for Conjunctive Queries with Built-in Predicates	1998	PODS	6.9551842e-05
4,452	Bounded Conjunctive Queries	2014	VLDB	6.5938977e-05
7,610	On Scale Independence for Querying Big Data	2014	PODS	5.4844912e-05
9,169	Efficient Approximations of Conjunctive Queries	2012	PODS	5.2141412e-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	3,526	Bag Query Containment and Information Theory	2020	PODS
2	4,551	Querying Big Graphs within Bounded Resources	2014	SIGMOD
3	7,991	When Can We Answer Queries Using Result-Bounded Data Interfaces?	2018	PODS
4	12,324	Bounded Query Rewriting Using Views	2016	PODS
5	9,169	Efficient Approximations of Conjunctive Queries	2012	PODS
6	869	Query Optimization in the Presence of Limited Access Patterns	1999	SIGMOD
7	7,610	On Scale Independence for Querying Big Data	2014	PODS
8	2,790	Processing First-Order Queries under Limited Access Patterns	2004	PODS
9	9,152	An Effective Syntax for Bounded Relational Queries	2016	SIGMOD
10	4,452	Bounded Conjunctive Queries	2014	VLDB