Cited By
View all- Walter BBenzschawel S(2005)Complex structures in (deductive) database systems: Variables and open property setsManagement and Processing of Complex Data Structures10.1007/3-540-57802-1_1(1-21)Online publication date: 28-May-2005
The term retrieval abstract machine
Author: 
Michael LeyAuthors Info & Claims
Abstract
Scans through large collections of complex objects often cannot be avoided. Even if sohphisticated 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.
References
[1]
H. Ait-Kaci: Warren's Abstract Machine, A Tutorial Reconstruction. MIT Press, 1991
[2]
J. Banerjee, W. Kim, S.-J. Kim, J.F. Garza: Cluster/ng a DAG for CAD Databases. IEEE Trans. Software Eng., vo1.14, no.11, Nov. 1988, 1684-1699
[3]
S. Benzschawel, E. Gehlen, M. Ley, T. Ludwig, A. Maier, B. Walter: LILOG-DB: Database Support for Knowledge Based Systems. in {15}, 501-594
[4]
D. Bitton, D.J. DeWitt, C. TurbO: Benchmarking Database Systems, a Systematic Approach. VLDB 1983, 8-19
[5]
E.g. Chang, R.H. Katz: Exploiting Inheritance and Structure Semantics/'or Effective Clustering and Buffering in an Object-Oriented DBMS. SIGMOD Conf. 89, 348-357
[6]
J.-b. R. Cheng, A.R. Hurson: Effective Clustering of Complex Objects in Object-Oriented Databases. SIGMOD Conf. 1991, 22-31
[7]
J. Cohen, T.J. Hickey: Parsing and Compiling Using Prolog. ACM Trans. Programming Languages and Systems, vol.9, no.2, April 1987', 125-163
[8]
P. Dadam et al.: A DBMS Prototype ~o Support Extended NF2 Relations: An Integrated View on Flat Tables and Hierarchies. SIGMOD Conf. 1986, 356-367
[9]
O. Deux et al.: The S~ory of 02. IEEE Trans. Knowledge and Data Eng., vo}.2, no.l, Mvxch 1990, 91-108
[10]
P. Drew, R. King: The PenCormanceand Utility o{ the Cactis Implementation Algorithms. VLDB 1990, 135-147
[11]
A.P. Ershov et al. (eds.): Selected Papers from the Workshop on Partial Evaluation and Mixed Computation, A vern~es, Denmark, October 1987. Special issue of: New Generation Computing, vol.6, nos.2,3, 1988
[12]
S.L. Graham, P.B. Kessler, M.K. McKusick:. gprof: a Call Graph Execution ProFder. Proceedings of the SIGPLAN'82 Symposium on Compiler Construction, SIGPLAN Notices, vol.17, no.6, 120-126, June 1982
[13]
J. Gray, A. Reuter: Transaction Processing: Concepts and Techniques. To be published by Morgan-Kaufman, San Mateo, CA, 1992
[14]
C.T. Haynes: Logic Continuations. Journal of Logic Prograxnming, vol.4, no.2, June-1987, 157-176
[15]
O. Herzog, C.-R. Rollinger (E<ts.): Text Understanding in LILOG. Lecture Notes in Computer Science, vol.546, Springer 1991
[16]
J. Joseph, S. Thatte, C. Thompson, D. Wells: Report on the Object-Oriented Database Workshop, held in conjunction with OOPLSA'88. SIGMOD Record, vo1.18, no.3, Sept. 1989, 78-101
[17]
T. Keller, G. Grbefe, D. Maier: Efficient Assembly of Complex Objects. SIGMOD Conf. 1991, 148-157
[18]
W. Kim, J~ Banerjee, H.-T. Chou, J.F. Garza, D. Woelk: Composite Object Support in an Object-Oriented Database System. OOPSLA'87 Proceedings, SIGPLAN Notices, vol.22, no.12, Dec. 1987, 118-125
[19]
W. Kim, H.-T. Chou, J. Banerjee: Operations and Implementation of Complex Objects. IEEE Trans. Software Eng., vo1.14, no.?, July 1988, 985-996
[20]
W. Kim, J.F. Garza, N. Ballou, D. Woe}k: Arch/tecture of the ORION Next-Generation Database System. IEEE Trans. Knowledge and Data Eng., vol.2, no.l, March 1990, 109-124
[21]
M. Klein: Leistungsanalyse des Datenbanksystems LILOG- DB. IBM, IWBS Report, 1991 (in German)
[22]
S. Khoshafian, M.J. Franklin, M.J. Carey: Storage Management/'or Persistent Complex Objects. Information Systems, voi.15, no.3, 1990, 303-320
[23]
P. Kursawe: How to Invent a Prolog Machine. Third Int. Conf. on Logic Programming, London 1986, Lecture Notes in Computer Science, vol.225, Springer 1986, 134-148
[24]
M. Ley: Low Level Main Memory Management in LILOG- DB -- notes from the implementation underground. Submitted for publication, 1991
[25]
M. Le~, B. Walter: Der LILOG-DB-Fact-Manager: gin Datenbankkern zur Speicherung variabel strukturiertex komplexer Objekte. Informatik Forsch. Entw., vol.5, 1990, 188- 201 (in German)
[26]
T. Ludwig: A Brie{ Overview of LILOG-DB. in: Proc. of 6th Data Eng. Conf., L.A. 1990, 420-426
[27]
T. Ludwig: Query Processing in LILOG-DB: What It is and Where it Goes. Datenbanksysteme in Bftro, Technik und Wissenschaft, Gi-Fac~htagung Kaiserslautern, M~z 1991, Informatik-Fachberichte, Bd.2?0, 271-287', Springer
[28]
T. Ludwig, B. Walter: EFTA: a database retrieval algebra for/.eature-terms. Data & Knowledge Engineering, vol.6, 1991, 125-149
[29]
A. Maier, M. Ley, E. Gehlen: Sort Processing in a Deductive Database System. IBM, IWBS Report 154, 1991
[30]
C. Mills, S.C. Ahalt, J. Fowler: Compiled Instruction Set Simulation. Software -- Practice and Experience, vol.21, no.8, August 1991, 877-889
[31]
Proceedings of the Symposium on Partial Evaluation and Semantics-Based Program Manipulation, PEPM'91, Yale University, New Haven, CT, USA, June 17-19, 1991. SIG- PLAN Notices, vol.26, no.9, Sept. 1991
[32]
H.-J. Schek, H.-B. Paul, M.H. Scholl, G. Weikum: The DASDBS Project: Objectives, Experiences, and Future Prospects. IEEE Trans. Knowledge and Data Eng., vol.2, no.l, March 1990, 25-43
[33]
S. Thatte: Report on the Object-Oriented Database Workshop: Implementation Aspects, held in conjunction with OOPSLA '87. SIGPLAN Notices, vol.23, no.5, May 1988, 73- 87
[34]
M.M. Tsangaris, J.F. Naughton: A Stochastic Approach {or Clustering in Object Bases. SIGMOD Conf. 1991, 12-21
[35]
D.H.D. Warren: Logic Programming and Compiler Writing. Software- Practice and Experience, vol.10, 1980, 97-125
[36]
D.H.D. Warren: An Abstract Prolog Instruction Set. Technical Note 309, Artificial Intelligence Center, SRI Intern~ tional, Menlo Park, CA, October 1983
Index Terms
- The term retrieval abstract machine
Recommendations
The term retrieval abstract machine
SIGMOD '92: Proceedings of the 1992 ACM SIGMOD international conference on Management of dataScans through large collections of complex objects often cannot be avoided. Even if sohphisticated indexing mechanisms are provided, it may be necessary to evaluate simple predicates against data stored on disk for filtering. For traditional record ...
Term distillation in patent retrieval
PATENT '03: Proceedings of the ACL-2003 workshop on Patent corpus processing - Volume 20In cross-database retrieval, the domain of queries differs from that of the retrieval target in the distribution of term occurrences. This causes incorrect term weighting in the retrieval system which assigns to each term a retrieval weight based on the ...
Term weighting for information retrieval based on term's discrimination power
One of the most important research topics in Information Retrieval is term weighting for document ranking and retrieval, such as TFIDF, BM25, etc. We propose a term weighting method that utilizes past retrieval results consisting of the queries that ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
June 1, 1992
415 pages
Copyright © 1992 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: 01 June 1992
Published in SIGMOD Volume 21, Issue 2
Check for updates
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 160Total Downloads
- Downloads (Last 12 months)98
- Downloads (Last 6 weeks)17
Reflects downloads up to 02 Mar 2025
Other Metrics
Citations
Cited By
View all- Walter BBenzschawel S(2005)Complex structures in (deductive) database systems: Variables and open property setsManagement and Processing of Complex Data Structures10.1007/3-540-57802-1_1(1-21)Online publication date: 28-May-2005
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in