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,883 | Efficient Approximations of Conjunctive Queries | 2012 | PODS | 5.4156287e-05 |
| 9,532 | Analysis and Application of Adaptive Sampling | 2000 | PODS | 5.318867e-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 |
|---|---|---|---|---|
| 966 | Why Not Negation By Fixpoint? | 1988 | PODS | 0.00012984689 |
| 1,283 | The Alternating Fixpoint of Logic Programs with Negation (Extended Abstract) | 1989 | PODS | 0.00011427621 |
| 6,827 | On the Expected Size of Recursive Datalog Queries | 1991 | PODS | 5.8194114e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 4,567 | Translation And Optimization Of Logic Queries: The Algebraic Approach | 1986 | VLDB | 6.6952073e-05 |
| 6,478 | Inherent Complexity of Recursive Queries (Extended Abstract) | 1999 | PODS | 5.9264069e-05 |
| 12,856 | Investigation of Algebraic Query Optimisation for Database Programming Languages | 1994 | VLDB | 5.1725247e-05 |
| 4,297 | Bounded Conjunctive Queries | 2014 | VLDB | 6.8454125e-05 |
| 1,057 | A General Framework for the Optimization of Object-Oriented Queries | 1992 | SIGMOD | 0.00012477821 |
| 774 | On the Complexity of Bounded-Variable Queries | 1995 | PODS | 0.00014160893 |
| 3,583 | On Probabilistic Fixpoint and Markov Chain Query Languages | 2010 | PODS | 7.3469638e-05 |
| 7,850 | Polynomial-time program transformations in deductive databases | 1990 | PODS | 5.6011137e-05 |
| 8,555 | Fine-Grained Complexity Analysis of Queries: From Decision to Counting and Enumeration | 2020 | PODS | 5.4726085e-05 |
| 527 | On the Complexity of Database Queries (Extended Abstract) | 1997 | PODS | 0.00017133432 |