Garbage Collection in Object Oriented Databases Using Transactional Cyclic Reference Counting

Garbage collection is important in object-oriented databases to free the programmer from explicitly deallocating memory. In this paper, we present a garbage collection al-gorithm, called Transactional Cyclic Refer-ence Counting (TCRC), for object oriented databases. The algorithm is based on a vari-ant of a reference counting algorithm pro-posed for functional programming languages The algorithm keeps track of auxiliary refer-ence count information to detect and collect cyclic garbage. The algorithm works correctly in the presence of concurrently running trans-actions, and system failures. It does not ob-t,ain 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 re-writt#en. Finally, it exploit,s schema informa-tion, if available, to reduce costs. We have im-plemented the TCRC algorithm and present results of a performance study of the imple-mentation