Heterogeneous database systems(HDBSs) are distributed database systems in which each site may use different data models, concurrency control methods, and deadlock detection methods, etc. In recent years, much research has focused on solving the concurrency control problems in HDBSs. However, the deadlock detection problem in HDBSs is yet to be unsolved, inspite of its importance. There are two principal methods for implementing deadlock detection in distributed database systems: graph constructing(or path pushing) method and edge chasing method. The basic idea underlying graph constructing method is to build some simplified form of global wait-for graph at each site. For this purpose, each site sends messages including the information of local path on its graph to its related sites. The basic idea underlying edge chasing method is to circulate messages called probes along the related sites. Unfortunately, these methods can't be applied for deadlock detection in HDBSs as the difference of message formats used in different sites makes the exchange of the messages impossible.
In this thesis, we propose a method, called a mediating composite method, for deadlock detection in HDBSs in which each site uses either a graph constructing method or an edge chasing method. In this method, a site called the mediating site is inserted between heterogeneous sites and this special site allows them to exchange messages and to detect deadlocks. The location autonomy and heterogeneity transparency, which are essential to HDBSs, are supported in our method.
