（计算机应用技术专业论文）数据集成及基于约束关系的xml查询重写研究.pdf

东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已 经发表或撰写过的研究成果，也不包含为获得东南大学或其它教育机构的学位或证书 而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示了谢意。 研究生签名：丛日期：幽 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文 的复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档 的内容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论文被查阅和借 阅，可以公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权东 南大学研究生院办理。 研究生签名：么企筮导师签名：研究生签名：么芷：趁导师签名： 摘要 随着计算机应用技术和电子商务的快速发展，企业可获取的信息数量和类型有了极大的 增长。在企业应用和w e b 数据集成的需求的推动下，w e b 环境下的数据集成系统的研究己 成蓬勃发展的趋势。由于x m l 的可扩展性、结构性以及平台无关性的优点，x m l 已经成 为i n t e m e t 数据交换事实上的标准。基于x m l 的数据集成不仅成为目前研究的热点，也成 为数据集成的一个理想的解决方案。 本文研究了基于x m l 的半结构化数据集成问题。首先介绍了x m l 及其相关技术、半 结构化数据的相关知识和半结构化数据中的约束关系；其次综述了如今数据集成研究领域的 主要问题，包括集成系统理论框架、基本映射方案、查询重写算法等。在此基础上，设计了 一个基于x m l 的数据集成系统框架。此系统框架用统一的x m l 视图来集成和查询异构数 据源。由于充分利用了订l 数据模型的优点，该系统具有较好的可扩展性。最后，在原算 法的重写思想基础上，提出了一种基于约束的改进的重写算法。通过引入映射规则中的约束 条件，消除阻碍重写的s k o l e m 函数，从而解决内定谓词问题，增大原算法的应用范围。证 明了改进算法的正确性。性能分析和测试结果都表明，改进算法并不增加实质性的性能代价。 关键词：x m l ，数据集成，映射方案，查询重写约束关系 4 a b s t r a c t d u et of a s td e v e l o p m e n to f c o m p u t e ra p p l i c a t i o nt e c h n i q u e sa n de - b u s i n e s s ，v a r i o u st y p e so f d a t ag r o wq u i c k l y w h a ti sm o r e , t om e e tal a r g ed e m a n do nd a t am a n a g e m e n ti ne n t e r p r i s e a p p l i c a t i o na n dw e b , r e s e a r c ho n d a t ai n t e g r a t i o nu n d e rw e be n v i r o n m e n ti sa c t i v ea n de n e r g e t i c x m lh a si nf a c tb e c o m et h es t a n d a r do fd a t ae x c h a l l g eo l li n t e r a c t , w h i c hm a k e sr e s e a r c ho n x m ld a t ai n t e g r a t i o nn e p s a r ya n de m e r g e n t i nt h i sp a p e r , t h ep r o b l e mo ft h ex m l - b a s e dd a t ai n t e g r a t i o ni sd i s c u s s e d f i r s t l y , 慨 i n t r o d u c e sx m le n di t sr e l a t e dt e c h n o l o g y , a n dt h ec o n s i 重a j 忸o fs e m i s t r u c t u r e dd a t a s e c o n d l y , t h es t a t e - o f - a r tr e s e a r c ho nd a t ai n t e g r a t i o ni sd i s c u s s e di n c l u d i n gat h e o r e t i c a li n t e g r a t i o ns y s t e m , m a p p i n gs c h e l n a s , q u e r yp r o c e s s i n gf o rd a t ai n t e g r a t i o n t h e nb a s e do l lt h er e s e a r c ha b o v e , a l l x m l - b a s c dd a t ai n t e g r a t i o ns y s t e mf r a m e w o r ki sd e s i g n e d t h i ss y s t e mm a k e su s eo fau n i f i e d x m lv i e wt oi n t e g r a t ee n dq u e r yh e t e r o g e n e o u sd a t as o u r e a t a k i n gf u l la d v a n t a g eo fx m ld a t a m o d e l ，t h i ss y s t e mp o s s e s s e sg o o de x t e n s i b i l i t y f i n a l l y , a ne x t e n s i o no f t h ea l g o r i t h mt os o l v et h e p r o b l e mc a u s e db yt h ep r e s e n c eo fb u i l d - i np r e d i c a t e s i sp r o p o s e & t h ee x t e n d e da l g o r i t h m i n c o r p o r a t e sac o n c e p to fi n f e r r e dc o n s t r a i n t sw i t h i nx m lm a p p i n gr u l e sa n ds e e k sa n yi m p l i c i t a s s u m p t i o n sw i t hn o n - s k o l e mf u n c t i o n st os u b s t i t u t es k o l e mt e r l n sw i t h i nt h eb u i l d - i np r e d i c a t e s d u r i n gt h et r a n s l a t i o np h a s e t h i sw a y , t h ep r o b l e mo f b u i l d i np r e d i c a t e sc a l lb es o l v e de f f i c i e n t l y a n dt h ea p p l i c a b i l i t yo fx m lq u e r yr e w r i t i n gc a nt h e r e f o r eb ee n h a n c e d i th a sa l s ob e e np r o v e d t h a tt h ee x t e n d e da l g o r i t h mc a nf m dt h em a x i m a l l yc o n t a i n e dr e w r i t i n go v a t h ex m ls c h e m ai n t h ep r e s e n c eo fb u i l d - i np r e d i c a m s b o t hp e r f o r m a n c ea n a l y s i sa n dm e a s 咖o n tr e s u l t so ft h e e x t e n d e da l g o r i t h ms h o wt h a ti td o e sn o ti n c u ras i g n i f i c o n ti n c r e a s ei nt h ec o s to f p e r f u r m a n c e k e y w o r d s ：x m l ，d a t ai n t e g r a t i o n ，m a p p i n gs c h e m e ，q u e r yr e m i t i n g ，c o n s t r a i n t 1 1 研究背景 第一章引言 随着i n t e m e t 技术的迅速发展，各种在线数据源不断涌现。然而由于各种信息源的高度 异构性，各个数据源的信息组织方式、所采用的数据模型、数据结构，内容表示、查询语言 都会有很大不同。因而面对海量的信息，人们往往会被淹没在信息的海洋中。如何帮助用户 在信息的海洋中快速准确地查找到所需的信息，则是当前信息检索和数据库领域的一个重要 研究方向。数据集成的研究就是在这样的需求之下产生并不断发展的。 数据集成的根本任务是提供用户对多种异构数据源透明、一致和实时访问。透明性是 屏蔽底层数据源的差异，让用户感觉数据来自一个大的数据源；一致性是消除数据源之间 存在的结构异构和语义异构；实时性则指访问到的数据是最新更新过的。数据集成系统 中，系统维护一个全局模式，该全局模式是定义在数据源模式上的虚拟集成视图。用户提 交一个全局模式上的查询时，系统根据全局模式与数据源模式的关系将查询分解成数据源 模式上的子查询，分解成的子查询交由数据源包装器处理，最后系统组合来自多个包装器 的中间结果，并将组合后的结果以一定形式返回给用户。在数据集成系统中根据全局模式 与数据源模式的关系，将查询重写成数据源模式上的子查询，也即查询重写问题，是数据集 成研究的核心问题之一。 然而，伴随着i n t e m e t 的迅速发展，大量数据往往存在于h t m l ( h y p e r - t e x tm a r k u p l a n g u a g e ) 和s g m l ( s t a n d a r dg e n e r a l i z e dm a r k u pl a n g u a g e ) 等数据格式文件中，并非由传统的 数据库管理系统( d b m s ) 管理。这些数据的结构经常是不规则的，不具有预先定义的结构， 并且是动态变化的。具有这些特征的数据通常称为半结构化数据：大量半结构化数据的出 现导致了对f 结构化查询重写问题的研究口j ，基于o e m ( o b j e c te x c h a n g em o d e l ) 的半结构 化数据模型应运而生。s t a n f o r d 人学和i b m 公司合作的t s i m m i s 项目【1 1 在树查询语言 t s l ( t r e es p e c i f i c a t i o nl a n g u a g e ) 的基础上了解决了基于o e m 模型的、仁结构化数据的等价查 询重写问题；而文献【2 】则在提高t s i m m i s 的算法效率方面作了一些有益的探讨。 近年来，x m l 以其可扩展性、结构性以及平台无关性的优点已经成为i n t e m e t 信息描 述与数据交换的标准。同时，x m l 的基本语法非常适合描述半结构化数据p 1 。由于网络上 信息的本质特性和x m l 数据内在的灵活性 彳良多用x m l 编码的数据都是半结构化的。随着 x m l 应用得越来越广泛，基于x m l 的半结构化数据的集成问题1 4 1 1 5 1 1 6 1 1 7 1 1 8 1 9 】1 1 0 】已成为数据库 研究人员关注的一个焦点。 本文研究了基于x m l 的半结构化数据集成问题。我们设计了一个基于x m l 的数据集 成系统框架。另外，在半结构化数据集成领域，考虑到数据源的不确定性，利用已有数据中 的语义约束更加重要。实质上，客观世界中存在多种语义约束，如关键字依赖、包含依赖， 这些语义约束和数据表现形式无关。因此，我们提出了一种基于约束的x m l 查询重写的改 进算法。该改进算法解决了x m l 查询重写中的内定谓词问题。在存在内定谓词的情况下， 改进算法可确定给定x m l 模式的最大包含重写。 1 2 国内外相关研究 数据集成主要研究如何将存放在不同的数据源的数据组合起来以一个统一的视图提供 给用户访问。自9 0 年代中期起，数据库和人工智能学界在数据集成的研究方面取得了大量 的研究成果。这些研究成果集中在如下几个方面： 基本映射方案：数据集成系统通常需要一种模式以便用户在此基础上提出查询，这种模 式称为全局模式( g l o b a ls c h e m a ) 或者中问层模式( m e d i a t e ds c h e m a ) 。为了能够利用各个 7 自治数据源同答用户的查询，就需要提供一种在中间层模式和各本地数据源模式之间的语义 关系映射。常见的映射方案有g l o b a l a s - v i e w ( g a v 舭j 和l o c a l a s v e w ( l a v ) 1 1 3 】【1 4 l 。在 g a v 方法中，对于中间层模式中的每一个关系吊使用基于各本地数据源的查询来描述，很 多信息集成系统都是g a v 方式的，如t s i m m i s l l l ，m o m i s i ”1 和s q u i r r e l i ”1 。反之，对于l a v 方法，各本地数据源是用基于中间层模式的查询来定义的，i n f o r m a t i o nm a n i f o l d ! 7 1 和a g o r a s l 信息集成系统就是采用l a v 方式。实际上，g a v 和l a v 方案各有其优劣( 具体分析将在 后面章节中给出) 。通过融合上述两种方案的优点又提出了称为g l o b a l - a n d - l o c a l - a s - v i e w ( g l a v ) v 3 l 的方案。 查询处理算法：用户在数据集成系统中所提出的查询是基于公共可见的中间层模式而并 非直接作用于物理存储的数据源模式。因此，数据集成系统必须提供一种依赖于基本映射方 案的查询转换机制( 即查询处理算法) ，从而将用户查询变换成直接基于数据源模式的查询。 理想的查询处理算法应该满足正确性( 即通过转换后的查询得到的所有结果都应为原查询的 正确结果) 和完整性( 即通过查询数据源的所有结果都应属于转换后的查询结果集中) 。在 g a v 方式下，查询处理算法相对直接，利用视图展开算法( v i e wu n f o l d i n g ) 即可；而在l a v 方式下，查询处理( 即查询重写) 问题相对复杂一些。 传统基于关系数据的查询重写算法的研究主要包括两类：b u c k e t 算法f l 习i 】卿和i n v e r s e r u l e 算法1 2 0 1 ”1 。s v b 算法以及m i n i c o n 算法田1 都是基于b u c k e t 算法的改进。但是随着 w e b 技术的发展，网络环境下产生并存储着大量半结构化数据和半结构化物化视图，在此 基础上进行的查询重写的问题引起了越来越多的重视。半结构化数据查询重写的算法主要有 s t a n f o r d 大学t s i m m l s 项目组开发的m s l 算法川，北京大学面向内容的海量信息集成、 分析处理与服务课题组开发的c o m m i x 算法口j 以及最近m i c h i g a n 大学t i m b e r 项目组提 出的查询重写算法i l 。 集成系统架构：目前通常采用联邦式、中间件模型( m e d i a t i o n ) 、数据仓库和对等数据 管理系统( p e e rd a mm a n a g e m e n ts y s t e m ) 等方法来构造集成系统，这些技术在不同的着重 点和应用上解决数据的集成问题以及为用户提供决策支持。 联邦数据库1 是早期人们采用的一种模式集成方法。联邦数据库中数据源之间共享自 己的一部分数据模式，形成一个联邦模式 中间件模型m 是另一种典型的数据集成方法，它通过在中间层提供一个全局的数据逻 辑视图来隐藏底层的数据细节，使得用户可以把集成数据源看为一个统一的整体。这种模型 下的关键问题是如何构造这个逻辑视图并使得不同数据源之间能映射到这个中间层。与联邦 数据库不同，中间件模型不仅能够集成结构化的数据源信息，还可以集成半结构化或非结构 化数据源中的信息。 数据仓库技术则是以面向主题的、集成的、时变的和稳定的为特点，在另一个层面上表 达数据之间的共享，它主要是为了针对企业某个应用领域提出的一种数据集成方法，利于支 持决策支持等应用所需的大量集成数据的高效处理。 对等数据管理系统是继p 2 p ( p m p e e r ) 文件共享系统兴起后的又一研究熟点【捌口7 1 i 卅。 除了具有传统p 2 p 的架构优势之外，在数据集成方面它还具备以下优点：第一，参与数据共 享的任何组织都不需要承担创建中间层模式以及维护其与数据源之间映射的任务。p 2 p 架构 的引入提供了一种真正的分布式数据共享机制。第二，在对等数据管理系统下，不存在唯一 的中间层模式( 即全局模式) 。数据共享只发生在网络中的邻近节点之间。 1 3 本文的主要内容和结构 本文的研究主要使用g l a v 作为数据源描述方法，因其融合了l a v 和g a v 的优势， 不仅能够与各数据源的具体细节保持独立性，同时也允许相对灵活的模式定义。在此基础上 8 我们的查询处理算法则考虑融入传统i n v e r s er u l e 算法的基本思想并针对x m l 的层次化特 性及约束关系加以改进。另外，由于x m l 本身在语法层面上提供的一致性，本文通过采用 中间件模型处理数据的异构性。 本文共分五章，重点论述了基于约束的x m l 半结构化数据的查询重写问题，安排如下： 第二章，“背景知识”。对x m l 及其相关技术、半结构化数据的相关知识和半结构化数 据中的约束关系进行介绍。 第三章，“数据集成系统研究”，从以下三方面展开综述：集成系统理论框架、基本映射 方案、和集成系统中的查询处理算法。 第四章，“基于约束的x m l 查询重写”，提出了一个基于x m l 的数据集成框架设计。 并提出了一种基于约束的重写改进算法，性能分析和测试结果都表明，该改进算法并不增加 实质性的性能代价。 第五章，“小结”，对我们所做的研究工作进行了总结和展望。 9 第二章背景知识 在本章中，我们首先介绍了x m l 基本概念，然后介绍了半结构化数据概念及目前常用 的半结构化数据模型，最后介绍了半结构化数据中的约束关系，在半结构化数据集成领域考 虑到数据源的不确定性，利用已有数据中的语义约束更加重要。这些概念将在后面章节用到。 2 1 蛆。相关知识 x m l 完整的名称是e x t e n s i b l e m a r k u p l a n g u a g e ( 可扩展的标记语言) ，是w 3 c 提出的 一项国际标准，目的是为了补充h t m l 以用于w e b 上的电子数据交换1 2 9 1 。由于x m l 已经 成为i n t e r n e t 上数据交换的标准，它提供了一种数据源之间共享数据的通用语法格式，大量 数据源采用x m l 作为输出格式，因此x m l 数据的集成问题也日益重要。下面我们将介绍 x m l 的相关概念。 2 1 1x m l 特点与语法规则 x m l 是一种m e t a - m a r k u pl a n g u a g e ( 元标记语言) ，可提供描述结构化资料的格式。x m l 提供了一种独立于运行程序的方法来共享数据，用来自描述信息的一种新标准语言。x m l 由若干规则组成，这些规则可用于创建标记语言，并能用一种被称作分析程序的简明程序处 理所有新创建的标记语言，正如h t m l 为计算机用户订阅i n t o m o t 文档提供一种显示方式一 样，x m l 也创建了一种任何人都能读出和写入的世界语。x m l 能增加结构和语义信息，可 使计算机和服务器即时处理多种形式的信息。运用x m l 的扩展功能不仅能从w e b 服务器下 载大量的信息，还能大大减少网络业务量。 x m l 中的标记( t a g ) 是没有预先定义的，使用者必须要预定义需要使用的标记，x m l 是能够进行自描述( s e l f - d e s c r i b i n g ) 的语言。x m l 使用d t d ( d o e u m e n t t y p ed e f i n i t i o n ) 来规范 这些数据，x s l ( e x t e n s i b l es t y l e s h e e tl a n g u a g e ) 是一种来描述这些文档如何显示的机制，它 是x m l 的样式表描述语言。x s l 包括两部分：一个用来转换x m l 的方法：一个用来格式 化x m l 文档的方法。利用x m l ，w e b 设计人员不仅能创建文字和图形，而且还能够创建 文档类型定义的多层次、相互依存的系统、数据树、源数据、超链接结构和样式表。 x m l 文档由存储单元e n t i t y 组成，e n t i t y 可以包含解析数据或朱解析数据。解析数据 由字符组成，其中一些字符组成字符数据，另一些字符组成标记。标记中包含了对文档存储 格式和逻辑结构的描述。 图2 1 - 2 一个x m l 文档 l o 2 1 2d t d 与x m ls c h e m a 一个x m l 文件遵守d t d ( d o c u m e n tt y p ed e f i n i t i ) 【”l 中定义的种种规定。d t d 描述了 一个x m l 文档的语法和词汇表，也就是定义了文档的整体结构以及语法。简而言之，d t d 规定了一个语法分析器为了解释一个“有效的”x m l 文件所需要知道的所有规则的细节。 d t d 原来是为使用s g m l 开发的，它可以是x m l 文档的一部分，但是它通常是一份单独 的文档或一系列文档。x m l 本身并没有一个通用的d t d ，想使用x m l 进行数据交换的行 业或组织可以定义他们自己的d t d 。d t d 标记声明可以是元素类型声明，属性表声明，实 体声明，或符号声明。 x m l 提供一种称为文档类型声明的机制，用于定义对逻辑结构的约束，支持预定义存 储单元的使用。文档类型声明指定了文档使用的d t d 。文档类型声明出现在文档的序言部 分，处在x m l 声明之后和第一个元素之前。它可以包括d i d ，也可以标识d t d 所在文档 的u r l 。一个合法的x m l 文档必须符合文档类型声明指定的约束条件。而且，它的基本元 素必须是在文档类型声明中指明的。 d t d 的功用很多：定义内容模式，限制范围、属性的数据类型。但它也有着一些缺点， 如采用了非x m l 的语法规则，不支持多种多样的数据类型，扩展性较差，不支持名称空间 ( n a m e s p a c e ) 等等。 因此，w 3 c 又推出了) ( m l s c h e m a t 3 0 规范。事实上s c h e m a 也是x m l 的一种应用，它 是将d t d 重新使用x m l 语言规范来定义。这从某种意义上讲正好体现了x m l 自描述性的 优点。与d t d 相比，x m l s c h e m a 具有如下一些优点： 1 一致性：s c h e m a 建立在x m l 之上，它的样子和一般的x m l 文件完全相同，使得x m l 达到了从内剑外的完美统一。 2 扩展性：s c h e m a 中引入了丰富的数据类型，它们包括：布尔型，数字，日期时间，u r l ， 整数，十进制数，实数，时问段，等等。而且它还支持由这些简单的类型生成复杂的类 型，以及由用户定义的数据类型( 原型) 。 3 规范性：同d t d 一样，s c h e m a 也提供了一套完整的机制以约束x m l 文档中标记的使 用，但相比之下，后者基于x m l ，更具有规范性。 4 支持名称空间。 5 互换性：每个人都可根据需要设计适合自己应用的s c h e m a ，并且可以同其他人交换彼 此的s c h e m a 。和用s c h e m a 能够书写x m l 文档，验证文档的合法性。另外，通过跃射 机制，还可以将不同的s c h e m a 进行转换，以实现更高层次的数据交换。 虽然x m ls c h e m a 有d t d 所不具备的很多优点，但在短期内d t d 还是有着它的优势 的：广泛的工具支持；广泛的应用；广泛的经验，d t d 应用多年，在实践中人们已积累了 许多宝贵的经验。 2 2 半结构化数据模型 半结构化数据缺乏统一结构，并且通常是自描述的，这就是说，模式和数据都存在于数 据之中。某些半结构化数据并没有固定的模式，另外一些半结构化数据虽然有模式但是对于 数据的约束不大。这些特点决定了半结构化数据不可能使用常规的关系摸型来进行描述，而 需要提出专门的半结构化数据模型。由于半结构化数据模型的灵活性，它可以描述绝大部分 其它数据模型的数据，考虑到这些原因。因此我们选择半结构化数据模型作为数据集成系统 的全局数据模型。 2 2 1o e m 半结构化数据模型 半结构化数据模型常见的有o e m ( o b j e c te x c h a n g em o d e l ) ”。o e m 是一种经典的半结构 化数据模型。o e m 在t s i m m i s 项目被首次提出来，引起了半结构化数据研究的热潮。差不 多在同一时期，s t a n f o r d 人学的另一个相关项目l o r e g l 入了o e m 的一个变形，它的不同之处 就在于边带标签，也就是通常所指的o e m 数据模型。 在o e m 数据模型中，数据是一个有向图，其中节点是对象，边的标签是属性名，某些 叶节点拥有原子值。o e m 数据可以用一个四元组疗= ( ke ，一来表示，其中：y = k uk 。v 是所有节点的集合，它是复杂对象集合啸原子对象集合i t 的并集；磋所有标签边的集合， 是v x a x 哟子集，其中a 是属性集合；r e 腥裉节点；y ：融缆原子对象的赋值定义( 磋 数据值的集合) 。图2 2 1 是一个o e m 数据模型的实例。其中正方形代表k 中原子对象( 其下 的字符串是该原子对象的值1 ，圆形代表k 中复杂对象，节点l 是根节点。 2 2 2 半结构化数据与x m l x m l 的基本思想很简单：数据元素的标签定义数据的意义，而不像h t m l 那样规定数 据的格式；另一方面，数据元素之间通过简单的嵌套和引用来描述其关系。然而它的影响是 深远的：如果w e b 服务器和应用程序都使用x m l 来编码数据，信息就能以一种简单而且可 用的格式表达，而且信息提供者可以轻松地进行互操作。信息内容从信息的表现中分离出来， 使得人们可以更容易地为同数据提供不同的视图。 由于具有这些特点，x m l 极大地方便了i n t e m e t 上的数据集成工作，近年来己经成为 w e b 上发布和交换数据的标准。许多数据源输出x m l 数据，并且使用d t d 或者x m l s c h e m a 描述信息内容：不论是本地存储x m l 文件或者将数据存放在关系数据库中t 都以x m l 的 方式对用户发布数据。同时也为数据集成提出了新的问题。 x m l 的基本语法非常适合描述半结构化数据pj ，x m l 文档核心其实就是一种半结构化 数据。在这个方面，已有人量的研究原型1 4 1 1 5 1 【6 】【7 1 1 8 1 1 9 1 0 1 等。 本文的工作正是在基于x m l 的半结构化数据集成系统的环境下展开的。 2 3 2 3 嵌套层次关系数据模型 为了便于描述，在本文中我们使用文献【l o 】中描述的数据模型，该数据模型同时支持关 系和x m l 两种类型的数据。 该模型包括一组原子类型f 的集合，记作s e l i d f i 订。另外还包括记录类型，形如 r c d a , ：r t ，缸硝，其中f f 可以表示一个原子类型，一个集合类型或者一个记录类型。符号 a ， ， 称作标签( 1 a b e l ) 或元素( e l e m e n t ) ，如果t 是一个原子类型，那么a ，就是一个原 子元素。r c d a , ：r z ，舭吼】类型的一条记录，是由标签值组成的数据对 a f a ， ，a = a p ，其中 a l , ，m 分别为f ，n 类型。集合类型s e t o f f t 的值用一个集合i d 以及一个相应的集合 e ，- ，b 来表示，其中自为类型q 。使用这种集合的表示方式( 通过i d 来标识一个集合) 非常有利于描述x m l 这种数据模式。为了方便描述，我们假定在本文中所有的s c h e m a 都 有唯一的一个根( r o o t ) ，就像在x m l 中那样。一个包含多个表的关系s c h e m a 是由一个记 录类型来表示的，该记录中每个元素是一个集合，而每个集合可以看作代表一个关系表。 2 3 半结构化数据中的约束关系 客观世界中存在多种语义约束，如关键字依赖、包含依赖，这些语义约束和数据表现 形式无关。不论数据是关系形式、对象形式还是半结构化数据形式，只要数据反映客观世 界，数据就满足语义约束。另一方面，如果集成系统中半结构化数据由关系数据、面向对 象数据转换而来，则原有数据形式中存在的语义约束应当在半结构化数据中得到保持。所 以，半结构化数据中存在语义约束。传统的查询重写没有考虑到数据中的语义约束。实际 上，在半结构化数据集成领域，考虑到数据源的不确定性，利用已有数据中的语义约束更 加重要。 2 3 1 半结构化数据中的约束关系 半结构化数据同其它形式数据一样，是现实世界的反映，也遵从现实世界的语义约束， 异构模式的信息通常需要转换到遵从d t d 或x m ls c h e m a 的通用模式。在此可以利用d t d 或 x m ls c h e m a 来形式化表达半结构化数据中的约束。 如果要表达x m l 中存在的语义约束，需要给出x m l 形式化的描述，在本文中，采用文 献【4 】中的定义，假定元素名称集合为e 属性名称集合为a ，字符串集合为s 所有矢量集合 为“则半结构化文档可以由以下定义表示。 定义1 ：半结构化数据树用4 元组( ke l e m 。a t t , r o o t ) 来定义，其中，壤示矢昔集合， e l e m 表示矢量到它的标签和其子女的映射( 无论是字符串值还是子树) ，鲥表示节点和属性名 称到元素值的映射，r o o t 是坤的一个特殊元素。 下文中，将使用下列标识：对于任何f 用e x t ( r ) 表示在冲标签为f 的节点集合：用t ， 来表示a t 玎t t ) ，即元素的属性，的值。n o d e s ( y p ) 表明有标签为y 的节点标签序列集合，p a t h s ( r ) 是节点标签序列集合，更准确地，p a t h s ( o 是属于纠腑号排列的集合。 在x m l 中， d d r e f 机制可用来表j 臼x m l 中的引用。但是，仅仅依赖上述简单的机制 不能表达更加丰富的语义约束，如关键字和包含依赖，所以，出现了大量x m l 语义描述的 研究，其中，文献【3 2 】研究了复杂x m l 语义的形式化定义和表达。 在x m l 中，存在类似对象标识的i d 属性，该i d 属性在整个x m l 文档中唯一。在x m l 中， 利用i d r e f 来表明对于对象标识的引用，i d r e f 相当于关系模式中的外键( f o r e i g nk e y ) 。和 传统的关系数据库不同，在x m l 中通过路径表达式来表达数据之间的约束。下面所定义的 三种约束分别表达了路径依赖约束、路径包含约束和路径逆反约束。这三种约束能够表达 x m l 中基本的语义约束信息。 1 路径依赖约束：p _ t 口，其中，f ep ，0 p a t h s ( t ) ，表明：v x ，y e x t ( r ) ( n o d e s ( x 力2n o d e s ( v p ) - + n 9 d e s ( x o = n o d e s ( y 毋) 。非形式化地，上述约束表明，如果节点媚过 路径p 得到的节点集合和节f 砂经过路径p 得到的节点集合相同，则节点斑过路径啼到 的节点集合和节点y 经过路径口得到的节点集合相同。通过这种约束可以表达类似关系模 式的关键字约束。 2 路径包含约束：3 1 p l c - f z p 2 ，其中。订，f 2 ep j p a l 嘶d ，p z e p a t h s ( r 2 ) ，表明： 1 3 e x t ( f ，p t ) e x t ( r 2 p 2 ) 。非形式化地，上述约束表明，节点订经过路 劫，得到的节点集合 是节点t 2 经过路径得到的节点集合以的子集，上述约束可以表达类似关系模式中的外键 约束。 3 路径逆反约束：r t p 0 f e p 2 ，其中，q ，勺ep t e p a t h s ( n ) ，, 0 2 e p a t h a ( t 2 ) ，表明：v x e e x t ( f 1 ) ，v y e e x l ( f 9 ( ，e n o d e s ( x p 1 ) + x e n o d e s o ：p 2 ) ) ；v x e e x t ( f 2 ) ，v y e 圳钾) n o d e s ( x p 2 ) - x n o d e s o p t ) ) 。 基于约束的查询重写过程中，输入的参数不但包括查询定义、映射定义、而且还包括在 查询数据上的语义约束集合，由于约束集合可能蕴涵着新的约束，为保证算法的完备性，应 首先计算出约束的闭包，即根据输入的约束集合获取该集合所能够推导出的所有约束。 在此提出了根据约束闭包图获取输入约束所蕴涵的约束闭包的方法。 定义2 ：约束闭包图疗= ( k0 ，其中壤明包含约束中元素的数据树的所有元素名和属 性名，璨合定义如下：从每一个元素到其属性建立一条边；如果在约束中存在= r 1 一“ 则在f 的属性腱立一条边一到元素f 如果在约束中存在= f i ，t 材，则在f 饷属性腱立一 条边到元素r i d ；如果在约束中存在= f ：，付t ，则在f 伯属性r 建立一条边付到f 的属 性，。 由上述的定义可知，图中的边表示元素之间的约束。利用下列规则，在图中构造约束 闭包。 如果在图中存在t p c 口，则对于任何t i 2 = “f 上p _ + t i l o ； 如果在图中存在z p z ：p 并且f ：p f ：p ”，则t p f ：p ”； 如果在图中存在z p c - - z p ， 则对于任何路径l ，【p e f ：p ：昏 如果在图中存在x = t 2 p 2 c “并且= = 研p ，印，则n p ， l ：2 p 2 ； 如果在图中存在x = r t p l 停功以，并且x = t 2 p 2 付 r 3 p j ，t i j x = r p ，p 2 付r 2 p 3 p ，。 根据上述约束的定义，易证上述规则是正确的。在文献【3 2 】中给出了完备的约束推导规 则，而本文中给定的约束闭包规则包含了上述推导规则，所以利用本文规则推导出的约束闭 包也是完备的。 在上述的约束闭包图中，应用上述规则直到约束闭包图不能发生变化为止。由于图中元 素的有限性，上述方法是可以终止的。根据得到的约束闭包图中的结构，可以获取输入约束 所蕴禽的所有约束的闭包。 定义3 ；给定查询q ，约束珊成的规则尼如果利用规则集合尼gr 对查询q 作变化， 得到查询q j ，如果对于任何数据库实例d ，q 佃归q ，( d ) ，则称上述规则胄，为等价约束记为 r t = e q u i v a l e n t ( r ) 。如果烈d ) q t ( d ) 。则称上述规则为偏序约束规则，记作r ，= p a r t i a l ( r ) 。 传统的数据集成系统中的查询处理没有考虑到数据中的语义约束。实际上，在半结构化 数据集成领域，考虑数据源访问的不确定性，利用已有数据中的语义约束更加重要。在本文 第四章中，我们探讨的查询重写就是基于约束的x m l 数据查询重写问题。该算法不仅利用 语义约束转换半结构化查询以提供中间层视图的表达能力；而且利用约束来组合不同数据源 中元组，来实现融合数据的目的。 1 4 第三章数据集成系统研究 在本章中酋先介绍了一个数据集成系统的理论框架。我们关注的数据集成系统其目标是 组合存在于不同数据源中的数据，给用户提供一个统一的全局集成视图。该统一的视图由全 局模式来表示，该视图为所有的数据提供协调的一致的全局集成视图，供用户提交查询。显 而易见，设计一个数据集成系统的关键任务之一就是建立数据源与全局模式之间的映射关 系。因此，在形式化的数据集成系统中也应该考虑这些映射关系。 在数据集成系统中根据全局模式与数据源模式的关系，将查询转换成数据源模式上的子 查询也是数据集成系统中非常关键的一步。在本章中我们也对集成系统中的核心研究问题之 一的查询处理进行了研究。 3 1 集成系统理论框架 数据集成系统框架( d a t ai n t e g r a t i o ns y s t e mf r a m e w o r k ) p 3 】主要由三个部分构成：全局模 式、数据源以及它们之间的映射关系。我们用，表示一个数据集成系统，因此，可以形式 化描述为一个三元组g & 彬，： g 代表全局模式，使用语言g 描述。k 使用符号表a g ；符号表a g 中每个符号对应g 中一个元素( 如果g 是关系型的，则其中每个元素就是一种关系；如果是面向对象的，每 个元素就是一个类) 。 s 是源模式，使用语言如描述。厶使用符号表a 肼符号表血中每个符号对应s 中一个 元素。 m 是g 和s 之间的映射关系，包含一组如下形式的对应关系：驰一们；g g 一驰。其中， 驰和们分别是基于源模式s 和全局模式g 提出的查询。查询卵使用符号表a s 上的语言厶s ， 查询q “使用符号表如上的语言厶啪。显然，一个映射和，犯表示源模式上的查询靠对应 于全局模式上的查询。反之，即一个映射g g 一船含义就是全局模式上的查询q g 对应于源 模式上的查询驰。 在系统中，数据源模式描述了真实数据所在的数据源结构，而全局模式为底层数据源提 供一个集成的、虚拟的视图。数据源和全局模式之间的映射关系则建立了全局模式元素与数 据源模式之间的联系。对数据集成系统，的查询都是建立在全局模式g 的基础上的，并使 用基于符号表a “的查询语言幻表述。查询实质上是对从数据集成系统所形成的虚拟数据库 中抽取的特定数据的形式化描述。 上述定义基本适用于所有的数据集成系统。显然，各种数据集成系统的区别在于其采用 映射方式，以及模式描述语言和查询语言的表现能力方面。比如：查询语言k 可能非常简 单，只允许基本的关系集合定义；或者允许用符号表一g 表达的各种形式的完整性约束条件。 下面我们将介绍数据集成系统的语义和查询语义： 假定存在一个模式为r 的数据库( d b ) 。它是由一个或多个集合所组成的集合，集合中 的每个元素对应模式r 的符号表中的一个符号( 如果r 是关系型的，则数据库中一个元素 关系，对应r 中一个关系名；如果，是面向对象的，则数据库中一个元素对象集合，对应 r 中一个类名) 。另外，我们假设与理论框架相关的所有数据库( 包括全局数据库或源数据 库) 中的组成成分均基于同一特定的定义域r 定义。 为了阐述一个数据集成系统，= g ，s 痧的语义，我们首先考虑，的一个源数据库d ， 它遵从源模式s 并满足其上的一切约束。基于数据库d ，下面我们来定义哪些是全局模式g 的数据内容。我们称基于模式g 的任意数据库为数据集成系统，的一个全局数据库。如果 满足下面两个条件，称数据集成系统，的一个全局数据库口对于源数据库d 合法。 1 曰符合g ，即口满足g 的所有约束； 2 对于源数据库d ，口满足m 定义的映射。 第二点，即b 对于d 满足m 定义的映射，依赖于我们如何解释这些映射也即映射方案。 然而，无论我们如何解释映射的语义，中仍可能存在多个全局数据库对于d 合法。 最后我们讲述数据集成系统中的查询语义。给定数据集成系统，的一个源数据库d ，对 于，上一个查询q ，记q 在源数据库为d 的情况下结果集为矿”。对于，的任一对d 合法的 全局数据库口记矿为查询q 在全局数据库b 上的结果集。很明显，它们都是r 中数据元 组或对象的集合。以后，如果不加特别说明，对于查询g 和数据库d b ，我们记g ”为查询 q 在数据库d b 上的结果集。 对于矿。的语义，我们有两种解释。对于元组或对象f 矿d 如果对川| 勺任