Join strategies using data space partitioning
Tóm tắt
In the recent investigations of reducing the relational join operation complexity several hash-based partitioned-join stategies have been introduced. All of these strategies depend upon the costly operation of data space partitioning before the join can be carried out. We had previously introduced a partitioned-join based on a dynamic and order preserving multidimensional data organization called DYOP. The present study extends the earlier research on DYOP and constructs a simulation model. The simulation studies on DYOP and subsequent comparisons of all the partitioned-join methodologies including DYOP have proven that space utilization of DYOP improves with the increasing number of attributes. Furthermore, the DYOP based join outperforms all the hash-based methodologies by greatly reducing the total I/O bandwidth required for the entire partitioned-join operation. The comparison model is independent of the architectural issues such as multiprocessing, multiple disk usage, and large memory availability all of which help to further increase the efficiency of the operation.
Tài liệu tham khảo
Babb, E., “Implementing a Relational Database by Means of Specialized Hardware,”ACM TODS, Vol. 4, No. 1, pp. 1–29, March 1979.
Bitton, D., Boral, H., Dewitt, D. and Wilkinson, W. K., “Parallel Algorithms for the Execution of Relational Database Operations,”ACM TODS, Vol. 8, No. 3, pp. 324–353, Sept. 1983.
Burkhard, W. A., “Interpolation-Based Index Maintenance,”Proc. of ACM SIGMOD-SIGACT Sym., pp. 76–85, 1983.
Dewitt, D. J., et al., “Implementation Techniques for Main Memory Database Systems,”Proc. of SIGMOD Conf., June 1984.
Dewitt, D. J. and Gerber, R., “Multiprocessor Hash-Based Join Algorithms,”Proc. of VLDB Conf., pp. 151–164, 1985.
Hsiao, D. (ed.),Advanced Database Machine Architectures, Prentice-Hall, Englewood Cliffs, N. J., 1983.
Kitsuregawa, M., Tanaka, H. and Moto-oka, T., “Application of Hash to Database Machine and its Architecture,”New Generation Computing, Vol. 1, No. 1, pp. 63–74, 1983.
Nievergelt, J., Hintenberger, J. and Sevcik, K. C., “The Grid File: An Adaptable, Symmetric Multikey File Structure,”ACM TODS, Vol. 9, No. 1, pp. 38–71, 1984.
Ouksel, M., “Order Preserving Dynamic Hashing Schemes for Associative Searching in Database Systems,”PhD Dissertation, Dept. of EECS, Northwestern University, Illinois, 1983.
Ouksel, M., “The Interpolation Based Grid File,”Proc. of ACM SIGMOD-SIGACT Sym., pp. 20–27, 1985.
Ozkarahan, E. A., “Desirable Functionalities of Database Architectures,Proc. of IFIP World Congress, pp. 357–362, 1983.
Ozkarahan, E. A., “Evolution and Implementations of the RAP Database Machine,”New Generation Computing, Vol., 3, No. 3, pp. 237–271, 1985.
Ozkarahan, E. A. and Ouksel, M., “Dynamic and Order Preserving Data Partitioning for Database Machines,”Proc. of VLDB Conf., pp. 358–368, 1985.
Ozkarahan, E. A.,Database Machines and Database Management, Prentice-Hall, Englewood Cliffs, N. J., 1986.
Ozkarahan, E. A. and Penaloza, M. A., “On-the-fly and Background Data Filtering System for Database Architectures,”New Generation Computing, Vol. 5, No. 3, pp. 281–314, 1987.
Valduriez, P. and Gardarin, G., “Join and Semi-Join Algorithms for a Multiprocessor Database Machine,”ACM Transactions on Database Systems, Vol. 9, No. 1, pp. 133–161, 1984.
Thom, J. A., Ramamohanarao, K. and Naish, L., “A Superjoin Algorithm for Deductive Databases,”Proc. of VLDB Conf., pp. 189–196, 1986.