The Tree Property Is Fundamental For Query Processing (Extended Abstract)

Summary: Partition schemas into tree vs cyclic; prove that computing full-join projections using join/project/semijoin is equivalent to constructing an embedded tree schema (a tree projection). Use tree projections to characterize solvability and bound the number of joins required. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 607
Venue: PODS
Year: 1982
Pagerank: 9.1638984e-05
Overall Rank: 2,102 | 85.58%
DOI: 10.1145/588111.588119

Incoming Non-self Citations Over Time

Authors

1. N. Goodman (Harvard University)
2. O. Shmueli (Harvard University)

BibTeX Citation

@inproceedings{goodman_pods82,
        address = {New York, NY, USA},
        series = {{PODS} '82},
        title = {{THE TREE PROPERTY IS FUNDAMENTAL FOR QUERY PROCESSING (EXTENDED ABSTRACT)}},
        url = {https://dl.acm.org/doi/10.1145/588111.588119},
        doi = {10.1145/588111.588119},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Goodman, N. and Shmueli, O.},
        year = {1982}
}

Incoming Citations (Sorted by Pagerank)

Showing 8 of 8 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
373	Maintenance Of Views	1984	SIGMOD	0.00019797816
1,651	On the Design of a Query Processing Strategy in a Distributed Database Environment	1983	SIGMOD	0.00010110141
2,957	Graph-Theoretic Methods In Database Theory	1990	PODS	7.9200375e-05
3,504	Elimination of Intersection Anomalies from Database Schemes (Extended Abstract)	1983	PODS	7.3590322e-05
5,311	Query Processing Utilizing Dependencies And Horizontal Decomposition	1983	SIGMOD	6.2700856e-05
5,526	Gyo Reductions, Canonical Connections, Tree And Cyclic Schemas And Tree Projections	1983	PODS	6.1864862e-05
5,561	On the Recognition and Design of Acyclic Databases	1984	PODS	6.1741042e-05
8,395	On the Cyclic to Acyclic Scheme Transformation and Solving Cyclic Queries (Extended Abstract)	1984	PODS	5.4347277e-05

Outgoing Citations (Sorted by Pagerank)

Showing 1 of 1 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
40	Testing Implications Of Data Dependencies	1979	SIGMOD	0.00046918506

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,052	Query Graphs, Implementing Trees, and Freely-Reorderable Outerjoins	1990	SIGMOD
2	7,759	The Power of Tree Projections: Local Consistency, Greedy Algorithms, and Larger Islands of Tractability	2010	PODS
3	13,145	Decomposition of Relational Schemata into Components Defined by Both Projection and Restriction	1988	PODS
4	10,044	The (Almost) Complete Guide to Tree Pattern Containment	2015	PODS
5	5,069	Query Processing For Distributed Databases Using Generalized Semi-Joins	1982	SIGMOD
6	1,510	A Methodology For Interpreting Tree Queries Into Optimal Semi-Join Expressions	1980	SIGMOD
7	5,311	Query Processing Utilizing Dependencies And Horizontal Decomposition	1983	SIGMOD
8	5,140	Transforming Cyclic Schemas Into Trees (Extended Abstract)	1982	PODS
9	5,526	Gyo Reductions, Canonical Connections, Tree And Cyclic Schemas And Tree Projections	1983	PODS
10	8,301	The Equivalence of Solving Queries and Producing Tree Projections (Extended Abstract)	1986	PODS