ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

On the Optimality of Disk Allocation for Cartesian Product Files.

Khaled A. S. Abdel-Ghaffar, Amr El Abbadi: On the Optimality of Disk Allocation for Cartesian Product Files. PODS 1990: 258-264
@inproceedings{DBLP:conf/pods/Abdel-GhaffarA90,
  author    = {Khaled A. S. Abdel-Ghaffar and
               Amr El Abbadi},
  title     = {On the Optimality of Disk Allocation for Cartesian Product Files},
  booktitle = {Proceedings of the Ninth ACM SIGACT-SIGMOD-SIGART Symposium on
               Principles of Database Systems, April 2-4, 1990, Nashville, Tennessee},
  publisher = {ACM Press},
  year      = {1990},
  isbn      = {0-89791-352-3},
  pages     = {258-264},
  ee        = {http://doi.acm.org/10.1145/298514.298578, db/conf/pods/Abdel-GhaffarA90.html},
  crossref  = {DBLP:conf/pods/90},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

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.

Copyright © 1990 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

Load The ACM SIGMOD Anthology, CDROM Edition, Volume 1-3, PODS '82-'98. and ... Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. and ... BibTeX

Printed Edition

Proceedings of the Ninth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, April 2-4, 1990, Nashville, Tennessee. ACM Press 1990, ISBN 0-89791-352-3
Contents BibTeX

Online Edition: ACM Digital Library

References

[1]
...
[2]
...
[3]
David Hung-Chang Du, J. S. Sobolewski: Disk Allocation for Cartesian Product Files on Multiple-Disk Systems. ACM Trans. Database Syst. 7(1): 82-101(1982) BibTeX
[4]
Christos Faloutsos, Dimitris N. Metaxas: Declustering Using Error Correcting Codes. PODS 1989: 253-258 BibTeX
[5]
Myoung-Ho Kim, Sakti Pramanik: Optimal File Distribution For Partial Match Retrieval. SIGMOD Conference 1988: 173-182 BibTeX
[6]
...
[7]
...
[8]
Ronald L. Rivest: Partial-Match Retrieval Algorithms. SIAM J. Comput. 5(1): 19-50(1976) BibTeX
[9]
James B. Rothnie Jr., Tomas Lozano: Attribute Based File Organization in a Paged Memory Environment. Commun. ACM 17(2): 63-69(1974) BibTeX
[10]
...
[11]
Sam Yuan Sung: Performance Analysis of Disk Modulo Allocation Method for Cartesian Product Files. IEEE Trans. Software Eng. 13(9): 1018-1026(1987) BibTeX

Referenced by

  1. Khaled A. S. Abdel-Ghaffar, Amr El Abbadi: Optimal Disk Allocation for Partial Match Queries. ACM Trans. Database Syst. 18(1): 132-156(1993)
  2. Jianzhong Li, Doron Rotem, Jaideep Srivastava: Algorithms for Loading Parallel Grid Files. SIGMOD Conference 1993: 347-356
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:34:01 2009