article

Free access

On searching transposed files

Editor: David K. Hsiao Author:

D. S. BatoryAuthors Info & Claims

ACM Transactions on Database Systems (TODS), Volume 4, Issue 4

Pages 531 - 544

https://doi.org/10.1145/320107.320125

Published: 01 December 1979 Publication History

Abstract

A transposed file is a collection of nonsequential files called subfiles. Each subfile contains selected attribute data for all records. It is shown that transposed file performance can be enhanced by using a proper strategy to process queries. Analytic cost expressions for processing conjunctive, disjunctive, and batched queries are developed and an effective heuristic for minimizing query processing costs is presented. Formulations of the problem of optimally processing queries for a particular family or transposed files are shown to be NP-complete. Query processing performance comparisons of multilist, inverted, and nonsequential files with transposed files are also considered.

References

[1]

AHO, A.V., HOPCROFT, J.E., AND ULLMAN, J.D. The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, Mass., 1975.

Digital Library

[2]

BABAD, J.M. A record and file partitioning model. Comm. ACM 20, 1 (Jan. 1977), 22-31.

Digital Library

[3]

BENNER, F.H. On designing generalized file records for management information systems. Proc. AFIPS 1976 FJCC, AFIPS Press, Arlington, Va., pp. 291-303.

[4]

BLASGEN, M.W., AND ESWARAN, K.P. Storage and access in relational databases. IBM Syst. J. 16, 4 (1977), 363-377.

Digital Library

[5]

DAY, R.H. On optimal extracting from a multiple file data storage system: An application of integer programming. Oper. Res. 13, 3 (May-June 1965), 482-494.

Digital Library

[6]

DEARNLEY, P. A model of self-organizing data management system. Comptr. J. 17, 1 (1974), 13- 16.

[7]

EISNER, M.J., AND SEVERANCE, D.G. Mathematical techniques for efficient record segmentation in large shared databases. J. ACM 23, 4 (Oct. 1976), 619-635.

Digital Library

[8]

GERMANO, F., AND WEYL, S. A database organization to support a time-oriented medical record. ACM Regional Conf. on Data: Its Use, Organization, and Management, April 1975, pp. 93-103.

[9]

HAMMER, M., AND CHAN, A. Index selection in a self-adaptive database management system. Proc. ACM SIGMOD Int. Conf. Management of Data, 1976, pp. 1-8.

[10]

HOFFER, J.A. A clustering approach to the generation of subfiles for the design of a computer database. Ph.D. Th., Cornell U., Ithaca, N.Y., Jan. 1975.

Digital Library

[11]

HOOFER, J.A., AND SEVERANCE, D.G. The use of cluster analysis in physical database design. Proc. Very Large Data Bases I (1975), 69-86.

[12]

KENNEDY, S.R. The use of access frequencies in database organizations. Ph.D. Th., Cornell U., Ithaca, N.Y., May 1973.

[13]

KING, W.F. On the selection of indices for a file. Rep. RJ1341, IBM, San Jose, Calif., Jan. 1974.

[14]

MARCH, S.T., AND SEVERANCE, D.G. The determination of efficient record segmentations and blocking factors for shared data files. ACM Trans. Database Syst. 2, 3 (Sept. 1977), 279-296.

Digital Library

[15]

MARTIN, J. Computer Data-Base Organization. Prentice-Hall, Englewood Cliffs, N.J., 1975.

Digital Library

[16]

NIAMIR, B. Attribute partitioning in a self-adaptive relational database system. Rep. MIT/LCS/ TR-192, M.S. Th., M.I.T., Cambridge, Mass.

Digital Library

[17]

Robot--its features and facilities. Software Sciences, London, Oct. 1972.

[18]

SEPPALA, Y. Definition of extraction files and their optimization by zero-one programming. BIT 7 (1967), 206-215.

[19]

SHNEIDERMAN, B., AND GOODMAN, V. Batched searching of sequential and tree structured files.

[20]

STOCKZR, P.M., AND DEAnNLEY, P.A. Self-organizing data management system. Comptr. J. 16, 2 (1973), pp. 100-105.

[21]

THEmS, H.E. Mathematical programming techniques for optimal computer use. Proc. ACM Nat. Conf., 1965, pp. 501-512.

Digital Library

[22]

WIEDERHOLD, G. Database Design. McGraw-Hill, New York, 1977.

Digital Library

[23]

YAO, S.B. Approximating block accesses in database organizations. Comm. ACM 20, 4 (April I977), 260--261.

Digital Library

[24]

YUE, P.C., AND WONG, C.K. Storage cost considerations in secondary index selection. Int. J. Comptr. Inform. Sci. 4, 4 (1975), 307-327.

Cited By

