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: 1655
Venue: PODS
Year: 2015
Pagerank: 5.7574257e-05
Overall Rank: 6,841 | 53.07%
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
772	VerdictDB: Universalizing Approximate Query Processing	2018	SIGMOD	0.00014147905
1,108	Approximate Query Processing: No Silver Bullet	2017	SIGMOD	0.00012145154
1,995	Database Learning: Toward a Database that Becomes Smarter Every Time	2017	SIGMOD	9.3403665e-05
6,876	A Hierarchical Contraction Scheme for Querying Big Graphs	2022	SIGMOD	5.7483615e-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,867	Block as a Value for SQL over NoSQL	2019	VLDB	5.093636e-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 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
213	Approximate Computation of Multidimensional Aggregates of Sparse Data Using Wavelets	1999	SIGMOD	0.00024723025
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,128	Graph Pattern Matching: From Intractable to Polynomial Time	2010	VLDB	0.0001206219
1,156	Wavelet Synopses with Error Guarantees	2002	SIGMOD	0.00011929041
1,401	Knowing When You’re Wrong: Building Fast and Reliable Approximate Query Processing Systems	2014	SIGMOD	0.00010889902
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,733	Processing First-Order Queries under Limited Access Patterns	2004	PODS	8.1927747e-05
3,801	On the Complexity of the Containment Problem for Conjunctive Queries with Built-in Predicates	1998	PODS	7.1130194e-05
4,393	Bounded Conjunctive Queries	2014	VLDB	6.7280426e-05
7,484	On Scale Independence for Querying Big Data	2014	PODS	5.6074278e-05
9,009	Efficient Approximations of Conjunctive Queries	2012	PODS	5.3335287e-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	3,457	Bag Query Containment and Information Theory	2020	PODS
2	4,474	Querying Big Graphs within Bounded Resources	2014	SIGMOD
3	7,830	When Can We Answer Queries Using Result-Bounded Data Interfaces?	2018	PODS
4	12,029	Bounded Query Rewriting Using Views	2016	PODS
5	9,009	Efficient Approximations of Conjunctive Queries	2012	PODS
6	851	Query Optimization in the Presence of Limited Access Patterns	1999	SIGMOD
7	7,484	On Scale Independence for Querying Big Data	2014	PODS
8	2,733	Processing First-Order Queries under Limited Access Patterns	2004	PODS
9	9,002	An Effective Syntax for Bounded Relational Queries	2016	SIGMOD
10	4,393	Bounded Conjunctive Queries	2014	VLDB