（计算机软件与理论专业论文）多数据库系统下统一查询平台的研究与应用.pdf

中山人学硕i ：学位论文多数据库系统下统一企咖、r 台的研究。j 应用 多数据库系统下统一查询平台的研究与应用 专业名称：计算机软件与理论 学位申请人：赵曜 指导教师：李磊教授 摘要 随着通信技术和数据库技术的发展，越来越多的应用系统需要访问一些异构 的，分布的数据库来完成任务。 本文对多数据库系统中模式集成、全局查询的分解和优化等问题进行了详细 而深入的研究和讨论。对于模式冲突的消解，本文采用了局部数据库视图集成， 异构数据库模式匹配的方法来处理数据库系统集成的方法。对于查询分解和查询 语句的优化，则在使用关系代数范式的基础上，对查询语句进行了基于关系代数 等价原则的优化，并对存在语义副本的查询进行了基于代价分析的优化。对于查 询后的优化处理，详细分析了静态和动态的不同优化策略的优缺点，采取了介于 二者之问的新策略，以静态形成的初始优化作为参考，在系统运行中动态调整。 对于数据库访问安全的处理上，首先详细分析了现有的几种用户权限授权方式， 然后使用了新式的基于角色的访问控制模型，达到了安全性和授权难易程度的平 衡。 最后，本文提出了一个多数据库下查询统一平台的原型，并在m i c r o s o n 的n e t 框架平台下进行了实现该系统屏蔽了各局部数据库的差异，以全局数据 库的方式向用户提供查询功能。 查询优化器的进一步完善将是本文以后的研究重点。 关键字：多数据库，模式异构，查询分解，查询优化，安全控制 中山人学顺l ：学位论义多数据库系统下统一查询r 台的研究。i 应用 r e s e a r c ha n d a l p p l i c a t i o no f u n i f i e ds e a r c h p l a t f o r m b a s e do nt h em u l t i d a t a b a s es y s t e m m a j o r ：c o m p u t e rs o r w a r ea n dt h e o 巧 n a m e ：z h a oy ，a o s u p e r v i s o r ：p r c f e s s o rl il e i a b s t r a c t a sc o m m u n i c a t i o nt e c l u l 0 1 0 9 ya i l dd a t a b a s et e c h n 0 1 0 9 yd e v e l o p i n g r a p i d l y ， m o r ea 1 1 dm o r ea p p l i c a t i o ns y s t 锄sh a v et oa c c e s s m a n yh e t e r o g e n e o u s a 1 1 d d i s t d b u t e dd a t a l b a s e st oa c h i e v et h e i rt a s k s 。 i nt h i st h e s i s ，s c h e l n ai n t e 鲈a t i o n ，舀o b a lq u e 巧d e c o m p o s i t i o na n do p t i m i z a t i o n a n d 四o b a l 仃a n s a c t i o n sm a n i p u l a t i o n i nm u l t i d a t a b a s e s y s t e m s a r ed i s c o u r s e e l a b o r a t e l y t oc l e a ru pm ep a t t e mc o n n i c t ，锄sp 印e ru s e sl o c a ld a t a b a s ev i e w i n t e 孕a t e d a n dh e t e r o g e n e o u sd a t a b a s ep a t t e n lm a t c h i n gt o 印p r o a c ht od a t a b a s e s y s t e mi n t e 伊a t i o nm e t h o d s f o r e n q u i r i e sd e c o m p o s i t i o na i l dq u e 叫s t a t e m e n t o p t i m i z a t i o n ，o nt h eb a s i so fu s i n gr e l a t i o n a la l g e b r ap a r a d i g m ，w eo p t i m i z et 1 1 eq u e 巧 s t a t e m e n tb a s e do nt l l er e l a t i o n a la l g e b r ae q u i v a l e i l c ep r i n c i p l ea n dt h eq u e w 、v 1 1 i c h h a ss e m a l l t i cc o p yb a s e do nt h ea n a l y s i so ft h ec o s t f i n a l l y ，f o rt h eo p t i m i z a t i o na f t e r q u e r y ，w ea 1 1 a l y z et h ea d v a j l t a g e sa 1 1 dd i s a d v a n t a g e so fm es t a t i ca n dd y l l a n l i c o p t i m i z a t i o ns t r a t e 舀e si nd e t a i l ；a d o p tt h en e ws t r a t e g yb e t w e e nt h e m ，a sas t a t i cf o m t h ei n i t i a l o p t i m i z a t i o na sar e f - e r e n c e ，t 1 1 es y s t 锄i s1 1 j n l l i n gi nt 1 1 ed y n 锄i c a d j u s t n l e n t f o rt h es a f e t yo fh a i l d l i n gd a t a b a s ea c c e s s ，f i r s t ，w e a 1 1 a l y z es e v e r a lu s e r a c c e s sc o n t l 0 lm e t h o d si nd e t a i l ，t h e nw eu s et h en e wr o l eb a s e da c c e s sc o n t r o lm o d e l ， b a l a n c e dt h es e c u r i t ya n dt h ed i 硒c u l t yo ft h ea u t h o r i z a t i o n i i a te n do ft h i st h e s i s ， au n i f i e ds e a r c hp l a t f o 舯 p r o t o t y p eb a s e do nt h e m u l t i d a t a b a s ei sp r e s e n t e da n di t i s i m p l e m e n t e di nm i c r o s o r n e tf r 锄e w o r k p l a t f o 咖1 1 1 es y s t e ms h i e l d s a 1 1t h ed i 脑e n c e si nt h el o c a ld a t a b a s ea j l dp r o v i d e st h e q u e 巧s e i c e s t ot h eu s e r sb ym e 酉o b a ld a t a b a s e t h ef u r t h e ri m p m v e m e n to fq u e r yo p t i m i z e rw i l lb et h ef o c a lp o i n to ft h e r e s e a r c hi n 向m r e k e y w o r d s ： m u l t i - d a t a b a s es y s t e m s ，h e t e r o g e n e o u s ，q u e 叫o p t i m i z a t i o n ， r o l eb a s e da c c e s sc o n t r o l 论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指 导下，独立进行研究工作所取得的成果。除文中已经注明引 用的内容外，本论文不包含任何其他个人或集体已经发表或 撰写过的作品成果。对本文的研究作出重要贡献的个人和集 体，均已在文中以明确方式标明。本人完全意识到本声明的 法律结果由本人承担。 学位论文作者签名：匙i j 翟 日期：纠年石月冲日 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规 定，即：学校有权保留学位论文并向国家主管部门或其指定 机构送交论文的电子版和纸质版，有权将学位论文用于非赢 利目的的少量复制并允许论文进入学校图书馆、院系资料室 被查阅，有权将学位论文的内容编入有关数据库进行检索， 可以采用复印、缩印或其他方法保存学位论文。 学位论文作者签名：趣目翟锄签名：仇 日期：刃僻石月叫日日期：矽口星年岁月护日 中山人学倾卜学位论文多数据库系统下统一查询l 台的研究。j 心用 1 1 多数据库发展需求 第一章引言 随着信息技术和网络通信技术的飞速发展，数据库的应用得到了深度上和广 度上两方面的持续发展。特别是世界范围内i n t 锄e t 环境的形成，用户们对于全球 化网络的依赖越来越多。i n t e m e t 成为现代生活中不可缺少的一环。而在n e m e t 的使用中，用户的信息的获取又是网络运用中最为重要和常见的需求。 在现今的使用中，用户们可能去专业数据库搜寻自己所需要的信息，比如万 方，维普的学术性信息网，或者去门户网站去浏览各种各样的信息，当然，利用 搜索引擎寻找所需要的信息也是常用的手段，现在还有百度知道，w i k i 等可以查 + 到人类知识的各个方面。 这种情况下，人们对于数据库的访问越来越需要各个数据库知识的融合和整 合，即更多的时候可能要涉及到不同部门之间异构数据库的数据共享。从我国目 前的发展情况来看，数据库应用与数据仓库应用己经有了相当的广度和深度，例 如，政府、银行、电信、医院、学校、保险等许多机构都各自采用了大型数据库 系统来管理其业务数据，但是这些专业数据库往往复用性很差，即使是在同一个 部门的内部，可能由于业务和职能需求的不同，也建立了多个不一样的数据库。 并且，这些数据库由于设计部门的不同，会出现一个企业内部的各个局部数据库 信息不能共享的情况。形成了所谓的信息孤岛现象。 随着涉及到多个数据库信息共同访问和使用的要求越来越多，多数据库联 合使用必将成为新的研究重点。 1 2 多数据库系统与发展现状 1 2 1 多数据系统 多数据库系统( m u l t i d a t a b a s es y s t e i n ，m d b s ) 是多个己存的、自治的、异 构的数据库系统的联合：多数据库系统的管理软件称为多数据库管理系统 中山人学坝i ：学位论文多数据库系统下统一查洵j p 台的研究j 应用 ( m u l t i d a t a b a s em a n a g e m e n ts y s t e m ，m d b m s ) o2 | 。参与构成多数据库系统的各 数据库系统称为局部或成员数据库系统( l o c a ld a t a b a s es y s t e m ，l d b s ) ，各局部 数据库有自己的局部数据库管理系统( l d b m s ) 【2 1 。局部数据库会分布在高速局域 网的不同的地方，甚至会可能会出现在广域网的不同地方。多数据库系统的最主 要功能，就是要屏蔽掉局部数据库的不同的访问方式，不同的数据格式，使得多 个数据库中的数据可以统一的被用户使用。同时，多数据库系统将不能涉及各个 局部数据库的自治性，即局部数据库的管理员和使用者可以完全不受多数据 库联合结构的影响，可以自主的使用自己的信息。因而，分布式、异构性和自治 性成为多数据库系统的典型特征【3 】。 目前研究的比较多的主要有两类多数据库的联合运用，包括联邦数据库系统 和多数据库系统。 联邦数据库是指没有全局模式的松耦合性数据库联合，这里没有所谓的全局 用户的说法，而是用户可以通过自己局部数据库的所在站点，对别的联邦数据库 中的数据库进行访问。此接入站点将提供与其有连接关系的别的数据库的模式信 息。用户利用此信息对与其相连的数据库进行访问。如果联邦数据库中有其他的 数据库，但是不与此接入节点相连，那么，用户将无权访问。联邦数据库也具有 一定的分布性、异构性和自治性的特点【4 1 。 多数据库系统则是一种耦合度较强的数据库的联合，多数据库需要提供一种 多数据库查询语言【5 】，全局用户使用多数据库语言对多数据库提出查询请求，多 数据库向用户返回全局结果。这里，多数据库系统将要负责构成全局模式，将系 统中的所有局部数据库的模式信息进行集成，屏蔽掉局部数据库的各种异构。这 里，用户将分为全局用户和局部用户两种，局部用户只能访问自己数据库的信息， 全局用户通过多数据库系统，访问所有可用资源。但是，全局用户不可以登录局 部数据库系统，即不可以从一个局部节点访问全局信息，而必须通过多数据库系 统进行访问。 1 2 2 多数据库系统的研究现状 自从八十年代中期多数据库系统的概念首次提出后，立即引起了数据库方面 研究人员及数据库厂商的密切关注，到1 9 8 7 年左右，各主要数据库厂商也分别推 2 中山人学坝i j 学位论文多数据库系统下统一金向j f ，俞的研究j 应用 出了支持多数据库系统的商业产品，包括s y b a s e 、e m p r e s sv 2 ，i n 铲e s s t a r ，o r a c l e 等。但是，分析这些系统会发现，这些支持多数据库的产品，主要是针对自己厂 商的异地数据库进行支持，并没有形成真正的所谓全局模式，同时，也对不是自 己厂商的异构数据库支持的远远不够。 同时，各个大学也积极研究出多个多数据库的系统原型有： 国内外各个大学研究的多数据库原型有： ( 1 ) p e g a s u s 【5 0 】 p e g a s u s 是惠普实验室数据库技术部开发的多数据库系统，它能提供对本地 和外部自治数据库的访i 司【6 7 1 。通过p e g a s u s 能访问外部数据库。p e g a s u s 的系统结 构包括三层：智能信息访问层，协作信息管理层和局部数据访问层。 p e g a s u s 使用h o s q l 的语言作为数据定义和数据操作语言。 ( 2 ) v i e w s y s t e n l 【5 0 】 v i e w s y s t e m 是一个面向对象的环境，v i e w s y s t e m 提供一种带有很多视图工 具的面向对象的查询语言，它能从来自数据库的类中定义虚类。v i e w s y s t e m 的实 现环境是s m a l l t a l k 一个面向对象的环境【8 】，v i e w s y s t e m 包括以下基本模块事务管 理器，消息处理器，通信管理器，对象管理器，查询处理器和编译器以及模式集 成工作平台。 v i e ws y s t e l n 的查询语言叫做v m l ，是基于编程的和面向集合的。查询被指 向相关的类，返回满足条件谓词的实例集合，查询可以嵌套。 ( 3 ) m i n d 【5 0 】 m i n d 是土耳其中东技术大学研究开发的基于d e co b j e c tb r o k e r 的多数据库 管理系统，使用c o r b a 来处理系统级的异构性和分布性【9 ，l0 1 。它实现了一个四层 的模式体系结构：局部模式、输出模式、派生模式和外模式。其中输出模式是由 局部模式翻译得到的。输出模式解决了各局部模式结构( 语法) 上的冲突，形成统 一的输出模式。派生模式是对输出模式的进一步集成。外模式面向用户和应用。 m n d 的四层模型处理方式是它的特点。 ( 4 ) c i s 【5 0 】 c i s ( c o m a n d o si n t e g r a t i o ns y s t 锄) 是欧洲信息技术研究战略计划e s 研t 的项 目c o m a n d o s 的一部分。它被用于集成关系d b m s ，图形数据库和公共数据库 中山人学硕一l ：学位论文 多数据库系统下统一咖、r 俞的研究1 j 心用 等应用系统。c i s 采用一种客户服务器的结构，一个c i s 的应用被称为一个客户， 一个服务器是一个已存应用的抽象。服务器的任务是在己存应用上提供给客户一 个统一的面向对象的接口【1 1 1 。 c i s 的一个主要特点是引入了操作映射的概斜12 1 ，通过定义操作之间的对应 关系来替代定义数据元素之间的对应关系。在使用抽象数据模型的每个局部数据 库系统上面定义一个面向对象的抽象视图，它对应于成员模式。抽象视图被定义 为一个抽象数据集合上的操作集合。根据下面系统的原始操作，操作映射被定义 这些抽象操作的实现。抽象操作是一个预定义的一般操作的集合，它分为类的操 作和对象的操作1 2 1 。 ( 5 ) 国内的相关研究5 0 】： 国内东北大学的s c o p e c i m 【1 3 1 4 1 是为满足c i m s 环境下信息集成需求而设 计、实现的基于c o r b a 的面向对象的多数据库信息集成系统，它采用了对象数 据库标准o d m g 9 3 中规定的对象数据模型和对象查询语言o q l 作为公共数据模 型和全局查询语言。s c o p e c i m s 系统中定义了模式集成操作以及基于模式集成 语义的基本查询处理规则和路径表达式的查询处理规则和查询处理方法【1 5 ，16 1 ，设 计了一种弹性事务管理系统，但未考虑并发控制机制，对查询计划的生成及查询 优化研究也不岁1 7 1 。 华中科技大学的p a n o r 锄a 系统基于c o r b a 平台，采用扩展的p a n o s q l 作为 查询语言，将传统关系数据库与面向对象概念相结合，在非关系数据处理上做出 了一定的贡献。 1 3 本文研究的内容 1 3 1 本文研究的意义 根据上文分析的内容可知，目前，多数据库研究领域已有了不错的进展。但 是，实际中我们会遇到一些不一样的问题。比如，对于政府、银行、电信等大型 部门，相互之间可能需要共享数据，做到信息的公开化和透明化。但是，每个部 门的数据只能由各个部门来提供，别的部门并不需要也不能够对其他的数据进行 修改或增添处理。并且，每个部门敏感的涉密信息，并不适合公开处理。这就对 4 中山人学硕1 ：学位论文 多数据库系统下统一查询，f 台的研究。j 席用 多数据库系统的使用提出了新的要求。同时，多数据库系统本身就是一种建立在 数据库之上的数据处理平台，当要求处理的数据量大，参加系统运算的局部站点 多，全局事务的处理将会变得难以控制。多层架构的体系又会在原有的数据库基 础上，加重处理器的负担，影响数据处理的速度。 基于新的应用要求，本文将在多数据库系统的原则下，建立起一个统一的查 询平台的原型。查询平台的用户对局部数据有着查询的访问权限，但除此之外， 统一平台并不处理其他的全局事务，将数据库写数据的任务和权限留给局部数据 库自身。在不影响局部自治数据库单独运用的前提下，为其他需要浏览数据的用 户提供统一的查询接口，这样，避免了信息孤岛的出现，同时，也避免了需要建 立体系庞大而代价很高的完整的多数据库系统。 1 4 论文章节安排 本论文章节安排如下： 第一章概述多数据库系统的产生原因和意义，关键技术，国内外研究情况及 本论文的研究重点。 第二章给出了本文所涉及到的查询预处理，查询和安全访问的重点相关理论 介绍。 第三章详细研究了模式匹配，全局查询分解，查询优化的关键技术，给出了 本文所要实现原型系统的查询相关各个部分重要算法，其中重点包括查询分解算 法和在静态优化的基础上给出了一种具有较好变通性的查询后调度算法。 第四章运用基于角色的权限授予模型，详细给出了本系统安全访问的规则和 策略，并给出了授权和鉴权的关键算法。 第五章给出了原型系统的设计架构，并对每一个部分进行比较详细的介绍， 在此基础上，给出了原型系统试验的部分结果。 第六章对论文进行了总结，并对未来研究方向进行了展望。 中山大学硕一i j 学位论文 多数据库系统下统一企询、f ，台的f i j f 究jj _ 用 第二章查询系统基础 本文将研究多数据库系统中统一查询平台的关键技术和在此基础上实现查 询平台在实际中的运用。查询平台是面向多数据库的，多数据库系统的所要研 究的大部分问题统一查询平台都会遇到。这篇论文中，我们将重点解决以下问 题： 首先，最重要的是用户得到的是一个统一的虚拟数据库信息，用户给统一 查询平台递交一份查询请求，但实际上，这个查询并不能在查询平台内部查询， 因为查询平台只是提供了数据查询的接口，而并非存放真实数据的数据库。所 以，怎样将一条面向查询平台的全局查询语句自动转化成发送到各局部数据库 真实执行的查询语句，将是统一查询平台首要解决的问题。 与查询语句的自动转化和拆分相关的，包括查询前处理与查询后处理。查 询前处理主要是解决局部数据库部分模式到整体模式的转变，其中重点需要考 虑的是各个部分异构数据源模式的匹配。查询后处理则需要考虑，一条全局查 询语句拆分后，发送到局部数据库查询得到的结果只是中间结果，怎样将这些 结果联合起来，得到真j 下的查询结果，怎样尽可能快速的调度各个中间结果的 连接，将是查询后处理需要考虑的重点。 同时，我们也必须考虑到数据安全。多数据库系统用户众多，很有可能就 会造成敏感数据的泄漏。所以，必须采取安全而且有效的数据库访问管理措施。 数据库访问安全，将是本论文的另一个重点。 在这一章，我们将要了解下本篇文章所使用到的数据查询和数据访问技术 中所要用到的理论知识。 2 1 查询理论基础 2 1 1 查询前的异构模式匹配 中l 【j 人学坝i j 学位论义多数据库系统下统一查洵，r 行的研究0 应用 异构性 在首先得到局部模式，再在局部模式构建下合成整体模式的系统构建方式 中，异构现象将不可避免。这里所说的异构性，主要包括有平台和系统的异构 性，句法和结构的异构性和语义的异构性。第一种异构方式针对的是计算机硬 件和操作系统的不同架构，这种异构，针对硬件和基础设施而言的，比较容易 解决【1 引，所以本文并不作为讨论的重点。 第二种和第三种异构是针对计算机需要处理的数据而言的，在形成多数据 库系统时，首先需要处理的就是这两种异构模式，设想一个简单的情况，在两 个局部数据库系统内，都有用户地址这个字段属性，但是，在其中一个系统内， 它被命名为a d d r e s s ，而在另外一个系统内，它被命名为a d d r 那么如果对这两 个属性作联合查询，那么，计算机将会认为是不同的属性。那么，如果我们希 望它们被作为同一属性被查询出来，就需要做相应的模式匹配。本文将对句法 结构和语法的异构作匹配处理。 句法和结构的异构性主要包括数据模型的异构，属性类型，格式或精确度 等的差异，命名和本体的差异5 1 1 。语义的异构性是指本地数据意义上的差异和 相似性【1 8 1 9 ，2 0 ，2 1 ，2 2 ，2 3 1 。例如两个本地数据源的模式包含相同的意义，仅名称不同， 那么在匹配的时候，这两个元素实际值的是相同的概念。另外，两个模式元素 可能名称相同，但他们包含的内容是不相同的，那么在匹配的时候，应该被看 作不同的两个对象。 模式匹配的概念： 模式匹配时意图获得两个模式中待匹配的个体对象之间的语义匹配的个体 对象之间的语义匹配和映射，其结果是表示源模式的个体对象与目标模式的个 体对象之间存在特定的语义关联，即得到两个模式之间的语义映射【5 1 1 。 模式匹配的方法 根据模式匹配时具体的侧重方向的区别，模式匹配的方法也有不一样。 匹配基数( m a t c h i n gc a r d i n a l 时) 【5 1 1 匹配基数包含4 种类型：一对一，一对多，多对一以及多对多。这种方法 侧重于分析待匹配的元素之间的关联数。即一个待匹配的源模式元素是否可以 对应多个模式元素，如表2 1 所示。这种方法可以确定各个匹配模式之间的关 7 中山人学硕i j 学位论文多数据库系统下统一企咖r 台的研歹e jj 用 联基数：根据类型，有1 ：1 ，1 ：n ，n ：l ，n ：m 这四种关联基数。匹配基数方式如 表2 1 所列。 表2 1 匹配基数方式 m a t c h i n g st m a t c h i n ge x p r e s s i o n c a r d i n a l i t i e s 1 ：1i t e mi t e mi t e m = i t e m d e l i v e r l r o p o s h i p t 0d e l i v e r l b = p o s h i p t o 1 ：nn 锄ef j r s 小j 锄e n 锄e = ( f i r s t n 锄时l a s t n l a s t n 锄e a l n e ) n ：1p c ec o s t c o s t = p r i c e 宰( 1 + t h x lo o ) t a x 由于需要使用复杂的匹配准则才能得到n ：1 和n ：m 的匹配，因此大多数的 匹配方法都是基于1 ：1 和1 ：n 的匹配方法【2 4 1 。 句法匹配( s y n t a c t i cm a t c h i n g ) 句法匹配用来处理各个待匹配模式元素之间的句法上的匹配度。比如， 属性类型是否一样，元素精确度是否一样，元素格式是否一样。它有着与基数 匹配相重合的地方，就是句法匹配判断元素之间结构是否匹配时，可以根据基 数匹配的方式，当单个对单个元素不匹配时，是否存在一对多或者多对已的元 素匹配。 语义匹配( s e m a n t i cm a t c h i n g ) 主要处理元素的概念之间的关系，匹配结果是得到元素之间的语义关系， 待匹配元素是否在语义层面上匹配，是否存在模式包含相同的意义，仅名称不 同，即同义异名现象。或者，是否存在两个模式元素可能名称相同，但他们包 含的内容是不相同的，即同名异义现象。 基于模式级或实例级的匹配方法 实例级或模式级的匹配方法是根据该方法是否能够考虑实例数据( 即数据 内容) 来进行的分类的【5 1 1 。 模式级匹配( s c h e i n a 1 e v e lm a t c l l i n g ) ，模式级匹配方法仅仅使用模式信息， 而不考虑实例数据，即只考虑模式元素的匹配。并不考虑到每一个元素不同的 中山人学坝f j 学位论文多数据库系统下统一_ 佥询- 、r 台的研究j 心用 实例之间的联系。 实例级匹配( m s t a n c e l e v e lm a t c h i n g ) ，则要更加细致的考虑待匹配的元素。 要深入的元素的每一个实例，来判断是否两个元素匹配。 对于目前的匹配方法，大多数都集中在模式级的匹配，少数的匹配方法可以 考虑到基于实例的匹配【2 5 ，2 6 1 。 2 1 2 查询时的保持等价性 由于用户递交的查询将要在系统内进行分解和转换，然后发送成各个局部的 查询发送到各个局部数据库，这里，会遇到查询分解的等价性问题。将等价性分 成以下两个部分，一，语义等价；二，代数等价。 语义的概念与语义等价性 大多数信息系统提供了一套概念结构( c o n s t m c t i o n ) 来对现实世界的数据进行 建模。每一个概念结构被认为是一个类型( t y p e ) ，它可以是一种复杂类型( 通常由 用户定义) 或一种基本类型( 通常由系统提供) 。在类型和它所表示的数据间的联 系被称为语义【3 2 ，3 3 1 。 定义1 在任何数据库的状态下，两个查询的执行结果相同时，那么这两个查 询是语义等价的。 定义2 当且仅当两个查询的限制条件可以相互转化( 利用标准的逻辑公式) 时，这两个查询是逻辑等价的。即代数关系意义上的等价。 显然，根据这两个定义可以知道，逻辑等价的查询一定是语义等价的，但是 语义等价的查询不一定是逻辑等价的。 在整体查询分解到各个局部数据库的查询和各个局部数据库的查询进行进 一步分解的过程中，我们都将会遇到保持代数等价性的问题，下面是关系代数中 有关代数等价性的基础知识： 基于关系代数的代数等价性0 3 4 l 1 查询语句的内部表示：查询树 为了将查询的外部表达式转换成对关系的操作序列，需要有一种查询的内 部表示，即查询表达式的内部结构，我们称它为查询树，也叫做语法树。 9 中山人学硕。i ：学位论文 多数据库系统下统一查询、f ，台的研究jj 衄用 定义：查询树是一棵树t = ( v ，e ) ，其中，v 是节点集，每个非叶节 点是关系操作符，叶节点是关系名( 即查询涉及的关系) ：e 是边集，二节 点有边( v l ，v 2 ) ，当且仅当v 2 是v i 的操作分量。 查询树示例：有查询q l ：“查询北部地区( a r e a = n o n h ) 所属部门 发出订单的供应商号。”这个查询q i 的s q l 表达式： s e l e c ts # f r o md 印t ，s p w h e r es p d # = d e p t d #a n da r e a = n o n h 其相应的代数表达式为： 砖撑盯彳r 翻：m 硼( 印d 撑型) 倒d 撑) 其相应的查询树如图2 1 所示。 态撑 1 ( ，a r e m 。n o n h i s p d i # ! 壁p e p t d 图2 1 查询树 2 关系代数的等价转换 关系代数等价变换规则：设e 1 和e 2 是两个等价关系代数表达式，常用的 变换规则如下【3 4 】： 1 连接、笛卡儿积的交换律 2 连接、笛卡儿积结合律 e l ，e 2 三e 2 0 0 ，e i 1 0 劬 d 中山人学顾i j 学位论文 多数据库系统下统一查询- 、i 台的研究1 j 应用 设巨、垦、毛为关系代数表达式，e 五为连接运算条件。则 ( e i e 2 ) 邑暑e i ( e 2 毛) ( e 她：) o o 毛三巨( 易b ) ( 巨 e 2 ) ，2 e 三巨 ( e 2 尼易) 3 投影的串接定律 万4 ，一：一。( 万马，岛，( e ) ) 三万 ，一：，一( e ) 设e 为关系代数表达式，彳f ( i = 1 ，2 ，n ) ，毋( j = 1 ，2 ，n ) 是属性名， 且印，么2 ，么甩) 构成徊，历，玩) 的子集 4 选择的串接律 仃 ( 盯，2 ( e ) ) 兰盯五，、最( e ) 设e 为关系代数表达式，f l 、f 2 为选择条件。选择的串接率说明选择条件可 以合并，这样一次就可以检查全部条件。 5 选择和投影的交换律 盯f ( 万 ，鸣，以( e ) ) 三万 ，以，以( 盯，( e ) ) 这里，选择条件只涉及属幽，彳2 ，彳疗。若f 中有不属于彳，彳2 ， 4 。的属性b i ，毋，b 州，则有更一般的规则： 万4 一：。以( 盯，( e ) ) 三万 ， ， ( 盯，( 刀 也， ，马毋，氐( e ) ) ) 6 选择与笛卡儿积的交换律 如果，中涉及的属性都是局中的属性，则： 口，( 巨易) 兰盯，( e 1 ) 易 如果，= e e ，并且一只涉及e ，的属性，最只涉及历中的属性，则由上面 的等价变换规则1 ，4 ，6 可以推出： 盯，( 巨易) 三盯五( 巨) 盯已( b ) 如果局只涉及e ，的属性，r 涉及e ，和局的属性，则仍有 盯f ( 巨易) 三仃最( 仃五( e ) 易) 中山人学顾i ：学位论文多数据库系统下统一查询甲台的研究0 应用 7 投影与笛卡儿积的交换 设e ，和局是两个关系表达式，彳j ，彳2 ，彳。是e ，的属性，b l ，毋， 既是毋的属性。则： 万4 ，：以，且。岛( 巨易) 三刀 ，月： ( e i ) 万马，岛，( 最) 8 投影与并的交换律 设e 和局有相同的属性名，则 石 ，一：， ( e lu 马) 兰万 爿：，以( 巨) u 万 ，以， ( 易) 3 查询条件的代数表达 在刚才的介绍中，我们对查询条件提得很少。事实上，查询条件的分解，将 是整个系统查询分解实现的基础，下面，将介绍一些查询条件表示的方式【5 0 】： 合取条件式：形如互 最八b 只的表达式，其中，最，昱，b ，只是无法进一 步拆分的简单查询条件。连接符为“ ”。 析取条件式：形如只v vbv 只的表达式，其中置，最，b ，e 是无法进一步 拆分的简单查询条件。连接符为“v 。 析取条件范式：一个只由合取表达式组成的析取表达形式，称为析取条件范 式。该表达式形如：彳lv 彳2v 彳3v 么。其中4 ，彳2 ，彳3 ，彳。都是合取表达式。 合取条件范式：一个只由析取表达式组成的合取表达形式，称为合取条件范 式。该表达式形如：么人彳2 彳3 人彳。其中彳。，么2 ，4 ，彳。都是析取表达式 2 1 3 查询后优化的代价模型 多数据库查询优化的研究现状 多数据库的优化是多数据库关键技术中的研究重点和难点。 目前对多数据库系统的查询优化主要从以下四个方面进行【3 3 ，3 5 】： l 查询语句优化： ( 1 ) 代数优化：使用代数变换来进行查询优化是集中式数据库系统经常用到 技术，通过运用一些的转换规则，将查询的代数表达转换成一系列等价的表达式， 选择其中一个能导致最小查询代价的表达式。这种方式，在多数据库中也会有一 1 2 中山人学硕1 j 学位论文多数据库系统下统一查询、r 台的研究j 应用 定的应用价值。 ( 2 ) 基于查询代价模型的优化策略：对于可能被使用到同一查询的不同查询 方式，通过估计查询时的局部查询速度，通信速度和结果连接速度，来选择各个 查询副本中代价最小的一种进行查询。 ( 3 ) 语义查询优化( s e m a n t i cq u e r yo p t i m i z a t i o n ) ：通过运用多数据库系统中全 局数据库和局部数据库的语义信息，对存在语义副本( 多个数据库中都可能含有 的信息) 的查询，确定查询代价最小的进行查询 2 查询后的优化 ( 1 ) 查询后外连接( o u t e r j o i n ) 优化：查询后各个中间结果的合成时，外连接( 包 括连接和半连接) 方式是经常被用到的方式。外连接的优化可以确定中间结果连 接顺序，或者系统使用半连接方式进行优化。 但是，这些研究还远远不够。比如，很多种多数据库查询的优化方式，都是 需要基于查询代价的预估的。而对于多数据库而言，模型信息的准确获取是一件 很困难的事情。首先，由于局部自治性，局部数据库可能并不能提供所需要的信 息，然后，即使在多数据库建立初期，已经有了所需要的统计信息，这些信息， 也会随着各个局部数据库的使用而产生变化，使得代价估计模型不够准确。 同时，对于通讯代价的估计，我们知道，在网络运行当中，可能会出现各种 突发情况，使得通信延时或者中断，那么，这些情况下，使用通信代价模型的统 计信息是不能令人满意的，怎么样应对网络中的突发情况，使得查询后调度连接 的方式不会因此而耽误太多时间，也是查询后优化调度的一项重点问题，本文将 在此后的章节继续进行讨论。 多数据库查询的代价估计 为了使用基于查询代价模型的优化方式，我们必须首先确定一些查询代价的 估计方式5 0 1 ，这些估计方式将在查询优化章节被用来当作代价模型估量的基 础。 下列数学式用来表达式表示物理关系的静态特性【5 0 】： 关系的元组数( 基数) ：c 砌( r ) 属性的宽度：s i z e ( a ) 关系的宽度：娩p ( 尺) = 姚( 么f ) 中山人学顾i j 学位论文多数据库系统下统一查询i f ，台的研究j 心用 属性在关系中不同值的个数：v a l ( a ( r ) ) 在数据库的语句操作中，一定的选择语句能够选择出具有一定物理尺寸的 数据，这里需要分析选择操作、投影操作、联接操作对于物理关系尺寸变化的 影响，对于关系的其他操作，可以类似导出【3 6 】。 ( 1 ) 选择操作 3 6 】 基数若我们假设不同值是均匀分布，那么一次简单的选择操作( 选择单 个属性) 有： c a r d ( s ) = c a r d ( r ) ，a l ( a ( r ) ) 关系的宽度，选择操作不影响关系的宽度，所以有： s i z e ( s ) = s i z e ( r ) ( 2 ) 投影操作【3 6 】 基数，本文不考虑到投影操作可能消除某些元组的影响，即认为投影前 后的基数不发生改变。 关系的宽度，关系的宽度投影以后的s 关系的宽度 肥p ( s ) = 娩p ( r ，彳f ) a i e a l l r t s l 不同值的个数，投影结果s 关系的不同值个数与r 关系相同，有： v a l ( a i s ) = v a l ( a i r ) ( 3 ) 联接操作5 0 】 基数，精确计算连接操作t 的元组数是一个相当复杂的问题。由于 c 口以( 丁) 劬坩( r ) c 口坩( s ) ，所以我们可给出c a r d ( t ) 的上界，即使这样，讨论 情况仍然比较复杂，这里。都将假设不同值均匀分布在两个待连接的关系r ，s 中均匀分布： 假设r 中所有a 值也都出现于s 中的b 值，或反之亦然，即有： v - a 1 ( a r 】) = v a l ( b s ) 坩( 丁) = 耐( 尺) c 口以( s ) 玩，( 4 尺 ) 仍是上述假设，但若两个属性之一如a ，是r 的一个键属性，即这里a 将出现在a 的每一个不同值上，则有： c a r d ( t ) = c a r d ( s ) 1 4 中山人学顾：i ：学位论义 多数据库系统下统一台词、r 台的研究o j 应用 若上述假设不成立，则上面二式可以作为上界。 关系的宽度，有： s i z e ( t ) = s i z e ( r ) + s i z e ( s ) 自然连接时，因为消除冗余元组，所以宽度会略小一些，这里不做讨论。 不同值的个数：我们可以给出一些联接操作结果关系中不同值个数的上 界，也有几种情况： 若a 是联接属性，有砌，( 彳 刀) 施疗( 肠，( 彳 尺】) ，砌，( 研s 】) ) 若a 不是连接属性，有砌，( 彳 丁 ) 砌，( 彳 尺 ) ，玩，( 研s ) 传输代价的计算 在多数据库系统中传输一般有两种影响：费用( c o s t ) 和延迟( d e l a y ) 。如果按传 输费用来考虑，那么最小的代价应该是网络数据量交互最小，即此代价衡量的 主要的是整个系统在不同的网络节点之间的数据传输量大小。如果按延迟考虑， 那么最小的代价应该是从此次应用激活到完成所经历的时间最小，即此代价主 要衡量的是一次完整的操作的时间大小。 这里，本文的研究以查询为主要功能，在考虑传输代价时，以响应时间作 为最主要的衡量标准，所以选用第二种延时的计算方式t d ( x ) = d o + x 木d l 作为 考虑传输代价时主要的参考标准。 一次传输延迟( t d ) 可以用下列函数表示，与数据量的大小呈线性关系： t d ( x ) = d o + x 鼻d l 其中d o 是两场地建立一次连接所需的固定时间；d l 是网络传输数据统一 的单位传输速率。 2 2 访问控制理论基础 2 2 1 自主访问控制 在自主访问控制( d a c ) 模型中【3 4 】，用户的访问权限是由用户主体的身份鉴别 和其对于系统中存在的每一个客体的访问权限总和所确定的。自主访问控制的模 型由主体，客体和基于客体的访问权限所构成。 中山人学硕1 ：学位论文多数据库系统下统一查询l ，- 台的研究与心用 系统在授权时，对于每一个单个用户，必须表明此用户对于系统中存在的每 一个客体的存取权限。例如，允许其读取，或者是允许其写入，或者是这个用户 有多个权限，例如，可以读并且可以写并且可以执行。当某用户需要访问此系统 时，系统对照此用户授权结果，给予此用户相应的访问权利。如果用户权限检测 失败，则拒绝访问。 表2 2 是一个简单的自主访问的控制矩阵示意。 表2 2 一个简单的访问控制矩阵 客体1客体2客体3 主体1读读读 主体2读，执行读，执行读，写 主体3读，写读，执行 自主访问的特点是，用户权限可以自由转移，具有传递性和自主性。这是说 拥有访问权利的用户可以自主进行授权工作，将自身所拥有权利再传递授权给其 他用户。传递授权需要遵循权限递减原则。即授权给别的用户时，不可以将自身 没有的权限授权给别的用户。 自主型访问控制的缺点是，安全性能较差。因为授权具有自主性和传递性。 系统不可能控制每个用户的行为。如果某个恶意用户得到了系统的用户权限，使 用传递方式给非法用户授权，将会对系统安全造成比较大的冲击。并且，将授权 方式完全交给个人，系统将很难进行统一的控制。 2 2 2 强制存取控制方法 m a c 是指系统为保证更高程度的安全性【3 4 】，按照t d i t c s e c 标淮中安全策 略的要求，所采取的强制存取检查手段，它不是用户能直接感知或进行控制的。 在m a c 中，自主访