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.00013890233
Overall Rank: 796 | 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
391	Conjunctive-Query Containment and Constraint Satisfaction	1998	PODS	0.0001918714
424	On the Complexity of Database Queries (Extended Abstract)	1997	PODS	0.00018448553
719	Querying Graph Databases	2013	PODS	0.00014493767
817	Composing Mappings Among Data Sources	2003	VLDB	0.00013671477
2,592	Advanced Processing for Ontological Queries	2010	VLDB	8.2282919e-05
4,448	Languages for Relational Databases over Interpreted Structures	1997	PODS	6.5789235e-05
5,196	Querying in the Age of Graph Databases and Knowledge Graphs	2021	SIGMOD	6.2198467e-05
6,417	Constraint Satisfaction and Database Theory: a Tutorial	2000	PODS	5.7743102e-05
6,820	Complexity of Nonrecursive Logic Programs with Complex Values	1998	PODS	5.6583428e-05
7,572	TriAL for RDF: Adapting Graph Query Languages for RDF Data	2013	PODS	5.4773124e-05
7,878	Conjunctive Queries on Probabilistic Graphs: Combined Complexity	2017	PODS	5.4187338e-05
8,259	An Incremental Algorithm for Computing Ranked Full Disjunctions	2005	PODS	5.351182e-05
8,296	The Complexity of Why-Provenance for Datalog Queries	2024	PODS	5.3439005e-05
8,745	Conditional XPath, the first order complete XPath dialect*	2004	PODS	5.2705676e-05
9,205	Efficient Approximations of Conjunctive Queries	2012	PODS	5.1945931e-05
9,387	Verification of Relational Transducers for Electronic Commerce	2000	PODS	5.1690656e-05
12,189	Compiling Existential-Positive Queries to Bounded-Variable Fragments	2019	PODS	4.9605343e-05
12,373	Bounded Query Rewriting Using Views	2016	PODS	4.9605343e-05
12,827	The Finite Model Theory Toolbox of a Database Theoretician	2009	PODS	4.9605343e-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,508	The Complexity of Evaluating Relational Queries	1983	PODS	0.00010416537
2,161	Theory of Database Queries (Extended Abstract)	1988	PODS	8.9203568e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	144	Optimization of Nonrecursive Queries	1986	VLDB
2	13,392	Interpreting a Reconstructed Relational Calculus: Extended Abstract	1993	SIGMOD
3	9,205	Efficient Approximations of Conjunctive Queries	2012	PODS
4	10,220	Efficient Algorithms for Cardinality Estimation and Conjunctive Query Evaluation With Simple Degree Constraints	2025	PODS
5	7,619	On the Calculation of Optimality Ranges for Relational Query Execution Plans	2018	SIGMOD
6	4,473	Bounded Conjunctive Queries	2014	VLDB
7	9,180	An Effective Syntax for Bounded Relational Queries	2016	SIGMOD
8	104	Efficient Optimization of a Class of Relational Expressions	1978	SIGMOD
9	1,508	The Complexity of Evaluating Relational Queries	1983	PODS
10	424	On the Complexity of Database Queries (Extended Abstract)	1997	PODS