Query processing utilizing dependencies and horizontal decomposition

ABSTRACT

Since join operations are expensive, usually join scheduling is very important for query processing. In this paper we will discuss new procedures 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. We have also developed MVD-based procedures which are generalized from the FD-based procedure.

REFERENCES

• 1: W. W. Armstrong , C. Deobel, Decompositions and functional dependencies in relations, ACM Transactions on Database Systems (TODS), v.5 n.4, p.404-430, Dec. 1980 [doi>10.1145/320610.320620]
• 2: Catriel Beeri , Ronald Fagin , David Maier , Alberto Mendelzon , Jeffrey Ullman , Mihalis Yannakakis, Properties of acyclic database schemes, Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.355-362, May 11-13, 1981, Milwaukee, Wisconsin, United States [doi>10.1145/800076.802489]
• 3: Philip A. Bernstein , Dah-Ming W. Chiu, Using Semi-Joins to Solve Relational Queries, Journal of the ACM (JACM), v.28 n.1, p.25-40, Jan. 1981 [doi>10.1145/322234.322238]
• 4: {BERNG8111} Bernstein,P.A. and Goodman,N., "Power of Natural Semijoins", SIAM J. Comput., Vol.10, No.4, pp.751--771, Nov. 1981.
• 5: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 6: N. Goodman , O. Shmueli, The tree property is fundamental for query processing, Proceedings of the 1st ACM SIGACT-SIGMOD symposium on Principles of database systems, March 29-31, 1982, Los Angeles, California [doi>10.1145/588111.588119]
• 7: Yahiko Kambayashi , Masatoshi Yoshikawa , Shuzo Yajima, Query processing for distributed databases using generalized semi-joins, Proceedings of the 1982 ACM SIGMOD international conference on Management of data, June 02-04, 1982, Orlando, Florida [doi>10.1145/582353.582381]
• 8: {SAGIF7903} Sagiv,Y. and Fagin,R., "An Equivalence between Database Dependencies and a Subclass of Propositional Logic.", IBM Res. Rep., RJ2500, Mar. 1979.
• 9: Katsumi Tanaka , Chung Le Viet , Yahiko Kambayashi , Shuzo Yajima, A file organization suitable for relational database operations, Proceedings of the International Conference on Mathematical Studies of Information Processing, p.193-227, August 23-26, 1978
• 10: Eugene Wong , Karel Youssefi, Decomposition—a strategy for query processing, ACM Transactions on Database Systems (TODS), v.1 n.3, p.223-241, Sept. 1976 [doi>10.1145/320473.320479]
• 11: {YU-07911} Yu,C.T. and Ozsoyoglu,M.Z., "An Algorithm for Tree-Query Membership of a Distributed Query", Proc. of 3rd International Computer Software and Applications Conference (COMPSAC), pp.306--312, Nov. 1979.