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: 1054
Venue: PODS
Year: 1995
Pagerank: 0.00014230134
Overall Rank: 763 | 94.77%
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
382	Conjunctive-Query Containment and Constraint Satisfaction	1998	PODS	0.00019546431
414	On the Complexity of Database Queries (Extended Abstract)	1997	PODS	0.00018893507
747	Querying Graph Databases	2013	PODS	0.00014400452
788	Composing Mappings Among Data Sources	2003	VLDB	0.00014031294
2,544	Advanced Processing for Ontological Queries	2010	VLDB	8.4444438e-05
4,336	Languages for Relational Databases over Interpreted Structures	1997	PODS	6.7554436e-05
5,453	Querying in the Age of Graph Databases and Knowledge Graphs	2021	SIGMOD	6.2137771e-05
6,278	Constraint Satisfaction and Database Theory: a Tutorial	2000	PODS	5.9287393e-05
6,661	Complexity of Nonrecursive Logic Programs with Complex Values	1998	PODS	5.8101181e-05
7,410	TriAL for RDF: Adapting Graph Query Languages for RDF Data	2013	PODS	5.6242786e-05
7,706	Conjunctive Queries on Probabilistic Graphs: Combined Complexity	2017	PODS	5.5638493e-05
8,071	An Incremental Algorithm for Computing Ranked Full Disjunctions	2005	PODS	5.4935818e-05
8,100	The Complexity of Why-Provenance for Datalog Queries	2024	PODS	5.4872887e-05
8,550	Conditional XPath, the first order complete XPath dialect*	2004	PODS	5.4119882e-05
9,009	Efficient Approximations of Conjunctive Queries	2012	PODS	5.3335287e-05
9,178	Verification of Relational Transducers for Electronic Commerce	2000	PODS	5.3077309e-05
11,838	Compiling Existential-Positive Queries to Bounded-Variable Fragments	2019	PODS	5.093636e-05
12,029	Bounded Query Rewriting Using Views	2016	PODS	5.093636e-05
12,487	The Finite Model Theory Toolbox of a Database Theoretician	2009	PODS	5.093636e-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,467	The Complexity of Evaluating Relational Queries	1983	PODS	0.00010687075
2,110	Theory of Database Queries (Extended Abstract)	1988	PODS	9.1532803e-05

Semantically Similar Papers

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