多数据库系统中查询分解算法的研究

多数据库系统允许用户使用一个集成模式和简单的全局查询语言同时访问多个异构的、自治的数据库系统。全局查询分解处理是多数据库系统中的一个很重要的问题。本文给出了一种多数据库环境中的模式信息管理方法,基于这些模式信息,我们提出一种易于实现的查询分解算法。由于多数据库查询分解处理与模式集成的实现紧密相关,所以本文对多数据库系统的模式集成作了一些描述。     

Using tickets to enforce the serializability of multidatabasetransactions

To enforce global serializability in a multidatabase environment the multidatabase transaction manager must take into account the indirect (transitive) conflicts between multidatabase transactions caused by local transactions. Such conflicts are difficult to resolve because the behavior or even the existence of local transactions is not known to the multidatabase system. To overcome these difficulties, we propose to incorporate additional data manipulation operations in the subtransactions of each multidatabase transaction. We show that if these operations create direct conflicts between subtransactions at each participating local database system, indirect conflicts can be resolved even if the multidatabase system is not aware of their existence. Based on this approach, we introduce optimistic and conservative multidatabase transaction management methods that require the local database systems to ensure only local serializability. The proposed methods do not violate the autonomy of the local database systems and guarantee global serializability by preventing multidatabase transactions from being serialized in different ways at the participating database systems. Refinements of these methods are also proposed for multidatabase environments where the participating database systems allow schedules that are cascadeless or transactions have analogous execution and serialization orders. In particular, we show that forced local conflicts can be eliminated in rigorous local systems, local cascadelessness simplifies the design of a global scheduler, and that local strictness offers no significant advantages over cascadelessness     

On Concurrency Control in Multidatabase Systems with an Extended Transaction Model

A major concurrency control problem that we have to cope in multidatabase systems is the global deadlock detection and resolution problem. This detection must take into account the autonomy of local systems, which make impossible the visibility of the state of local transactions. A well-known approach to detect such deadlocks, called potential global deadlocks, is one based on the potential conflict graph (PCG) appropriate for the multidatabase transaction model with a global commit protocol. This classical transaction model is very constraining for applications manipulating great volumes of information, and where subtransaction terminations (commit or abort) of global transactions are not totally dependant. In this paper we present an effective potential global deadlock characterization, and an efficient potential global deadlock detection algorithm, in multidatabase systems with an extended transaction model more suited for such applications.     

多数据库事务处理模型中局部代理的设计与实现

在多数据库事务处理模型中，局部代理提供了全局事务管理层与局部数据库系统的接口，它使多数据库系统能够对分布在不同站点的局部数据库进行透明访问。文中提出了基于两阶段代理（２ＰＣＡ）的局部代理模型，它集成了支持两阶段提交或单阶段提并的数据库系统、以及并不支持事务提交协议的文件系统。文中还介绍了采用专用接口和ＯＤＢＣ两种实现局部代理的方法。文中着重介绍了使用ＯＤＢＣ方法的具体实现，并对两种方法实现的局部代     

An extended transaction to maintain consistency and recovery in multidatabase systems

A complete practical solution to transaction management preserving multidatabase consistency in the presence of multidatabase updates and failures is presented. The approach developed does not require support for the two-phase commit (2PC) protocol in the participating local database management systems (LDBMSs). Furthermore, it does not violate local autonomy; the source code of the LDBMSs is not modified in any way and the multidatabase system (MDBS) does not access or modify any control information of the LDBMS. The principles of the 2PC protocol in the process of global transaction commitment are adopted. The presented method does not rely on any specific concurrency control mechanism for LDBMSs. Consideration is given to global transaction failures due to subtransaction aborts by the LDBMSs and local site crashes. The recovery process is based on undo operations. While a global transaction is in progress, the tables accessed by subtransactions of this transaction at each local site are locked using specially initiated table locks. These locks are stored and maintained in the local database itself as control tables. The approach taken is easy to implement, and its limitations are discussed.     

多数据库系统中的模式映射方法

