论文部分内容阅读
分布式数据集成系统连接物理或逻辑上分布于不同位置的数据源,向用户提供对这些数据源的一个综合全面的全局视图,同时负责对这些数据源的自动访问和访问结果的集成。 分布式数据集成具有广泛的应用前景,例如因特网上商务信息的集成,集成各个政府部门信息的面向公众的电子政务系统,企业之间以及企业各部门之间的信息共享和协作都需要数据集成。 数据仓库、对等(peer-to-peer)结构以及中介器结构都可以用于实现分布式数据集成。本文以中介器结构数据集成为背景,重点研究了实现中介器上查询处理的若干关键问题。作为后续内容的基础,本文首先介绍了构成数据集成系统基本结构的全局数据模式、基于这个全局模式描述的每个数据源局部模式。随后的内容在以下几方面展开。 1.基于数据源的查询重写:本文的数据集成系统采用LAV方式,数据源被描述为基于全局模式的视图,因此可以通过查询重写技术构造对全局查询的处理过程。查询重写技术来源于利用实化视图(Materialized View)处理查询的需要。其算法复杂性包括构造视图与查询之间的变量映射和组合这些变量映射这两个相互独立的NP完全问题,现有算法往往通过简单的枚举检查所有可能的变量映射和这些映射的所有组合,其结果是需要做很多无效或冗余的检查和计算。本文针对这两个问题提出了在实现中的优化方法,在构造视图与查询之间的变量映射关系时限定只产生不被包含的映射,并且提出一种方法在特定情况下可以利用Bachman图按唯一的计算顺序构造出所有不被包含的映射。在组合各种映射构造查询重写阶段,本文提出的算法避免了对所有可能的映射组合的构造,而只组合和检查能够覆盖当前查询所有子目标的查询重写。此外,本文还针对数据源具有查询能力约束或某些语义约束的情况改进了有关的算法。 2.查询优化:分布式数据集成系统查询优化的目标与集中式数据库有所不同。本文从降低网络数据流量和提高查询响应速度两个方面研究优化问题。首先,在安排多个联接操作的顺序方面,本文证明了以降低网络数据流量为优化目标时只需要考虑线性联接树构成的联接顺序,但如果以提高查询响应速度为目的,则需要同时考虑包括灌木型树在内的所有联接顺序,并提出了相应的算法。其次,在实际环境中,数据源以及网络的性能在一定程度上是动态变化的,静态的查询计划很难适应,但以往的研究几乎都忽视了这个问题。而本文则提出了直接把联接计划的构造策略结合到查询执行过程中的方法,能够根据网络的当前状况动态调整联接操作的执行顺序。最后,为了优化选择操作,本文提出了在数据源之间分配选择条件的方法,能够尽量多地利用数据源本地的处理能力以降低网络数据流量和提高查询响应速度。 3.构造datalog程序处理查询:在开放世界假设下,为了得到尽量多的查询结果并避免对相同数据源的重复访问,一个更好的方法是把