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: 1055
Venue: PODS
Year: 1995
Pagerank: 0.00019334592
Overall Rank: 603 | 95.82%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Moshe Y. Vardi

Incoming Citations (Sorted by Pagerank)

Showing 19 of 19 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
401	Conjunctive-Query Containment and Constraint Satisfaction	1998	PODS	0.00024281448
432	On the Complexity of Database Queries (Extended Abstract)	1997	PODS	0.00023349408
877	Composing Mappings Among Data Sources	2003	VLDB	0.00015659754
1,040	Querying Graph Databases	2013	PODS	0.00014483577
2,763	Advanced Processing for Ontological Queries	2010	VLDB	8.1614123e-05
4,343	Languages for Relational Databases over Interpreted Structures	1997	PODS	6.2665123e-05
4,978	Constraint Satisfaction and Database Theory: a Tutorial	2000	PODS	5.7833452e-05
5,802	Querying in the Age of Graph Databases and Knowledge Graphs	2021	SIGMOD	5.3209544e-05
6,795	Complexity of Nonrecursive Logic Programs with Complex Values	1998	PODS	4.9197522e-05
6,846	TriAL for RDF: Adapting Graph Query Languages for RDF Data	2013	PODS	4.9042778e-05
7,604	Conjunctive Queries on Probabilistic Graphs: Combined Complexity	2017	PODS	4.6944524e-05
8,076	An Incremental Algorithm for Computing Ranked Full Disjunctions	2005	PODS	4.587923e-05
8,129	The Complexity of Why-Provenance for Datalog Queries	2024	PODS	4.5753896e-05
8,308	Conditional XPath, the first order complete XPath dialect*	2004	PODS	4.5392079e-05
8,833	Verification of Relational Transducers for Electronic Commerce	2000	PODS	4.4352158e-05
8,850	Efficient Approximations of Conjunctive Queries	2012	PODS	4.4324268e-05
11,648	Compiling Existential-Positive Queries to Bounded-Variable Fragments	2019	PODS	4.1905499e-05
11,834	Bounded Query Rewriting Using Views	2016	PODS	4.1905499e-05
12,300	The Finite Model Theory Toolbox of a Database Theoretician	2009	PODS	4.1905499e-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
912	The Complexity of Evaluating Relational Queries	1983	PODS	0.00015374685
1,450	Theory of Database Queries (Extended Abstract)	1988	PODS	0.00011926567

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
144	Optimization of Nonrecursive Queries	1986	VLDB	0.00041430126
12,871	Interpreting a Reconstructed Relational Calculus: Extended Abstract	1993	SIGMOD	4.1905499e-05
8,850	Efficient Approximations of Conjunctive Queries	2012	PODS	4.4324268e-05
9,843	Efficient Algorithms for Cardinality Estimation and Conjunctive Query Evaluation With Simple Degree Constraints	2025	PODS	4.2680295e-05
8,193	On the Calculation of Optimality Ranges for Relational Query Execution Plans	2018	SIGMOD	4.5575291e-05
4,545	Bounded Conjunctive Queries	2014	VLDB	6.0917464e-05
8,963	An Effective Syntax for Bounded Relational Queries	2016	SIGMOD	4.4165156e-05
58	Efficient Optimization of a Class of Relational Expressions	1978	SIGMOD	0.00064817807
912	The Complexity of Evaluating Relational Queries	1983	PODS	0.00015374685
432	On the Complexity of Database Queries (Extended Abstract)	1997	PODS	0.00023349408