多数据库系统一般具有四级模式结构，全局用户只能访问全局模式，而最终的数据必须从各局部数据库系统中获得，因此必须建立多数据库系统的模式映射，它表示了局部模式通过输出模式集成为全局模式的相应转换。本文给出了一种多数据库系统中的模式映射方法，并使用 模式映射树来存储和表达这种模式映射。     

Transaction management issues in a failure-prone multidatabase system environment

This paper is concerned with the problem of integrating a number of existing off-the-shelf local database systems into a multidatabase system that maintains consistency in the face of concurrency and failures.The major difficulties in designing such systems stem from the requirements that local transactions be allowed to execute outside the multidatabase system control, and that the various local database systems cannot participate in the execution of a global commit protocol. A scheme based on the assumption that the component local database systems use the strict two-phase locking protocol is developed. Two major problems are addressed: How to ensure global transaction atomicity without the provision of a commit protocol, and how to ensure freedom from global deadlocks.     

A theory of global concurrency control in multidatabase systems

This article presents a theoretical basis for global concurrency control to maintain global serializability in multidatabase systems. Three correctness criteria are formulated that utilize the intrinsic characteristics of global transactions to determine the serialization order of global subtransactions at each local site. In particular, two new types of serializability, chain-conflicting serializability and sharing serializability, are proposed and hybrid serializability, which combines these two basic criteria, is discussed. These criteria offer the advantage of imposing no restrictions on local sites other than local serializability while retaining global serializability. The graph testing techniques of the three criteria are provided as guidance for global transaction scheduling. In addition, an optimal property of global transactions for determinating the serialization order of global subtransactions at local sites is formulated. This property defines the upper limit on global serializability in multidatabase systems.     

Revisiting Transaction Management in Multidatabase Systems

A lot of research efforts have focused on global serializability, global atomicity, and global deadlocks in multidatabase systems. Surprisingly, however, very few transaction processing model exists that ensures global serializability, global atomicity, and freedom from global deadlocks in a uniform manner. In this paper, we examine previous transaction processing models and propose a new transaction processing model that generates globally serializable and deadlock-free schedules in failure-prone multidatabase systems. A new transaction processing model adopts rigid conflict serializability as a correctness criterion on global serializability, and follows an emulated 2PC, criteria for global commitment, and an abort-based multidatabase recovery scheme for global serializability in failure-prone multidatabase systems. In addition, a deadlock-free policy is suggested where rigid conflict serializability is enforced when each subtransaction, including redo transactions, begins its execution. To practically support a new transaction processing model, Rigid Ticket Ordering (RTO) methods are designed. The proposed transaction processing model has the following improvements: (a) it resolves abnormal direct conflicts identified in this paper, (b) it imposes no restrictions on the execution of local transactions, and (c) it relaxes the restrictions on the execution of global transactions.     

在多数据库系统中维护完整性约束

在多数据库系统中,需要维护全局完整性约束,针对这一问题,本文提出了将主动机制集成到多数据库系统中以维护全局完整性约束的方法,并给出了具体的实例,由于主动规则与系统无关,因此该方法具有很大的灵活性。     

Query optimization in multidatabase systems considering schemaconflicts

In a multidatabase system, the participating databases are autonomous. The schemas of these databases may be different in various ways, while the same information is represented. A global query issued against the global database needs to be translated to a proper form before it can be executed in a local database. Since data requested by a query (or a part of a query) is sometimes available in multiple sites, the site (database) that processes the query with the least cost is the desired query processing site. The authors study the effect of differences in schemas on the cost of query processing in a multidatabase environment. They first classify schema conflicts to different types. For each type of conflict, they show how much more or less complex a translated query can become in comparison with the originally user-issued global query. Based on this observation, they propose an analytical method that considers the conflicts between local databases and finds the database(s) that renders the least execution cost in processing a global query. This research introduces a new level of query optimization (termed the schema-level optimization) in multidatabase environments. The results provide a new dimension of enhancement for the capability of a query optimizer in multidatabase systems     

Overview of multidatabase transaction management

