GARBAGE COLLECTION IN OBJECT-ORIENTED DATABASES USING TRANSACTIONAL CYCLIC REFERENCE COUNTING

Garbage collection is important in object-oriented databases to free t he programmer from explicitly deallocating memory. In this paper, we p resent a garbage collection algorithm, called Transactional Cyclic Ref erence Counting (TCRC), for object-oriented databases. The algorithm i s based on a variant of a reference-counting algorithm proposed for fu nctional programming languages The algorithm keeps track of auxiliary reference count information to detect and collect cyclic garbage. The algorithm works correctly in the presence of concurrently running tran sactions, and system failures. It does not obtain any long-term locks, thereby minimizing interference with transaction processing. It uses recovery subsystem logs to detect pointer updates; thus, existing code need not be rewritten. Finally, it exploits schema information, if av ailable, to reduce costs. We have implemented the TCRC algorithm and p resent results of a performance study of the implementation.