Optimal disk allocation for partial match queries

ABSTRACT

The problem of disk allocation addresses the issue of how to distribute a file on several disks in order to maximize concurrent disk accesses in response to a partial match query. In this paper a coding-theoretic analysis of this problem is presented, and both necessary and sufficient conditions for the existence of strictly optimal allocation methods are provided. Based on a class of optimal codes, known as maximum distance separable codes, strictly optimal allocation methods are constructed. Using the necessary conditions proved, we argue that the standard definition of strict optimality is too strong and cannot be attained, in general. Hence, we reconsider the definition of optimality. Instead of basing it on an abstract definition that may not be attainable, we propose a new definition based on the best possible allocation method. Using coding theory, allocation methods that are optimal according to our proposed criterion are developed.

REFERENCES

• 1: Khaled A. S. Abdel-Ghaffar , Amr El Abbadi, On the optimality of disk allocation for Cartesian product files (extended abstract), Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.258-264, April 02-04, 1990, Nashville, Tennessee, United States [doi>10.1145/298514.298578]
• 2: 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]
• 3: DINES, J., AND KEEUWELL, A.D. Latin Squares and Their Applicatmns. Academic Press, New York, 1974.
• 4: H. C. Du, Disk allocation methods for binary Cartesian product files, BIT, v.26 n.2, p.138-147, June 1986 [doi>10.1007/BF01933739]
• 5: H. C. Du , J. S. Sobolewski, Disk allocation for Cartesian product files on multiple-disk systems, ACM Transactions on Database Systems (TODS), v.7 n.1, p.82-101, March 1982 [doi>10.1145/319682.319698]
• 6: C. Faloutsos , D. Metaxas, Declustering using error correcting codes, Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.253-258, March 1989, Philadelphia, Pennsylvania, United States [doi>10.1145/73721.73747]
• 7: FUJIWARA, T., ITO, M., KASAMI, T., KATAOKA, M., AND OKUI, J. Performance analysis of disk allocation method using error-correcting codes. IEEE Trans. Inf. Theory. 37, 2 (Mar, 1991), 379 384.
• 8: Myoung Ho Kim , Sakti Pramanik, Optimal file distribution for partial match retrieval, Proceedings of the 1988 ACM SIGMOD international conference on Management of data, p.173-182, June 01-03, 1988, Chicago, Illinois, United States
• 9: MACWILLLtMS, F. J., AND SLOANE~ N. J.A. The Theory of Error-Correcting Codes. North- Holland, Amsterdam, 1977.
• 10: MANERI, C., AND SmVERMAN, R. A vector-space packing problem. J. Algebra 4, 3 (1966), 321 330.
• 11: McELmCE, R. J. Flnzte Fields for Computer Sc~entzsts and Engineers. Kluwer, Boston, Mass., 1987.
• 12: NORDSTROM, A. W., AND ROBINSON, J. P. An optimum nonlinear code. Inf. Control 11 (Nov.-Dec. 1967), 613-616.
• 13: David A. Patterson , Garth Gibson , Randy H. Katz, A case for redundant arrays of inexpensive disks (RAID), Proceedings of the 1988 ACM SIGMOD international conference on Management of data, p.109-116, June 01-03, 1988, Chicago, Illinois, United States
• 14: RIVEST, R.L. Partial-match retrieval algorithms. SIAM J. Comput. 5, 1 (Mar. 1976), 19-50.
• 15: 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]
• 16: SINGLETON, R. C. Maximum distance q-nary codes. IEEE Trans. Inf. Theory 10, 2 (Apr. 1964), 116-118.
• 17: Yuan Y. Sung, Parallel searching for binary Cartesian product files, Proceedings of the 1985 ACM thirteenth annual conference on Computer Science, p.163-172, March 1985, New Orleans, Louisiana, United States [doi>10.1145/320599.320668]
• 18: Yuan Y. Sung, Performance analysis of disk modulo allocation method for Cartesian product files, IEEE Transactions on Software Engineering, v.13 n.9, p.1018-1026, September 1, 1987 [doi>10.1109/TSE.1987.233524]
• 19: Tom Verhoeff, An updated table of minimum-distance bounds for binary linear codes, IEEE Transactions on Information Theory, v.33 n.5, p.665-680, September 1, 1987 [doi>10.1109/TIT.1987.1057356]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.2 Information Storage
          Subjects: File organization

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.3 File Systems Management
          Subjects: File organization

  E. Data
  E.5 FILES
      Subjects: Organization/structure

  H. Information Systems
  H.1 MODELS AND PRINCIPLES
      H.1.1 Systems and Information Theory
          Subjects: Information theory
  H.2 DATABASE MANAGEMENT
      H.2.2 Physical Design
          Subjects: Access methods

General Terms:
Algorithms, Design, Theory

Keywords:
Cartesian product files, coding theory, multiple disk systems, partial match queries