A multidatabase system (MDBS) is a facility that allows users access to data located in multiple autonomous database management systems (DBMSs). In such a system,global transactions are executed under the control of the MDBS. Independently,local transactions are executed under the control of the local DBMSs. Each local DBMS integrated by the MDBS may employ a different transaction management scheme. In addition, each local DBMS has complete control over all transactions (global and local) executing at its site, including the ability to abort at any point any of the transactions executing at its site. Typically, no design or internal DBMS structure changes are allowed in order to accommodate the MDBS. Furthermore, the local DBMSs may not be aware of each other and, as a consequence, cannot coordinate their actions. Thus, traditional techniques for ensuring transaction atomicity and consistency in homogeneous distributed database systems may not be appropriate for an MDBS environment. The objective of this article is to provide a brief review of the most current work in the area of multidatabase transaction management. We first define the problem and argue that the multidatabase research will become increasingly important in the coming years. We then outline basic research issues in multidatabase transaction management and review recent results in the area. We conclude with a discussion of open problems and practical implications of this research.     

多数据库系统查询优化算法的研究

介绍了自行研制的panorama多数据库系统的查询优化的实现方法．提出了一种在分布式对象管理体系结构环境下的多数据库系统的动态查询优化技术．在查询优化的执行过程中．使用了基于多元线性回归模型的统计决策机制．由于多数据库的查询优化和模式集成的实现方式也有一定的关系．所以对多数据库系统的模式集成也作了一些描述。     

Concurrency control in hierarchical multidatabase systems

Over the past decade, significant research has been done towards developing transaction management algorithms for multidatabase systems. Most of this work assumes a monolithic architecture of the multidatabase system with a single software module that follows a single transaction management algorithm to ensure the consistency of data stored in the local databases. This monolithic architecture is not appropriate in a multidatabase environment where the system spans multiple different organizations that are distributed over various geographically distant locations. In this paper, we propose an alternative multidatabase transaction management architecture, where the system is hierarchical in nature. Hierarchical architecture has consequences on the design of transaction management algorithms. An implication of the architecture is that the transaction management algorithms followed by a multidatabase system must be composable– that is, it must be possible to incorporate individual multidatabase systems as elements in a larger multidatabase system. We present a hierarchical architecture for a multidatabase environment and develop techniques for concurrency control in such systems. Edited by R. Sacks-Davis. Received June 27, 1994 / Accepted September 26, 1995     

On rigorous transaction scheduling

The class of transaction scheduling mechanisms in which the transaction serialization order can be determined by controlling their commitment order, is defined. This class of transaction management mechanisms is important, because it simplifies transaction management in a multidatabase system environment. The notion of analogous execution and serialization orders of transactions is defined and the concept of strongly recoverable and rigorous execution schedules is introduced. It is then proven that rigorous schedulers always produce analogous execution and serialization orders. It is shown that the systems using the rigorous scheduling can be naturally incorporated in hierarchical transaction management mechanisms. It is proven that several previously proposed multidatabase transaction management mechanisms guarantee global serializability only if all participating databases systems produce rigorous schedules     

多库系统中高效的视图维护机制

外连接是多库系统中经常使用的生成全局视图的方法 ,但是外连接给维护多库系统视图带来了很大的困难 .目前已有的多库系统视图维护算法只考虑了连接操作 (select project join,SPJ) ,如果全局视图是通过外连接生成的 ,这些算法就不能有效地维护多库系统视图的正确性 .提出了一种新的多库系统视图维护算法 ,它能够在有外连接及数据不一致的情况下高效地维护多库系统视图 ,并最大限度地减少了向局部数据库发送的查询数 ,使得多库系统更加高效     

Performance analysis of three text-join algorithms

