ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

The Term Retrieval Machine.

Michael Ley: The Term Retrieval Machine. SIGMOD Conference 1992: 154-163
@inproceedings{DBLP:conf/sigmod/Ley92,
  author    = {Michael Ley},
  editor    = {Michael Stonebraker},
  title     = {The Term Retrieval Machine},
  booktitle = {Proceedings of the 1992 ACM SIGMOD International Conference on
               Management of Data, San Diego, California, June 2-5, 1992},
  publisher = {ACM Press},
  year      = {1992},
  pages     = {154-163},
  ee        = {http://doi.acm.org/10.1145/130283.130309, db/conf/sigmod/Ley92.html},
  crossref  = {DBLP:conf/sigmod/92},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Scans through large collections of complex objects often cannot be avoided. Even if sophisticated indexing mechanisms are provided, it may be necessary to evaluate simple predicates against data stored on disk for filtering. For traditional record oriented data models i/o and buffer management are the main bottlenecks for this operation, the interpretation of data structures is straightforward and usually not an important cost factor. For heterogeneously shaped complex objects it may become a dominant cost factor.

In this paper we demonstrate a technique to make data structure traversal inside of complex objects much cheaper than naive interpretation. We compile navigation necessary to evaluate condition predicates and physical schema information into a program to be executed by a specialized abstract machine. Our approach is demonstrated for the Feature Term Data Model (FTDM), but the technique is applicable to many other complex data models. Main parts of this paper are dedicated to the method we used to design the Term Retrieval Abstract Machine (TRAM) architecture by partial evaluation of a tuned interpreter.

Copyright © 1992 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.


ACM SIGMOD Anthology

Online Version (ACM WWW Account required): Full Text in PDF Format

CDROM Version: Load the CDROM "Volume 1 Issue 2, SIGMOD '75-'92" and ...

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Printed Edition

Michael Stonebraker (Ed.): Proceedings of the 1992 ACM SIGMOD International Conference on Management of Data, San Diego, California, June 2-5, 1992. ACM Press 1992 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML, SIGMOD Record 21(2), June 1992
Contents

Online Edition: ACM Digital Library

[Abstract and Index Terms]
[Full Text in PDF Format, 1189 KB]

References

[1]
Hassan Aït-Kaci: Warren's Abstract Machine: A Tutorial Reconstruction. MIT Press 1991, ISBN 0-262-01123-9
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[2]
Jay Banerjee, Won Kim, Sung-Jo Kim, Jorge F. Garza: Clustering a DAG for CAD Databases. IEEE Trans. Software Eng. 14(11): 1684-1699(1988) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[3]
...
[4]
Dina Bitton, David J. DeWitt, Carolyn Turbyfill: Benchmarking Database Systems A Systematic Approach. VLDB 1983: 8-19 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[5]
Ellis E. Chang, Randy H. Katz: Exploiting Inheritance and Structure Semantics for Effective Clustering and Buffering in an Object-Oriented DBMS. SIGMOD Conference 1989: 348-357 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[6]
Jia-bing R. Cheng, Ali R. Hurson: Effective Clustering of Complex Objects in Object-Oriented Databases. SIGMOD Conference 1991: 22-31 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[7]
Jacques Cohen, Timothy J. Hickey: Parsing and Compiling Using Prolog. ACM Trans. Program. Lang. Syst. 9(2): 125-163(1987) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[8]
Peter Dadam, Klaus Küspert, F. Andersen, Henk M. Blanken, R. Erbe, Jürgen Günauer, Vincent Y. Lum, Peter Pistor, Georg Walch: A DBMS Prototype to Support Extended NF2 Relations: An Integrated View on Flat Tables and Hierarchies. SIGMOD Conference 1986: 356-367 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[9]
O. Deux: The Story of O2. IEEE Trans. Knowl. Data Eng. 2(1): 91-108(1990) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[10]
Pamela Drew, Roger King, Scott E. Hudson: The Performance and Utility of the Cactis Implementation Algorithms. VLDB 1990: 135-147 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[11]
...
[12]
...
[13]
Jim Gray, Andreas Reuter: Transaction Processing: Concepts and Techniques. Morgan Kaufmann 1993, ISBN 1-55860-190-2
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[14]
Christopher T. Haynes: Logic Continuations. J. Log. Program. 4(2): 157-176(1987) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[15]
...
[16]
John Joseph, Satish M. Thatte, Craig W. Thompson, David L. Wells: Report on the Object-Oriented Database Workshop, Held in Conjuction with OOPSLA '88. SIGMOD Record 18(3): 78-101(1989) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[17]
Thomas Keller, Goetz Graefe, David Maier: Efficient Assembly of Complex Objects. SIGMOD Conference 1991: 148-157 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[18]
Won Kim, Jay Banerjee, Hong-Tai Chou, Jorge F. Garza, Darrell Woelk: Composite Object Support in an Object-Oriented Database System. OOPSLA 1987: 118-125 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[19]
Won Kim, Hong-Tai Chou, Jay Banerjee: Operations and Implementation of Complex Objects. IEEE Trans. Software Eng. 14(7): 985-996(1988) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[20]
Won Kim, Jorge F. Garza, Nat Ballou, Darrell Woelk: Architecture of the ORION Next-Generation Database System. IEEE Trans. Knowl. Data Eng. 2(1): 109-124(1990) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[21]
...
[22]
Setrag Khoshafian, Michael J. Franklin, Michael J. Carey: Storage management for persistent complex objects. Inf. Syst. 15(3): 303-320(1990) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[23]
Peter Kursawe: How to Invent a Prolog Machine. ICLP 1986: 134-148 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[24]
...
[25]
Michael Ley, Bernd Walter: Der LILOG-DB-Fact-Manager: Ein Datenbankkern zur Speicherung variabel strukturierter komplexer Objekte. Inform., Forsch. Entwickl. 5(4): 188-201(1990) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[26]
Thomas Ludwig: A Brief Overview of LILOG-DB. ICDE 1990: 420-427 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[27]
Thomas Ludwig: Query Processing in LILOG-DB: What It Is and Where It Goes. BTW 1991: 271-287 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[28]
Thomas Ludwig, Bernd Walter: EFTA: A Database Retrieval Algebra for Feature-Terms. Data Knowl. Eng. 6: 125-149(1991) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[29]
...
[30]
Christopher Mills, Stanley C. Ahalt, James E. Fowler: Compiled Instruction Set Simulation. Softw., Pract. Exper. 21(8): 877-889(1991) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[31]
...
[32]
Hans-Jörg Schek, H.-Bernhard Paul, Marc H. Scholl, Gerhard Weikum: The DASDBS Project: Objectives, Experiences, and Future Prospects. IEEE Trans. Knowl. Data Eng. 2(1): 25-43(1990) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[33]
...
[34]
Manolis M. Tsangaris, Jeffrey F. Naughton: A Stochastic Approach for Clustering in Object Bases. SIGMOD Conference 1991: 12-21 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[35]
David H. D. Warren: Logic Programming and Compiler Writing. Softw., Pract. Exper. 10(2): 97-125(1980) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[36]
...

Copyright © Fri Mar 12 17:21:30 2010 by Michael Ley (ley@uni-trier.de)