The Term Retrieval Machine.

@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

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

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the CD and click on the path of your mount point:
  /Anthology/smod7592 or /cdrom

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD1 or /dvd

Printed Edition

Online Edition: ACM Digital Library

References

[1]

Hassan Aït-Kaci: Warren's Abstract Machine: A Tutorial Reconstruction. MIT Press 1991, ISBN 0-262-01123-9
BibTeX

[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) BibTeX

[3]

...

[4]

Dina Bitton, David J. DeWitt, Carolyn Turbyfill: Benchmarking Database Systems A Systematic Approach. VLDB 1983: 8-19 BibTeX

[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 BibTeX

[6]

Jia-bing R. Cheng, Ali R. Hurson: Effective Clustering of Complex Objects in Object-Oriented Databases. SIGMOD Conference 1991: 22-31 BibTeX

[7]

Jacques Cohen, Timothy J. Hickey: Parsing and Compiling Using Prolog. ACM Trans. Program. Lang. Syst. 9(2): 125-163(1987) BibTeX

[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 BibTeX

[9]

O. Deux: The Story of O2. IEEE Trans. Knowl. Data Eng. 2(1): 91-108(1990) BibTeX

[10]

Pamela Drew, Roger King, Scott E. Hudson: The Performance and Utility of the Cactis Implementation Algorithms. VLDB 1990: 135-147 BibTeX

[11]

...

[12]

...

[13]

Jim Gray, Andreas Reuter: Transaction Processing: Concepts and Techniques. Morgan Kaufmann 1993, ISBN 1-55860-190-2
Contents BibTeX

[14]

Christopher T. Haynes: Logic Continuations. J. Log. Program. 4(2): 157-176(1987) BibTeX

[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) BibTeX

[17]

Thomas Keller, Goetz Graefe, David Maier: Efficient Assembly of Complex Objects. SIGMOD Conference 1991: 148-157 BibTeX

[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 BibTeX

[19]

Won Kim, Hong-Tai Chou, Jay Banerjee: Operations and Implementation of Complex Objects. IEEE Trans. Software Eng. 14(7): 985-996(1988) BibTeX

[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) BibTeX

[21]

...

[22]

Setrag Khoshafian, Michael J. Franklin, Michael J. Carey: Storage management for persistent complex objects. Inf. Syst. 15(3): 303-320(1990) BibTeX

[23]

Peter Kursawe: How to Invent a Prolog Machine. ICLP 1986: 134-148 BibTeX

[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) BibTeX

[26]

Thomas Ludwig: A Brief Overview of LILOG-DB. ICDE 1990: 420-427 BibTeX

[27]

Thomas Ludwig: Query Processing in LILOG-DB: What It Is and Where It Goes. BTW 1991: 271-287 BibTeX

[28]

Thomas Ludwig, Bernd Walter: EFTA: A Database Retrieval Algebra for Feature-Terms. Data Knowl. Eng. 6: 125-149(1991) BibTeX

[29]

...

[30]

Christopher Mills, Stanley C. Ahalt, James E. Fowler: Compiled Instruction Set Simulation. Softw., Pract. Exper. 21(8): 877-889(1991) BibTeX

[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) BibTeX

[33]

...

[34]

Manolis M. Tsangaris, Jeffrey F. Naughton: A Stochastic Approach for Clustering in Object Bases. SIGMOD Conference 1991: 12-21 BibTeX

[35]

David H. D. Warren: Logic Programming and Compiler Writing. Softw., Pract. Exper. 10(2): 97-125(1980) BibTeX

[36]

...