On Scale Independence for Querying Big Data

Summary: Formalizes scale independence—queries whose needed retrieval size depends on query+access methods, not dataset size—and gives matching upper/lower bounds for deciding it across languages and complexity regimes. Since exact checks are hard and non-syntactic, derives sufficient conditions via access schemas (indexes, constraints, cardinality bounds) and studies scale-independent incremental maintenance and view-based rewrites. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: h085be824798f96e6
Venue: PODS
Year: 2014
Pagerank: 5.4649494e-05
Overall Rank: 7,628 | 48.87%
DOI: 10.1145/2594538.2594551

Incoming Non-self Citations Over Time

Authors

1. Wenfei Fan (Beihang University; University of Edinburgh)
2. Floris Geerts (University of Antwerp)
3. Leonid Libkin (University of Edinburgh)

BibTeX Citation

@inproceedings{fan_pods14,
        address = {New York, NY, USA},
        series = {{PODS} '14},
        title = {{On Scale Independence for Querying Big Data}},
        url = {https://dl.acm.org/doi/10.1145/2594538.2594551},
        doi = {10.1145/2594538.2594551},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Fan, Wenfei and Geerts, Floris and Libkin, Leonid},
        year = {2014}
}

Incoming Citations (Sorted by Pagerank)

Showing 10 of 10 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,065	Approximate Query Processing: No Silver Bullet	2017	SIGMOD	0.00012181098
3,913	Automatic Enforcement of Data Use Policies with DataLawyer	2015	SIGMOD	6.9088542e-05
4,473	Bounded Conjunctive Queries	2014	VLDB	6.570529e-05
6,964	Querying Big Data by Accessing Small Data	2015	PODS	5.617412e-05
8,870	Data Driven Approximation with Bounded Resources	2017	VLDB	5.246202e-05
9,180	An Effective Syntax for Bounded Relational Queries	2016	SIGMOD	5.1992243e-05
12,216	Block as a Value for SQL over NoSQL	2019	VLDB	4.9605343e-05
12,337	BEAS: Bounded Evaluation of SQL Queries	2017	SIGMOD	4.9605343e-05
12,373	Bounded Query Rewriting Using Views	2016	PODS	4.9605343e-05
12,376	Logical Aspects of Massively Parallel and Distributed Systems	2016	PODS	4.9605343e-05

Outgoing Citations (Sorted by Pagerank)

Showing 12 of 12 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
24	Data Integration: A Theoretical Perspective	2002	PODS	0.00055201845
72	Answering Queries Using Views (Extended Abstract)	1995	PODS	0.00037421163
408	DBToaster: Higher-order Delta Processing for Dynamic, Frequently Fresh Views	2012	VLDB	0.00018836656
878	Queries Independent of Updates	1993	VLDB	0.0001326705
982	Parallel Evaluation of Conjunctive Queries	2011	PODS	0.00012687016
1,643	SCADS: Scale-Independent Storage for Social Computing Applications	2009	CIDR	9.9801601e-05
2,018	PIQL: Success-Tolerant Query Processing in the Cloud	2012	VLDB	9.1687512e-05
2,561	Minimal MapReduce Algorithms	2013	SIGMOD	8.2743492e-05
2,799	Processing First-Order Queries under Limited Access Patterns	2004	PODS	7.9805096e-05
4,338	Generalized Scale Independence Through Incremental Precomputation	2013	SIGMOD	6.6413964e-05
5,754	Relative Information Completeness	2009	PODS	5.9887721e-05
12,634	Making Queries Tractable on Big Data with Preprocessing (through the eyes of complexity theory)	2013	VLDB	4.9605343e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,725	Query Centric Partitioning and Allocation for Partially Replicated Database Systems	2017	SIGMOD
2	13,050	Scalable Continuous Query Processing by Tracking Hotspots	2006	VLDB
3	4,473	Bounded Conjunctive Queries	2014	VLDB
4	982	Parallel Evaluation of Conjunctive Queries	2011	PODS
5	6,452	Scalable Querying of Nested Data	2021	VLDB
6	4,842	Continuous Cloud-Scale Query Optimization and Processing	2013	VLDB
7	6,239	Scalable Query Rewriting: A Graph-Based Approach	2011	SIGMOD
8	940	A Scalable Algorithm for Answering Queries Using Views	2000	VLDB
9	6,964	Querying Big Data by Accessing Small Data	2015	PODS
10	4,338	Generalized Scale Independence Through Incremental Precomputation	2013	SIGMOD