On Tree-Based Techniques for Query Evaluation

Summary: Uses tree-structured intermediate results for query evaluation; gives a new algorithm for computing transitive closure from specified source nodes that outperforms prior methods and applies to many nonrecursive queries. Shows tree-based Warshall achieves an O(n·e) bound versus worse flat-representation costs. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 981
Venue: PODS
Year: 1992
Pagerank: 5.5028526e-05
Overall Rank: 8,035 | 44.88%
DOI: 10.1145/137097.137914

Incoming Non-self Citations Over Time

Authors

1. Hkan Jakobsson (Stanford University)

BibTeX Citation

@inproceedings{jakobsson_pods92,
        address = {New York, NY, USA},
        series = {{PODS} '92},
        title = {{On Tree-Based Techniques for Query Evaluation}},
        url = {https://dl.acm.org/doi/10.1145/137097.137914},
        doi = {10.1145/137097.137914},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Jakobsson, Hkan},
        year = {1992}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,491	A Performance Study Of Transitive Closure Algorithms	1994	SIGMOD	7.3658999e-05

Outgoing Citations (Sorted by Pagerank)

Showing 10 of 10 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
1,114	Direct Algorithms for Computing the Transitive Closure of Database Relations	1987	VLDB	0.00012118382
1,330	Efficient Transitive Closure Algorithms	1988	VLDB	0.00011140171
1,855	The Input/Output Complexity Of Transitive Closure	1990	SIGMOD	9.606146e-05
1,921	Efficient Evaluation of Right-, Left-, and Multi-Linear Rules	1989	SIGMOD	9.4809066e-05
2,033	One-Sided Recursions	1987	PODS	9.2819369e-05
2,076	A Study of Transitive Closure As a Recursion Mechanism	1987	SIGMOD	9.212586e-05
2,957	Graph-Theoretic Methods In Database Theory	1990	PODS	7.9200375e-05
3,603	Overbound and Right-Linear Queries	1991	PODS	7.2683975e-05
3,767	Right-, left- and multi-linear rule transformations that maintain context information	1990	VLDB	7.1421254e-05
5,975	Mixed-Approach Algorithms for Transitive Closure	1991	PODS	6.0220239e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,491	A Performance Study Of Transitive Closure Algorithms	1994	SIGMOD
2	9,173	Optimizing Recursive Queries in SQL	2005	SIGMOD
3	7,438	A Generalized Transitive Closure for Relational Queries	1988	PODS
4	1,114	Direct Algorithms for Computing the Transitive Closure of Database Relations	1987	VLDB
5	4,107	Processing Queries on Tree-Structured Data Efficiently	2006	PODS
6	7,029	Tree-Width and Functional Dependencies in Databases	2008	PODS
7	4,425	EFFICIENT EVALUATION FOR A SUBSET OF RECURSIVE QUERIES (Extended Abstract)	1987	PODS
8	1,259	On the Computation of the Transitive Closure of Relational Operators	1986	VLDB
9	1,330	Efficient Transitive Closure Algorithms	1988	VLDB
10	5,975	Mixed-Approach Algorithms for Transitive Closure	1991	PODS