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: hff4ddfecc3caa683
Venue: SIGMOD
Year: 1987
Pagerank: 6.4255719e-05
Overall Rank: 4,768 | 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,713	Compiling Separable Recursions	1988	SIGMOD	7.0770304e-05
9,347	Optimizing Recursive Queries in SQL	2005	SIGMOD	5.1900828e-05
9,689	Counting Methods for Cyclic Relations	1988	PODS	5.1406988e-05
11,126	Dynamic Pruning for Recursive Joins	2025	SIGMOD	4.9793485e-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
18	MAGIC SETS AND OTHER STRANGE WAYS TO IMPLEMENT LOGIC PROGRAMS (Extended Abstract)	1986	PODS	0.00059023577
67	An Amateur's Introduction to Recursive Query Processing Strategies	1986	SIGMOD	0.00038009523
225	Traversal Recursion: A Practical Approach to Supporting Recursive Applications	1986	SIGMOD	0.00023995155
317	OPTIMIZING DATALOG PROGRAMS (Extended Abstract)	1987	PODS	0.00021220438

Semantically Similar Papers

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