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: 1656
Venue: PODS
Year: 2015
Pagerank: 4.8388174e-05
Overall Rank: 7,085 | 50.72%
DOI: 10.1145/2745754.2745771

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 10 of 10 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,204	VerdictDB: Universalizing Approximate Query Processing	2018	SIGMOD	0.00013319541
1,574	Approximate Query Processing: No Silver Bullet	2017	SIGMOD	0.00011287495
2,588	Database Learning: Toward a Database that Becomes Smarter Every Time	2017	SIGMOD	8.4909562e-05
6,730	A Hierarchical Contraction Scheme for Querying Big Graphs	2022	SIGMOD	4.9479867e-05
8,715	Data Driven Approximation with Bounded Resources	2017	VLDB	4.4619052e-05
8,961	An Effective Syntax for Bounded Relational Queries	2016	SIGMOD	4.4206115e-05
11,672	Block as a Value for SQL over NoSQL	2019	VLDB	4.1945683e-05
11,785	BEAS: Bounded Evaluation of SQL Queries	2017	SIGMOD	4.1945683e-05
11,826	Bounded Query Rewriting Using Views	2016	PODS	4.1945683e-05
11,831	Logical Aspects of Massively Parallel and Distributed Systems	2016	PODS	4.1945683e-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
273	Approximate Computation of Multidimensional Aggregates of Sparse Data Using Wavelets	1999	SIGMOD	0.00029390945
361	Histogram-Based Approximation of Set-Valued Query Answers	1999	VLDB	0.00025775749
1,260	Dynamic Sample Selection for Approximate Query Processing	2003	SIGMOD	0.00012993347
1,400	Wavelet Synopses with Error Guarantees	2002	SIGMOD	0.00012191684
1,414	Graph Pattern Matching: From Intractable to Polynomial Time	2010	VLDB	0.00012118275
1,711	SCADS: Scale-Independent Storage for Social Computing Applications	2009	CIDR	0.0001080509
1,874	Knowing When You’re Wrong: Building Fast and Reliable Approximate Query Processing Systems	2014	SIGMOD	0.00010244443
2,056	PIQL: Success-Tolerant Query Processing in the Cloud	2012	VLDB	9.6645763e-05
3,065	Processing First-Order Queries under Limited Access Patterns	2004	PODS	7.6230903e-05
4,048	On the Complexity of the Containment Problem for Conjunctive Queries with Built-in Predicates	1998	PODS	6.4968603e-05
4,546	Bounded Conjunctive Queries	2014	VLDB	6.0987778e-05
7,413	On Scale Independence for Querying Big Data	2014	PODS	4.7358047e-05
8,851	Efficient Approximations of Conjunctive Queries	2012	PODS	4.4363908e-05
12,097	Making Queries Tractable on Big Data with Preprocessing (through the eyes of complexity theory)	2013	VLDB	4.1945683e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
9,843	Efficient Algorithms for Cardinality Estimation and Conjunctive Query Evaluation With Simple Degree Constraints	2025	PODS	4.2721228e-05
3,775	Bag Query Containment and Information Theory	2020	PODS	6.775636e-05
4,211	Querying Big Graphs within Bounded Resources	2014	SIGMOD	6.3563454e-05
11,826	Bounded Query Rewriting Using Views	2016	PODS	4.1945683e-05
8,851	Efficient Approximations of Conjunctive Queries	2012	PODS	4.4363908e-05
870	Query Optimization in the Presence of Limited Access Patterns	1999	SIGMOD	0.00015771912
7,413	On Scale Independence for Querying Big Data	2014	PODS	4.7358047e-05
3,065	Processing First-Order Queries under Limited Access Patterns	2004	PODS	7.6230903e-05
8,961	An Effective Syntax for Bounded Relational Queries	2016	SIGMOD	4.4206115e-05
4,546	Bounded Conjunctive Queries	2014	VLDB	6.0987778e-05