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)

Paper ID: 951
Venue: PODS
Year: 1992
Pagerank: 5.8396421e-05
Overall Rank: 6,558 | 55.01%
DOI: 10.1145/137097.137105

Incoming Non-self Citations Over Time

Authors

1. Serge Abiteboul (INRIA)
2. Kevin Compton (INRIA; University of Michigan)
3. Victor Vianu (INRIA; University of California San Diego)

BibTeX Citation

@inproceedings{abiteboul_pods92,
        address = {New York, NY, USA},
        series = {{PODS} '92},
        title = {{Queries are easier than you thought (probably)}},
        url = {https://dl.acm.org/doi/10.1145/137097.137105},
        doi = {10.1145/137097.137105},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Abiteboul, Serge and Compton, Kevin and Vianu, Victor},
        year = {1992}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
9,009	Efficient Approximations of Conjunctive Queries	2012	PODS	5.3335287e-05
9,676	Analysis and Application of Adaptive Sampling	2000	PODS	5.2377579e-05

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
989	Why Not Negation By Fixpoint?	1988	PODS	0.00012804792
1,297	The Alternating Fixpoint of Logic Programs with Negation (Extended Abstract)	1989	PODS	0.0001126031
6,948	On the Expected Size of Recursive Datalog Queries	1991	PODS	5.7306589e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,613	Inherent Complexity of Recursive Queries (Extended Abstract)	1999	PODS
2	4,634	Translation and Optimization of Logic Queries: The Algebraic Approach	1986	VLDB
3	13,040	Investigation of Algebraic Query Optimisation for Database Programming Languages	1994	VLDB
4	4,393	Bounded Conjunctive Queries	2014	VLDB
5	1,073	A General Framework for the Optimization of Object-Oriented Queries	1992	SIGMOD
6	3,590	On Probabilistic Fixpoint and Markov Chain Query Languages	2010	PODS
7	763	On the Complexity of Bounded-Variable Queries	1995	PODS
8	7,886	Polynomial-time program transformations in deductive databases	1990	PODS
9	8,673	Fine-Grained Complexity Analysis of Queries: From Decision to Counting and Enumeration	2020	PODS
10	414	On the Complexity of Database Queries (Extended Abstract)	1997	PODS