Nishikawa NFujiwara SHayamizu YGoda K(2023)Physical Database Design for Manufacturing Business Analytics2023 IEEE International Conference on Big Data (BigData)10.1109/BigData59044.2023.10386475(1793-1802)Online publication date: 15-Dec-2023
https://doi.org/10.1109/BigData59044.2023.10386475
Wong HLi JOlken FRotem DWong L(2023)Bit transposition for very large scientific and statistical databasesAlgorithmica10.1007/BF018404491:1-4(289-309)Online publication date: 22-Mar-2023
https://dl.acm.org/doi/10.1007/BF01840449
Reznichenko V(2022)60 Years of Databases (part four)PROBLEMS IN PROGRAMMING10.15407/pp2022.02.057(57-95)Online publication date: Jun-2022
https://doi.org/10.15407/pp2022.02.057
Show More Cited By

Index Terms

On searching transposed files
1. Information systems
  1. Information retrieval
    1. Information retrieval query processing
  2. Information storage systems
    1. Record storage systems
      1. Record storage alternatives
        Hashed file organization
        Indexed file organization

Recommendations

Bit transposed files
VLDB '85: Proceedings of the 11th international conference on Very Large Data Bases - Volume 11

Conventional access methods cannot be effectively used in large Scientific/Statistical Database (SSDB) applications. A file structure (called bit transposed file) is proposed which offers several attractive features that are better suited for the ...
On Multiple Random Accesses and Physical Data Placement in Dynamic Files

In the study of data storage and retrieval involving secondary storage devices, for example, magnetic disks, a simplified model of storage that is often used is that each access takes a constant amount of time. However, if some information about the ...
Optimizing Sort Order Query Execution in Balanced and Nested Grid Files

Disk input/output (I/O) efficient query execution is an important topic with respect to DBMS performance. In this context, we elaborate on the construction of disk access plans for sort order queries in balanced and nested grid files. The key idea is to ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Database Systems

ACM Transactions on Database Systems Volume 4, Issue 4

Dec. 1979

150 pages

ISSN:0362-5915

EISSN:1557-4644

DOI:10.1145/320107

Editor:
David K. Hsiao
Ohio State Univ., Columbus

Issue’s Table of Contents

Copyright © 1979 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 December 1979

Published in TODS Volume 4, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

86
Total Citations
View Citations
621
Total Downloads

Downloads (Last 12 months)93
Downloads (Last 6 weeks)6

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Nishikawa NFujiwara SHayamizu YGoda K(2023)Physical Database Design for Manufacturing Business Analytics2023 IEEE International Conference on Big Data (BigData)10.1109/BigData59044.2023.10386475(1793-1802)Online publication date: 15-Dec-2023
https://doi.org/10.1109/BigData59044.2023.10386475
Wong HLi JOlken FRotem DWong L(2023)Bit transposition for very large scientific and statistical databasesAlgorithmica10.1007/BF018404491:1-4(289-309)Online publication date: 22-Mar-2023
https://dl.acm.org/doi/10.1007/BF01840449
Reznichenko V(2022)60 Years of Databases (part four)PROBLEMS IN PROGRAMMING10.15407/pp2022.02.057(57-95)Online publication date: Jun-2022
https://doi.org/10.15407/pp2022.02.057
Wandelt SSun XLeser U(2018)Column-wise compression of open relational dataInformation Sciences: an International Journal10.1016/j.ins.2018.04.074457:C(48-61)Online publication date: 1-Aug-2018
https://dl.acm.org/doi/10.1016/j.ins.2018.04.074
Böhm ADittrich JMukherjee NPandis ISen R(2016)Operational analytics data management systemsProceedings of the VLDB Endowment10.14778/3007263.30073199:13(1601-1604)Online publication date: 1-Sep-2016
https://dl.acm.org/doi/10.14778/3007263.3007319
Wandelt SSun XZhu Y(2016)Lossless Compression of Public Transit SchedulesIEEE Transactions on Intelligent Transportation Systems10.1109/TITS.2016.254213117:11(3075-3086)Online publication date: 1-Nov-2016
https://dl.acm.org/doi/10.1109/TITS.2016.2542131
Xu TWang D(2016)KCGS-Store: A Columnar Storage Based on Group Sorting of Key Columns2016 IEEE 9th International Conference on Cloud Computing (CLOUD)10.1109/CLOUD.2016.0041(244-251)Online publication date: Jun-2016
https://doi.org/10.1109/CLOUD.2016.0041
Olteanu DZávodný J(2015)Size Bounds for Factorised Representations of Query ResultsACM Transactions on Database Systems10.1145/265633540:1(1-44)Online publication date: 25-Mar-2015
https://dl.acm.org/doi/10.1145/2656335
Wang HLi FZhou XCao YQin XChen JWang S(2014)HC-StoreFrontiers of Computer Science: Selected Publications from Chinese Universities10.1007/s11704-014-3376-38:6(859-871)Online publication date: 1-Dec-2014
https://dl.acm.org/doi/10.1007/s11704-014-3376-3
Dehdouh KBentayeb FBoussaid OKabachi N(2014)Towards an OLAP Environment for Column-Oriented Data WarehousesData Warehousing and Knowledge Discovery10.1007/978-3-319-10160-6_20(221-232)Online publication date: 2014
https://doi.org/10.1007/978-3-319-10160-6_20
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents