Database Paper Browser

Back to papers

On the Complexity of Database Queries (Extended Abstract)

Summary: Parameterizing by query size/#vars, classify relational calculus and fragments (conjunctive, positive) into the W-hierarchy, showing query size is inherently in the exponent of data complexity, increasingly so for more expressive languages. For recursive languages (fixpoint, Datalog) this exponential dependence is provable; acyclic queries with counting (#) avoid the blow-up, while adding order/inequalities does not. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID
1098
Venue
PODS
Year
1997
Pagerank
0.00023349408
Overall Rank
432 | 97.00%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 23 of 23 citing papers.

Rank Citing Paper Year Venue Pagerank
1,039 Weighted Hypertree Decompositions and Optimal Query Plans 2004 PODS 0.00014488271
1,040 Querying Graph Databases 2013 PODS 0.00014483577
1,556 Beyond Worst-case Analysis for Joins with Minesweeper 2014 PODS 0.00011383141
2,298 Joins via Geometric Resolutions: Worst-case and Beyond 2015 PODS 9.0746479e-05
2,804 Hypertree Decompositions and Tractable Queries 1999 PODS 8.1039107e-05
2,835 Computing Cores for Data Exchange: New Algorithms and Practical Solutions 2005 PODS 8.0468415e-05
2,981 Matching Twigs in Probabilistic XML 2007 VLDB 7.7783189e-05
3,005 Counting Answers to Existential Positive Queries: A Complexity Classification 2016 PODS 7.7315492e-05
4,636 Reverse Engineering SPJ-Queries from Examples 2017 PODS 6.0270157e-05
5,963 Beyond Equi-joins: Ranking, Enumeration and Factorization 2021 VLDB 5.2485815e-05
6,175 Enumeration of First-Order Queries on Classes of Structures With Bounded Expansion 2013 PODS 5.1667995e-05
6,238 The Parameterized Complexity of Database Queries 2001 PODS 5.1369162e-05
6,795 Complexity of Nonrecursive Logic Programs with Complex Values 1998 PODS 4.9197522e-05
6,945 Semantic Acyclicity on Graph Databases 2013 PODS 4.8874695e-05
7,161 Computing the Difference of Conjunctive Queries Efficiently 2023 SIGMOD 4.8086254e-05
8,650 Fine-Grained Complexity Analysis of Queries: From Decision to Counting and Enumeration 2020 PODS 4.4710131e-05
8,994 Approximately Counting Answers to Conjunctive Queries with Disequalities and Negations 2022 PODS 4.4094348e-05
11,211 Enriching Recommendation Models with Logic Conditions 2023 SIGMOD 4.1905499e-05
11,560 The Limits of Efficiency for Open- and Closed-World Query Evaluation Under Guarded TGDs 2020 PODS 4.1905499e-05
11,642 Testability of Homomorphism Inadmissibility: Property Testing Meets Database Theory 2019 PODS 4.1905499e-05
11,837 Semantic Acyclicity Under Constraints 2016 PODS 4.1905499e-05
12,039 The Fine Classification of Conjunctive Queries and Parameterized Logarithmic Space Complexity 2013 PODS 4.1905499e-05
12,221 Transducing Markov Sequences 2010 PODS 4.1905499e-05
Previous Page 1 / 1 Next

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
603 On the Complexity of Bounded-Variable Queries 1995 PODS 0.00019334592
618 Constraint Programming and Database Languages: A Tutorial 1995 PODS 0.00018990567
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
12,039 The Fine Classification of Conjunctive Queries and Parameterized Logarithmic Space Complexity 2013 PODS 4.1905499e-05
5,516 Expressive power and data complexity of nonrecursive query languages for lists and trees (Extended Abstract) 2000 PODS 5.4685963e-05
3,195 On Accessing Object-Oriented Databases: Expressive Power, Complexity, and Restrictions 1989 SIGMOD 7.4052272e-05
572 The Complexity of Query Reliability 1998 PODS 0.00019888988
3,043 Tractable Query Languages for Complex Object Databases 1991 PODS 7.6632326e-05
6,238 The Parameterized Complexity of Database Queries 2001 PODS 5.1369162e-05
6,234 Inherent Complexity of Recursive Queries (Extended Abstract) 1999 PODS 5.1387584e-05
2,808 On the Expressive Power of Database Queries with Intermediate Types 1988 PODS 8.0939851e-05
912 The Complexity of Evaluating Relational Queries 1983 PODS 0.00015374685
603 On the Complexity of Bounded-Variable Queries 1995 PODS 0.00019334592