The Tree Property is Fundamental for Query Processing.
Nathan Goodman, Oded Shmueli:
The Tree Property is Fundamental for Query Processing.
PODS 1982: 40-48@inproceedings{DBLP:conf/pods/GoodmanS82,
author = {Nathan Goodman and
Oded Shmueli},
title = {The Tree Property is Fundamental for Query Processing},
booktitle = {Proceedings of the ACM Symposium on Principles of Database Systems,
March 29-31, 1982, Los Angeles, California},
publisher = {ACM},
year = {1982},
pages = {40-48},
ee = {http://doi.acm.org/10.1145/588111.588119, db/conf/pods/GoodmanS82.html},
crossref = {DBLP:conf/pods/82},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX
Abstract
One can partition the class of relational database
schemas into tree schemas and cyclic schemas.
In this paper we examine query processing implications
of the partitioning; other areas impacted
include dependency theory, schema design and graph theory.
We consider a class of queries that compute
the join of all relations in the database projected
onto a prescribed set of attributes. We show that
solving such queries (using the join, project
and semijoin operators) is tantamount to creating
an "embedded" tree schema which we call a tree projection.
This lends further credibility to the
pivotal nature of the tree/cyclic partitioning.
Using the tree projection concept we analyze
the problem of determining how many joins are needed to solve a query.
Copyright © 1982 by the ACM,
Inc., used by permission. Permission to make
digital or hard copies is granted provided that
copies are not made or distributed for profit or
direct commercial advantage, and that copies show
this notice on the first page or initial screen of
a display along with the full citation.
Load The ACM SIGMOD Anthology, CDROM Edition, Volume 1-3, PODS '82-'98.
and ...
Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings.
and ...
BibTeX
Printed Edition
Proceedings of the ACM Symposium on Principles of Database Systems, March 29-31, 1982, Los Angeles, California.
ACM 1982
Contents BibTeX
References
- [ASU 79]
- Alfred V. Aho, Yehoshua Sagiv, Jeffrey D. Ullman:
Equivalences Among Relational Expressions.
SIAM J. Comput. 8(2): 218-246(1979) BibTeX
- [BC 81]
- Philip A. Bernstein, Dah-Ming W. Chiu:
Using Semi-Joins to Solve Relational Queries.
J. ACM 28(1): 25-40(1981) BibTeX
- [BFMMUY 81]
- Catriel Beeri, Ronald Fagin, David Maier, Alberto O. Mendelzon, Jeffrey D. Ullman, Mihalis Yannakakis:
Properties of Acyclic Database Schemes.
STOC 1981: 355-362 BibTeX
- [BG 81]
- Philip A. Bernstein, Nathan Goodman:
Power of Natural Semijoins.
SIAM J. Comput. 10(4): 751-771(1981) BibTeX
- [FMU 80]
- Ronald Fagin, Alberto O. Mendelzon, Jeffrey D. Ullman:
A Simplified Universal Relation Assumption and Its Properties.
ACM Trans. Database Syst. 7(3): 343-360(1982) BibTeX
- [Graham 79]
- ...
- [GJ 79]
- ...
- [GS1 80]
- ...
- [GS2 81]
- Nathan Goodman, Oded Shmueli:
Syntactic Characterization of Tree Database Schemas.
J. ACM 30(4): 767-786(1983) BibTeX
- [HSW 75]
- ...
- [Hull 81]
- ...
- [MMS 79]
- David Maier, Alberto O. Mendelzon, Yehoshua Sagiv:
Testing Implications of Data Dependencies.
ACM Trans. Database Syst. 4(4): 455-469(1979) BibTeX
- [MU2 81]
- David Maier, Jeffrey D. Ullman:
Connections in Acyclic Hypergraphs.
Theor. Comput. Sci. 32: 185-199(1984) BibTeX
- [Shmueli 81]
- ...
- [YO 79]
- ...
Referenced by
- Chihping Wang, Ming-Syan Chen:
On the Complexity of Distributed Query Optimization.
IEEE Trans. Knowl. Data Eng. 8(4): 650-662(1996)
- Ming-Syan Chen, Philip S. Yu:
A Graph Theoretical Approach to Determine a Join Reducer Sequence in Distributed Query Processing.
IEEE Trans. Knowl. Data Eng. 6(1): 152-165(1994)
- Ming-Syan Chen, Philip S. Yu:
Combining Join and Semi-Join Operations for Distributed Query Processing.
IEEE Trans. Knowl. Data Eng. 5(3): 534-542(1993)
- Ming-Syan Chen, Philip S. Yu:
Determining Beneficial Semijoins for a Join Sequence in Distributed Query Processing.
ICDE 1991: 50-58
- Mihalis Yannakakis:
Graph-Theoretic Methods in Database Theory.
PODS 1990: 230-242
- Hyunchul Kang, Nick Roussopoulos:
Using 2-way Semijoins in Distributed Query Processing.
ICDE 1987: 644-651
- Clement T. Yu, C. C. Chang:
Distributed Query Processing.
ACM Comput. Surv. 16(4): 399-433(1984)
- Oded Shmueli, Alon Itai:
Maintenance of Views.
SIGMOD Conference 1984: 240-255
- Z. Meral Özsoyoglu, Elarbi Choukhmane:
On the Cyclic to Acyclic Scheme Transformation and Solving Cyclic Queries.
PODS 1984: 133-142
- Alessandro D'Atri, Marina Moscarini:
On the Recognition and Design of Acyclic Databases.
PODS 1984: 1-8
- Clement T. Yu, C. C. Chang:
On the Design of a Query Processing Strategy in a Distributed Database Environment.
SIGMOD Conference 1983: 30-39
- Yahiko Kambayashi, Masatoshi Yoshikawa:
Query Processing Utilizing Dependencies and Horizontal Decomposition.
SIGMOD Conference 1983: 55-67
- Nathan Goodman, Oded Shmueli, Y. C. Tay:
GYO Reductions, Canonical Connections, Tree and Cyclic Schemas and Tree Projections.
PODS 1983: 267-278
- Catriel Beeri, Michael Kifer:
Elimination of Intersection Anomalies from Database Schemes.
PODS 1983: 340-351
BibTeX
ACM SIGMOD Anthology - DBLP:
[Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:33:38 2009