Queries are easier than you thought (probably)
Summary: Leverages a recently proven normal form to optimize a broad class of queries (fixpoint, while, while+arithmetic). Probabilistic analysis shows these programs are “bounded almost everywhere” and typically have much better average complexity than pessimistic worst-case, with a practical exploitation method. (summarized by gpt-5-mini on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Serge Abiteboul
- 2. Kevin Compton
- 3. Victor Vianu
Incoming Citations (Sorted by Pagerank)
Showing 2 of 2 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 8,851 | Efficient Approximations of Conjunctive Queries | 2012 | PODS | 4.4363908e-05 |
| 9,523 | Analysis and Application of Adaptive Sampling | 2000 | PODS | 4.331052e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 3 of 3 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 551 | Why Not Negation By Fixpoint? | 1988 | PODS | 0.00020329959 |
| 1,205 | The Alternating Fixpoint of Logic Programs with Negation (Extended Abstract) | 1989 | PODS | 0.00013285448 |
| 6,365 | On the Expected Size of Recursive Datalog Queries | 1991 | PODS | 5.0945408e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 6,236 | Inherent Complexity of Recursive Queries (Extended Abstract) | 1999 | PODS | 5.1436959e-05 |
| 4,881 | Translation And Optimization Of Logic Queries: The Algebraic Approach | 1986 | VLDB | 5.8567721e-05 |
| 12,847 | Investigation of Algebraic Query Optimisation for Database Programming Languages | 1994 | VLDB | 4.1945683e-05 |
| 4,546 | Bounded Conjunctive Queries | 2014 | VLDB | 6.0987778e-05 |
| 1,199 | A General Framework for the Optimization of Object-Oriented Queries | 1992 | SIGMOD | 0.00013354204 |
| 3,251 | On Probabilistic Fixpoint and Markov Chain Query Languages | 2010 | PODS | 7.3215694e-05 |
| 602 | On the Complexity of Bounded-Variable Queries | 1995 | PODS | 0.00019352415 |
| 7,598 | Polynomial-time program transformations in deductive databases | 1990 | PODS | 4.7004867e-05 |
| 8,652 | Fine-Grained Complexity Analysis of Queries: From Decision to Counting and Enumeration | 2020 | PODS | 4.4753042e-05 |
| 431 | On the Complexity of Database Queries (Extended Abstract) | 1997 | PODS | 0.00023370207 |