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: hedc41ed998c4dbe0
Venue: PODS
Year: 1987
Pagerank: 6.5811933e-05
Overall Rank: 4,479 | 69.89%
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,597	Finding Regular Simple Paths in Graph Databases	1989	VLDB	0.0001012429
3,020	Graph-Theoretic Methods In Database Theory	1990	PODS	7.7448163e-05
9,689	Counting Methods for Cyclic Relations	1988	PODS	5.1406988e-05
13,280	Magic Factoring of Closure Programs (Extended Abstract)	1995	PODS	4.9793485e-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
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

Semantically Similar Papers

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