Compiling Separable Recursions

Summary: Defines separable recursions and a selective evaluation algorithm that uses constants to prune irrelevant data. Compared with GM sets and Generalized Counting, it attains O(n) on simple cases and can outperform general evaluators by a factor proportional to database size; separable recursions extend linear recursions to non-chain rules and non-binary predicates. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h51cf03b8a3d910e8
Venue: SIGMOD
Year: 1988
Pagerank: 7.0736815e-05
Overall Rank: 3,715 | 75.04%
DOI: 10.1145/50202.50240

Incoming Non-self Citations Over Time

Authors

1. Jeffrey F. Naughton (Princeton University)

BibTeX Citation

@inproceedings{naughton_sigmod88,
        title = {{Compiling Separable Recursions}},
        author = {Naughton, Jeffrey F.},
        series = {{SIGMOD} '88},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/50202.50240},
        url = {https://dl.acm.org/doi/10.1145/50202.50240},
        year = {1988}
}

Incoming Citations (Sorted by Pagerank)

Showing 7 of 7 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,981	Efficient Evaluation of Right-, Left-, and Multi-Linear Rules	1989	SIGMOD	9.267247e-05
2,026	Proof-Tree Transformation Theorems and Their Applications	1989	PODS	9.1626332e-05
4,187	Argument Reduction by Factoring	1989	VLDB	6.7450426e-05
4,228	Commutativity and Its Role in the Processing of Linear Recursion	1989	VLDB	6.7134031e-05
7,702	Hard problems for simple logic programs	1990	SIGMOD	5.4729121e-05
8,059	Polynomial-time program transformations in deductive databases	1990	PODS	5.3961311e-05
13,420	Factoring Augmented Regular Chain Programs	1990	VLDB	4.9769913e-05

Outgoing Citations (Sorted by Pagerank)

Showing 5 of 5 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.00058997063
353	On the Power of Magic	1987	PODS	0.00020213935
1,682	Bounds on the Propagation of Selection into Logic Programs	1987	PODS	9.8804595e-05
2,067	One-Sided Recursions	1987	PODS	9.0898007e-05
4,770	Handling Redundancy in the Processing of Recursive Database Queries	1987	SIGMOD	6.4225302e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	9,695	Counting Methods for Cyclic Relations	1988	PODS
2	13,454	Classification Of Recursive Formulas In Deductive Databases	1988	SIGMOD
3	7,281	Magic-sets Transformation in Nonrecursive Systems	1992	PODS
4	13,412	Semigroup techniques in recursive query optimization	1990	PODS
5	6,875	Efficient Implementation of Loops in Bottom-Up Evaluation of Logic Queries	1990	VLDB
6	4,483	EFFICIENT EVALUATION FOR A SUBSET OF RECURSIVE QUERIES (Extended Abstract)	1987	PODS
7	18	MAGIC SETS AND OTHER STRANGE WAYS TO IMPLEMENT LOGIC PROGRAMS (Extended Abstract)	1986	PODS
8	440	On the Implementation of a Simple Class of Logic Queries for Databases	1986	PODS
9	2,100	Evaluation Of Database Recursive Logic Programs As Recurrent Function Series	1986	SIGMOD
10	1,981	Efficient Evaluation of Right-, Left-, and Multi-Linear Rules	1989	SIGMOD