On the Complexity of Bounded-Variable Queries

Summary: Studies evaluation complexity of relational queries restricted to a bounded number of variables so all intermediate results are polynomial-size. Shows expression/combined vs. data complexity gap narrows or disappears for such queries, motivating variable-minimization as a query-optimization strategy. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: h578a7b64713073c8
Venue: PODS
Year: 1995
Pagerank: 0.00013941847
Overall Rank: 794 | 94.67%
DOI: 10.1145/212433.212474

Incoming Non-self Citations Over Time

Authors

1. Moshe Y. Vardi (IBM; Rice University)

BibTeX Citation

@inproceedings{vardi_pods95,
        address = {New York, NY, USA},
        series = {{PODS} '95},
        title = {{On the Complexity of Bounded-Variable Queries}},
        url = {https://dl.acm.org/doi/10.1145/212433.212474},
        doi = {10.1145/212433.212474},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Vardi, Moshe Y.},
        year = {1995}
}

Incoming Citations (Sorted by Pagerank)

Showing 19 of 19 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
390	Conjunctive-Query Containment and Constraint Satisfaction	1998	PODS	0.00019248147
421	On the Complexity of Database Queries (Extended Abstract)	1997	PODS	0.00018516535
719	Querying Graph Databases	2013	PODS	0.00014529156
813	Composing Mappings Among Data Sources	2003	VLDB	0.00013722762
2,584	Advanced Processing for Ontological Queries	2010	VLDB	8.2585389e-05
4,426	Languages for Relational Databases over Interpreted Structures	1997	PODS	6.6038751e-05
5,174	Querying in the Age of Graph Databases and Knowledge Graphs	2021	SIGMOD	6.243251e-05
6,404	Constraint Satisfaction and Database Theory: a Tutorial	2000	PODS	5.796156e-05
6,798	Complexity of Nonrecursive Logic Programs with Complex Values	1998	PODS	5.6797989e-05
7,551	TriAL for RDF: Adapting Graph Query Languages for RDF Data	2013	PODS	5.4980866e-05
7,858	Conjunctive Queries on Probabilistic Graphs: Combined Complexity	2017	PODS	5.4392859e-05
8,234	An Incremental Algorithm for Computing Ranked Full Disjunctions	2005	PODS	5.3711847e-05
8,275	The Complexity of Why-Provenance for Datalog Queries	2024	PODS	5.3641687e-05
8,717	Conditional XPath, the first order complete XPath dialect*	2004	PODS	5.2905577e-05
9,169	Efficient Approximations of Conjunctive Queries	2012	PODS	5.2141412e-05
9,353	Verification of Relational Transducers for Electronic Commerce	2000	PODS	5.1886678e-05
12,139	Compiling Existential-Positive Queries to Bounded-Variable Fragments	2019	PODS	4.9793485e-05
12,324	Bounded Query Rewriting Using Views	2016	PODS	4.9793485e-05
12,778	The Finite Model Theory Toolbox of a Database Theoretician	2009	PODS	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 2 of 2 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
1,503	The Complexity of Evaluating Relational Queries	1983	PODS	0.00010455233
2,150	Theory of Database Queries (Extended Abstract)	1988	PODS	8.953998e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	143	Optimization of Nonrecursive Queries	1986	VLDB
2	13,345	Interpreting a Reconstructed Relational Calculus: Extended Abstract	1993	SIGMOD
3	9,169	Efficient Approximations of Conjunctive Queries	2012	PODS
4	10,182	Efficient Algorithms for Cardinality Estimation and Conjunctive Query Evaluation With Simple Degree Constraints	2025	PODS
5	7,597	On the Calculation of Optimality Ranges for Relational Query Execution Plans	2018	SIGMOD
6	4,452	Bounded Conjunctive Queries	2014	VLDB
7	9,152	An Effective Syntax for Bounded Relational Queries	2016	SIGMOD
8	102	Efficient Optimization of a Class of Relational Expressions	1978	SIGMOD
9	1,503	The Complexity of Evaluating Relational Queries	1983	PODS
10	421	On the Complexity of Database Queries (Extended Abstract)	1997	PODS