article

Free access

Optimizing queries on files

Authors:

Mariano P. Consens,

Tova MiloAuthors Info & Claims

ACM SIGMOD Record, Volume 23, Issue 2

Pages 301 - 312

https://doi.org/10.1145/191843.191898

Published: 24 May 1994 Publication History

Abstract

We present a framework which allows the user to access and manipulate data uniformly, regardless of whether it resides in a database or in the file system (or in both). A key issue is the performance of the system. We show that text indexing, combined with newly developed optimization techniques, can be used to provide an efficient high level interface to information stored in files. Furthermore, using these techniques, some queries can be evaluated significantly faster than in standard database implementations. We also study the tradeoff between efficiency and the amount of indexing.

References

[1]

S. Abiteboul, S. Cluet, and T. Milo. Querying and updating the file. In Proc. of the 19th Int. Conf. on Very Large Databases, VLDB93, pages 73-84, 1993.

Digital Library

[2]

A.V. Aho and S. C. Johnson. Programming utilities and libraries LR parsing. Computing Surveys, June 1974.

Digital Library

[3]

F. Bancilhon, S. Cluet, and C. Delobel. Query languages for object-oriented database systems: the 02 proposal, in Proc. DBPL, Salishan Lodge, Oregon, June 1989.

Digital Library

[4]

E. Bertino. A Survey of Indexing Techniques for Object-Oriented Database Management Systems. In Freytag# J. and Maier, D. and Vossen, G., editor, Query Processing for Advanced Database Systems, pages 383-418, San Mateo, CA, 1994. Morgan Kaufmann.

[5]

T.F. Bowen, G. Gopal, G. Herman, T. Hickey, K. C. Lee, W. H. Mansfield, J. Raitz, and A. Weinrib. The Datacycle architecture. Communications of the A CM, 35(12):71-81, December 1992.

Digital Library

[6]

D. Barbara, H. Garcia-Molia, and S. Mehrota. The gold mailer, in IEEE Data Eng., pages 92- 99, 1993.

Digital Library

[7]

F.J. Burkowski. Retrieval activities in a database consisting of heterogeneous collections of structured text. in Proc. of the 15th. SIGIR Conference, pages 112-125, 1992.

Digital Library

[8]

M. Consens and A. Mendelzon. GraphLog: a visual formalism for real life recursion. In Proceedings of the Ninth A CM SIGA CT-SIGMOD Symposium on Principles of Database Systems, pages 404-416, 1990.

Digital Library

[9]

M. Gonsens and A. Mendelzon. Hy: A hygraphbased query and visualization system. In Proceedings of the A CM-SIGMOD 1993 Annual Conference on Management of Data, pages 511- 516, 1993.

Digital Library

[10]

Mariano P. Consens. Graphlog: "real life" recursive queries using graphs. Master's thesis, Department of Computer Science, University of Toronto, January 1989.

[11]

D. Goldberg, D. Nichols, B. M. Oki, and D. Terry. Using collaborative filtering to weave an information tapestry. CA CM, 35(12), December 1992.

Digital Library

[12]

G. Gonnet. Examples of PAT applied to the Oxford English Dictionary. Technical Report OED-87-02, University of Waterloo, 1987.

[13]

G. Gonnet and F. Tompa. Mind your grammar: a new approach to modelling text. In Proc. of the 13th Int. Conf. on Very Large Databases, pages 339-346, 1987.

Digital Library

[14]

M. Kifer, W. Kim, and Y. Sagiv. Querying object-oriented databases, in Proc. SIGMOD, San-Diego, 1992.

Digital Library

[15]

P. Kilpel#inen and H. Mannila. Retrieval from hierarchical texts by partial patterns. In Proc. of the 15th. SIGIR Conference, 1993.

Digital Library

[16]

L. Lamport. LaTeX: A Document Preparation System. Addison-Wesley, Reading, MA, 1985.

Digital Library

[17]

J. Mylopoulos, P. A. Bernstein, and H. K. T Wong. A language facility for designing database-intensive applications. A CM Transactions on Database Systems, 5(2), 1980.

Digital Library

[18]

Open Text Corporation. PAT Reference Manual and Tutorial, 1993.

[19]

A. Paepcke. An object oriented view onto public hetrogeneous text databases. In IEEE Data Eng., page 484, 1993.

Digital Library

[20]

M.F. Schwartz. Internet Resource Discovery at the University of Colorado. IEEE Computer Networking, 26(9), September 1993.

Digital Library

[21]

R. Sethi. Testing for Church-Rosser Property. JACM, 21(4), October 1974.

Digital Library

[22]

K. Shoens, A. Luniewski, P. Schwartz, J. Stamos, and J. Thomas. The Rofus system: Information organization for semi-structured data. In Proc. of the 19th Int. conf. on Very Large Databases, VLDB 93, pages 97-107, 1993.

Digital Library

[23]

G Salton and M. J. McGill. Introduction to modern information retrieval. McGraw-Hill, 1983.

Digital Library

[24]

A. Salminen and F. W. Tompa. PAT expressions: an algebra for text search. In Papers in Computational Lexicography: COMPLEX'92, pages 309-332, 1992.

[25]

A. Yeung. Text Searching in the Hy+ Visualization System. Master's thesis, Department of Computer Science, University of Toronto, October 1993.

Cited By

