EFFICIENT EVALUATION FOR A SUBSET OF RECURSIVE QUERIES (Extended Abstract)

Summary: Adapts graph-traversal results into a practical, efficient algorithm for evaluating regular and linear recursive queries over databases restricted to binary relations. Gives transformations that reduce a subset of regular/linear n-ary recursive queries to binary form. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 802
Venue: PODS
Year: 1987
Pagerank: 6.7101609e-05
Overall Rank: 4,425 | 69.65%
DOI: 10.1145/28659.28690

Incoming Non-self Citations Over Time

Authors

1. Gosta Grahne (University of Helsinki)
2. Seppo Sippu (University of Jyvaskyla)
3. Eljas Soisalon-Soininen (University of Helsinki; University of Karlsruhe)

BibTeX Citation

@inproceedings{grahne_pods87,
        address = {New York, NY, USA},
        series = {{PODS} '87},
        title = {{EFFICIENT EVALUATION FOR A SUBSET OF RECURSIVE QUERIES (Extended Abstract)}},
        url = {https://dl.acm.org/doi/10.1145/28659.28690},
        doi = {10.1145/28659.28690},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Grahne, Gosta and Sippu, Seppo and Soisalon-Soininen, Eljas},
        year = {1987}
}

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,658	Finding Regular Simple Paths in Graph Databases	1989	VLDB	0.00010092304
2,957	Graph-Theoretic Methods In Database Theory	1990	PODS	7.9200375e-05
9,503	Counting Methods for Cyclic Relations	1988	PODS	5.2586367e-05
12,990	Magic Factoring of Closure Programs (Extended Abstract)	1995	PODS	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 2 of 2 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

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,382	Estimating the Size of Generalized Transitive Closures	1989	VLDB
2	2,198	A Recursive Algebra and Query Optimization for Nested Relations	1989	SIGMOD
3	7,438	A Generalized Transitive Closure for Relational Queries	1988	PODS
4	143	Optimization of Nonrecursive Queries	1986	VLDB
5	8,035	On Tree-Based Techniques for Query Evaluation	1992	PODS
6	4,972	On the Optimization of Recursive Relational Queries: Application to Graph Queries	2020	SIGMOD
7	2,054	Evaluation Of Database Recursive Logic Programs As Recurrent Function Series	1986	SIGMOD
8	13,158	Classification Of Recursive Formulas In Deductive Databases	1988	SIGMOD
9	1,921	Efficient Evaluation of Right-, Left-, and Multi-Linear Rules	1989	SIGMOD
10	9,173	Optimizing Recursive Queries in SQL	2005	SIGMOD