The thesis examines issues of consistency maintenance in advanced database systems; primarily, multidatabase systems. A multidatabase system consists of a number of pre-existing local database systems. A local database system is unaware of its participation in the multidatabase system and, likewise, the multidatabase system has no knowledge of local transaction executions. Enforcing global constraints in such an environment is clearly a challenging task. A methodology for constraint enforcement is presented which utilises existing technology for the replication of data in an attempt to enforce global consistency. While it is shown to have limited applicability, it is nonetheless an interesting study and serves to qualify the limits of such a solution. An alternative method for global consistency maintenance, which relies on the existence of triggers at each of the participant local databases, is then discussed. This method is shown to be particularly suitable when the issue of local database autonomy is of concern. It is, however, only suited to systems where each of the local databases provides a capability for triggering external actions based on the occurrence of particular database events. As a result of this methodology, the requirement for identification of enforcement actions which access sites where the instigating transaction originated becomes apparent. Such enforcement actions can cause deadlock in certain circumstances when they are executed at the same site which initially triggered the global constraint. This issue is dealt with in a novel way by proposing a methodology for statically checking relations at each participant site with a view to determining their susceptibility to this form of deadlock. The method, a graphical representation of the constraint enforcement process in a distributed system, is also shown to have other desirable properties. Arising from the requirements of other work within the thesis, an algorithm for detecting all cycles in a given directed graph is presented. It is shown that, while the well-known adaptation of the Depth First Search algorithm to cycle detection in directed graphs can detect the existence of cycles, it cannot in all circumstances identify all cycles. An algorithm which performs this task is presented together with an analysis of its complexity and correctness. In a more general sense, the issue of deferred constraint enforcement is discussed. Several scenarios where deferred enforcement of constraints is required are presented, together with a method for detecting the presence of cyclic dependencies within a given database schema.
| Identifer | oai:union.ndltd.org:ADTP/286553 |
| Creators | John Gilmore |
| Source Sets | Australiasian Digital Theses Program |
| Detected Language | English |
Page generated in 0.0025 seconds