（计算机软件与理论专业论文）信息集成系统中的查询优化与处理.pdf

摘要 摘要 信息集成和互联网技术的发展，促进了人们对完整获取分布、异质信息的需 求。信息集成的一个主要特征就是需要同时处理大量的查询请求，因此有效地进 行查询对于信息集成系统是十分重要的。 本文在现有信息集成技术的基础上，研究了信息集成系统中的查询优化和查 询处理两部分。在查询优化方面，针对信息集成系统的特点，分析了传统的查询 包含概念的不足，利用了伪包含的概念，通过对查询集合构造伪包含树的方法确 定查询顺序，由此达到了对查询集合的优化的目的：在查询处理方面，建立了两 级映射规则，研究了从局部本体到关系数据库的子查询重写算法。采用了本体查 询语言作为查询语言，它针对全局本体进行查询。通过对查询语句的解析，建立 查询树，根据两级映射规则，通过变量绑定、查询分解以及子查询重写，最终将 针对全局本体的查询语言转化为与关系数据库相关的查询语言。 本文采用了p r o t 6 9 6 对本体进行建模，最后通过典型的查询用例对信息集成中 的查询处理与优化进行了结果上的分析。 关键词：信息集成伪包含映射规则查询分解子查询重写 a b s t r a c t a b s tr a c t w i t ht h ed e v e l o p m e n to ft e c h n o l o g yo fi n f o r m a t i o ni n t e g r a t i o na n dt h e 弹嘲 p e o p l ew a n tt og e tt h ec o m p l e t ei n f o r m a t i o nf r o md i s t r i b u t e da n dh e t e r o g e n e i t y i n f o r m a t i o n o n eo ft h em a i nc h a r a c t e r i s t i c so fi n f o r m a t i o ni n t e g r a t i o ni st od e a l 、析n l p l e n t i f u lr e q u e s t so fq u e r y , s o ，q u e r yp r o c e s s i n ga n do p t i m i z a t i o na r ev e r yi m p o r t a n tt o i n f o r m a t i o ni n t e g r a t i o ns y s t e m i nt h i sp a p e r , t h ee m p h a s e sw er e s e a r c h e da r eq u e r yo p t i m i z a t i o na n d p r o c e s s i n gi n i n f o r m a t i o ni n t e g r a t i o ns y s t e mb a s e do ne x i s t i n gt e c h n o l o g i e si ni n f o r m a t i o ni n t e g r a t i o n i nq u e r yo p t i m i z a t i o n , w er e s e a r c h e dt h es h o r t a g ei nt r a d i t i o n a lc o n c e p to fq u e r y c o n t a i n m e n tb a s e do nt h ec h a r a c t e r i s t i co fi n f o r m a t i o ni n t e g r a t i o ns y s t e m ；w eo p t i m i z e d t h ea g g r e g a t eo fq u e r yb a s e do i lp s e u d oc o n t a i n m e n ta n dd e c i d et h es e q u e n c eo fq u e r y b yt h ep s e u d oc o n t a i n m e n tt r e eo ft h ea g g r e g a t e i nq u e r yp r o c e s s i n g ，w er e s e a r c h e d m a p p i n gr u l e sa n ds u b q u e r yr e w r i t ef r o ml o c a lo n t o l o g yt od a t a b a s e t h eq u e r y l a n g u a g ei so n t o l o g yq u e r yl a n g u a g e ，i ti st h eq u e r yl a n g u a g et h a tq u e r yi ng l o b a l o n t o l o g y f r o mp a r s i n go ft h es i n g l eo n t o l o g yq u e r yl a n g u a g e ，w eb u i l daq u e r yt r e e ， b a s e do nm a p p i n gr u l e st h a tf r o ml o c a lo n t o l o g yt og l o b a lo n t o l o g ya n df r o ml o c a l o n t o l o g yt od a t as o u r c e ，u s e da r i t h m e t i co fq u e r yd e c o m p o s i t i o na n ds u b - q u e r yr e w r i t e ， c h a n g e dt h es u b - q u e r yl a n g u a g et os q l t h a ti sc o r r e l a t i v et od a t as o u r c ea tl a s t i no n t o l o g ym o d e l i n g ，w eu s e dp r o t 6 9 6 a tl a s t , w ea n a l y z e dt h er e s u l t si nq u e r y p r o c e s s i n ga n do p t i m i z a t i o nb yt y p i c a lq u e r ye x a m p l e k e y w o r d s ： i n f o r m a t i o ni n t e g r a t i o n ，p s e u d oc o n t a i n m e n t ，m a p p i n gr u l e ，q u e r y d e c o m p o s e ，s u b q u e r yr e w r i t e 学位论文创新性声明 秉承学校严谨的学风和优良的科学道德，本人声明所呈交的论文是我个人在 导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标 注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成 果；也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的 材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说 明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切的法律责任。 本人签名：牲 日期二盟吐 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全 部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。( 保密的论文 在解密后遵守此规定) 本学位论文属于保密，在年解密后适用本授权书。 本人签名： 导师签名： 埠垃 刿 日期趔盟z 日期j - 矽口矿i 7 第一章绪论 第一章绪论 1 1 研究背景 计算机网络技术与存储技术的进步使得联机信息发生了爆炸性增长，万维网 技术把所有这些信息连结起来，使得任何人都很容易地访问数据，它逐渐成为信 息传播的主要工具。但是，用户要得到需要的信息却越来越困难了。各种数据源 在不断发生变化，用户必须处理这些动态变化的数据源。这些数据源的异构性和 动态变化使得用户很难利用这些信息。在这种背景下，信息集成研究成为数据库 研究领域内的一个重要的课题。信息集成系统中的查询处理与优化是信息集成研 究中的热点。 信息集成的目的【l 】就是提供一个统一的查询接1 2 1 ，屏蔽底层数据源的不同，使 得用户不必再考虑底层数据源的数据模型、物理位置和语义异构等问题，能够通 过一个统一的查询界面实现对分布的异构数据源的灵活访问。集成系统提供模式 转换与集成、全局查询处理等功能，将从多数据源取得的数据以统一的方式呈现 给用户。这样就使得对多数据源的操作就像操作单独的数据源一样简单。 1 2 研究现状 信息集成技术已经历了2 0 多年的发展过程，研究者已提出了很多信息集成的 体系结构和实现方案，主要可以分为【2 j ：联邦方式、数据仓库方法、w r a p p e r m e d i a t o r 方法。 早期普遍采用单个联邦系统【3 】，将所有数据源统一到一个单一的集成系统中。 但是它存在一系列的问题：首先，构建这样一个集中式的系统需要很长的开发时 间，要求高性能的主机设备，实现代价较高；其次，系统的扩展和维护会涉及到 整个系统，而且一个集成系统无法共享另一个集成系统的模块。 随着分布异构计算环境下互操作性的研究及进展，由于数据源的多样性和分 布性，单个联邦系统的集成方法，己无法适应人们获取更多更新数据的需要。随 之出现了使用分布式的对象模型【4 】，如微软的分布式组件对象模型d c o m ，c o r b a 或s u n 的r m i 来构建数据集成系统。这种方法有效的避免了联邦系统带来的开发 代价大，代码难以重用的问题，利用网络计算环境可以有效的实现复杂的大规模 的信息集成。但是，d c o m ，c o r b a 或r m i 要求服务客户端与系统提供的服务本 身之间必须进行紧密耦合，要求特定的语言形态、特定的系统结构。同时随着信 2 信息集成系统中的查询优化与处理 息源种类和形态的不断增长，系统的脆弱性问题变得比较突出。 数据仓库方法【5 】是将各数据源的数据按照需要的全局模式从各数据源抽取并 转换，存储在数据仓库中。用户的查询就是对数据仓库中的数据进行查询。对于 数据源数目不是很多并且数据变动不是很频繁的应用来说，该方法十分有效。但 对目前的海量数据，数据源繁多且变化快，对数据源的数据抽取和转化要复杂得 多，数据仓库方法的不足十分明显。 目前比较流行的建立数据集成系统的方法是w r a p p e r m e d i a t o r 方法。该方法 并不将各数据源的数据集中存放，而是通过w r a p p e r m e d i a t o r 结构满足上层集成应 用的需求。数据集成系统通过中介模式将各数据源的数据集成起来，而数据仍存 储在局部数据源中，通过各数据源的包装器( w r a p p e r ) 对数据进行转换使之符合中 介模式。用户的查询基于中介模式，不必知道每个数据源的特点，中介器( m e d i a t o r ) 将基于中介模式的查询转换为基于各局部数据源的模式查询，它的查询执行引擎 再通过各数据源的包装器将结果抽取出来，最后由中介器将结果集成并返回给用 户。w r a p p e r m e d i a t o r 方法解决了数据的更新问题，从而弥补了数据仓库方法的不 足。 近年来，随着w r e bs e r v i c e 的出现，操作界面在浏览器层面上得到统一【6 】，兼 容性由相关标准技术实现( 如s o a p , u d d i ，w s d l 等) 。在w e bs e r v i c e s 的框架下， 使用一组w e bs e r v i c e s 协议，构建数据集成系统。对每个数据源都为其创建一个 w e bs e r v i c e ，然后使用w s d l 向服务中心注册。当要构建一个新的集成应用时， 集成端首先要向注册中心发送查找请求收集并选择合适的数据源，然后通过s o a p 协议从这些数据源获取数据。这种方法与联邦方法和数据仓库方法相比，具有完 好封装，松散耦合，高度可集成能力等特性。w e bs e r v i c e 方法为数据集成提供了 灵活的集成方式，为快速新增和部署新数据源提供了方便。 从发展趋势看，信息集成系统的框架日趋成熟，但是伴随多样化数据的产生， 异构数据源在集成过程中表现出来的异构性问题变得十分突出，主要包括结构异 构，语法异构，系统异构和语义异构。对于异构数据的集成，作为信息集成研究 的一个分支，逐渐成为信息集成系统中的查询与优化要解决的一个主要问题。为 了解决数据异构问题，许多研究组织进行了研究。并提出将本体作为一种工具用 于信息集成系统中，在一定程度上解决了数据异构问题。利用本体，可以用计算 机理解的方式去描述数据源信息和数据模式。利用全局本体建立共享词汇库，以 及待集成领域的领域知识，所有的分布的数据源都利用全局本体的共享词汇和共 享知识，从而最大程度的减少各个数据源的语义异构问题。不少数据集成系统采 用了基于本体的数据集成方案【7 j 如m o m i s c w e b ，s t y x 等。 从发展现状和趋势来看，在信息集成领域，利用本体来描述数据源，从而解 决信息集成中的查询问题是一个热点。 第一章绪论 3 1 3 研究内容和目标 本文采用了基于本体的信息集成方法，使用本体来解决信息集成中的查询问 题。该方法要达到的目标主要包括四个：第一，利用伪包含的概念来进行查询集 合的优化处理；第二，提供灵活的数据源集成能力；第三，对查询的回答能得到 尽可能完整的结果，而不必关心局部数据源的细节；第四，支持语义异构的集成 能力。 本文研究内容是：在信息集成系统中，如何进行有效的查询处理与优化。主 要包括： 1 ) 通过研究传统的查询包含的不足，利用伪包含的概念，它能有效地避免传统的 查询优化技术中的“回连接操作。 2 ) 针对信息集成系统的特点，利用多查询优化思想，这种思想基于伪包含的概念， 通过把大的查询集合分拆成若干个较小的集合，然后对每个查询集合进行优化。 3 ) 全局本体和局部本体的建立问题。采用有效而方便的手段建立全局本体和局部 本体。 4 ) 本体映射关系建立问题。提出了从局部本体到全局本体的映射规则建立方法以 及数据源到局部本体的映射规则建立方法。建立的映射规则为查询分解和查询重 写提供了指导。 1 4 论文章节安排 本文的各章节的安排如下： 第二章，“信息集成相关技术 ，主要介绍了信息集成的基本概念及语义异构 问题。还介绍了与信息集成相关的技术，如本体在数据集成中的应用，本体描述 语言。对于在以后的查询处理与优化中用到的本体查询语言和伪包含做了简要说 明。 第三章，“查询处理与优化分析，首先对传统优化中存在的问题进行了分析， 为以后的优化工作提供了参考。简要介绍了本文参考的m e d i a t o r w r a p p e r 信息集成 系统架构，然后提出本文设计的查询优化与处理的架构。 第四章，“查询优化 ，对传统多查询优化在信息集成环境下的缺点进行分析， 提出了扩展投影属性的方法。利用伪包含的思想对查询集合进行优化，并对算法 进行性能分析。 第五章，“查询处理”，介绍了查询处理中的关键技术，包括查询语言，数据 4 信息集成系统中的查询优化与处理 模式的描述，映射关系的描述，查询变量绑定，查询分解和查询重写。最后通过 测试用例对查询处理和优化的结果进行分析。 第六章，“结论与展望”，总结了本文的结论和不足之处，并对进一步的研究 工作做出了展望。 第二章信息集成相关技术 5 第二章信息集成相关技术 2 1 1 信息集成的定义 2 1 信息集成简介 信息集成这个概念由来已久，文献 1 2 】中对信息集成系统进行了形式化的定 义：一个信息集成系统可以形式化定义为一个三元组i g ，s ，m ，其中：g 是 全局模式，s 是数据源模式，m 是全局模式和数据源模式的映射关系。 信息集成屏蔽了各种异构数据间的差异，它使得可以统一的表示、存储和管 理各种异构数据。集成后的异构数据对用户来说是统一的和无差异的。 2 1 2 异构信息集成的目标 信息集成的目标是为了实现各个异构数据源之间的数据共享，有效利用资源， 提高整个异构数据集成系统的性能。而信息集成的理想目标是在分布式环境下给 用户提供一个单一系统映像s s i ( s i n g l es y s t e mi m a g e ) 。这意味着各个数据源之间的 相互作用必须透明地进行。透明就是说把所有相互作用地细节向用户隐蔽起来， 使用户把各个子系统看成是一个无缝的信息集成系统。具体来说，信息集成应达 到这样两个目标，即分布的透明性和异构数据源的透明性。 分布的透明性。 这包括两方面：位置的透明性，即用户不必知道数据的物理存储地，就好像 所用到的数据全部存储在本地一样。这是由一个专门地分布式数据库管理系统来 实现的。如果缺乏数据位置透明性，则每个应用程序都必须关心自己的位置，本 地数据就不得不与远程数据分离开来。分布式存取透明，即可以处理各种网络资 源，就如同他们在本地机器上一样，系统必须对存取进行控制，同时提供设备目 录。 数据源的透明性。 在信息集成中，如果仅从数据的角度来考虑，则主要是实现单一数据映像s d i ( s i n g l ed a t ai m a g e ) 。即对于系统中的任何一个用户，不管它所需要的数据在什么 地方，来自什么样的数据源，在用户看来，这些数据是透明的。异构数据源的透 明性主要表现在两个方面：不同d b m s 的常规数据之间的透明性；不同d b m s 的 常规数据和非常规数据( 工程数据、制造自动化的实时数据、多媒体数据等) 之 6 信息集成系统中的查询优化与处理 间的透明性。 2 1 3 集成模式分类 按照集成模式的不同，又可将信息集成系统分为两类，l a v ( l o c a la sv i e w ) 和 g a v ( g l o b a la sv i e w ) 。 l o c a la sv i e w 是以数据源为中心的方法，全局模式的设计独立于数据源：如果 i = 是基于l a v 集成模式的数据集成系统，那么m = p sls 哼q 。 即m 包含的映射关系为，对于数据源模式s 中每个元素s ，从jj 皱的断言。q 是全局模式上的查询。l a v 的特点是具有高度的模块化程度和良好的可扩展性， 如果设计的全局模式比较好，那么当数据源改变时，只会影响到它的定义，而对 整个集成系统没有影响；当有新的数据源加入时，可以比较容易地扩展整个l a v 数据集成系统。l a v 主要的缺点是可能产生不完全的查询结果，查询过程需要进 行推理，即查询重组比较复杂。采用这种方法的质量依赖于我们特征化数据源的 好坏程度。 g l o b a la sv i e w 是以全局模式为中心的方法：如果i = 是基于g a v 集成模式的数据集成系统，那么m = g g i g 专q ) 。即m 包含的映射关系为： 对于全局模式g 中每个元素g ，从g 到q 的断言。q j 是数据源模式上的查询。g a v 的缺点是缺乏扩展性，如果有新的数据源需要集成，则需要修改视图定义。如 t s i m m s ，i n t e r v i s o 和g a r l i c 都是使用g a v 方法的系统。系统c a r r o t ，s i m s ， t s i m m i s ，i b i s ，p i c s e l 等都是采用g a v 方法，采用这种方法的质量依赖于我们将数 据源映射到全局模式的好坏程度，当数据源改变或有新的数据源增加时，全局模 式就需要进行改动。 2 2 1 本体的概念 2 2 本体与信息集成 本体最早是一个哲学上的概念【8 】，从哲学的范畴来说，本体是客观存在的一个 系统的解释或说明，关心的是客观现实的抽象本质，它用于说明某种形式语言( 或 逻辑) 内在含义( 即语义) 的逻辑理论，通过一种本体化约定的方式近似地描述 了关于现实世界的概念化，本体的本质是“建立在逻辑理论上的对概念化的近似 描述”。在人工智能界，最早给出本体定义的是n e c h e s 等人，他们将本体定义为 “给出构成相关领域词汇的基本术语和关系，以及利用这些术语和关系构成的规 定这些词汇外延的规则的定义”。本体是依靠人的智慧而创建的工程化产品，它包 第二章信息集成相关技术 7 含了许多领域中的技术，如知识表示与推理、面向对象建模、数据库理论以及人 工智能等。它可能被包含在一个软件系统中，像知识库一样工作，提供智能化的 信息处理功能。本体在英文中表示为“o n t o l o g y 或“o n t o l o g y ，前者用于哲学领 域，整个计算机科学领域使用“o n t o l o g y 。一个本体其实就是一套关于某一领域 的规范而清晰的描述，它包含类( c l a s s e s ，有时也被称作概念c o n c e p t s ) ，每一个 概念的属性( p r o p e r t i e s ) 描述了有关概念的各种特征和属性( 又称s l o t s ，有时也称为 r o l e s 或a t t r i b u t e s ) ，还有属性的限制条件( r e s t r i c t i o n s ，即面f a c e t s ，有时也称为r o l e r e s t r i c t i o n s 或c o n s t r a i n t s ) 。一个完整的本体还要包含一系列与某个类相关的实例 ( i n s t a n c e s ) ，这些实例组成了一个知识库( k b k n o w l e d g eb a s e ) 。 本体描述现实世界的能力十分强大。从描述对象的类型来说，本体既可以用 来描述简单的事实，又可以用来描述信念、假设、预测等抽象的概念；既可以描 述静态的实体，又可以描述与时间推移相关的概念，如事件、活动、过程等。从 描述对象的范围来说，本体可以定义通用的、适合所有领域知识表示的术语，如 空间、时间等；也可以定义特定领域知识才使用的术语。本体的表示有多种：有 仅表示概念的简单表示，有表示概念和属性的框架和语义网络表示，还有能表达 丰富语义的逻辑表示。e r 模型和u m l 类图也可认为是本体的表达。但总的来讲， 这些本体表示基本上属于两类：非逻辑和逻辑本体表达。从概念的分类来看，非 逻辑表达直观方便但推理必须由用户自己实现，逻辑表达可以通过谓词演算清晰 表达所描述领域。 2 2 2 本体在信息集成中的应用 在信息集成的许多经典论述中，都将本体及其相关技术，作为达到系统互操 作的数据集成方案的基础。通过对概念的严格定义和概念之间的关系来确定概念 的精确含义，表示共同认可的、可共享的知识，从而解决语义异构的问题。一个 本体为特定领域的实体给出名字和描述，使用谓词来表示这些实体之间的关系。 它为表示和交流领域的知识给出了一个词汇库，并给出了一系列包含着词汇库里 的术语的关系，具体的来说，本体在数据集成中起着公共语义描述、查询模型、 推理基础三大作用。 公共语义描述( 概念定义) 利用本体作为语义描述的许多实现中，都提供了一个覆盖了几乎所有包含在 被集成数据源中的概念的本体。概念定义有两层含义：第一，本体内部复杂概念 和关系通过其它基本的概念和关系定义出来。第二，可以将本体作为公共概念模 型，来定义各数据源的概念和关系，作为各数据源语义数据集成的基础。 查询模型 8 信息集成系统中的查询优化与处理 本体用于信息集成系统的主要意义在于，它使本体可以作为一个中介或代理， 让大量的异构的底层数据源对用户来说是透明的。即用户可以不知道数据源的结 构，仅提交一个针对本体的查询：系统基于语义定义，可以自动地将针对本体的 查询重写为针对数据源的查询。这样，用户就可以仅仅提出需要什么数据，而不 需要指出如何去发现数据。在l a v 集成方式下体现本体的查询模型作用，关键是 要考虑多数据源的绑定问题，这将在第五章中进行详细讨论。 推理基础 本体用于信息集成系统的另一个意义在于：由于本体可以建立在逻辑基础上， 这使数据源中的一些隐在的概念或关系可以被发现。如果用户查询本体中的一个 概念，相关的答案可能在和其子概念和父概念联接的元素和属性中找到。从一个 明确的被查询的概念出发，可以按照本体的结构，依次找到子孙概念和祖先概念 作为其潜在的支持答案的概念。通过本体的推理，局部数据源之间元素和属性之 间的关系可以根据他们在本体中映射的概念之间的关系得到。因此，本体的推理 基础作用，体现在异构、分布环境下的数据集成中，可以提高数据的查全率和查 准率。 因此，本体具有描述数据源语义和解决异构的潜力，在信息集成中使用本体 有许多的优点：本体提供了一个丰富的、预定义的词汇库，可作为与数据源的稳 定的概念接口，并且独立于数据模式。第二，本体表示的知识足够支持所有相关 信息源的转换。第三，本体支持一致的管理和非一致数据的识别等。 本文解决语义异构问题的方法是形式化地指定每个系统术语的含义，并且定 义每个系统术语集和中介术语集之间的转换。使用形式化本体指定系统术语集和 中介术语集。并使用本体映射指定它们之间的转换。 2 3 信息集成中的查询处理与优化 2 3 1 本体查询语言o q l 上一小节中我们提出了本体在信息集成系统中的应用，在查询处理方面，用户 不必关心数据源的异构性而直接提出对全局本体的查询语句( o n t o l o g yq u e r y l a n g u a g e ) ，我们需要在信息集成系统中通过对逐步的转化，最终将其转化为对数 据源表的标准s q l 查询，这就是查询处理的目的，具体的查询处理我们将在第五 章进行讨论。 下面简单地对本文采用的本体查询语言加以说明： 用户的查询接口提供o q l 查询语句的输入，查询语句被解析，经过处理后被 第二章信息集成相关技术 9 分解成子查询。o q l 语言是一种由s e l e c t f r o m w h e r e 三部分组成的查询语言。 s e l e c t 部分指定要输出的属性，类似于s q l 语句中的s e l e c t 子旬；f r o m 部分是 一棵由查询变量构成的查询树，查询树覆盖了全局本体图中的节点和路径，即覆 盖了全局本体中的概念、属性和角色。查询树的属性节点是树的叶子节点。w h e r e 子旬是指定选择条件的子句。 q 肼：s e l e c tx i ，x j f r o m p l - - x i ，x j 国2 2 x 2 ，琊p ! i i = x i w h e r e x i o c k ，x j o c ，1 1 查询q 卅是o q l 语言的语法结构。x i 是查询变量，f r o m 子句中的p i 是全局本 体中的角色路径，也称为变量x i 的绑定路径。第一个变量x l 称为查询的根变量， 它的绑定路径是p l 。对于形如x j i p j i - - x i 的表达式，我们称x i i 是x i 的父变量。因此查 询语句中的所有变量可以根据父子关系构造出一棵查询树。w h e r e 子旬中的c k 代表 查询条件的值，0 是条件表达式o e ， 1 0 0 1 0信息集成系统中的查询优化与处理 q ：q ( x ，】，) ：- p l ( z 】，) ，x 2 0 0 显然，q 不包含q 2 ，因为q 的头部只有一个x 被投影，而q 中有两个变量 x y 被投影。 但是，在不考虑头部变量的情况下，两个查询具有包含关系，这时称q 是伪 包含q 2 的。这一概念类似于包含的概念，不同之处在于，它并不要求一个查询头 部在映射下成为另一查询的头部。 定义2 1 ： 设有两个查询骇，皱，如果q ，q 满足条件a ，称q 伪包含q ，记作q 当q 。 条件a ：q 和q 2 的头部变量可以不同。但是查询的体部分和算术比较子目标 部分满足包含映射的条件。 定理2 2 ： 如果蜴2 pq 2 ，q p q ，则有q 墨珐。 证明：设g 到q 2 的一个包含映射为p ，q 2 到q 3 的包含映射为a p 2 p ( p 1 ) 岛允( 反) 所以有色a o p ( t 3 , ) 同时，；t o p 满足把q 的常量映射到q 中一个相同的常量，q 中的变量映射到 q 中常量或者变量。所以ao p 是从g 到q 的一个包含映射。所以有q q 3 。 上述定理说明伪包含关系是满足传递性的。具体伪包含在信息集成查询优化中的 应用，将在第四章进行详细分析。 2 4 本章小结 本章首先介绍了信息集成的基本概念，然后介绍了本体的特点和在信息集成 系统中的应用，对本体描述语言进行了介绍，概述了本文采用的查询语言o q l ， 对伪包含的概念和伪包含的传递性进行了说明，为以后的查询优化做好了准备。 通过以上相关技术的介绍，为后面讨论的系统体系架构及关键技术实现做了 准备。在后面的章节中将详细讨论这些技术在系统设计中的具体应用。 第三章查询处理与优化分析 第三章查询处理与优化分析 本章首先对传统意义上的查询优化做出了分析，针对现有的m e d i a t o r w r a p p e r 方式的集成架构进行分析，从而提出了适合本文的查询处理与优化的体系架构。 为以后的研究提供了支持。 3 。l 传统查询中存在的问题 本节主要讨论传统查询中存在的问题以及传统查询优化的解决方法，对以后 的信息集成系统中的查询优化提供改进的方向。在信息集成系统中，从接口输入 的o q l 查询语句，通过逐步地转换，最终要将对全局本体的查询转化为对数据库 关系表的查询，因此，我们将通过标准s q l 查询集合中存在的问题来分析。下面 通过一个例子说明传统多查询优化中出现的问题。 考虑大学科系事物管理的一个例子： 有三个关系： p r o f e s s o r ( p n o ，p n a m e ，c n o ，p a g e ，e x p e r i e n c e ，s a l a r y ) s t u d e n t ( s n o ，扑啪，m a j o r ) c o u r s e ( c n o ，c n a m e ) r e g i s t e r e d ( s n o ，c n o ) q u e r y l ： s e l e c t p n a m e ，e x p e r i e n c e f r o mp r o f e s s o r w h e r e e x p e r i e n c e 2 0 q u e r y l 是一个在关系p r o f e s s o r 上的查询，所有教龄在2 0 年以及2 0 年以上的 教授被选择，并且属性p n a m e ，e x p e r i e n c e 被投影。 q u e r y 2 ： s e l e c t p n a m e ，e x p e r i e n c e f r o mp r o f e s s o r w h e r e e x p e r i e n c e 2 0 a n d a g e 5 0 q u e 巧2 也是一个在关系p r o f e s s o r 上的查询，所有教龄在大于等于2 0 年并且 年龄小于等于5 0 岁的教授被选择，并且属性p n a m e ，e x p e r i e n c e 被投影。显然，满 足q u e 巧2 的元组也是满足q u e r y l 的，但是在查询q u e l l 中，p a g e 属性没有被 1 2 信息集成系统中的查询优化与处理 投影，这个就使q u e r y 2 没有办法利用q u e r y l 的查询结果去得到自己的结果，这 个问题被称作选择缺失。 q u e r y 3 ： s e l e c t p n a m e ，e x p e r i e n c e f r o mp r o f e ：s s o r w h e r e e x p e r i e n c e _ 2 0 a n d p c n o = c c n o a n d c c n a m e = 数据库原理 q u e r y 3 是一个在关系p r o f e s s o r 和c o u r s e 上的查询，所有教龄大于等于2 0 年 并且教授数据库原理的教授被选择，并且属性p n a m e ，e x p e r i e n c e 被投影。显然， 满足q u e r y 3 的元组也是满足q u e r y l 的，但是在查询q u e r y l 中，c n o 属性没有被 投影，这个就使q u e r y 3 没有办法利用q u e r y l 的查询结果去得到自己的结果，这 个问题被称作连接缺失。 q u e r y 4 ： s e l e c t p n a m e ，s a l a r y f r o mp r o f e s s o r w h e r e e x p e r i e n c e 2 0 q u e r y 4 是一个在关系p r o f e s s o r 上的查询，所有教龄在大于等于2 0 年的教授被 选择，并且属性p n a m e ，s a l a r y 被投影。显然，由于q u e r y l 和q u e r y 4 的w h e r e 子 句相同，在关系p r o f e s s o r 中，满足q u e r y 4 的元组也是满足q u e r y l 的，但在查询 q u e r y l 中，s a l a r y 属性没有被投影，这就使q u e r y4 没有办法利用q u e r y l 的查询 结果去得到自己的结果，称这个问题为投影缺失。 如果查询系统在执行查询q u e r y l 时事先知道后来的查询q u e r y 2 ，那么它就可 以扩展q u e r y l 的被投影属性，使之包括p a g e 属性，这样就可以在查询q u e r y l 的 结果上去执行q u e r y 2 。 在传统的查询优化中，是这样来解决这一问题的：首先我们称查询q u e r y1 的 结果为s n a p s h o t l 来执行查询q u e r y 2 。可以修改查询q u e r y 2 为q u e r y 2 。 q u e r y 2 ： s e l e c t p n a m e ，e x p e r i e n c e f r o m s n a p s h o t ls ，p r o f e s s o rp w h e r e s p n o = p p n o a n d p a g e 5 0 查询q u e r y 2 是在q u e r y1 的临时结果s n a p s h o t l 和基关系p r o f e s s o r 上进行的。 这里条件e x p e r i e n c e = 2 0 是不需要的。这种方法被称为回连接( b a c k - j o i n ) ，表面 看起来，q u e r y 2 需要连接操作，而q u e r y 2 不需要，q u e r y 2 的效率会比q u e r y 2 低， 第三章查询处理与优化分析 1 3 但实际则不然。在s n a p s h o t l 的元组数较少，且在关系p r o f e s s o r 的属性p n o 上建 有索引的时候，q u e r y 2 的效率更高。但是在信息集成系统中，回连接的方法并不 适用。具体的内容我们将在第四章信息集成中的优化方法中加以讨论。 上述对传统查询优化问题的分析，为我们的查询优化提供了思路。下面要设 计出适合本系统的架构。 3 2m e d i a t o r w r a p p e r 方式体系结构 m e d i a t o r w r a p p e r 方式本身是一种软件构件，通过提供所有异构数据源的虚拟 视图进行集成。数据源可以是数据库、遗留系统( 1 e g a c ys y s t e m ) ，w e b 数据源等。这 种集成方式本身并不存储任何实际数据。系统提供给用户一个全局模式( 也称为 m e d i a t o r 模式) ，用户针对全局模式提交查询而不必知道数据源的位置、模式和访 问方法，系统将用户查询翻译成一个或多个对数据源的查询。然后将数据源的查 询结构进行综合处理，并将它返回给用户。中介系统中的数据源是完全自治的， 可以容易地增加删除数据源。中介系统一般由一个中介器和多个包装- 器( w r a p p e r ) 组成。包装器用于将数据源的数据转换为集成系统可以处理的某种结构化的数据。 中介器的功能是分析针对全局模式的查询，分解为子查询，并将它们转换为针对 相应数据源的查询，最后合并所有数据源的结果返回给用户。 中介系统的体系结构如图3 1 所示： 图3 1 中介方式信息集成系统体系结构 1 4信息集成系统中的查询优化与处理 3 3 查询处理和优化架构设计 本文中提出的查询处理与优化子系统体系架构要求适应各种异质数据源的集 成，并且能够快速灵活的应付数据源的变化。根据m e d i a t o r w r a p p e r 方式的信息集 成体系结构特点，本文采用m e d i a t o r w r a p p e r 的方式构建信息集成系统，并将本体 作为一种工具引入到系统中，利用本体在描述语义上的优势解决信息集成中的语 义异构问题。系统采用全局本体描述信息集成系统的全局模式，局部本体描述数 据源模式，并增加了表示从局部本体到全局本体的映射规则库。在单条查询语句 输入以前对查询集合首先进行了查询优化，为最终的查询处理提供方便。查询处 理与优化子模块如图3 2 所示： 图3 2 查询处理与优化子系统 如上图所示，查询处理和优化从查询接口开始处理，最终的目标是要向w r a p p e r 输入标准s q l 语句。结果处理部分不包括在查询处理和优化过程中。底层数据源 假设是已配置完成的异构的关系数据库。 下面对图3 2 做一个详细介绍： 1 查询接口提供给用户输入查询语句，本系统将采用文献 2 】提出的树形查询 语言o q l ( o n t o l o g yq u e r yl a n g u a g e ) 进行查询。查询是基于全局本体所描述的全局 第三章查询处理与优化分析 1 5 模式的，因此用户不必关心底层数据源的分布情况和数据模式的差异。 2 从接口层获取查询语句后，所有的查询优化和查询处理部分将会在中介层进 行，该层是系统的核心部分。主要负责：查询集合的优化、查询语句的解析、查 询的分解，查询计划的执行。下面详细介绍上述各个部分： 查询优化： 在中间件体系结构中，当多个查询同时到达中间件后，中间件要能够识别出 这些查询中存在的冗余部分，然后消除冗余部分，这样就大大节约了数据源处理 查询的时间和查询结果从数据源到中间件的传输时间。有些查询集合在传统意义 上是不能进行优化的，本文利用伪包含的概念进行优化，通过生成的一棵伪包含 树，并且标识出树中每个节点的父节点，这样就可以把一个大的查询集合划分为 几个小的查询集合进行处理，每一个集合将确保是具有伪包含关系的。详细内容 将在第四章进行讨论。 查询语句的解析： o q l 语言的查询变量之间的父子关系将所有的查询变量组织成一棵查询树。 查询解析器负责将查询语句解析为查询树。该查询树的每个节点都包含查询变量 名称以及该查询变量对应于全局本体中的概念。得到的查询树是全局本体的一个 局部视图。详细的内容将在第五章讨论。 查询分解： 通过对查询树的解析，利用全局本体和局部本体之间的映射关系，将针对全 局本体的查询，分解为对局部本体的子查询。各个子查询组成了全局查询的查询 计划。 查询重写： 数据源包装器在接收到子查询语句的时候，该子查询语句是o q l 语言。需要 通过重写将对局部本体的查询转换为对数据库的查询。即通过重写操作将针对于 局部本体的查询转换为对关系数据库的查询。 3 4 本章小结 本章首先分析了传统查询优化中存在的问题以及在传统优化方法下的解决方 法，然后介绍了m e d i t o r w r a p p e r 方式的信息集成架构。在此基础上，提出了查询 处理与优化的架构，并对查询处理与优化的具体实现过程进行了分析，在后面的 章节中，将围绕该体系架构对应的查询处理与优化的架构展开讨论，对系统中用 到的关键技术进行研究。 第四章查询优化 1 7 第四章查询优化 本章主要讨论在信息集成系统中的查询优化的方法。首先介绍现有的几种查 询，然后分析传统多查询在信息集成环境下的缺点，提出了扩展投影属性的优化 方法，通过构造伪包含树的方法对查询集合进行优化，最后对算法进行了性能上 的分析。 4 1 信息集成中查询优化方法 4 1 1 合取查询 本文主要考虑合取查询( c o n j u n c t i v eq u e r y ) ，也被称作投影一选择一连接( s p j ) 查 询，一个合取查询( 简记作“c q ”) ：h ( x ) ：一a ( 五) ，见( 五) 。 在这个查询中，h ( x ) 被称为查询的头部( h e a d ) ，它表示这个查询的结果。这个 查询的体( b o d y ) 是子目标a ( 五) ，仇( 互) 的集合。每一个子目标p a x , ) 对应一个 关系模式，其中觑是一个关系，置是参数元组，其中的每一个参数是一个变量或 者常量，x 中的变量被称作全称变量( d i s t i n g u i s h e dv a r i a b l e s ) 。不在x 中的变量称为 存在变量。如果每一个全称变量都出现在体中，那么这