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

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

多数据库系统中的查询处理

在多数据库系统中,为实现局部系统的互操作,通常需要建立局部系统的集成视图u多数据库系统的用户针对集成视图表达全局查询请求后,多数据库系统的查询处理器经多级转换和处理后将全局查请求等价地转换为优化的针对局部模式的一组局邮子查询,主局部系统取得的部分查询结果经组装后取得最终的查询结果。     

多数据库系统的数据模式集成与查询处理

在分析了多数据库系统数据模式体系结构的基础上 ,讨论了多数据库查询处理问题 :查询分解、查询转换和查询优化。给出了全局查询分解算法和全局查询优化算法     

一种适合多数据库系统的查询表示方法

1 引言随着分布计算和网络技术的不断发展,传统的数据库技术已越来越不能满足数据共享和互操作的需要。同时,已有的数据库系统又不可能全部丢弃.因而研制能同时访问和处理来自多个数据库中数据的多数据库系统已成为必然趋势。多数据库系统是解决已存的、异构的、分布的多个局部数据库系统之间数据共享和集成的问题。由于多数据库系统具有异构性、分布性和局部自治性的特点,使得多数据库查询处理与传统数据库查询处理有很大的不同。多数据库系统呈现给用户的是全局模式,用户使用全局查询语言提交对多数据库的查询,而所需的数据又必须从各局部数据库获得,所以必须将全局查询转换成与局部数据库对应的局部查询。在全局查询转换为局部查询的过程中,需要     

PANORAMA多数据库系统的后处理查询策略

分析不同的模式集成语义 ,从而得出后处理查询的两种主要运算 :场地间联接和外联接运算 .运用规则把后处理查询先转换成普通表达式 ,再转换成析取条件范式 ,并讨论了其内部树结构的实现机制 ,生成实际用于调度的全局查询超图集 ,并给出了具体的算法 .在此基础上 ,根据超图集的特点 ,给出后处理查询的三级调度     

多数据库系统中的全局查询转换方法研究

使用查询树作为查询转换的内部表示,通过使用多数据库规范树对全局查询树进行规范化处理,并给出了相应的转换规则。最后给出了多数据库查询转换算法,并对查询转换的等价性进行了分析。     

基于图的适应性多连接查询优化算法

提出一种基于图的适应性多连接查询优化算法,分析关系结果集到达时间和结果集大小之间的关系,借鉴适应性查询优化的动态调整思想,对基于图的多连接查询进行改进。仿真实验结果表明,该算法在最好情况下的时间复杂度为O（n）,且能有效提高查询效率。     

多数据库系统中的关键技术

本文主要介绍多数据库系统（ＭＤＢＳ）中的几个关键技术,包括ＭＤＢＳ的设计原则及体系结构、异构模式消解、查询处理、事务处理等方面的问题。     

利用数据库系统表实现多表关联查询

通过分析数据库系统表,提出一种快速的多表关联查询方法。     

Query Optimization in Multidatabase Systems

Global query execution in a multidatabase system can be done parallelly, as all the local databases are independent. In this paper, a cost model that considers parallel execution of subqueries for a global query is developed. In order to obtain maximum parallelism in query execution, it is required to find a query execution plan that is represented in the form of a bushy tree and this query tree should be balanced to the maximal possible extent with respect to execution time. A new bottom up approach called Agglomerative Approach (AA) is proposed to construct balanced bushy trees with respect to execution time. By the deterministic nature of this approach, it generates local optimal solutions. This local minima problem will be severe in the case of graph queries, i.e., queries that are represented with a graph structure. A Simulated annealing Approach (SA) is employed to obtain a (near) optimal solution. These approaches (AA and SA) are suitable for handling on-line and off-line queries respectively. A Hybrid Approach (HA), that is an integration of AA and SA, is proposed to optimize queries for which the estimated time to be spent on optimization is known a priori. Results obtained with AA and SA on both tree and graph structured queries are presented.     

Solving Local Cost Estimation Problem for Global Query Optimization in Multidatabase Systems

