Development and evaluation of multidatabase schedulers

Abstract

The autonomy of local database systems in multidatabase environment poses consistency problems in transaction scheduling. Several approaches have been proposed to overcome this problem. In this thesis, we consider the algorithms using two major scheduling approaches. The aggressive approach submits transaction concurrently, but, to ensure the consistency, transactions may have to be aborted and restarted several times. The other approach is serial (or near serial) submission that ensures consistent ordering of transactions. This prevents subsequent aborts. Two serial schedulers using serial submission approach are developed in this thesis and the results are compared with the best known aggressive "Ticket Method" algorithm. A generic simulator is developed using SMS libraries to implement and evaluate the schedulers. First, the aggressive approach used by Ticket Method is problematic because it does not provide any load control. Second, tuning the Ticket Method is extremely difficult and it does not react well to changes in the load on the local databases. Lastly, the overheads due to rollback and re-executions of this aggressive algorithm makes it less feasible. In this simulation study our serial schedulers perform much better than the Ticket Method in terms of residence time and number of aborts under different levels of load in local databases. This study suggests that it is worthwhile to concentrate on developing schedulers that submit transactions to guarantee that they will not be aborted at the cost of less concurrency.