On the optimality of disk allocation for Cartesian product files (extended abstract)

ABSTRACT

In this paper we present a coding-theoretic analysis of the disk allocation problem. We provide both necessary and sufficient conditions for the existence of strictly optimal allocation methods. 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. A new criterion for optimality is therefore defined whose objective is to design allocation methods that yield a response time of one for all queries with a minimum number of specified attributes. Using coding theory, we determined this minimum number for binary files, assuming that the number of disks is a power of two. In general, our approach provides better allocation methods than previous techniques.

REFERENCES

• 1: D~nes, J. and A. D. Keedwell, Latin squares and their applications, Academic Press, 1974.
• 2: 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]
• 3: 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]
• 4: 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]
• 5: 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
• 6: Maneri, C. and R. Silverman, "A Vector-Space Packing Problem," Journal of Algebra, Vol. 4, pp. 321-330, 1966.
• 7: MacWilliams, F. }. and N. J. A. Sloane, The Theory of Error-Correcting Codes, North-Holland, 1977.
• 8: Rivest, R.L., "Partial-Match Retrieval Algorithms," SIAM Journal of Computing, Vol. 5, No. 1, pp. 19-50, March 1976.
• 9: 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]
• 10: 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]
• 11: 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]

INDEX TERMS

Primary Classification:
  E. Data

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Allocation/deallocation strategies

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

General Terms:
Design, Management, Measurement, Performance, Theory, Verification