To meet users' growing needs for accessing pre-existing heterogeneous databases, a multidatabase system (MDBS) integrating multiple databases has attracted many researchers recently. A key feature of an MDBS is local autonomy. For a query retrieving data from multiple databases, global query optimization should be performed to achieve good system performance. There are a number of new challenges for global query optimization in an MDBS. Among them, a major one is that some local optimization information, such as local cost parameters, may not be available at the global level because of local autonomy. It creates difficulties for finding a good decomposition of a global query during query optimization. To tackle this challenge, a new query sampling method is proposed in this paper. The idea is to group component queries into homogeneous classes, draw a sample of queries from each class, and use observed costs of sample queries to derive a cost formula for each class by multiple regression. The derived formulas can be used to estimate the cost of a query during query optimization. The relevant issues, such as query classification rules, sampling procedures, and cost model development and validation, are explored in this paper. To verify the feasibility of the method, experiments were conducted on three commercial database management systems supported in an MDBS. Experimental results demonstrate that the proposed method is quite promising in estimating local cost parameters in an MDBS.     

基于XML的文件系统与多数据库系统的集成

文件系统与多数据库系统集成是解决多个分布的异构数据源数据共享的必由之路。本文在对文件系统与多数据库系统集成中的问题进行分析的基础上，提出利用可扩展置标语言XML来实现文件系统与多数据库系统集成，并且提出了一种面向XML Schema的公共数据模型XIDM。XIDM能较好描述无结构化和半结构化数据的数据，建立在一系列XML标准的基础上，具有较强的实用性和通用性。文章还对目前XML的查询语言进行了讨论，确定将扩展的XML－QL作为配合XIDM的查询语言。     

多数据库系统中基于XIDM的模式映射方法研究

建立多数据库系统中多种模式间的映射是多数据库解决模式异构性的关键,而选用一种适用于这些映射的集成数据模型又是模式映射的基础。为了集成数据库、文件系统、Web文档等多种异构系统中的数据,提出了一种基于XML的集成数据模型（XIDM)作为多数据库系统的公共数据模型,基于XIDM模型,给出了全局模式与输出模式、输出模式与局部模式之间的模式映射方法,并对全局映射和局部映射在多数据库原型系统Panorama中的实现进行了示例,最后从数据模型的集成能力和模式映射的可操作性方面对基于XIDM的模式映射方法进行了性能比较和分析。     

浅谈分布式数据库系统查询优化

分布式数据库系统的查询优化,就是要寻找执行代价最小的查询执行策略,使系统执行效率达到最高。我们在应用中需要选择适当优化方法,在执行代价和便捷度之间得到最佳执行方案。     

Query reformulation for dynamic information integration

The standard approach to integrating heterogeneous information sources is to build a global schema that relates all of the information in the different sources, and to pose queries directly against it. The problem is that schema integration is usually difficult, and as soon as any of the information sources change or a new source is added, the process may have to be repeated.The SIMS system uses an alternative approach. A domain model of the application domain is created, establishing a fixed vocabulary for describing data sets in the domain. Using this language, each available information source is described. Queries to SIMS against the collection of available information sources are posed using terms from the domain model, and reformulation operators are employed to dynamically select an appropriate set of information sources and to determine how to integrate the available information to satisfy a query. This approach results in a system that is more flexible than existing ones, more easily scalable, and able to respond dynamically to newly available or unexpectedly missing information sources.This paper describes the query reformulation process in SIMS and the operators used in it. We provide precise definitions of the reformulation operators and explain the rationale behind choosing the specific ones SIMS uses. We have demonstrated the feasibility and effectiveness of this approach by applying SIMS in the domains of transportation planning and medical trauma care.     

基于多数据库查询优化的图形工具的设计

设计了一个定义多库查询的工具,该工具的设计提供了一个新的抽象层面,该抽象层面向下可将查询映射到各种具体的数据库中,向上则隐藏了各个数据库的差异,在前端采用统一的方式显示给用户。用户可以以一种直观的方式定义查询,并且在查询执行过程中使用了查询采样优化算法,使得整个用户查询变得简单而快捷。     

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.