Hierarchical timestamping algorithm

摘要

The Hierarchical Timestamping Algorithm is proposed for handling database concurrency control. By analyzing transaction conflicts and partitioning the data base into hierarchical partitions to which transactions will access discriminantly using different synchronization protocols, the algorithm can offer significant performance gain. It also reduces the need for transactions to leave traces (e.g. locks, timestamps) when accessing a data element. It is shown that the algorithm is correct in terms of transaction serializability. This is done by showing that the algorithm enforces a topological order among transactions. This research advocates the potential benefit of application analysis in enhancing performance of concurrency control algorithms where the level of concurrency is vital to system performance.