On the Expected Size of Recursive Datalog Queries

Summary: Asymptotically exact formulas for expected fixpoint sizes of two Datalog recursions (same-generation, canonical factorable) and of their Magic Sets/Factoring rewrites under selection queries. Finds recursive relations near worst-case even on sparse bases; Magic Sets yields sizes within a small constant of no-rewrite, while Factoring (when applicable) yields much smaller relations—analytic formulas closely match experiments. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: hcd554ed3f76e6a4b
Venue: PODS
Year: 1991
Pagerank: 5.6020796e-05
Overall Rank: 7,088 | 52.35%
DOI: 10.1145/113413.113438

Incoming Non-self Citations Over Time

Authors

1. S. Seshadri (University of Wisconsin)
2. Jeffrey F. Naughton (University of Wisconsin)

BibTeX Citation

@inproceedings{seshadri_pods91,
        address = {New York, NY, USA},
        series = {{PODS} '91},
        title = {{On the Expected Size of Recursive Datalog Queries}},
        url = {https://dl.acm.org/doi/10.1145/113413.113438},
        doi = {10.1145/113413.113438},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Seshadri, S. and Naughton, Jeffrey F.},
        year = {1991}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
6,684	Queries are easier than you thought (probably)	1992	PODS	5.7086289e-05
11,126	Dynamic Pruning for Recursive Joins	2025	SIGMOD	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 6 of 6 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
18	MAGIC SETS AND OTHER STRANGE WAYS TO IMPLEMENT LOGIC PROGRAMS (Extended Abstract)	1986	PODS	0.00059023577
352	On the Power of Magic	1987	PODS	0.00020223279
1,682	Bounds on the Propagation of Selection into Logic Programs	1987	PODS	9.8850863e-05
4,425	Magic Counting Methods	1987	SIGMOD	6.6039832e-05
5,419	Worst-case Complexity Analysis of Methods for Logic Query Implementation	1987	PODS	6.137651e-05
9,689	Counting Methods for Cyclic Relations	1988	PODS	5.1406988e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,416	Estimating the Size of Generalized Transitive Closures	1989	VLDB
2	440	On the Implementation of a Simple Class of Logic Queries for Databases	1986	PODS
3	6,131	More Efficient Datalog Queries: Subsumptive Tabling Beats Magic Sets	2011	SIGMOD
4	4,425	Magic Counting Methods	1987	SIGMOD
5	421	On the Complexity of Database Queries (Extended Abstract)	1997	PODS
6	10,365	Size Bound-Adorned Datalog	2026	PODS
7	13,389	Structural Query Optimization — A Uniform Framework For Semantic Query Optimization In Deductive Databases	1991	PODS
8	1,979	Efficient Evaluation of Right-, Left-, and Multi-Linear Rules	1989	SIGMOD
9	10,159	Magic Functions: A Technique to Optimize Extended Datalog Recursive Programs	1987	VLDB
10	6,741	Inherent Complexity of Recursive Queries (Extended Abstract)	1999	PODS