ACM SIGMOD Anthology TODS dblp.uni-trier.de

On Searching Transposed Files.

Don S. Batory: On Searching Transposed Files. ACM Trans. Database Syst. 4(4): 531-544(1979)
@article{DBLP:journals/tods/Batory79,
  author    = {Don S. Batory},
  title     = {On Searching Transposed Files},
  journal   = {ACM Trans. Database Syst.},
  volume    = {4},
  number    = {4},
  year      = {1979},
  pages     = {531-544},
  ee        = {http://doi.acm.org/10.1145/320107.320125, db/journals/tods/Batory79.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

A transposed file is a collection of nonsequential files called subfiles. Each subfile contains selected attribute data for alI 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 cr transposed files are shown to be NP-complete. Query processing performance comparisons of multilist, inverted, and nonsequential files with transposed files are also considered.

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.

Joint ACM SIGMOD / IEEE Computer Society Anthology

CDROM Version: Load the CDROM "Volume 3 Issue 1, TODS 1976-1990" and ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ... BibTeX

Conference Abstract

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

References

[1]
Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman: The Design and Analysis of Computer Algorithms. Addison-Wesley 1974, ISBN 0-201-00029-6
BibTeX
[2]
Jair M. Babad: A Record and File Partitioning Model. Commun. ACM 20(1): 22-31(1977) BibTeX
[3]
...
[4]
Mike W. Blasgen, Kapali P. Eswaran: Storage and Access in Relational Data Bases. IBM Systems Journal 16(4): 362-377(1977) BibTeX
[5]
...
[6]
P. A. Dearnley: A Model of a Self-Organising Data Management System. Comput. J. 17(1): 13-16(1974) BibTeX
[7]
Mark J. Eisner, Dennis G. Severance: Mathematical Techniques for Efficient Record Segmentation in Large Shared Databases. J. ACM 23(4): 619-635(1976) BibTeX
[8]
Frank Germano Jr., Stephen Weyl: A Data Base Organization to Support a Time-Oriented Medical Record. ACM Pacific 1975: 93-103 BibTeX
[9]
Michael Hammer, Arvola Chan: Index Selection in a Self-Adaptive Data Base Management System. SIGMOD Conference 1976: 1-8 BibTeX
[10]
...
[11]
Jeffrey A. Hoffer, Dennis G. Severance: The Use of Cluster Analysis in Physical Data Base Design. VLDB 1975: 69-86 BibTeX
[12]
...
[13]
...
[14]
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
[15]
...
[16]
...
[17]
...
[18]
...
[19]
Ben Shneiderman, Victor Goodman: Batched Searching of Sequential and Tree Structured Files. ACM Trans. Database Syst. 1(3): 268-275(1976) BibTeX
[20]
Peter M. Stocker, P. A. Dearnley: Self-Organising Data Management Systems. Comput. J. 16(2): 100-105(1973) BibTeX
[21]
...
[22]
...
[23]
S. Bing Yao: Approximating the Number of Accesses in Database Organizations. Commun. ACM 20(4): 260-261(1977) BibTeX
[24]
...

Referenced by

  1. Zhe Li, Kenneth A. Ross: Fast Joins Using Join Indices. VLDB J. 8(1): 1-24(1999)
  2. Lina Al-Jadir, Michel Léonard: Transposed Storage of an Object Database to Reduce the Cost of Schema Changes. ER (Workshops) 1999: 48-61
  3. Wee Keong Ng, Chinya V. Ravishankar: Block-Oriented Compression Techniques for Large Statistical Databases. IEEE Trans. Knowl. Data Eng. 9(2): 314-328(1997)
  4. Surajit Chaudhuri, Luis Gravano: Optimizing Queries over Multimedia Repositories. SIGMOD Conference 1996: 91-102
  5. Lina Al-Jadir, Thibault Estier, Gilles Falquet, Michel Léonard: Evolution Features of the F2 OODBMS. DASFAA 1995: 284-291
  6. Doron Rotem, Gerhard A. Schloss, Arie Segev: Data Allocation for Multi-Disk Databases. IEEE Trans. Knowl. Data Eng. 5(5): 882-887(1993)
  7. Robert L. Read, Donald S. Fussell, Abraham Silberschatz: A Multi-Resolution Relational Data Model. VLDB 1992: 139-150
  8. John L. Pfaltz, James C. French: Implementing Subscripted Identifiers in Scientific Databases. SSDBM 1990: 80-91
  9. Magnus Andersson, Per Svensson: A Study of Modified Interpolation Search in Compressed, Fully Transposed, Ordered Files. SSDBM 1988: 72-92
  10. Harry K. T. Wong, J. Z. Li: Transposition Algorithms on Very Large Compressed Databases. VLDB 1986: 304-311
  11. Patrick Valduriez, Setrag Khoshafian, George P. Copeland: Implementation Techniques of Complex Objects. VLDB 1986: 101-110
  12. Frank Olken, Doron Rotem: Rearranging Data to Maximize the Efficiency of Compression. PODS 1986: 78-90
  13. Don S. Batory: Modeling the Storage Architectures of Commercial Database Systems. ACM Trans. Database Syst. 10(4): 463-528(1985)
  14. Harry K. T. Wong, Hsiu-Fen Liu, Frank Olken, Doron Rotem, Linda Wong: Bit Transposed Files. VLDB 1985: 448-457
  15. Shinya Fushimi, Masaru Kitsuregawa, Masaya Nakayama, Hidehiko Tanaka, Tohru Moto-Oka: Algorithm and Performance Evaluation of Adaptive Multidimensional Clustering Technique. SIGMOD Conference 1985: 308-318
  16. George P. Copeland, Setrag Khoshafian: A Decomposition Storage Model. SIGMOD Conference 1985: 268-279
  17. Jürg Nievergelt, Hans Hinterberger, Kenneth C. Sevcik: The Grid File: An Adaptable, Symmetric Multikey File Structure. ACM Trans. Database Syst. 9(1): 38-71(1984)
  18. Salvatore T. March: Techniques for Structuring Database Records. ACM Comput. Surv. 15(1): 45-79(1983)
  19. Illka Karasalo, Per Svensson: An Overview of Cantor - A New System for Data Analysis. SSDBM 1983: 315-324
  20. Hamid Farsi, John Tartar: A Relational Database Machine for Efficient Processing of Statistical Queries. SSDBM 1983: 64-72
  21. Don S. Batory, C. C. Gotlieb: A Unifying Model of Physical Databases. ACM Trans. Database Syst. 7(4): 509-539(1982)
  22. Susan J. Eggers, Frank Olken, Arie Shoshani: A Compression Technique for Large Statistical Data-Bases. VLDB 1981: 424-434
  23. Robert A. Burnett, James J. Thomas: Data Management Support for Statistical Data Editing and Subset Selection. SSDBM 1981: 88-102
  24. Susan J. Eggers, Arie Shoshani: Efficient Access of Compressed Data. VLDB 1980: 205-211
  25. Per Svensson: On Search Performance for Conjunctive Queries in Compressed, Fully Transposed Ordered Files. VLDB 1979: 155-163
  26. Rudolf Munz: Design of the WELL System. ER 1979: 505-522
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
TODS, ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Tue Jun 24 18:38:42 2008