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.00019352415
Overall Rank: 602 | 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
407	Conjunctive-Query Containment and Constraint Satisfaction	1998	PODS	0.00024004562
431	On the Complexity of Database Queries (Extended Abstract)	1997	PODS	0.00023370207
879	Composing Mappings Among Data Sources	2003	VLDB	0.00015674595
1,037	Querying Graph Databases	2013	PODS	0.00014502493
2,755	Advanced Processing for Ontological Queries	2010	VLDB	8.1690695e-05
4,346	Languages for Relational Databases over Interpreted Structures	1997	PODS	6.2725564e-05
4,977	Constraint Satisfaction and Database Theory: a Tutorial	2000	PODS	5.7881576e-05
5,792	Querying in the Age of Graph Databases and Knowledge Graphs	2021	SIGMOD	5.325937e-05
6,794	Complexity of Nonrecursive Logic Programs with Complex Values	1998	PODS	4.9244886e-05
6,847	TriAL for RDF: Adapting Graph Query Languages for RDF Data	2013	PODS	4.9089877e-05
7,601	Conjunctive Queries on Probabilistic Graphs: Combined Complexity	2017	PODS	4.698961e-05
8,072	An Incremental Algorithm for Computing Ranked Full Disjunctions	2005	PODS	4.5922874e-05
8,125	The Complexity of Why-Provenance for Datalog Queries	2024	PODS	4.5797807e-05
8,314	Conditional XPath, the first order complete XPath dialect*	2004	PODS	4.5435639e-05
8,833	Verification of Relational Transducers for Electronic Commerce	2000	PODS	4.439447e-05
8,851	Efficient Approximations of Conjunctive Queries	2012	PODS	4.4363908e-05
11,644	Compiling Existential-Positive Queries to Bounded-Variable Fragments	2019	PODS	4.1945683e-05
11,826	Bounded Query Rewriting Using Views	2016	PODS	4.1945683e-05
12,292	The Finite Model Theory Toolbox of a Database Theoretician	2009	PODS	4.1945683e-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
915	The Complexity of Evaluating Relational Queries	1983	PODS	0.0001538509
1,448	Theory of Database Queries (Extended Abstract)	1988	PODS	0.00011938045

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
143	Optimization of Nonrecursive Queries	1986	VLDB	0.00041510555
12,861	Interpreting a Reconstructed Relational Calculus: Extended Abstract	1993	SIGMOD	4.1945683e-05
8,851	Efficient Approximations of Conjunctive Queries	2012	PODS	4.4363908e-05
9,843	Efficient Algorithms for Cardinality Estimation and Conjunctive Query Evaluation With Simple Degree Constraints	2025	PODS	4.2721228e-05
8,213	On the Calculation of Optimality Ranges for Relational Query Execution Plans	2018	SIGMOD	4.557937e-05
4,546	Bounded Conjunctive Queries	2014	VLDB	6.0987778e-05
8,961	An Effective Syntax for Bounded Relational Queries	2016	SIGMOD	4.4206115e-05
58	Efficient Optimization of a Class of Relational Expressions	1978	SIGMOD	0.00064826446
915	The Complexity of Evaluating Relational Queries	1983	PODS	0.0001538509
431	On the Complexity of Database Queries (Extended Abstract)	1997	PODS	0.00023370207