Disk allocation for Cartesian product files on multiple-disk systems

ABSTRACT

Cartesian product files have recently been shown to exhibit attractive properties for partial match queries. This paper considers the file allocation problem for Cartesian product files, which can be stated as follows: Given a k-attribute Cartesian product file and an m-disk system, allocate buckets among the m disks in such a way that, for all possible partial match queries, the concurrency of disk accesses is maximized. The Disk Modulo (DM) allocation method is described first, and it is shown to be strict optimal under many conditions commonly occurring in practice, including all possible partial match queries when the number of disks is 2 or 3. It is also shown that although it has good performance, the DM allocation method is not strict optimal for all possible partial match queries when the number of disks is greater than 3. The General Disk Modulo (GDM) allocation method is then described, and a sufficient but not necessary condition for strict optimality of the GDM method for all partial match queries and any number of disks is then derived. Simulation studies comparing the DM and random allocation methods in terms of the average number of disk accesses, in response to various classes of partial match queries, show the former to be significantly more effective even when the number of disks is greater than 3, that is, even in cases where the DM method is not strict optimal. The results that have been derived formally and shown by simulation can be used for more effective design of optimal file systems for partial match queries. When considering multiple-disk systems with independent access paths, it is important to ensure that similar records are clustered into the same or similar buckets, while similar buckets should be dispersed uniformly among the disks.

REFERENCES

• 1: Alfred V. Aho , Jeffrey D. Ullman, Optimal partial-match retrieval when fields are independently specified, ACM Transactions on Database Systems (TODS), v.4 n.2, p.168-179, June 1979 [doi>10.1145/320071.320074]
• 2: Walter A. Burkhard, Partial-match hash coding: benefits of redundancy, ACM Transactions on Database Systems (TODS), v.4 n.2, p.228-239, June 1979 [doi>10.1145/320071.320079]
• 3: C. C. Chang , R. C. T. Lee , H. C. Du, Some properties of Cartesian product files, Proceedings of the 1980 ACM SIGMOD international conference on Management of data, May 14-16, 1980, Santa Monica, California [doi>10.1145/582250.582276]
• 4: LIN, W.C., LEE, R.C.T., AND DU, H.C. Common properties of some multi-attribute file systems. IEEE Trans. Software Eng. SE-5, 2 (March 1979}, 160-174.
• 5: LIou, J.H., AND YAO, S.B. Multi-dimensional clustering for data base organizations. Information Syst. 2 (1977) 187-198.
• 6: RIVEST, R.L. Partial-match retrieval algorithms. SIAM J. Comput. 15, 1 (March 1976), 19-50.
• 7: James B. Rothnie, Jr. , Tomas Lozano, Attribute based file organization in a paged memory environment, Communications of the ACM, v.17 n.2, p.63-69, Feb. 1974 [doi>10.1145/360827.360831]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.2 Information Storage
          Subjects: File organization
      H.3.3 Information Search and Retrieval
          Subjects: Search process

General Terms:
Algorithms, Performance

Keywords:
Cartesian product files