A Heuristic Approach to Attribute Partitioning.

@inproceedings{DBLP:conf/sigmod/HammerN79,
  author    = {Michael Hammer and
               Bahram Niamir},
  editor    = {Philip A. Bernstein},
  title     = {A Heuristic Approach to Attribute Partitioning},
  booktitle = {Proceedings of the 1979 ACM SIGMOD International Conference on
               Management of Data, Boston, Massachusetts, May 30 - June 1},
  publisher = {ACM},
  year      = {1979},
  isbn      = {0-89791-001-X},
  pages     = {93-101},
  ee        = {http://doi.acm.org/10.1145/582095.582110, db/conf/sigmod/HammerN79.html},
  crossref  = {DBLP:conf/sigmod/79},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

One technique that is sometimes employed to enhance the performance of a database management system is known as attribute partitioning. This is the process of dividing the attributes of a file into separately stored subfiles. By storing together those attributes that are frequently requested together by transactions, and by separating those that are not, attribute partitioning can reduce the number of pages that are transferred from secondary storage to primary memory in the processing of a transaction.

The goal of this work is to design mechanisms that can automatically select a near-optimal attribute partition of a file's attributes, based on the usage pattern of the file and on the characteristics of the data in the file. The approach taken to this problem is based on the use of an accurate partition evaluator and of a heuristic that guides a search through the large space of possible partitions. The heuristics propose a small set of promising partitions to submit for detailed analysis. The evaluator assigns a figure of merit to any proposed partition that reflects the cost that would be incurred in processing the transactions in the usage pattern if the file were partitioned in the proposed way.

We have implemented an evaluator for a particular model database system and have developed a heuristic search technique. A series of experiments has demonstrated the accuracy and efficiency of this heuristic.

Copyright © 1979 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.

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 2, SIGMOD '75-'92" and ...

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the CD and click on the path of your mount point:
  /Anthology/smod7592 or /cdrom

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD1 or /dvd

Printed Edition

Online Edition: ACM Digital Library

References

[1]

...

[2]

Jair M. Babad: A Record and File Partitioning Model. Commun. ACM 20(1): 22-31(1977) BibTeX

[3]

Don S. Batory: On Searching Transposed Files (Abstract). VLDB 1978: 488 BibTeX

[4]

...

[5]

...

[6]

...

[7]

...

[8]

...

[9]

P. A. Dearnley: A Model of a Self-Organising Data Management System. Comput. J. 17(1): 13-16(1974) BibTeX

[10]

Mark J. Eisner, Dennis G. Severance: Mathematical Techniques for Efficient Record Segmentation in Large Shared Databases. J. ACM 23(4): 619-635(1976) BibTeX

[11]

...

[12]

Michael Hammer, Arvola Chan: Index Selection in a Self-Adaptive Data Base Management System. SIGMOD Conference 1976: 1-8 BibTeX

[13]

...

[14]

...

[15]

...

[16]

...

[17]

Jeffrey A. Hoffer, Dennis G. Severance: The Use of Cluster Analysis in Physical Data Base Design. VLDB 1975: 69-86 BibTeX

[18]

...

[19]

...

[20]

Salvatore T. March, Dennis G. Severance: The Determination of Efficient Record Segmentations and Blocking Factors for Shared Data Files. ACM Trans. Database Syst. 2(3): 279-296(1977) BibTeX

[21]

...

[22]

...

[23]

Arvola Chan, Bahram Niamir: On Estimating the Cost of Accessing Records in Blocked Database Organizations. Comput. J. 25(3): 368-374(1982) BibTeX

[24]

...

[25]

Mario Schkolnick: A Clustering Algorithm for Hierarchical Structures. ACM Trans. Database Syst. 2(1): 27-44(1977) BibTeX

[26]

...

[27]

Peter M. Stocker, P. A. Dearnley: Self-Organising Data Management Systems. Comput. J. 16(2): 100-105(1973) BibTeX

[28]

...

[29]

...

[30]

S. Bing Yao: Approximating the Number of Accesses in Database Organizations. Commun. ACM 20(4): 260-261(1977) BibTeX

[31]

...

Referenced by

1. Surajit Chaudhuri, Vivek R. Narasayya: Index Merging. ICDE 1999: 296-303
2. Elzbieta Malinowski, Sharma Chakravarthy: Fragmentation Techniques for Distributing Object-Oriented Databases. ER 1997: 347-360
3. Gultekin Özsoyoglu, Aladdin Hafez: Near-Optimum Storage Models for Nested Relations Based on Workload Information. IEEE Trans. Knowl. Data Eng. 5(6): 1018-1038(1993)
4. Minyoung Ra, Y.-S. Park: Data Fragmentation and Allocation for PC-Based Distributed Database Design. DASFAA 1993: 90-96
5. Philippe Pucheral, Jean-Marc Thévenin: Pipelined Query Processing in the DBGraph Storage Model. EDBT 1992: 516-533
6. Aladdin Hafez, Gultekin Özsoyoglu: The Partial Normalized Storage Model of Nested Relations. VLDB 1988: 100-111
7. Clement T. Yu, Cheing-Mei Suen, K. Lam, M. K. Siu: Adaptive Record Clustering. ACM Trans. Database Syst. 10(2): 180-204(1985)
8. Domenico Saccà, Gio Wiederhold: Database Partitioning in a Cluster of Processors. ACM Trans. Database Syst. 10(1): 29-56(1985)
9. Clement T. Yu, C. H. Chen: Adaptive Information System Design: One Query at a Time. SIGMOD Conference 1985: 280-290
10. Shamkant B. Navathe, Stefano Ceri, Gio Wiederhold, Jinglie Dou: Vertical Partitioning Algorithms for Database Design. ACM Trans. Database Syst. 9(4): 680-710(1984)
11. Salvatore T. March, Gary D. Scudder: On the Selection of Efficient Record Segmentations and Backup Strategies for Large Shared Databases. ACM Trans. Database Syst. 9(3): 409-438(1984)
12. Stavros Christodoulakis: Implications of Certain Assumptions in Database Performance Evaluation. ACM Trans. Database Syst. 9(2): 163-186(1984)
13. Matthias Jarke, Jürgen Koch: Query Optimization in Database Systems. ACM Comput. Surv. 16(2): 111-152(1984)
14. Salvatore T. March: Techniques for Structuring Database Records. ACM Comput. Surv. 15(1): 45-79(1983)
15. Clement T. Yu, M. K. Siu, K. Lam, C. H. Chen: File Allocation in Distributed Databases with Interaction between Files. VLDB 1983: 248-259
16. Arie Shoshani: Statistical Databases: Characteristics, Problems, and some Solutions. VLDB 1982: 208-222
17. Paula B. Hawthorn: Microprocessor Assisted Tuple Access, Decompression and Assembly for Statistical Database Systems. VLDB 1982: 223-233
18. Michele Missikoff: A Domain Based Internal Schema for Relational Database Machines. SIGMOD Conference 1982: 215-224
19. Stefano Ceri, Mauro Negri, Giuseppe Pelagatti: Horizontal Data Partitioning in Database Design. SIGMOD Conference 1982: 128-136
20. Kenneth C. Sevcik: Data Base System Performance Prediction Using an Analytical Model (Invited Paper). VLDB 1981: 182-198
21. Susan J. Eggers, Frank Olken, Arie Shoshani: A Compression Technique for Large Statistical Data-Bases. VLDB 1981: 424-434
22. Susan J. Eggers, Arie Shoshani: Efficient Access of Compressed Data. VLDB 1980: 205-211