Garbage collection in objectoriented databases using transactional cyclic reference counting

Abstract. Garbage collection is important in object-oriented databases to free the programmer from explicitly deallocat-ing memory. In this paper, we present a garbage collec-tion algorithm, called Transactional Cyclic Reference Count-ing (TCRC), for object-oriented databases. The algorithm is based on a variant of a reference-counting algorithm pro-posed for functional programming languages The algorithm keeps track of auxiliary reference count information to de-tect and collect cyclic garbage. The algorithm works cor-rectly in the presence of concurrently running transactions, 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 available, to reduce costs. We have implemented the TCRC algorithm and present results of a performance study of the implementation.