When a multidatabase system contains textual database systems (i.e., information retrieval systems), queries against the global schema of the multidatabase system may contain a new type of joins-joins between attributes of textual type. Three algorithms for processing such a type of joins are presented and their I/O costs are analyzed in this paper. Since such a type of joins often involves document collections of very large size, it is very important to find efficient algorithms to process them. The three algorithms differ on whether the documents themselves or the inverted files on the documents are used to process the join. Our analysis and the simulation results indicate that the relative performance of these algorithms depends on the input document collections, system characteristics, and the input query. For each algorithm, the type of input document collections with which the algorithm is likely to perform well is identified. An integrated algorithm that automatically selects the best algorithm to use is also proposed     

An Object Algebra Approach to Multidatabase Query Decomposition in Donají

This paper presents an approach to query decomposition in a multidatabase environment. The unique aspect of this approach is that it is based on performing transformations over an object algebra that can be used as the basis for a global query language. In the paper, we first present our multidatabase environment and semantic framework, where a global conceptual schema based on the Object Data Management Group standard encompasses the information from heterogeneous data sources that include relational databases as well as object-oriented databases and flat file sources. The meta-data about the global schema is enhanced with information about virtual classes as well as virtual relationships and inheritance hierarchies that exist between multiple sources. The AQUA object algebra is used as the formal foundation for manipulation of the query expression over the multidatabase. AQUA is enhanced with distribution operators for dealing with data distribution issues. During query decomposition we perform an extensive analysis of traversals for path expressions that involve virtual relationships and hierarchies for access to several heterogeneous sources. The distribution operators defined in algebraic terms enhance the global algebra expression with semantic information about the structure, distribution, and localization of the data sources relevant to the solution of the query. By using an object algebra as the basis for query processing, we are able to define algebraic transformations and exploit rewriting techniques during the decomposition phase. Our use of an object algebra also provides a formal and uniform representation for dealing with an object-oriented approach to multidatabase query processing. As part of our query processing discussion, we include an overview of a global object identification approach for relating semantically equivalent objects from diverse data sources, illustrating how knowledge about global object identity is used in the decomposition and assembly processes.     

Fuzzy Statistics Estimation in Supporting Multidatabase Query Optimization

Advances in networking and database technology have made global information sharing a reality. Multidatabase systems (MDBSs) represent a promising approach to addressing the challenges of achieving interoperability among multiple pre-existing databases that are highly autonomous and possibly heterogeneous. The performance of an MDBS is greatly dependent on effectiveness of multidatabase query optimization (MQO). However, the unavailability of and uncertainty in the statistics essential to query optimization have made multidatabase query optimization (MQO) significantly more challenging than distributed query optimization. This research undertook to develop a fuzzy statistics-based MQO approach to addressing statistics estimation and uncertainty problems in an MDBS environment. We analyzed the statistics needed in an MDBS environment and classified them into three categories: point-based, distribution-function-based and dependency-based. Fuzzy numbers were adopted to represent point-based statistics, and a fuzzy polynomial regression method was developed for estimating distribution function-based statistics (i.e., attribute or join selectivity) from a set of subquery results. For dependency-based statistics, a fuzzy regression method was employed for estimating logical-parameter-based local cost functions. Furthermore, methods for ranking the fuzzy numbers that are fundamental to fuzzy-statistics-based MQO were also discussed. The proposed fuzzy statistics estimation methods were illustrated using examples to demonstrate its applicability in supporting MQO.     

Multidatabase Query Optimization

A multidatabase system (MDBS) allows the users to simultaneously access heterogeneous,and autonomous databases using an integrated schema and a single global query language. The query optimization problem in MDBSs is quite different from the query optimization problem in distributed homogeneous databases due to schema heterogeneity and autonomy of local database systems. In this work, we consider the optimization of query distribution in case of data replication and the optimization of intersite joins, that is, the join of the results returned by the local sitesin response to the global subqueries. The algorithms presented for the optimization of intersite joins try to maximize the parallelism in execution and take the federated nature of the problem into account. It has also been shown through a comparativeperformance study that the proposed intersite join optimization algorithms are efficient.The approach presented can easily be generalized to any operation required for intersite query processing. The query optimization scheme presentedin this paper is being implemented within the scopeof a multidatabase system which is based on OMG‘sobject management architecture.