Query Processing Utilizing Dependencies and Horizontal Decomposition.

Yahiko Kambayashi, Masatoshi Yoshikawa: Query Processing Utilizing Dependencies and Horizontal Decomposition. SIGMOD Conference 1983: 55-67

@inproceedings{DBLP:conf/sigmod/KambayashiY83,
  author    = {Yahiko Kambayashi and
               Masatoshi Yoshikawa},
  editor    = {David J. DeWitt and
               Georges Gardarin},
  title     = {Query Processing Utilizing Dependencies and Horizontal Decomposition},
  booktitle = {SIGMOD'83, Proceedings of Annual Meeting, San Jose, California,
               May 23-26, 1983},
  publisher = {ACM Press},
  year      = {1983},
  pages     = {55-67},
  ee        = {http://doi.acm.org/10.1145/582192.582205, db/conf/sigmod/KambayashiY83.html},
  crossref  = {DBLP:conf/sigmod/83},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

BibTeX

Abstract

Since join operations are expensive, usually join scheduling is very important for query processing. In this paper we will discuss new procdeures to handle cyclic queries utilizing dependencies and horizontal decompositions. There are three known procedures for cyclic query processing: (1) Relation merging, (2) Tuple-wise processing, (3) Attribute addition. As join operations are applied to relations which are processed by selection operations, the number of tuples is usually less than the original relation and thus there are situations in which temporary FDs are satisfied. Such FDs can be used to simplify the given query. To convert a given cyclic query into a tree, some relations must satisfy a set of FDs. This can be attained by horizontal decomposition. Tuple-wise processing and attribute addition are shown to be special cases of the FD-based procedure. Ye have also developed MVD-based procedures which are generalized from the FD-based procedure.

Copyright © 1983 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.

ACM SIGMOD Anthology

Online Version (ACM WWW Account required): Full Text in PDF Format

CDROM Version: Load the CDROM "Volume 1 Issue 2, SIGMOD '75-'92" and ...

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/smod7592 or /cdrom

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

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/aDVD1 or /dvd

BibTeX

Printed Edition

David J. DeWitt, Georges Gardarin (Eds.): SIGMOD'83, Proceedings of Annual Meeting, San Jose, California, May 23-26, 1983. ACM Press 1983 BibTeX , SIGMOD Record 13(4)
Contents

Online Edition: ACM Digital Library

References

[ARMSD8012]: William Ward Armstrong, Claude Delobel: Decomposition and Functional Dependencies in Relations. ACM Trans. Database Syst. 5(4): 404-430(1980) BibTeX
[BEERF8105]: Catriel Beeri, Ronald Fagin, David Maier, Alberto O. Mendelzon, Jeffrey D. Ullman, Mihalis Yannakakis: Properties of Acyclic Database Schemes. STOC 1981: 355-362 BibTeX
[BERNC8101]: Philip A. Bernstein, Dah-Ming W. Chiu: Using Semi-Joins to Solve Relational Queries. J. ACM 28(1): 25-40(1981) BibTeX
[BERNG8111]: Philip A. Bernstein, Nathan Goodman: Power of Natural Semijoins. SIAM J. Comput. 10(4): 751-771(1981) BibTeX
[GAREJ79]: M. R. Garey, David S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman 1979, ISBN 0-7167-1044-7
BibTeX
[GOODS8203]: Nathan Goodman, Oded Shmueli: The Tree Property is Fundamental for Query Processing. PODS 1982: 40-48 BibTeX
[KAMBY8206]: Yahiko Kambayashi, Masatoshi Yoshikawa, Shuzo Yajima: Query Processing for Distributed Databases Using Generalized Semi-Joins. SIGMOD Conference 1982: 151-160 BibTeX
[SAGIF7903]: ...
[TANAL7808]: ...
[WONGY7609]: Eugene Wong, Karel Youssefi: Decomposition - A Strategy for Query Processing. ACM Trans. Database Syst. 1(3): 223-241(1976) BibTeX
[YU--07911]: ...

Referenced by

Yehoshua Sagiv, Oded Shmueli: Solving Queries by Tree Projections. ACM Trans. Database Syst. 18(3): 487-511(1993)
Kyu-Young Whang, Ravi Krishnamurthy: Query Optimization in a Memory-Resident Domain Relational Calculus Database System. ACM Trans. Database Syst. 15(1): 67-95(1990)
Y. C. Tay: Attribute Agreement. PODS 1989: 110-119
Yehoshua Sagiv, Oded Shmueli: The Equivalence of Solving Queries and Production Tree Projections. PODS 1986: 160-172
Clement T. Yu, C. C. Chang: Distributed Query Processing. ACM Comput. Surv. 16(4): 399-433(1984)
Matthias Jarke, Jürgen Koch: Query Optimization in Database Systems. ACM Comput. Surv. 16(2): 111-152(1984)
Masatoshi Yoshikawa, Yahiko Kambayashi: Processing Inequality Queries Based on Generalized Semi-Joins. VLDB 1984: 416-428
Patrick C. Fischer, Dirk Van Gucht: Weak Multivalued Dependencies. PODS 1984: 266-274

BibTeX

ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]