A heuristic file reorganization algorithm based on record clustering

Peter I Scheuermann*, Young Chul Park, Edward Omiecinski

*Corresponding author for this work

Research output: Contribution to journalArticle

3 Scopus citations

Abstract

The problem of file organization which we consider involves altering the placement of records on pages of a secondary storage device. In addition, we want this reorganization to be done in-place, i.e., using the file's original storage space for the newly reorganized file. The motivation for such a physical change is to improve the database system's performance. For example, by placing frequently and jointly accessed records on the same page or pages, we can try to minimize the number of page accesses made in answering a set of queeries. The optimal assignment (or reassignment) of records to clusters is exactly what record clustering algorithms attempt to do. However, record clustering algorithms usually do not solve the entire problem, i.e., they do not specify how to efficiently reorganize the file to reflect the clustering assignment which they determine. Our algorithm is a companion to general record clustering algorithms since it actually transforms the file. The problem of optimal file reorganization is NP-hard. Consequently, our reorganization algorithm is based on heuristics. The algorithm's time and space requirements are reasonable and its solution is near optimal. In addition, the reorganization problem which we consider in this paper is similar to the problem of join processing when indexes are used.

Original languageEnglish (US)
Pages (from-to)428-447
Number of pages20
JournalBIT
Volume29
Issue number3
DOIs
StatePublished - Sep 1 1989

Keywords

  • H.0
  • H.2.2
  • H.3.3

ASJC Scopus subject areas

  • Computational Mathematics
  • Applied Mathematics
  • Software
  • Computer Graphics and Computer-Aided Design

Fingerprint Dive into the research topics of 'A heuristic file reorganization algorithm based on record clustering'. Together they form a unique fingerprint.

  • Cite this