Handling Redundancy in the Processing of Recursive Database Queries

Summary: Redundancy in recursive query processing: four levels. Techniques: subexpr sharing, frontier-based counting, tuple merge/filter, and level-relaxed I/O, yielding substantial redundancy reductions. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 2394
Venue: SIGMOD
Year: 1987
Pagerank: 6.573022e-05
Overall Rank: 4,673 | 67.95%
DOI: 10.1145/38713.38727

Incoming Non-self Citations Over Time

Authors

1. Jiawei Han (Northwestern University)
2. Lawrence J. Henschen (Northwestern University)

BibTeX Citation

@inproceedings{han_sigmod87,
        title = {{Handling Redundancy in the Processing of Recursive Database Queries}},
        author = {Han, Jiawei and Henschen, Lawrence J.},
        series = {{SIGMOD} '87},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/38713.38727},
        url = {https://dl.acm.org/doi/10.1145/38713.38727},
        year = {1987}
}

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,629	Compiling Separable Recursions	1988	SIGMOD	7.2392728e-05
9,173	Optimizing Recursive Queries in SQL	2005	SIGMOD	5.3090815e-05
9,503	Counting Methods for Cyclic Relations	1988	PODS	5.2586367e-05
10,690	Dynamic Pruning for Recursive Joins	2025	SIGMOD	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 4 of 4 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
16	MAGIC SETS AND OTHER STRANGE WAYS TO IMPLEMENT LOGIC PROGRAMS (Extended Abstract)	1986	PODS	0.00060089598
63	An Amateur's Introduction to Recursive Query Processing Strategies	1986	SIGMOD	0.00038782376
217	Traversal Recursion: A Practical Approach to Supporting Recursive Applications	1986	SIGMOD	0.00024458594
313	OPTIMIZING DATALOG PROGRAMS (Extended Abstract)	1987	PODS	0.0002168869

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,136	Eliminating Costly Redundant Computations from SQL Trigger Executions	1997	SIGMOD
2	143	Optimization of Nonrecursive Queries	1986	VLDB
3	1,530	Multiple Query Processing in Deductive Databases using Query Graphs	1986	VLDB
4	2,054	Evaluation Of Database Recursive Logic Programs As Recurrent Function Series	1986	SIGMOD
5	13,100	Detecting Redundant Tuples During Query Evaluation	1991	PODS
6	129	Optimization of Nested SQL Queries Revisited	1987	SIGMOD
7	13,116	Semigroup techniques in recursive query optimization	1990	PODS
8	2,198	A Recursive Algebra and Query Optimization for Nested Relations	1989	SIGMOD
9	5,563	A Parallel Processing Strategy for Evaluating Recursive Queries	1986	VLDB
10	9,173	Optimizing Recursive Queries in SQL	2005	SIGMOD