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.00023370207
Overall Rank
431 | 97.01%
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,037 Querying Graph Databases 2013 PODS 0.00014502493
1,038 Weighted Hypertree Decompositions and Optimal Query Plans 2004 PODS 0.00014492414
1,557 Beyond Worst-case Analysis for Joins with Minesweeper 2014 PODS 0.00011392493
2,296 Joins via Geometric Resolutions: Worst-case and Beyond 2015 PODS 9.0776226e-05
2,796 Hypertree Decompositions and Tractable Queries 1999 PODS 8.1112658e-05
2,829 Computing Cores for Data Exchange: New Algorithms and Practical Solutions 2005 PODS 8.0546963e-05
2,978 Matching Twigs in Probabilistic XML 2007 VLDB 7.7845728e-05
3,003 Counting Answers to Existential Positive Queries: A Complexity Classification 2016 PODS 7.7388586e-05
4,636 Reverse Engineering SPJ-Queries from Examples 2017 PODS 6.0303761e-05
5,962 Beyond Equi-joins: Ranking, Enumeration and Factorization 2021 VLDB 5.2536266e-05
6,167 Enumeration of First-Order Queries on Classes of Structures With Bounded Expansion 2013 PODS 5.1717635e-05
6,239 The Parameterized Complexity of Database Queries 2001 PODS 5.1417208e-05
6,794 Complexity of Nonrecursive Logic Programs with Complex Values 1998 PODS 4.9244886e-05
6,948 Semantic Acyclicity on Graph Databases 2013 PODS 4.8898337e-05
7,162 Computing the Difference of Conjunctive Queries Efficiently 2023 SIGMOD 4.8132423e-05
8,652 Fine-Grained Complexity Analysis of Queries: From Decision to Counting and Enumeration 2020 PODS 4.4753042e-05
8,992 Approximately Counting Answers to Conjunctive Queries with Disequalities and Negations 2022 PODS 4.413099e-05
11,209 Enriching Recommendation Models with Logic Conditions 2023 SIGMOD 4.1945683e-05
11,556 The Limits of Efficiency for Open- and Closed-World Query Evaluation Under Guarded TGDs 2020 PODS 4.1945683e-05
11,638 Testability of Homomorphism Inadmissibility: Property Testing Meets Database Theory 2019 PODS 4.1945683e-05
11,829 Semantic Acyclicity Under Constraints 2016 PODS 4.1945683e-05
12,031 The Fine Classification of Conjunctive Queries and Parameterized Logarithmic Space Complexity 2013 PODS 4.1945683e-05
12,213 Transducing Markov Sequences 2010 PODS 4.1945683e-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
602 On the Complexity of Bounded-Variable Queries 1995 PODS 0.00019352415
620 Constraint Programming and Database Languages: A Tutorial 1995 PODS 0.00019005954
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
12,031 The Fine Classification of Conjunctive Queries and Parameterized Logarithmic Space Complexity 2013 PODS 4.1945683e-05
3,189 On Accessing Object-Oriented Databases: Expressive Power, Complexity, and Restrictions 1989 SIGMOD 7.4116834e-05
5,503 Expressive power and data complexity of nonrecursive query languages for lists and trees (Extended Abstract) 2000 PODS 5.4738619e-05
571 The Complexity of Query Reliability 1998 PODS 0.00019910719
3,040 Tractable Query Languages for Complex Object Databases 1991 PODS 7.6707607e-05
6,239 The Parameterized Complexity of Database Queries 2001 PODS 5.1417208e-05
6,236 Inherent Complexity of Recursive Queries (Extended Abstract) 1999 PODS 5.1436959e-05
2,800 On the Expressive Power of Database Queries with Intermediate Types 1988 PODS 8.1019352e-05
915 The Complexity of Evaluating Relational Queries 1983 PODS 0.0001538509
602 On the Complexity of Bounded-Variable Queries 1995 PODS 0.00019352415