GC-Consistent Cuts of Databases

Marcin Skubiszewski 1 Nicolas Porteix
1 RODIN - Database Systems
Inria Paris-Rocquencourt
Abstract : We introduce a new method for concurrent garbage collection in object-oriented databases. For this purpose, we define a {\em cut} of a database to be a collection containing one or more copies of every page in the database; the copies may have been made at different times during the operation of the database. We define a class of cuts called {\em GC-consistent cuts}, and prove formally that a garbage collector can correctly determine which objects to delete by examining a GC-consistent cut of a database instead of the database itself. We show that GC-consistent cuts can synchronize the concurrent collector with the mutator, \ie perform the task usually assigned to a write barrier: while a database is in operation, a GC-consistent cut of it can be built in an efficient and inobtrusive way, and, while still under construction, can be used by a garbage collector. We investigate other fundamental properties of GC-consistent cuts. We compare their consistency properties with those of causal cuts of distributed systems. We show that although the reachability of objects in a GC-consistent cut is inherited from the underlying database, many other interesting properties of the cut are unrelated to those of the database; this weak consistency is related to the low cost of building GC-consistent cuts.
Type de document :
[Research Report] RR-2681, INRIA. 1995
Liste complète des métadonnées

Littérature citée [23 références]  Voir  Masquer  Télécharger

Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 14:17:22
Dernière modification le : vendredi 25 mai 2018 - 12:02:05
Document(s) archivé(s) le : lundi 5 avril 2010 - 00:03:25



  • HAL Id : inria-00074010, version 1



Marcin Skubiszewski, Nicolas Porteix. GC-Consistent Cuts of Databases. [Research Report] RR-2681, INRIA. 1995. 〈inria-00074010〉



Consultations de la notice


Téléchargements de fichiers