Consens M(2018)Structural IndexingEncyclopedia of Database Systems10.1007/978-1-4614-8265-9_376(3813-3818)Online publication date: 7-Dec-2018
https://doi.org/10.1007/978-1-4614-8265-9_376
Consens M(2017)Structural IndexingEncyclopedia of Database Systems10.1007/978-1-4899-7993-3_376-2(1-6)Online publication date: 12-Jan-2017
https://doi.org/10.1007/978-1-4899-7993-3_376-2
Lee SRyu BWu K(2012)Examining the impact of data-access cost on XML twig pattern matchingInformation Sciences: an International Journal10.1016/j.ins.2012.03.011203(24-43)Online publication date: 1-Oct-2012
https://dl.acm.org/doi/10.1016/j.ins.2012.03.011
Show More Cited By

Index Terms

Recommendations

Optimizing queries on files
SIGMOD '94: Proceedings of the 1994 ACM SIGMOD international conference on Management of data

We present a framework which allows the user to access and manipulate data uniformly, regardless of whether it resides in a database or in the file system (or in both). A key issue is the performance of the system. We show that text indexing, combined ...
Large files, small writes, and pNFS
ICS '06: Proceedings of the 20th annual international conference on Supercomputing

Workload characterization studies highlight the prevalence of small and sequential data requests in scientific applications. Parallel file systems excel at large data transfers but sometimes at the expense of small I/O performance. pNFS is an NFSv4.1 ...
Twin grid files: space optimizing access schemes

Storage access schemes for points, supporting spatial searching, usually suffer from an undesirably low storage space utilization. We show how a given set of points can be distributed among two grid files in such a way that storage space utilization is ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGMOD Record

ACM SIGMOD Record Volume 23, Issue 2

June 1994

522 pages

ISSN:0163-5808

DOI:10.1145/191843

Editors:
Richard Thomas Snodgrass
Univ. of Arizona
,
Marianne Winslett
Univ. of Illinois

Issue’s Table of Contents

SIGMOD '94: Proceedings of the 1994 ACM SIGMOD international conference on Management of data
May 1994
525 pages
ISBN:0897916395
DOI:10.1145/191839
Editors:
Richard Thomas Snodgrass
Univ. of Arizona
,
Marianne Winslett
Univ. of Illinois

Copyright © 1994 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 24 May 1994

Published in SIGMOD Volume 23, Issue 2

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

52
Total Citations
View Citations
596
Total Downloads

Downloads (Last 12 months)122
Downloads (Last 6 weeks)21

Reflects downloads up to 13 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Consens M(2018)Structural IndexingEncyclopedia of Database Systems10.1007/978-1-4614-8265-9_376(3813-3818)Online publication date: 7-Dec-2018
https://doi.org/10.1007/978-1-4614-8265-9_376
Consens M(2017)Structural IndexingEncyclopedia of Database Systems10.1007/978-1-4899-7993-3_376-2(1-6)Online publication date: 12-Jan-2017
https://doi.org/10.1007/978-1-4899-7993-3_376-2
Lee SRyu BWu K(2012)Examining the impact of data-access cost on XML twig pattern matchingInformation Sciences: an International Journal10.1016/j.ins.2012.03.011203(24-43)Online publication date: 1-Oct-2012
https://dl.acm.org/doi/10.1016/j.ins.2012.03.011
Consens M(2009)Structure IndexingEncyclopedia of Database Systems10.1007/978-0-387-39940-9_376(2857-2862)Online publication date: 2009
https://doi.org/10.1007/978-0-387-39940-9_376
Miliaraki IKaoudi ZKoubarakis MHuai JChen RHon HLiu YMa WTomkins AZhang X(2008)Xml data dissemination using automata on top of structured overlay networksProceedings of the 17th international conference on World Wide Web10.1145/1367497.1367614(865-874)Online publication date: 21-Apr-2008
https://dl.acm.org/doi/10.1145/1367497.1367614
Ling YSun WRishe NXiang X(1999)A Hybrid Estimator for Selectivity EstimationIEEE Transactions on Knowledge and Data Engineering10.1109/69.76166711:2(338-354)Online publication date: 1-Mar-1999
https://dl.acm.org/doi/10.1109/69.761667
Consens M(2018)Structural IndexingEncyclopedia of Database Systems10.1007/978-1-4614-8265-9_376(3813-3818)Online publication date: 7-Dec-2018
https://doi.org/10.1007/978-1-4614-8265-9_376
Consens M(2017)Structural IndexingEncyclopedia of Database Systems10.1007/978-1-4899-7993-3_376-2(1-6)Online publication date: 12-Jan-2017
https://doi.org/10.1007/978-1-4899-7993-3_376-2
Miliaraki IKoubarakis M(2012)FoXtrotACM Transactions on the Web10.1145/2344416.23444196:3(1-34)Online publication date: 2-Oct-2012
https://dl.acm.org/doi/10.1145/2344416.2344419
Ji JWang YLei KWang T(2012)Holistic twig joins based on Sketch Tree2012 9th International Conference on Fuzzy Systems and Knowledge Discovery10.1109/FSKD.2012.6233872(1191-1195)Online publication date: May-2012
https://doi.org/10.1109/FSKD.2012.6233872
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 Publication

Figures

Tables

Media

View Issue’s Table of Contents