Tree Queries: A Simple Class of Relational Queries.

@article{DBLP:journals/tods/GoodmanS82,
  author    = {Nathan Goodman and
               Oded Shmueli},
  title     = {Tree Queries: A Simple Class of Relational Queries},
  journal   = {ACM Trans. Database Syst.},
  volume    = {7},
  number    = {4},
  year      = {1982},
  pages     = {653-677},
  ee        = {http://doi.acm.org/10.1145/319758.319775, db/journals/tods/GoodmanS82.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

One can partition the class of relational database schemas into tree schemas and cyclic schemas. (These are called acyclic hypergraphs and cyclic hypergraphs elsewhere in the literature.) This partition has interesting implications in query processing, dependency theory, and graph theory.

The tree/cyclic partitioning of database schemas originated with a similar partition of equijoin queries. Given an arbitrary equijoin query one can obtain an equivalent query that calculates the natural join of all relations in (an efficiently) derived database; such a query is called a natural join (NJ) query. If the derived database is a tree schema the original query is said to be a tree query, and otherwise a cyclic query.

In this paper we analyze query processing consequences of the tree/cyclic partitioning. We are able to argue, qualitatively, that queries which imply a tree schema are easier to process than those implying a cyclic schema. Our results also extend the study of the semijoin operator.

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.

Joint ACM SIGMOD / IEEE Computer Society Anthology

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the CD and click on the path of your mount point:
  /Anthology/An3-1 or /cdrom

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD2 or /dvd

References

[1]

Edward Babb: Implementing a Relational Database by Means of Specialized Hardware. ACM Trans. Database Syst. 4(1): 1-29(1979) BibTeX

[2]

Catriel Beeri: On the Membership Problem for Functional and Multivalued Dependencies in Relational Databases. ACM Trans. Database Syst. 5(3): 241-259(1980) BibTeX

[3]

Catriel Beeri, Ronald Fagin, John H. Howard: A Complete Axiomatization for Functional and Multivalued Dependencies in Database Relations. SIGMOD Conference 1977: 47-61 BibTeX

[4]

Catriel Beeri, Ronald Fagin, David Maier, Alberto O. Mendelzon, Jeffrey D. Ullman, Mihalis Yannakakis: Properties of Acyclic Database Schemes. STOC 1981: 355-362 BibTeX

[5]

Catriel Beeri, Moshe Y. Vardi: On the Properties of Join Dependencies. Advances in Data Base Theory 1979: 25-71 BibTeX

[6]

Philip A. Bernstein, Dah-Ming W. Chiu: Using Semi-Joins to Solve Relational Queries. J. ACM 28(1): 25-40(1981) BibTeX

[7]

Philip A. Bernstein, Nathan Goodman: Power of Natural Semijoins. SIAM J. Comput. 10(4): 751-771(1981) BibTeX

[8]

Philip A. Bernstein, Nathan Goodman, Eugene Wong, Christopher L. Reeve, James B. Rothnie Jr.: Query Processing in a System for Distributed Databases (SDD-1). ACM Trans. Database Syst. 6(4): 602-625(1981) BibTeX

[9]

...

[10]

D. M. Chiu, Y. C. Ho: A Methodology for Interpreting Tree Queries Into Optimal Semi-Join Expressions. SIGMOD Conference 1980: 169-178 BibTeX

[11]

Claude Delobel: Normalization and Hierarchical Dependencies in the Relational Data Model. ACM Trans. Database Syst. 3(3): 201-222(1978) BibTeX

[12]

Robert S. Epstein, Michael Stonebraker, Eugene Wong: Distributed Query Processing in a Relational Data Base System. SIGMOD Conference 1978: 169-180 BibTeX

[13]

Ronald Fagin: Multivalued Dependencies and a New Normal Form for Relational Databases. ACM Trans. Database Syst. 2(3): 262-278(1977) BibTeX

[14]

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

[15]

...

[16]

Nathan Goodman, Oded Shmueli: Syntactic Characterization of Tree Database Schemas. J. ACM 30(4): 767-786(1983) BibTeX

[17]

Mohamed G. Gouda, Umeshwar Dayal: Optimal Semijoin Schedules For Query Processing in Local Distributed Database Systems. SIGMOD Conference 1981: 164-175 BibTeX

[18]

...

[19]

Alan R. Hevner, S. Bing Yao: Query Processing in Distributed Database Systems. IEEE Trans. Software Eng. 5(3): 177-187(1979) BibTeX

[20]

Richard Hull: Acyclic Join Dependency and Data Base Projections. J. Comput. Syst. Sci. 27(3): 331-349(1983) BibTeX

[21]

Larry Kerschberg, Peter D. Ting, S. Bing Yao: Query Optimization in Star Computer Networks. ACM Trans. Database Syst. 7(4): 678-711(1982) BibTeX

[22]

...

[23]

David Maier, Jeffrey D. Ullman: Maximal Objects and the Semantics of Universal Relation Databases. ACM Trans. Database Syst. 8(1): 1-14(1983) BibTeX

[24]

David Maier, Jeffrey D. Ullman: Connections in Acyclic Hypergraphs. PODS 1982: 34-39 BibTeX

[25]

Esen A. Ozkarahan, Stewart A. Schuster, Kenneth C. Sevcik: Performance Evaluation of a Relational Associative Processor. ACM Trans. Database Syst. 2(2): 175-195(1977) BibTeX

[26]

...

[27]

Patricia G. Selinger, Morton M. Astrahan, Donald D. Chamberlin, Raymond A. Lorie, Thomas G. Price: Access Path Selection in a Relational Database Management System. SIGMOD Conference 1979: 23-34 BibTeX

[28]

...

[29]

...

[30]

Stanley Y. W. Su, Ahmed Emam: CASDAL: CASSM'a DAta Language. ACM Trans. Database Syst. 3(1): 57-91(1978) BibTeX

[31]

Jeffrey D. Ullman: The U. R. Strikes Back. PODS 1982: 10-22 BibTeX

[32]

Eugene Wong: Retrieving Dispersed Data from SDD-1: A System for Distributed Databases. Berkeley Workshop 1977: 217-235 BibTeX

[33]

Eugene Wong, Karel Youssefi: Decomposition - A Strategy for Query Processing. ACM Trans. Database Syst. 1(3): 223-241(1976) BibTeX

[34]

...

[35]

...

Referenced by

1. Georg Gottlob, Nicola Leone, Francesco Scarcello: Hypertree Decompositions and Tractable Queries. PODS 1999: 21-32
2. Chihping Wang, Ming-Syan Chen: On the Complexity of Distributed Query Optimization. IEEE Trans. Knowl. Data Eng. 8(4): 650-662(1996)
3. Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
   Contents
4. Yehoshua Sagiv, Oded Shmueli: Solving Queries by Tree Projections. ACM Trans. Database Syst. 18(3): 487-511(1993)
5. Dennis Shasha, Jason Tsong-Li Wang: Optimizing Equijoin Queries In Distributed Databases Where Relations Are Hash Partitioned. ACM Trans. Database Syst. 16(2): 279-308(1991)
6. Dan E. Willard: Quasilinear Algorithms for Processing Relational Calculus Expressions. PODS 1990: 243-257
7. Y. C. Tay: Attribute Agreement. PODS 1989: 110-119
8. Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
   Contents
9. Michael Kifer, Raghu Ramakrishnan, Abraham Silberschatz: An Axiomatic Approach to Deciding Query Safety in Deductive Databases. PODS 1988: 52-60
10. Stéphane Lafortune, Eugene Wong: A State Transition Model for Distributed Query Processing. ACM Trans. Database Syst. 11(3): 294-322(1986)
11. Yehoshua Sagiv, Oded Shmueli: On Finite FD-Acyclicity. PODS 1986: 173-182
12. Yehoshua Sagiv, Oded Shmueli: The Equivalence of Solving Queries and Production Tree Projections. PODS 1986: 160-172
13. Matthias Jarke, Yannis Vassiliou: A Framework for Choosing a Database Query Language. ACM Comput. Surv. 17(3): 313-340(1985)
14. Joseph A. Wald, Paul G. Sorenson: Resolving the Query Inference Problem Using Steiner Trees. ACM Trans. Database Syst. 9(3): 348-368(1984)
15. Matthias Jarke, Jürgen Koch: Query Optimization in Database Systems. ACM Comput. Surv. 16(2): 111-152(1984)
16. Dan E. Willard: Efficient Processing of Relational Calculus Expressions Using Range Query Theory. SIGMOD Conference 1984: 164-175
17. Oded Shmueli, Alon Itai: Maintenance of Views. SIGMOD Conference 1984: 240-255
18. Kent Laver, Alberto O. Mendelzon, Marc H. Graham: Functional Dependencies on Cyclic Database Schemes. SIGMOD Conference 1983: 79-91
19. Nathan Goodman, Oded Shmueli, Y. C. Tay: GYO Reductions, Canonical Connections, Tree and Cyclic Schemas and Tree Projections. PODS 1983: 267-278
20. Philip A. Bernstein, Nathan Goodman, Eugene Wong, Christopher L. Reeve, James B. Rothnie Jr.: Query Processing in a System for Distributed Databases (SDD-1). ACM Trans. Database Syst. 6(4): 602-625(1981)