The Equivalence of Solving Queries and Producing Tree Projections (Extended Abstract)

Summary: Establishes that the ability to compute the join of all relations from extensions of a state over D is equivalent to the existence of a tree projection of D' onto D (holds for unrestricted DBs). If added schemas form a tree schema, equivalence holds for finite DBs and tree-projection existence is testable in polynomial time. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 758
Venue: PODS
Year: 1986
Pagerank: 4.613363e-05
Overall Rank: 7,984 | 44.46%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Yehoshua Sagiv
2. Oded Shmueli

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
12,890	Avoiding Cartesian Products in Programs for Multiple Joins (Extended Abstract)	1992	PODS	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 9 of 9 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
38	Testing Implications Of Data Dependencies	1979	SIGMOD	0.00075110004
144	Testing Containment of Conjunctive Queries Under Functional and Inclusion Dependencies (Extended Abstract)	1982	PODS	0.00041462501
3,361	Functional Dependencies on Cyclic Database Schemes	1983	SIGMOD	7.1735665e-05
4,848	Transforming Cyclic Schemas Into Trees (Extended Abstract)	1982	PODS	5.8774511e-05
5,036	Query Processing For Distributed Databases Using Generalized Semi-Joins	1982	SIGMOD	5.745922e-05
5,155	Gyo Reductions, Canonical Connections, Tree And Cyclic Schemas And Tree Projections	1983	PODS	5.660316e-05
5,162	Query Processing Utilizing Dependencies And Horizontal Decomposition	1983	SIGMOD	5.6554478e-05
6,603	Properties Of Database Schemata With Functional Dependencies	1984	PODS	4.9971153e-05
8,134	On the Cyclic to Acyclic Scheme Transformation and Solving Cyclic Queries (Extended Abstract)	1984	PODS	4.5783206e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
14,281	EFFICIENT PROCESSING OF RELATIONAL CALCULUS EXPRESSIONS USING RANGE QUERY THEORY (Extended Abstract)	1984	SIGMOD	-
5,697	Conjunctive Query Equivalence of Keyed Relational Schemas (Extended Abstract)	1997	PODS	5.3671336e-05
2,318	Efficient Query Answering in the Representative Instance Approach	1985	PODS	9.0400919e-05
6,949	Tree-Width and Functional Dependencies in Databases	2008	PODS	4.8898337e-05
6,168	Optimal Computation of Total Projections with Unions of Simple Chase Join Expressions	1984	SIGMOD	5.1716335e-05
1,870	Flexible Queries over Semistructured Data	2001	PODS	0.00010263799
5,962	Beyond Equi-joins: Ranking, Enumeration and Factorization	2021	VLDB	5.2536266e-05
7,473	The Power of Tree Projections: Local Consistency, Greedy Algorithms, and Larger Islands of Tractability	2010	PODS	4.7198203e-05
915	The Complexity of Evaluating Relational Queries	1983	PODS	0.0001538509
1,358	The Tree Property Is Fundamental For Query Processing (Extended Abstract)	1982	PODS	0.00012387987