论文题目: LAV数据集成系统的查询处理
论文类型: 博士论文
论文专业: 计算机软件与理论
作者: 陈彤兵
导师: 施伯乐
关键词: 自治数据源,查询重写,绑定模式,查询计划,数据源能力,数据集成,程序,线性联接树,灌木型联接树,执行空间
文献来源: 复旦大学
发表年度: 2005
论文摘要: 分布式数据集成系统连接物理或逻辑上分布于不同位置的数据源,向用户提供对这些数据源的一个综合全面的全局视图,同时负责对这些数据源的自动访问和访问结果的集成。 分布式数据集成具有广泛的应用前景,例如因特网上商务信息的集成,集成各个政府部门信息的面向公众的电子政务系统,企业之间以及企业各部门之间的信息共享和协作都需要数据集成。 数据仓库、对等(peer-to-peer)结构以及中介器结构都可以用于实现分布式数据集成。本文以中介器结构数据集成为背景,重点研究了实现中介器上查询处理的若干关键问题。作为后续内容的基础,本文首先介绍了构成数据集成系统基本结构的全局数据模式、基于这个全局模式描述的每个数据源局部模式。随后的内容在以下几方面展开。 1.基于数据源的查询重写:本文的数据集成系统采用LAV方式,数据源被描述为基于全局模式的视图,因此可以通过查询重写技术构造对全局查询的处理过程。查询重写技术来源于利用实化视图(Materialized View)处理查询的需要。其算法复杂性包括构造视图与查询之间的变量映射和组合这些变量映射这两个相互独立的NP完全问题,现有算法往往通过简单的枚举检查所有可能的变量映射和这些映射的所有组合,其结果是需要做很多无效或冗余的检查和计算。本文针对这两个问题提出了在实现中的优化方法,在构造视图与查询之间的变量映射关系时限定只产生不被包含的映射,并且提出一种方法在特定情况下可以利用Bachman图按唯一的计算顺序构造出所有不被包含的映射。在组合各种映射构造查询重写阶段,本文提出的算法避免了对所有可能的映射组合的构造,而只组合和检查能够覆盖当前查询所有子目标的查询重写。此外,本文还针对数据源具有查询能力约束或某些语义约束的情况改进了有关的算法。 2.查询优化:分布式数据集成系统查询优化的目标与集中式数据库有所不同。本文从降低网络数据流量和提高查询响应速度两个方面研究优化问题。首先,在安排多个联接操作的顺序方面,本文证明了以降低网络数据流量为优化目标时只需要考虑线性联接树构成的联接顺序,但如果以提高查询响应速度为目的,则需要同时考虑包括灌木型树在内的所有联接顺序,并提出了相应的算法。其次,在实际环境中,数据源以及网络的性能在一定程度上是动态变化的,静态的查询计划很难适应,但以往的研究几乎都忽视了这个问题。而本文则提出了直接把联接计划的构造策略结合到查询执行过程中的方法,能够根据网络的当前状况动态调整联接操作的执行顺序。最后,为了优化选择操作,本文提出了在数据源之间分配选择条件的方法,能够尽量多地利用数据源本地的处理能力以降低网络数据流量和提高查询响应速度。 3.构造datalog程序处理查询:在开放世界假设下,为了得到尽量多的查询结果并避免对相同数据源的重复访问,一个更好的方法是把
论文目录:
摘要
Abstract
第一章 绪论
1．1 数据集成系统
1．2 LAV和GAV数据集成
1．3 LAV数据集成系统的基本结构
1．4 中介器
1．5 本文内容安排
第二章 全局模式和局部模式
2．1 相关工作
2．2 全局模式
2．3 数据源描述
2．3．1 描述数据源结构化接口
2．3．2 全局模式和数据源结构化接口之间的映射关系
2．3．3 查询和视图
2．4 进一步的工作
2．5 小结
第三章 基于数据接口的查询重写
3．1 相关工作
3．2 基于视图的查询重写
3．2．1 基本定义
3．2．2 数据源能够提供的数据
3．2．3 不考虑数据源查询能力时的查询方法
3．2．4 查询重写的组合
3．2．5 选择最优的查询重写
3．3 基于数据接口查询能力的查询方法
3．3．1 安排访问数据接口的顺序
3．3．2 基于可查询数据接口构造查询重写
3．3．3 放宽查询条件
3．3．4 任意多个视图
3．3．5 查询能力可变的数据接口
3．3．6 内置(built-in)谓词
3．3．7 函数依赖的作用
3．4 讨论
3．5 小结
第四章 查询优化
4．1 相关工作
4．2 传统的查询优化技术
4．3 优化联接顺序
4．3．1 以数据流量为指标的代价模型
4．3．2 以降低流量为目的的联接顺序
4．3．3 以响应时间为指标的代价模型
4．3．4 以缩短响应时间为目的的联接顺序
4．3．5 快速确定联接顺序
4．4 动态调整联接顺序
4．5 内置谓词的处理
4．5．1 构造对每个数据接口的查询条件
4．5．2 对能够接受内置谓词的数据接口的联接优化算法
4．6 小结
第五章 基于datalog的查询处理
5．1 相关工作
5．2 封闭世界假设与开放世界假设
5．3 数据接口没有查询能力约束时datalog程序的构造
5．4 基于查询能力受限的数据接口构造datalog程序
5．4．1 数据接口具有固定查询能力的情况
5．4．2 实验结果
5．4．3 放宽对b-谓词的约束
5．4．4 基于可变查询能力的数据接口的查询
5．4．5 查询中给定条件的表示
5．4．6 处理内置谓词
5．5 优化构造过程
5．5．1 数据接口之间关系的有向图表示
5．4．2 实验
5．6 查询重写和datalog程序两种方法的比较
5．7 讨论
5．8 小结
第六章 系统实现
6．1 系统基本结构
第七章 总结和展望
致谢
参考文献
附录：攻读学位期间参与的科研项目和发表的论文
1．参加的科研项目
2．发表的论文
论文独创性声明
论文使用授权声明
发布时间: 2005-09-19
参考文献
- [1].面向防汛抗旱指挥系统的应用集成中间件平台研究[D]. 张永进.西北大学2007
- [2].Web数据集成中实体演化与关联问题研究[D]. 张燕.山东大学2015
相关论文
- [1].自治异构数据源的集成查询处理[D]. 李效东.中国科学院研究生院（软件研究所）2002
- [2].XML与RDB的多层次双向数据集成技术研究[D]. 孙宏伟.西北工业大学2003
- [3].异构信息集成中的查询处理与优化研究[D]. 李瑞轩.华中科技大学2004
- [4].面向复杂数据源的数据抽取模型和算法研究[D]. 邓绪斌.复旦大学2005
- [5].XML数据的查询、转换和集成[D]. 郭志懋.复旦大学2005
- [6].企业应用集成架构研究与实现[D]. 陈亚华.复旦大学2005
- [7].异构数据库语义集成技术研究[D]. 强保华.重庆大学2005
- [8].生物学数据集成若干关键问题研究[D]. 曹顺良.复旦大学2005
标签：自治数据源论文; 查询重写论文; 绑定模式论文; 查询计划论文; 数据源能力论文; 数据集成论文; 程序论文; 线性联接树论文; 灌木型联接树论文; 执行空间论文;