Persistent caching: an implementation technique for complex objects with object identity

Many recent complex object database systems support the concepts of object identity and object identifier. Following an object identifier to access the referenced object is called navigation operation and is an essential operation in dealing with complex objects. Navigation operation is a difficult operation to implement efficiently since every navigation operation inherently causes one disk access operation. A scheme to notably accelerate the navigation operation among a sea of complex objects, by increasing the effective number of objects in one disk page is proposed. The main concept of the presented technique is threefold. The first idea is to store a cached value within a complex object that is referencing another complex object. The second is that when the referenced object is to be updated the update propagation is delayed until the time when the cached value is referenced. The third is to utilize a hashed table on main memory to efficiently validate the consistency between the cached values and the original values