ISSN:
1573-7640
Keywords:
Consecutive retrieval property
;
unique incidence matrix
;
row binary patterns
;
column binary patterns
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Notes:
Abstract Ghosh's consecutive retrieval property (CR property) not only represents an elegant file organization, but also raises the problem of how to construct such a file with this property. Ghosh used ann ×m 0–1 incidence matrix, wheren is the number of records andm is the number of queries, as a tool for constructing a file with the CR property. In this paper the rows and columns of the incidence matrix are restricted to unique 0–1 patterns. It is found that such a unique incidence matrix cannot have the CR property if the number of rows is greater than 2m−1. This upper bound can be used to generatem(2m−1) columns, which form all the matrices with the CR property that may correspond to the given matrix. Two algorithms are presented which map the columns of the given incidence matrix to these columns with consecutive l's. A proposed implementation in terms of data base design is also presented.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF00993055