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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
S. P. Ghosh, “On the Theory of Consecutive Storage of Relevant Records,”Inf. Sci. G:1–9 (1973).
S. P. Ghosh, “File organization: the consecutive retrieval property,”Commun. ACM, 802–808 (September 4, 1972), also published as IBM Research Report No. RJ 765 (1970).
S. P. Ghosh, “File organization: consecutive storage of relevant records on a drumtype storage,”Inf. Control 25(2):145–165 (1974).
S. P. Ghosh, “Consecutive storage of relevant records with redundancy,”Commun. ACM, 464–471 (August 8, 1975).
S. P. Ghosh,Data Base Organization for Data Management (Academic Press, New York, 1977).
A. N. Patrinos and S. L. Hakimi, “File Organization with Consecutive Retrieval and Related Properties,” Report, Computer Sciences Department, Northwestern University (1975).
A. N. Patrinos, “On the Ordering of Vertices in Graphs,” Ph.D. Thesis, Northwestern University, Evanston, Illinois (1974).
D. R. Fulkerson and O. A. Gross, “Incidence matrices and interval graphs,”Pacific J. Math. 3:835–855 (1965).
K. P. Eswaran, “Consecutive Retrieval Information System,” Ph.D. thesis, University of California, Berkeley (1973).
K. P. Eswaran, “Faithful representation of a family of sets by a set of intervals,”SIAM J. Comput. 4:56–67 (1975).
N. J. A. Sloane,A Handbook of Integer Sequences (Academic Press, New York-London, 1973).
E. Wong and T. C. Chiang, “Canonical structure in attribute based file organization,”Commun. ACM 14(9):593–597 (September 1971).
D. C. Tsichsitzis and F. H. Lochovsky,Data Base Management Systems (Academic Press, New York, 1977).
CODASYL, “CODASYL Data Base Task Group Report Conference,” ACM New York (1971).
Y. H. Chin, “An analysis of distributed free space in an operating and data management system environment,”IEEE TSE, Vol. SE-4, No. 5:436–440.
S. S. Al-Fedaghi, “A study in Consecutive Retrieval Property: A general approach in theory, implementation and applications,” Masters thesis, Computer Science Department, Northwestern University, Evanston, Illinois (June 1977).
S. Yamamoto, K. Ushio, S. Tazawa, H. Ikeda, F. Tamari, and N. Hamada, “Partition of a query set into minimal number of subsets having consecutive retreival property,”J. Stat. Plann. Inference 1:41–51 (1977).
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Al-Fedaghi, S.S., Chin, Y.H. Algorithmic approach to the consecutive retrieval property. International Journal of Computer and Information Sciences 8, 279–301 (1979). https://doi.org/10.1007/BF00993055
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF00993055