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

Storage Reclamation in Object Oriented Database Systems.

Margaret H. Butler: Storage Reclamation in Object Oriented Database Systems. SIGMOD Conference 1987: 410-425
@inproceedings{DBLP:conf/sigmod/Butler87,
  author    = {Margaret H. Butler},
  editor    = {Umeshwar Dayal and
               Irving L. Traiger},
  title     = {Storage Reclamation in Object Oriented Database Systems},
  booktitle = {Proceedings of the Association for Computing Machinery Special
               Interest Group on Management of Data 1987 Annual Conference,
               San Francisco, California, May 27-29, 1987},
  publisher = {ACM Press},
  year      = {1987},
  pages     = {410-425},
  ee        = {http://doi.acm.org/10.1145/38713.38757, db/conf/sigmod/Butler87.html},
  crossref  = {DBLP:conf/sigmod/87},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

When providing data management for nontraditional data, database systems encounter storage reclamation problems similar to those encountered by virtual memory managers. The paging behavior of existing automatic storage reclamation schemes as applied to objects stored in a database management system is one indicator of the performance cost of various features of storage reclamation algorithms. The results of modeling the paging behavior suggest that Mark and Sweep causes many more input/output operations than Copy-Compact. A contributing factor to the expense of Mark and Sweep is that it does not recluster memory as does Copy-Compact. If memory is not reclustered, the average cost of accessing data can go up tremendously. Other algorithms that do not recluster memory also suffer performance problems, namely all reference counting schemes. The main advantage of a reference count scheme is that it does not force a running program to pause for a long period of time while reclamation takes place, it amortizes the cost of reclamation across all accesses. The reclustering of Copy-Compact and the cost amortization of Reference Count are combined to great advantage in Baker's algorithm. This algorithm proves to be the least prohibitive for operating on disk-based data.

Copyright © 1987 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 ... BibTeX

Printed Edition

Umeshwar Dayal, Irving L. Traiger (Eds.): Proceedings of the Association for Computing Machinery Special Interest Group on Management of Data 1987 Annual Conference, San Francisco, California, May 27-29, 1987. ACM Press 1987 BibTeX , SIGMOD Record 16(3)
Contents

Online Edition: ACM Digital Library


References

[Bake76]
Henry G. Baker Jr.: List Processing in Real Time on a Serial Computer. Commun. ACM 21(4): 280-294(1978) BibTeX
[Banc86a]
François Bancilhon, Setrag Khoshafian: A Calculus for Complex Objects. PODS 1986: 53-60 BibTeX
[Banc86b]
François Bancilhon, Raghu Ramakrishnan: An Amateur's Introduction to Recursive Query Processing Strategies. SIGMOD Conference 1986: 16-52 BibTeX
[Bobr79]
Daniel G. Bobrow, Douglas W. Clark: Compact Encodings of List Structure. ACM Trans. Program. Lang. Syst. 1(2): 266-286(1979) BibTeX
[Bobr86]
Daniel G. Bobrow, Kenneth M. Kahn, Gregor Kiczales, Larry Masinter, Mark Stefik, Frank Zdybel: CommonLoops: Merging Lisp and Object-Oriented Programming. OOPSLA 1986: 17-29 BibTeX
[Butl86a]
...
[Cock84]
W. Paul Cockshott, Malcolm P. Atkinson, Kenneth Chisholm, Peter J. Bailey, Ronald Morrison: Persistent Object Management System. Softw., Pract. Exper. 14(1): 49-71(1984) BibTeX
[Cohe81]
Jacques Cohen: Garbage Collection of Linked Data Structures. ACM Comput. Surv. 13(3): 341-367(1981) BibTeX
[Cope84]
George P. Copeland, David Maier: Making Smalltalk a Database System. SIGMOD Conference 1984: 316-325 BibTeX
[Derr85]
...
[Deut79]
L. Peter Deutsch, Daniel G. Bobrow: An Efficient, Incremental, Automatic Garbage Collector. Commun. ACM 19(9): 522-526(1976) BibTeX
[Gold83]
Adele Goldberg, David Robson: Smalltalk-80: The Language and Its Implementation. Addison-Wesley 1983
BibTeX
[Lieb83]
Henry Lieberman, Carl Hewitt: A Real-Time Garbage Collector Based on the Lifetimes of Objects. Commun. ACM 26(6): 419-429(1983) BibTeX
[Mins63]
...
[Mish84]
...
[Ston83]
...
[Ston86]
Michael Stonebraker, Lawrence A. Rowe: The Design of Postgres. SIGMOD Conference 1986: 340-355 BibTeX
[That85]
...
[Unga85]
David Ungar: Generation Scavenging: A Non-Disruptive High Performance Storage Reclamation Algorithm. Software Development Environments (SDE) 1984: 157-167 BibTeX
[Zani86]
Carlo Zaniolo, Hassan Aït-Kaci, David Beech, Stephanie J. Cammarata, David Maier: Object Oriented Database Systems and Knowledge Systems. Expert Database Workshop 1984: 49-65 BibTeX

Referenced by

  1. Jonathan E. Cook, Alexander L. Wolf, Benjamin G. Zorn: A Highly Effective Partition Selection Policy for Object Database Garbage Collection. IEEE Trans. Knowl. Data Eng. 10(1): 153-172(1998)
  2. Jonathan E. Cook, Artur Klauser, Alexander L. Wolf, Benjamin G. Zorn: Semi-automatic, Self-adaptive Control of Garbage Collection Rates in Object Databases. SIGMOD Conference 1996: 377-388
  3. Laurent Amsaleg, Michael J. Franklin, Olivier Gruber: Efficient Incremental Garbage Collection for Client-Server Object Database Systems. VLDB 1995: 42-53
  4. Jonathan E. Cook, Alexander L. Wolf, Benjamin G. Zorn: Partition Selection Policies in Object Database Garbage Collection. SIGMOD Conference 1994: 371-382
  5. Voon-Fee Yong, Jeffrey F. Naughton, Jie-Bing Yu: Storage Reclamation and Reorganization in Client-Server Persistent Object Stores. ICDE 1994: 120-131
  6. Lawrence Chung, Daniel Rios-Zertuche, Brian A. Nixon, John Mylopoulos: Process Management and Assertion Enforcement for a Semantic Data Model. EDBT 1988: 469-487
  7. Brian A. Nixon, John Mylopoulos: Integration Issues in Implementing Semantic Data Models. DBPL 1987: 187-217
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:39:50 2009