In a database management system (DBMS), partial rollback is an important mechanism for canceling only part of the operations executed in a transaction back to a savepoint. Partial rollback complicates buffer management because it should restore the state of the buffers as well as that of the database. Several relational DBMSs (RDBMSs) currently provide this mechanism using page buffers. However, object-oriented or object-relational DBMSs (OO/ORDBMSs) cannot utilize the partial rollback scheme of RDBMSs as is because, unlike RDBMSs, many of them use a dual buffer consisting of an object buffer and a page buffer. In this paper, we propose a thorough study of partial rollback schemes of OO/ORDBMSs with a dual buffer. First, we classify the partial rollback schemes of OO/ORDBMSs into a single buffer-based scheme and a dual buffer-based scheme by the number of buffers used to process rollback. Next, we propose four alternative partial rollback schemes: a page buffer-based scheme, an object buffer-based scheme, a dual buffer-based scheme using a soft log, and a dual buffer-based scheme using shadows. We then evaluate their performance through simulations. The results show that the dual buffer-based partial rollback scheme using shadows provides the best performance. Partial rollback in OO/ORDBMS has not been addressed in the literature; yet, it is a useful mechanism that must be implemented. The proposed schemes are practical ones that can be implemented in such DBMSs.

Web caching is an important technique for accelerating Web applications and reducing the load on the Web server and the network through local cache accesses. As in traditional data caching, Web caching poses the well-recognized problem of maintaining cache consistency. Web caching, however, has the advantage of delaying the refreshment of caches when the Web server updates the original data, i.e., Web caching tries to get better performance allowing tolerable inconsistency. This weak consistency requirement introduced the concept of time-to-live (TTL: the time during which the cached data item is expected to be valid) in the face of future updates. Subsequently, a number of methods have been invented to have the cache server estimate the TTL. However, the two well-known TTL estimation methods - the fixed TTL method and the heuristic method - do not allow intuitive understanding of the estimation processes and lack theoretical reasoning behind them, disallowing administrators from configuring the cache server by their intention. To mend these deficiencies, we propose the update-risk based TTL estimation method. This method uses a formal, yet intuitive, approach based on probabilistic analysis. In the proposed method, users provide the update risk as the probability that the original data will be updated within the estimated TTL. Then, based on our model, the cache server calculates the value of TTL using the update risk. The results of our experiments, performed using logs of a real cache server, show experimentally that the measured update risk closely matches that used to estimate TTL. Moreover, the notion of update risk is clear in its intention and semantics. These confirm the superiority of our method to conventional ones. We also show the impact of update risk on performance and consistency in order to help administrators select an appropriate value for update risk to obtain performance and consistency desired. In addition, we reassess the two aforementioned conventional methods in light of our method.

Ray tracing requires many ray-object intersection tests. A way of reducing the number of ray-object intersection tests is to subdivide the space occupied by objects into many nonoverlapping subregions, called voxels, and to construct an octree for the subdivided space. We propose the Octree-R, an octree-variant data structure for efficient ray tracing. The algorithm for constructing the Octree-R first estimates the number of ray-object intersection tests. Then, it partitions the space along the plane that minimizes the estimated number of ray-object intersection tests. We present the results of experiments for verifying the effectiveness of the Octree-R. In the experiment, the Octree-R provides a 4% to 47% performance gain over the conventional octree. The result shows the more skewed the object distribution (as is typical for real data), the more performance gain the Octree-R achieves.