A multidatabase system (MDBS) is a facility that allows users access to data located in multiple autonomous local database management systems (LDBMSs). In the MDBS, global serializability, reliability, and local autonomy are important issues. Especially, local autonomy is the most important requirement for the MDBS since the modification of LDBMSs may create difficult problems in the maintenance of current applications and local DBMS software itself. To maintain local autonomy, the global concurrency control algorithms can cause the problems such as the unnecessary delay of global transactions and the unnecessary abort of global transactions in global concurrency control. Especially, global serializability can be destroyed due to an indirect conflict among global transactions via local transactions if global transaction manager schedules global transactions without the local information. In this thesis, we propose the transaction processing model for an MDBS and its three-level scheduling algorithm for a global scheduler, for integrated local and global transaction schedulers (ILGSs), and for local schedulers to achieve global serializability, local autonomy, and higher concurrency. A recovery algorithm is proposed for reliable transaction management in the presence of failures. The most difficult problem to ensure global serializability for an MDBS is to schedule global transactions so that their execution order and their serialization order are identical at each site. In our scheduling algorithm, this problem is resolved by two different ILGS modules: the first ILGS module is used in the case that local concurrency control (LCC) algorithm produces a history in which the execution of a transaction is always the same as its serializable order, and the second ILGS module is used for each LCC algorithm that can generate a history whose execution order is different from its serialization order. To achieve a high degree of concurrency, transactions are scheduled at the ILGS module, regardless of local or global transaction, in a way that unnecessary abort or delay for transactions is not caused. By simply adding the ILGS module on top of each local DBMS, local DBMSs need not be changed at all. Therefore, local autonomy is guaranteed. Our scheduling algorithm also provides freedom from a deadlock at the global level and may be used even if data items are replicated at several sites. The problem of the conventional recovery management algorithms is that global serializability can be destroyed when a globally committed but locally aborted subtransaction is restarted in the case that there are active local transactions. Our recovery management algorithm can resolve this problem since it can delay the submission of local transactions at each ILGS module in the case that there is a possibility of the destruction of global serializability. Finally, the comparative performance evaluation with other two global concurrency control algorithms is performed through a simulation. Keywords: global serializability, reliability, recovery, and local autonomy
최근 통신과 데이타베이스 기술의 발달에 따라 이전에 존재하는 이질적인 여러 지역 데이타베이스에 존재하는 데이타의 접근을 요구하는 욕구가 점점 많아지고 있다. 이러한 욕구를 자연스럽게 충족시킬수 있는 것이 멀티 데이타베이스 시스템이다. 멀티 데이타베이스 시스템은 여러 이질적인 지역 데이타베이스 시스템이 통신선을 통하여 서로 연결된 분산 데이타베이스 시스템이다. 멀티 데이타베이스 시스템의 구축에 있어서 가장 중요한 것이 지역 자치성의 유지이다. 지역 자치성의 유지는 지역 데이타베이스에서 개발된 소프트웨어와 그 지역 데이타베이스 시스템자체의 변경을 요구하지 않으므로 지역 데이타베이스의 통합비용을 최소화할수 있다. 전역 데이타베이스의 일관성을 유지 시키기 위하여는 전역트랜잭션의 효율적인 관리가 필요하다. 전역트랜잭션 관리는 전역 동시성제어 알고리즘과 회복 알고리즘으로 구성이 된다. 지역 데이타베이스의 자치성을 완전히 보장하기 위하여 지역트랜잭션에 대한 수행정보 없이 전역 레벨에서 전역트랜잭션들을 스케쥴링 하여야 하기 때문에 전역적 직렬성을 보장하는 전역 동시성 제어 알고리즘을 개발하기가 상당히 어렵다. 전역레벨에서 전역트랜잭션을 스케쥴할 때 전역적 직렬성의 파괴 가능성이 있으면 해당 전역트랜잭션을 스케쥴할 수 없기 때문에 전역트랜잭션의 불 필요한 지연이나 철회가 발생할수 있다. 또한 지역트랜잭션을 통한 전역트랜잭션들 사이의 간접충돌로 인하여 전역적 직렬성이 파괴될 가능성이 있다. 일반적으로 지역 데이타베이스에 제약을 가하지 않거나 새로운 지역트랜잭션의 수행 시점을 조정하지 않고서는 전역 회복알고리즘에서 재 수행트랜잭션과 새로운 지역 트랜잭션이 동시에 수행이 될 때 전역 데이타베이스의 일관성이 파괴될 가능성을 가지고 있다. 본 논문은 멀티 데이타베이스 시스템에서 트랜잭션 관리에서 발생하는 이러한 문제점들을 해결하기 위한 트랜잭션 처리모델과 이 모델에 기반을 둔 3-단계 전역동시성 제어 알고리즘과 회복 알고리즘을 제안하고 각 알고리즘의 정확성은 증명을 통하여 입증하였다. 3-단계 전역 동시성 제어 알고리즘은 중간 단계인 ILGS 모듈에서 지역 데이타베이스 시스템에 제출한 지역트랜잭션과 부 트랜잭션들을 노드로 하는 그래프를 유지하여 연결된 요소 그래프가 하나 이하의 전역트랜잭션을 갖도록 하므로서 지역트랜잭션을 통한 전역트랜잭션들 사이의 간접충돌 문제를 해결하였다. 그리고 전역트랜잭션들의 순서적인 제출과 위그래프의 유지로 불 필요한 지연과 철회를 방지할수 있었다. ILGS 모듈에서 유지하는 그래프에서 재수행 트랜잭션을 마크하여 재수행 트랜잭션이 배타적으로 수행될수 있도록 하게 함으로서 재 수행 트랜잭션과 새로운 지역트랜잭션이 동시에 수행되더라도 전역 데이타베이스의 일관성이 유지될수 있도록 하였다. 시뮬레이션 방법을 이용하여 성능평가한 결과 3-단계 스케쥴링 알고리즘에서 전역트랜잭션의 평균 응답시간이 트랜잭션 그래프 알고리즘과 낙관적 티켓 방법에서 보다 훨씬 작다는 것을 입증하였다. 지역트랜잭션에 대한 응답시간은 도착하는 트랜잭션의 수가 처리되는 트랜잭션의 수 보다 많을 때 트랜잭션 그래프 알고리즘과 낙관적 티켓 방법에서 보다 약간 길지만 도착하는 트랜잭션의 수 와 처리되는 트랜잭션의 수가 비슷하다면 세방법 모두 비슷한 응답시간을 보였다. 트랜잭션이 철회될 확률은 3-단계 스케쥴링 알고리즘이 트랜잭션 그래프 알고리즘과 낙관적 티켓 방법 보다 훨씬 작음을 알수 있었다.