（计算机应用技术专业论文）数据集成中查询重写算法的研究.pdf

摘要 摘要 查询重写是数据库查询处理过程中的一个基本问题，与查询优化、物 理数据的独立性维护、数据集成、语义缓存、数据仓库和决策支持等问题 密切相关。随着数据集成的发展，数据集成中的查询重写问题成为近年来 的研究热点。本文对国内外数据集成中的查询重写的研究现状进行了综合 分析，从一个全新的角度对查询重写问题进行了研究。 首先，介绍了数据集成的基本理论和d a t a l o g 语言的基本概念，分析 了两种典型的重写算法，即桶算法和逆规则算法，并指出了这两种重写算 法存在的不足。 其次，介绍了传统的m i n i c o n 算法，并指出了该算法的不足，提出了 基于域约束的m i n i c o n 算法。该算法在传统的m i n i c o n 算法中增加了一步 视图选择，解决了传统的m i n i c o n 算法中丢失查询重写和生成冗余查询重 写的问题，保证了算法的正确性和完备性，并给出了相应的算法分析和实 例分析。 然后，分析了现有的聚合查询的重写算法穷举算法的不足，将 m i n i c o n 算法的思想融入到了聚合查询的重写中。针对c o u n t - 查询和$ 1 1 n 3 查询，分别提出了相应的重写算法c o u n t 算法和_rewritings u m _ r e w r i t i n g 算法，并对c o u n t _ r e w r i t i n g 算法进行了正确性证明和实例分析。 最后，对c o u n t _ r e w r i t i n g 算法和穷举算法进行了实验。实验结果证明 了c o u n t 算法的效率相对于穷举算法具有大幅度提高。_rewriting 关键词数据集成；查询重写；m i n i c o n ；域约束；聚合 燕山大学工学硕士学位论文 a b s t r a c t q u e r yr e w r i t i n gi sab a s i cp r o b l e mi nd a m b a s eq u e r yd i s p o s a lp r o c e s s i o n i t i sc l o s e l yr e l a t e dt ot h eq u e r yo p t i m i z a t i o n , m a i n t e n a n c eo fp h y s i c a ld a t a i n d e p e n d e n c e ，d a t ai n t e g r a t i o n , s e m a n t i cd a t ac a c h i n g ，d a t aw a r e h o u s i n ga n d d e c i s i o ns u p p o r t w i t ht h ed e v e l o p m e n to fd a t ai n t e g r a t i o n ，q u e r yr e w r i t i n g p r o b l e mi nd a t ai n t e g r a t i o nb e c o m er e s e a r c hh o t s p o t t h i sp a p e ra n a l y z e st h e c l l r r e n ts i t u a t i o no ft h ed o m e s t i ca n di n t e r n a t i o n a lq u e r yr e w r i t i n gp r o b l e mi n d a t ai n t e g r a t i o n ，a n dr e s e a r c h e sf o rt h ep r o b l e mo fq u e r yr e w r i t i n gf r o ma c o m p l e t e l yn c wp e r s p e c t i v e a tf i r s t , t h ee l e m e n t a r yt h e o r yo fd a t ai n t e g r a t i o na n db a s i cc o n c e p t i o no f d a t a l o gl a n g u a g ea r ei n t r o d u c e d t h r o u g ha n a l y z i n gt w oq u e r yr e w r i t i n g a l g o r i t h m s ，t h i sc h a p t e rp o i n t so u tt h ed e f i c i e n c i e so f t w oa l g o r i t h m s s e c o n d l y , t h r o u g ha n a l y z i n gt r a d i t i o n a lm i n i c o na l g o r i t h m , t h i sc h a p t e r p o i n t so u t t h ed e f i c i e n c i e so ft h ea l g o r i t h m c o n s t r a i n t - b a s e dm i n i c o n a l g o r i t h mi sp r o p o s e d t h i sa l g o r i t h ma d d sas t e po f v i e ws e l e c t i o n a sar e s u l t , t h ep r o b l e m so fm i s s i n gq u e r yr e w r i t i n g sa n dg e n e r a t i n gr e d u n d a n tq u e r y r e w r i t i n g si nt r a d i t i o n a lm i n i c o na l g o r i t h mi np r e s e n c eo fd o m a i nc o n s t r a i n t s a r es o l v e d ，a n dt h ea c c u r a c ya n dc o m p l e t e n e s so ft h ea l g o r i t h mi se n s u r e d t h i s c h a p t e ra l s og i v e st h ec o r r e s p o n d i n ga l g o r i t h m i ca n a l y s i sa n dt h ee x a m p l e a n a l y s i s t h i r d l y , t h r o u g ha 1 1 a l y z i n ga g g r e g a t eq u e r yr e w r i t i n ga l g o r i t h m i n e x i t e n c e ，t h i sc h a p t e rp o i n t so u tt h ed e f i c i e n c i e so fa l g o r i t h m t h em i n i c o r t a l g o r i t h m t h o u g h t i s i n t e g r a t e d i n t h e a g g r e g a t eq u e r yr e w r i t i n g c o u n t _ r e w r i t i n ga l g o r i t h ma n ds u m _ r e w r i t i n ga l g o r i t h ma r ep r o p o s e d t h e a c c u r a t ep r o o fa n dt h ee x a m p l ea n a l y s i sa r ec a r r i e do nt ot h ec o u n t _ r e w r i t i n g a l g o r i t h m a b s t r a c t f i n a l l y , t h ee x p e r i m e n t sa r ec a r r i e do nt oc o u n t _ r e w r i t i n ga l g o r i t h ma n d e x h a u s t i o na l g o r i t h m t h r o u g ha n a l y z i n ge x p e r i m e n tr e s u l t s ，i tp r o v e st h a tt h e a l g o r i t h me f f i c i e n c yi nc o u n t _ r e w r i t i n ga l g o r i t h mi sh i g h e rt h a nt h ea l g o r i t h m e f f i c i e n c yi ne x h a u s t i o na l g o r i t h m k e y w o r d sd a t ai n t e g r a t i o n ；q u e r yr e w r i t i n g ；m i n i c o n ；d o m a i nc o n s t r a i n t ； a g g r e g a t e i i i 燕山大学硕士学位论文原创性声明 本人郑重声明：此处所提交的硕士学位论文数据集成中查询重写算法的 研究，是本人在导师指导下，在燕山大学攻读硕士学位期间独立进行研究 工作所取得的成果。据本人所知，论文中除己注明部分外不包含他人己发 表或撰写过的研究成果。对本文的研究工作做出重要贡献的个人和集体， 均已在文中以明确方式注明。本声明的法律结果将完全由本人承担。 作者签字苏香张日期：o 缉1 2 月斗日 燕山大学硕士学位论文使用授权书 数据集成中查询重写算法的研究系本人在燕山大学攻读硕士学位 期间在导师指导下完成的硕士学位论文。本论文的研究成果归燕山大学所 有，本人如需发表将署名燕山大学为第一完成单位及相关人员。本人完全 了解燕山大学关于保存、使用学位论文的规定，同意学校保留并向有关部 门送交论文的复印件和电子版本，允许论文被查阅和借阅。本人授权燕山 大学，可以采用影印、缩印或其他复制手段保存论文，可以公布论文的全 部或部分内容。 保密口，在 本学位论文属于 不保密口。 ( 请在以上相应方框内打“4 ”) 作者签名：苏舂缒 导师签名：莎1 1 1 年解密后适用本授权书。 日期：o 幺f1 2 月耳日 日期：钙2 节日 第1 章绪论 1 1 研究背景 第1 章绪论 查询重写是数据库研究的一个基本问题，与查询优化【1 删、物理数据的 独立性维护【4 】、数据集成5 1 、数据仓库和决策支持 8 - 1 5 1 、语义缓存【1 “1 8 1 等问题密切相关，成为近年来的研究热点。 目前的数据集成系统一般遵从w i e d e r h o l d 提出的中间件模式【1 9 1 。为了 提高系统的查询效率，系统选择频繁提交的查询在中间层建立物化视图。 考虑到数据源访问的不确定性和网络传输的代价，当用户提交查询后，系 统尽可能利用中间层视图，而不是访问数据源来应答查询。本质上，这个 问题可以抽象为查询重写问题1 2 。 目前对于查询重写已做了大量的研究。早在1 9 9 6 年a y l e v y 等人首 先提出了桶算法。自此以后提出了大量的关系查询重写算法，大致可以分 为两类，基于桶的重写算法和基于逆规则的重写算法。如：桶算法 2 1 , 2 2 1 、 逆规则算法【2 3 2 5 1 、s v b 算、法【2 6 1 和m i n i c o n 算法【2 7 1 。 人们提出了大量的半结构化数据模型、查询语言、视图定义语言，以 满足数据集成、生物数据库、w e b 数据查询和管理、数字图书馆等各个领 域的半结构化数据管理1 2 8 j 的需要。大量半结构化数据的出现导致了对半结 构化数据的查询重写问题的研究 2 9 3 0 1 。文献【2 9 】在树查询语言t s l ( t r e e s p e c i f i c a t i o nl a n g u a g e ) 1 构基础上解决了基于o e m ( o b j e c te x c h a n g em o d e l ) 模 型的半结构化数据的等价查询重写问题；文献 3 0 贝l j 在提高文献【2 9 】的算法 效率方面做了一些有益的探讨。 在数据集成领域，随着x m l ( e x t e n s i b l em a r k u pl a n g u a g e ) 成为目前信 息表示和交换的标准，x m l 数据查询语言成为中间层定义物化视图的查询 语言，迸一步讲，集成系统面临的一个问题是半结构化x m l 数据的查询 重写的问题。为了解决这一问题，提出了一些基于x m l 的查询重写算法。 燕山大学工学硕士学位论文 如：基本查询重写算法和查询分解算法【”1 。 1 2 研究现状 查询重写是近年来的研究热点。目前，国内外已提出了大量的重写算 法。下面分别介绍国内外的研究成果。 1 9 9 6 年v l d b ( v e r yl a r g ed a t a b a s e s ) 会议上，a y l e v y 等人提出了桶 算法( 2 。桶算法的主要思想是：对于给定的查询q ，首先，为查询的每个 子目标创建一个桶，并将视图放入相应的桶中。然后，通过合并每个桶中 的视图生成候选的查询计划。最后，用包含测试来证明这些计划的正确性。 这种算法的缺点是视图连接的运算量较大。 1 9 9 7 年p o d s ( p r i n c i p l e s o f d a t a b a s es y s t e m s ) 会议上，o d u s c h k a 等人 提出了逆规则算法1 2 4 1 。逆规则算法的主要思想是：建立从视图定义转化而 来的规则集合，也就是说，规则集合展示了怎样利用视图中的元组来计算 数据库关系中的元组。 2 0 0 0 年，o d u s c h k a 等人考虑了关系型l a v 数据集成系统中基于约束 的查询应答问题。他们的算法提出了一个递归的查询计划，通过一系列的 递归规则来进行合并 3 2 】。 2 0 0 1 年，m i t r a 等人提出了s v b 算法1 2 “。s v b 算法的主要思想是：如 果一个体变量出现在多于一个视图子目标中，则视其为共享变量。在s v b 算法中，给定查询q ，创建两种类型的桶。一种类型的桶是一个查询子目 标对应一个桶，另一种类型的桶是为共享变量创建的桶。一旦创建完所有 的桶，算法将通过合并视图来生成重写查询。 2 0 0 1 年v l d b 会议上，a h a l e v y 等人提出了m i n i c o n 算法1 2 ”。m i n i c o n 算法的主要思想是：在算法的第一阶段，为查询q 创建m i n i c o n 描述( 简称 m c d ) 。m c d 与s v b 算法中的桶扮演着同样的角色。m i n i c o n 算法中的 m c d 和最小m c d 分别对应s v b 中单个子目标的桶和共享变量的桶。在 第二阶段，m i n i c o n 算法合并m c d 生成重写查询。m i n i c o n 算法是一种可 伸缩的高效的重写算法，但它没有考虑完整性约束，也没有考虑含有聚合 2 第l 章绪论 函数的查询的重写。 2 0 0 2 年，高军等人提出了c o m m i x 算法【3 3 】。该算法是建立在o e m 模型之上的。c o m m i x 算法的主要思想是：首先，根据查询定义建立查询 子目标对应的桶。然后，建立桶中从查询子目标到视图的映射，再根据桶 中的每一个映射查找最优映射集。最后，在最优映射集的基础上构造新查 询并验证是否正确。 2 0 0 2 年，高军等人提出了一种新的半结构化数据查询重写的算法【2 0 1 。 相对于传统的查询重写算法，该算法分析了半结构化数据之问的约束关系。 根据得到的约束关系对查询进行变换，利用已有的物化视图来应答尽可能 多的查询，扩展了查询重写方法的应用范围。 2 0 0 2 年，b m l l l a n n 等人提出了在不完整映射和存在目标约束的条件下 的查询重写问题【3 4 i 。但是他们只是处理简单的映射、查询和约束，并没有 分析算法的属性( 如完整性) ，也没有对算法进行实验以证明其有效性。 2 0 0 3 年，a d e u t s c h 等人提出了m a r s 系统【”j 。m a r s 系统为混合模 式( 包括x m l 模式和关系型模式) 的查询重写提供了有效的方法。方法中， 从数据源到目标模式之间的映射是无损的，所以查询重写是等价保持的。 该算法还考虑到了目标约束。 2 0 0 4 年，陶春等人提出了半结构化查询重写的m i n i c o n 算法【3 6 l 。半结 构化查询重写问题具有如下的新特点：首先，变量之间隐含着对象标识符 依赖。其次，对象模式中值变量具有二义性，既可能映射为原子值，也可 能映射为对象模式的集合，因此包含映射需要更加复杂的定义。最后，函 数符号的引入也会带来额外的复杂性。这些特点在半结构化查询重写中都 需要解决。半结构化查询重写的m i n i c o n 算法基于t s l 查询语言，借用了 m i n i c o n 算法的思想，解决了这些问题。它提升效率的基本思想是减少子 目标匹配的重复性工作，尽早裁减不必要的搜索分支。 2 0 0 4 年，钱钢等人提出了一种实现数据集成中查询重写的方法1 37 1 。基 于路径映射的x m l 数据集成系统在查询重写时可能会生成不合理的子查 询。为了让生成的各个子查询中的实体属性是一致的，按照模式之间的路 径映射提出了映射依赖的概念，并设计了一种查询重写的方法。重写时依 3 燕山大学工学硕士学位论文 次遍历查询树的各个结点，记录每个中间结果的p c 环境，根据启发式规 则判断p c 环境与当前映射的依赖是否保持一致。在时间复杂度上，该方 法和数据源的数目成线性关系。 2 0 0 4 年s i g m o d ( s p e c i a li n t e r e s tg r o u po i lm a n a g e m e n to fd a m ) 会议 上，c y u 等人提出了基本查询重写算法和查询分解算法刚。这两种算法的 数据源模式可以是关系型模式和x m l 模式的任意组合。基本查询重写算 法是对于嵌套结构而言第一个基于映射进行查询重写的完整的算法。查询 分解算法是基本查询重写算法的扩展，考虑了目标约束( 嵌套的等价生成依 赖 3 8 , 3 9 ) 。方法中，映射是不完整映射，为目标模式提供了不完整视图。这 种不完整性导致了查询重写的结果得到的是被包含重写，如果可能的话得 到最大被包含重写，而不是等价重写。这种含有有损映射的数据集成系统 的设计是现实世界的需求。通常从每个数据源到目标模式的映射的定义是 独立于其他映射或其他数据源的，并且仅仅涉及目标模式的一部分，这种 设计的优点是模块性。新的映射或目标约束可以很容易添加到系统中，而 不会影响其他的映射和约束。这两种算法的缺点是没有考虑到含有聚合函 数的查询的重写。 2 0 0 5 年s i g m o d 会议上，s c o h e n 等人对聚合查询的等价问题进行了 概述【4 0 j 。首先，讨论了聚合查询的等价与非聚合查询的等价之间的不同。 然后，介绍了聚合查询的等价问题的一些重要成果。 2 0 0 5 年，s m o h a n 等人针对x m l 的访问控制提出了一个动态的查询 重写方法【4 l l 。a d f u x m a n 等人为不一致数据库提出了f i r s t o r d e r 查询重 写方法h 2 】。 1 3 研究意义 查询重写与数据库查询处理过程中的若干问题密切相关，下面简要介 绍一下查询重写的三个主要应用。 查询重写的第一个应用是查询优化和数据库设计。在查询优化领域中， 因为查询计算的一部分在计算视图时已经得到，所以运用现有的物化视图 4 第1 章绪论 来计算查询可以节约查询处理的时间。当视图和查询包含分组和聚合函数 时，这种节约在决策支持应用中是非常重要的。在数据库设计领域中，视 图定义提供了支持数据的物化视图和逻辑视图的独立性的机制。这种独立 性使改变数据的物化视图的同时不需改变它的逻辑视图，并且可以为更复 杂类型的索引建模。所以，可以将存储模式看作逻辑模式上的一组视图， 当己知存储模式的描述时，计算查询执行计划的问题即为解决如何利用视 图来应答查询的问题。 查询重写的第二个应用是数据集成。数据集成系统为多个自治的数据 源提供统一的查询接口。数据集成系统使用户不需确定与查询相关的数据 源，然后从多个数据源手工合并数据。数据集成系统的用户不是根据数据 的存储模式提出查询，而是根据全局模式提出查询。全局模式是为特定的 数据集成应用设计的一组关系。数据集成系统中并不存储全局模式的元组， 系统中包含一组数据源描述，该描述提供了数据源模式与全局模式之间的 语义映射。 查询重写的第三个应用是语义缓存。在一些操作中，缓存在客户端的 数据是用一组查询来进行语义建模，而不是用一组数据页或元组。所以， 为了应答给定的查询，并决定哪些数据需要从服务器装载，可以运用缓存 视图来应答。 1 4 本文主要研究内容 根据上面所阐述的研究背景和研究现状，课题的研究内容主要可以分 为以下两个方面。 ( 1 ) 对m i n i c o n 算法的改进对m i n i c o n 算法进行了深入的研究，提出 了基于域约束的m i n i c o n 算法，解决了m i n i c o n 算法中丢失查询重写或生 成冗余查询重写的问题，保证了算法的正确性和完备性。 ( 2 ) 研究了聚合查询的重写问题分别提出了c o u n tr e w r i t i n g 算法和 s u m _ r e w r i t i n g 算法，借用了m i n i c o n 算法的思想，解决了在给定一个连 接的c o u n t 查询( 或s u m 查询) 和一组连接的c o u n t - 视图的情况下，找到最 5 燕山大学工学硕士学位论文 大被包含重写的问题。证明了算法的正确性，并进行了实验验证。 1 5 本文组织结构 本论文总体上分为5 章，从第2 章开始具体布局如下。 第2 章介绍基础知识。首先，介绍了数据集成模型和数据源描述的方 法。然后，介绍了d a t a l o g 语言。最后，分析了两种典型的查询重写算法， 并指出了这两种算法的不足。 第3 章提出了基于域约束的m i n i c o n 算法。首先，介绍了m i n i c o n 算 法。然后，提出了基于域约束的m i n i c o n 算法，并进行了算法分析。 第4 章提出了c o u n tr e w r i t i n g 算法和s u mr e w r i t i n g 算法。首先，介 绍了现有的聚合查询的重写算法。然后，提出了c o u n tr e w r i t i n g 算法和 s u mr e w r i t i n g 算法，并进行了算法分析和正确性证明。 第5 章是算法的实验验证。本章对c o u n t 算法进行了实验验rewriting 证和结果分析。 最后是本文的结论，并对下一步的研究工作进行了展望。 6 第2 章基础知识概述 2 1 数据集成 第2 章基础知识概述 在一个大型企业的信息化建设过程中，可能由于各种历史条件的限制， 各个部门根据各自的信息要求和特定的应用选择了各自的软硬件环境，从 而使得在一个企业往往存在着多种不同类型的硬件平台、操作系统、网络 协议和来自不同厂商的数据库管理系统。数据的这种按部门或功能进行组 织和管理，导致了企业数据资源与服务的分片，形成了一个个“信息孤岛”。 “信息孤岛”不仅增加了企业维护数据的费用，而且企业很难根据分散的 数据做出正确的决策。为了改善这种局面，同时在各个“信息孤岛”之中 共享和交换数据，并且给企业用户提供企业数据的集成视图，从而根据集 成之后的数据及时的调整业务策略，就必须考虑数据集成问题。 随着网络技术的推广和普及，网上的信息迅猛增加，成为一个巨大的 信息库，由成千上万个异构的信息源组成，有传统的数据库、文件系统、 及h t m l 、x m l 等半结构化的数据。但由于平台差异、数据库技术以及 通信协议等方面的不同，使各数据源间的互操作变得复杂、困难，使它们 成为信息孤岛。如何更好的利用网络上浩如烟海的信息，已成为人们日益 关心的问题。数据集成系统在其中扮演着十分重要的角色。 2 1 1 数据集成模型 在企业数据集成领域，已经有了很多成熟的框架可以利用。目前通常 采用联邦式、基于中间件模型和数据仓库等方法来构造集成的系统，这些 技术在不同的着重点和应用上解决数据共享和为企业提供决策支持。在这 里将对这几种数据集成模型做一个基本的分析。 联邦数据库系统由半自治数据库系统构成，相互之间分享数据，联盟 各数据源之间相互提供访问接口，同时联盟数据库系统可以是集中数据库 7 燕山大学工学硕士学位论文 系统或分布式数据库系统及其他联邦式系统。在这种模式下又分为紧耦合 和松耦合两种情况，紧耦合提供统一的访问模式，一般是静态的，在增加 数据源上比较困难；而松耦合则不提供统一的接口，但可以通过统一的语 言访问数据源，其中，核心问题是必须解决所有数据源语义上的问题。 中间件模式通过统一的全局数据模型来访问异构的数据库、遗留系统、 w e b 资源等。中间件位于数据源系统( 数据层) 和应用程序( 应用层) 之间，向 下协调各数据源系统，向上为访问集成数据的应用提供统一的数据模式和 数据访问的通用接口。各数据源的应用仍然完成它们的任务，中间件系统 则主要为异构数据源提供一个高层次的检索服务。 数据仓库是在企业管理和决策中面向主题的、集成的、与对间相关的 和不可修改的数据集合。其中，数据被归类为广义的、功能上独立的、没 有重叠的主题。 这几种方法在一定程度上解决了应用之间的数据共享和互通的问题， 但也存在以下的异同。 联邦数据库系统主要面向多个数据库系统的集成，其中，数据源有可 能要映射到一个数据模式，将会带来n x ( n 1 ) 的开销，当集成的系统很大 时，对实际开发将带来巨大的困难。 中间件模式是目前比较流行的数据集成方法，它通过在中间层提供一 个统一的数据逻辑视图来隐藏底层的数据细节，使得用户可以把集成数据 源看为一个统一的整体。这种模型下的关键问题是如何构造这个逻辑视图 并使得不同数据源都能映射到这个中间层。 数据仓库技术则在另外一个层面上表达数据之间的共享，它主要是为 了针对企业某个应用领域提出的种数据集成方法，也就是在上面所提到 的面向主题并为企业提供数据挖掘和决策支持的系统。 本文的研究内容所涉及的数据集成系统是基于中间件模式的。 2 1 2 数据源描述的方法 在数据集成系统中，为了应答查询，系统必须包含一系列的数据源描 述，以便将全局模式上的查询重新阐述为数据源模式上的查询。因为全局 8 第2 章基础知识概述 模式关系不能与数据源关系进行一对一匹配，所以数据源描述是必要的。 全局模式与数据源模式的错误匹配有两个原因：首先，数据源模式在细节 上彼此不同，与全局模式也不同。其次，为相同信息的不同建模，它们将 以不同的方式将属性划分到关系中。数据源描述现有三种方法。 一种方法是将全局模式定义为局部模式上的一个视图，这种方法被称 为g l o b a l - a s v i e w ( 简称g a v ) 。g a v 处理的情况是数据源包含的细节不在全 局模式中出现。g a v 描述的形式是： v l ( x l ，】，1 ) v ，( z ，y j ) = ，( r ) 式中，v 是数据源关系，r 是中间模式关系，并且x = u x ，。 另一种与之相反的方法是将局部数据源定义为全局模式上的视图，这 种方法被称为l o c a l a s v i e w ( 简称l a v ) 。l a v 处理的情况是全局模式包含 的细节不在每个数据源中出现。l a v 描述的形式是： v ( ) ；r l ( x i ，z 1 ) a r k ( 石t ，z 女) g a v 和l a v 的权衡如下。在g a v 方法中，将全局模式上的查询翻译 为局部模式上的查询是一个视图展开的过程。在l a v 方法中，全局模式上 的查询需要根据局部数据源模式来重新阐述。传统的，这个过程被称为“运 用视图重写查询”，也是本文的研究内容。另一方面，在g a v 体系结构中， 若局部数据源集合或其模式做了修改，则需要根据所有的修改来重新设计 新的全局模式，并且，如果局部数据源没有统一的数据格式，则全局模式 是很难设计的。在l a v 中，每个数据源可以独立描述。 g a v 方法的缺点是为冗余的数据源数据建模很难。l a v 的缺点是所有 可用的私有数据都在发布视图的数据中，所以，l a v 方法不能恰当的支持 秘密私有数据隐藏。 g l a v 方法综合了l a v 和g a v 的表达能力，允许数据源描述中包含 数据源上的递归查询，允许弹性模式定义，独立于数据源的详细细节。 g l a v 的形式为： v ( x ，r ) j n ( x i ，z 1 ) a r k ( x k ，z k ) 式中，( u ，z ，) n y = 由，v ( x ，y ) 是数据源关系的连接，或是数据源关系上 9 燕山大学工学硕士学位论文 d a t a l o g 查询的查询谓词。 2 2 d a t a l o g 语言 关系代数是关系型数据库的理论基础，是数据库产品应用和发展的坚 实基础。随着数据技术的不断提高，关系代数也暴露了一些局限性，例如， 无法有效的表示递归运算和逻辑表达能力弱等。在这种情况下，d a t a l o g 语言应运而生。d a t a l o g 语言是一种基于逻辑编程语言p r o l o g 的一种非过 程化的语言。就像使用关系验算一样，用户只需要给出所描述的信息，不 需要给出获取信息的具体过程。d a t a l o g 语言使用声明的方式定义，简化了 简单查询的书写，使查询优化更容易进行。 d a t a l o g 语言也可以表示关系查询。d a t a l o g 语言不是使用过程语言来 表示查询，而是使用一种规则来表示出这种想法，即可以通过己知的关系 中的某些元组的组合来推测某个其他元组是否在某个其他关系中。在本文 中就是用d a t a l o g 语言来表示查询。 2 2 1基本概念 2 2 1 1 基本结构d a t a l o g 语言包括了两种基本的原子，即关系原子和算 术原子。d a t a l o g 语言是由这些原子按照一定的规则组成的。 在d a t a l o g 语言中，关系通过称为谓词的符号来表示，每一个谓词都 有固定数量的参数。关系原子是由符号谓词和其后的参数组成，关系原子 也经常简称原子。例如，如果谓词是r 其参数分别是t l ，t 2 ，t n ，那 么r ( h t 2 ，t 1 1 ) 就是一个关系原子。 从本质上讲，谓词是一个可以返回布尔值的函数名。例如，如果关系 r 是以某种固定顺序排列的n 个属性的关系，那么一般使用该关系名称r 作为这个谓词的名称。例如，如果( u 1 ，u 2 ，i l i i ) 是关系r 的个元组，那么 关系原子r ( u l ，u 2 ，) 的值为真( t r u e ) ；相反，如果( u j ，1 2 ，u 。) 不是关系r 的元组，那么关系原子g ( u 1 ，u 2 ，u 1 1 ) 的值为假( f a l s e ) 。 在d a t a l o g 语言中，谓词后面的参数，既可以是变量，也可以是常量。 l o 第2 章基础知识概述 如果一个关系原子的参数都是变量，那么该关系原子就是一个布尔值函数， 该函数的值随变量取值不同而为真或假。 算术原子是两个算术表达式的比较。算术原子的值也是布尔值。例如， 下面就是一些算术表达式的实例。 x y x 4 + t 5 x x 8 x y = 6 算术原子和关系原子是非常类似的，它们都是d a t a l o g 语言中的基本 元素，都是以任意变量为参数，取值都是为真( t r u e ) 或为假( f a l s e ) 。 这两种基本元素也存在着差别。在效果上，算术运算( 例如= 或 等) 就 像是某个关系名，其关系实例包括了比较结果为真的所有参数对。因此， 可以把关系运算x _ 2 5 0 在上面的d a t a l o g 规则中，头部是关系原子t h i c k b o o k ( t i t l e ) ，规则体包 括了以下两个子目标。 第一个子目标是由谓词b o o k 和6 个参数组成的关系原子。这些参数 分别对应着关系b o o k 的6 个属性。当该子目标取值关系b o o k 的当前实例 时，关系原子为真。否则，当取值关系b o o k 的非当前实例时，关系原子 为假。 第二个子目标是一个算术原子p a g e n u m b e r 2 5 0 ，它表示当图书的页 数大于或等于2 5 0 时该算术原子为真。 2 2 1 3 安全规则d a t a l o g 语言是一种由许多原子构成的规则，规则包含 了许多变量。规则的目标是使规则的头部关系原子为真。由于关系实例总 是有限的，所以还需要由规则保证得到的头部关系也都是有限的。如果得 到的头部关系是无限的，那么这种规则是无意义的。 如何保证得到的查询结果是有意义的。在子目标中，包括了关系子目 标、求反关系子目标、算术子目标和求反算术子目标。 关系子目标总是有限的。因为任何一个关系的实例总是有限的，所以 不论关系子目标中的变量如何变化，使关系子目标为真的值是有限的，即 变量的取值范围是被限制的。关系子目标的取值总能保证查询结果是有意 义的。 如果对关系子目标求反，则一般是无意义的。如果对关系子目标r ( x ，y ) 求反，即n o tr ( x ，y ) ，那么使得n o tr ( x ，y ) 为真的x 和y 的取值是无限的， 因为使得r ( x ，y ) 为假的x 和y 的取值则使得n o tr ( x ，y ) 为真。所以，为了 使求反关系子目标的取值是有限的，必须限制求反关系子目标的参数取值 在一定的范围内。 再看算术子目标。一般来说，可以使算术子目标为真的变量取值是无 限的。例如x s y 这种算术子目标，有无限的x 和y 的取值使其为真。同样， 使得求反算术子目标为真的变量取值也是无限的。所以，为了使得头部关 系有意义，必须保证算术子目标中变量的取值限制在一定的范围之内。 1 2 第2 苹基础知识概述 为了保证规则的结果有意义，使得带有算术予目标或求反子目标的规 则具有直观的意义，可以增加对规则中变量使用范围的限制条件，这种条 件就是安全规则。安全规则的含义是：出现在规则中任何地方的变量必须 出现在某个非求反的关系子目标中。也就是说，在头部、求反关系子目标 或任何算术子目标中出现的变量，必须出现在非求反的关系子目标中。通 过把变量限制在取值有限的关系子目标中，使得规则的查询结果是有限的。 2 2 2 关系代数向d a t a l o g 规则的转换 2 2 2 1 从集合运算到d a t a l o g 规则集合运算是关系代数的最基本的运 算形式，包括了交集、并集和差集三种运算形式。下面介绍如何使用d a t a l o g 规则模拟这三种集合运算形式。 交集运算可以使用一个d a t a l o g 规则来表示。由于交集运算涉及了两 个关系，那么在d a t a l o g 规则中，具有与两个关系对应的子目标。在规则 中，相应的参数使用相同的变量。 例如，关系p r e s s 包括了三个属性，即n a m e 、a d d r e s s 和p o s t c o d e 。假 设两个关系具有与p l e s s 相同的关系模式，那么这两个关系的交集可以使 用下面的d a t a l o g 规则来表示： i ( n ，a ，p ) + u ( n ，a ，p ) a n dv ( n ，a ，p ) 在上面的d a t a l o g 规则中，i 是一个i d b 谓词，其对应的关系是u n v 。 该d a t a l o g 规则的含义是，对于某个元组，为了使两个子目标都为真，该 元组必须同时在关系u 和v 中。 并集运算可以使用两个规则来表示。在d a t a l o g 规则中，每一个规则 都对应着一个并集运算中的关系，且两个规则的头部都有相同的i d b 谓词。 头部的参数与各个子目标中的参数完全相同。 例如，为了得到前面示例中关系u 和v 的并集，可以使用下面的两个 规则： 0 ) w ( r l ，a ，p ) 卜u ( n a p ) ( 2 ) w 仳a ，p ) 扣v ( n ，a , p ) 在上面的d a t a l o g 规则中，规则( 1 ) 表明关系u 中的每一个元组都是关 1 3 燕山大学工学硕士学位论文 系w 的一个元组，规则( 2 ) 表示关系v 中的每个元组也都是关系w 的一 个元组。这两个规则合在一起意味着并集u u v 中的每一个元组都在w 中。 如果在规则中没有写更多的涉及关系w 的规则，那么任何其他元组都不能 进入到关系w 中。因此，可以说关系w 正好是u u v 。 由于关系是集合，所以即使一个元组在两个关系u 和v 中都出现，那 么它在关系w 中也只能出现一次。 差集运算可以使用具有求反子目标的一个规则来计算。也就是说，如 果计算两个关系u 和v 的差集，那么可以这样来计算，非求反子目标是谓 词u ，求反子目标是谓词v 。在该规则中，子目标和头部对于相应的参数 都有相同的变量。 例如，如果求关系u 和v 的差集，那么可以把u v 表示为如下所示 的d a t a l o g 规则： y ( n ，a ，p ) 卜u ( n ，a ，p ) a n dn o tv a , p ) 2 2 2 2 从投影运算到d a t a t o g 规则把关系代数中的投影运算形式转换 成d a t a l o g 规则，可以使用一个具有单一子目标的规则。该子目标的参数 是数量不同于关系的属性数量的变量，每一个变量都对应着关系的一个属 性。头部是带有参数的原子，这些参数是按照要求的顺序与投影的属性表 对应的变量。头部原子的这些变量只是子目标投影过来的变量，因此两者 的数量不同。 例如，如果希望把关系模式： b o o k ( i s b n ，f i t l t ，p a g e n u m b e r , b o o k t y p e ，p r i c e ，p r e s s n a m e ) 投影到该关系模式的前两个属性i s b n 和t i t l e 上，那么可以使用下面 的d a t a l o g 规则： t ( i s b n ，t i t l e ) 卜b o o k ( i s b n ，r i f l e ，p a g e n u m b e r , b o o k t y p e ，p r i c e ，p r e s s n a m e ) 在上面的规则中，头部关系原子t ( i s b n ，t r l e ) 就是投影的结果。 2 2 2 3 从笛卡儿乘积到d a t a l o g 规则两个关系u 和v 的笛卡儿乘积 u x v 可以使用单一的d a t a l o g 规则来表示。在这个d a t a l o g 规则中，有两 个子目标。一个子目标对应关系u ，另一个子目标对应关系v 。每一个子 目标都有不同的变量，每一个变量对应关系u 或v 中的一个属性。头部关 1 4 第2 章基础知识概述 系原子把出现的两个子目标中的所有变量作为参数，且严格按照出现的先 后顺序，即出现在关系u 子目标中的变量排列在关系v 子目标的变量之前。 例如，两个关系模式u 和v 分别是u ( a , b ，c ，d ) 和v ( e ，f , g ，h ) ，那么可以 使用下面的d a t a l o g 规则表示u x v ： w ( a , b ，c ，d ，e ，f , g ，h ) 卜u ( a bcd ) a n dv ( e ，f , g ，h ) 在这里，应该尽量避开相同属性的名称。如果两个关系u 和v 中有相 同的属性，那么应该首先对其属性进行改名运算。 改名运算不需要使用d a t a l o g 规则，而只需要直接引用即可。例如， 对于关系模式u ( a , b ，c ，d ) ，如果需要把其四个属性的名称分别改成x 、y 、z 和t ，且关系名称改为v ，那么不可以使用下面的d a t a l o g 规则，因为该规 则是不安全的： v ( x ，y , z ，0 卜u b ，c ，d ) 应该使用下面的d a t a l o g 规则把谓词名称改变，然后，直接引用 v ( x ，y , z ，0 关系模式即可： v ( a , b ，c ，d ) - u ( a ，b ，c ，d ) 2 2 2 4 从选择运算到d a t a l o g 规则把关系运算中的选择转换为d a t a l o g 规则是比较复杂的。下面只介绍一种简单的情况。 如果选择条件是一个算术比较表达式或多个比较表达式的a n d 运算， 那么可以建立一个具有下列子目标的d a t a l o g 规则。 一个关系子目标对应于将其进行选择的关系。该关系子目标的每一个 分量都有不同的变量，且每一个分量都对应关系的一个属性。 多个算术子目标，每一个算术子目标都对应着选择条件的一个比较运 算。虽然在选择条件中使用属性名，但是在算术子目标中却使用相应的变 量，并且与关系予目标中建立的变量保持一致。 例如，b ( i ，t ，n b ，t p ，p ，n m ) - -