（生物医学工程专业论文）分布式医学图像数据库系统的研究和实现.pdf

一查妻查堂篓主笙塞 a b s t r a c 下 t h e s i st i t l e ：r e s e a r c ha n dr e a l i z a t i o no ft h ed i s t r i b u t e dm e d i c a l i m a g ed a t a b a s e s y s t e m g r a d u a t e s t u d e n t ：w a n g b e s u p e r v i s o r ：p r o f e s s o rl u ol i m i n p r o f e s s o rb a o x u d o n g s c h o o l ：s o u t 舰a s tu n i v e r s i t y w i t ht h e r a p i da d v a n c e m e n to fc o m p u t e rt e c h n o l o g y , t h eb u r d e no fs e r v e rh a sb e e nt h e b o n l e n e e ko fn e t w o r ki nc e n t r a l i z e dd a t a b a s es y s t e m d i s t r i b u t e dd a t a b a s es y s t e mc a nn o to n y s o l v et h i sp r o b l e mb u ta l s oi m p r o v et h er e l i a b i l i t yo f s y s t e m ，d i s t r i b u t e dd a t a b a s es y s t e mi sa c o l l e c t i o no f m u l t i p l el o g i c a l l yi n t e r r e l a t e dd a t a b a s e sd i s t r i b u t e do v e ra c o m p u t e rn e t w o r k ad i s t r i b u t e dd a t a b a s es y s t e mw h i c hi sb a s e do ne x i s t e dc e n t r a l i z e dm e d i c a li m a g ed a t a b a s e s y s t e mi sd e s i g n e d a st o p d o w nd e s i g np r o c e s s ，t h es y s t e ms t r u c t u r ei sd e v i s e dn e w l gd a t ai s f r a g m e n t e da n dd i s t r i b u t e da c c o r d i n gt oa p p l i c a t i o na n a l y s i s 。m o s to fq u e r i e s 搬r e s t r i c t e dt o l o c a ls e r v e r , s ot h eb u r d e no fn e t w o r ki se a s e d a l t h o u g ho n es e r v e ri nt h es y s t e mi si nt r o u b l e ， 0 t h e r sw i l ls t i l lw o r kw e l l 。 t h em e t h o do fd i s t r i b u t e d q u e r yo p t i m i z a t i o n i s a n a l y z e dd e e p l yw h i c hu s es e m i - j o i n a l g o r i t h ma n dq u e r yt r e ed i s a s s e m b l i n g ac a s ei s u s e dt o p r o v et h a tt h ed a t a i st r a n s m i t t e d t h r o u g hn e t w o r kw i l lb eh i g h l yr e d u c e d 姆t h i sw a y , d a t ad i c t i o n a r ya n dd i s t r i b u t e dv i e wa r ed e s i g n e d ，w h i c hc a nh e l pt om a k et h ed i s t r i b u t i o n t r a n s p a r e n tt ot h eu s e r s 。t h em o d u l eo fd i s t r i b u t e dq u e r ya n du p d a t ei sd e s i g n e dt o 撑m i z et h e a c c e s st od a t a b a s e 2 p c p r o t o c o li su s e d t oa s s u r ed i s t r i b u t e dt r a n s a c t i o nr o l l b a c k sw h e nc i t e ri so c c u r r e d 。w i t h d a t ar e p l i c a t i o nt e c h n o l o g y , a w c h a n g ei no n e s e r v e rw i l lr e s u l ti nt h ec h a n g ei no t h e rs e r v e r s a m o d u l eo f m a n a g i n gu s e r s g r a n t si sa p p r o a c ht or e a l i z et h es a f e t yo f d a t a b a s e w i t ht h i sm e t h o d ， u s e r s g r o u t sc a nb em a n a g e d o v e rw h o l ed i s t r i b u t e d s y s t e m k e y w o r d s ：d i s t r i b u t e dd a t a b a s es y s t e m ，d a t af r a g m e n t a t i o n ，0 p t i m i z a t i o no fd i s t r i b u t e d q u e r i e s ，d i s t r i b u t e dc o n c u r r e n c yc o n t r o l ，d i s t r i b u t e dt r a n s a c t i o n 东南大学学俊论文独创憔声瞪 本人声明所呈交的学位沧文是我个人在导师指导下进行的研究工作及取得 薛蓊究或巢。尽我掰甄，除了文孛祷裂攘以耩注露皴落懿魏方舞，论文中不包含 其它人已经发表或撰写过的研究成果，也不包含为获得东南大学或其它教育机构 酌学位或证书而便瘸过韵孝芎料。与我一同工作的同态对奉磷究所骰豹任何贾献均 己在论文中作了明确的说明著表示了谢意。 研究生签名：一日期： 东南大学学憧论文使用授权声明 东南大学、中圆科学技术信息研究所、国家图书馆有权保留本人所送交学位 论文翁复露 孛窝鬯予文趟，可菠栗怒影鼙、缭露或蒸它复刳手段爨存论文。本人 电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论 文被查阕稻借阖，可黻公繇( 包括稍登 论文静全都或部分雨容。论文翡公布( 包 括= f = 【j 登) 授权东南大学研究生院办理。 研究生签名：导师签名： 日期： 第一章绪论 1 1引言 第一章绪论 数据库管理系统已经广泛而深入地应用于各个领域的信息处理技术中，它与迅速发展的 网络技术相结合，可实现对远程数据库的操作，发展成为分布式数据库技术。这一技术开始 于七十年代末期，为适应应用的需求及各应用部门数据信息的急剧增长，要求改变原有集中 存放的处理方式，是数据的存放和流通趋于合理，同时，也可对已有数据库利用提供可能。 应用和技术的双重驱动促进了分布式数据库的发展，但最初追求的完美数据库系统还未出 现这一技术仍处于迅速发展和完善之中。 分布式数据库系统的优势 1 ，可以解决组织结构分散而数据需要相互连接的问题。 2 ，如果一个系统需要增加新的相对自主的单位，分布式数据库系统可以在对当前系统 影响最小的情况下进行扩充。 3 ，数据的分布使操作负担分担在各个节点，避免负担过重导致阻塞。 4 ，分布式数据库故障的影响仅限于局部数据应用，对整个系统的运行影响不大【l 】。 1 。2 分布式数据库的研究背景 一个分布式数据库由一个逻辑数据库组成，该逻辑数据库的数据存储在一个和多个网络 节点的物理数据库中。实现并支持这一单一逻辑数据库视图应用而开发的软件即分布式数据 库管理系统。美国的c c a 公司率先研制同构型分布式数据库系统的原型s d d - l ，s d d l 及随 后研制的d d m ，d l n g r e s ，p o r e l ，s i r i u s - d e l t a ，c - p r o e l ，w d d b s ，等原型系统的 经验，充实了同构型分布式数据库系统的理论和实现技术，明确了存在的主要问题。所谓同 构型系统主要是指各物理数据库具有同类的数据模型。 同构型分布式数据库系统的关键技术主要有：系统结构( 包括网络于d b 间的接口) ， 数据分割，分布透明，分布式查询优化，分布式并发控制，分布式事务管理，分布式的字典 钎理，可靠性，安全性，保密性等吐 东南大学硕士论文 明确的主要问题有：系统设计实现复杂，网络开销大( 通信频度高，通信量大) ，造成 响应速度慢，故障恢复和多副本的数据修改一致性不易解决，可靠性难以保证。这些问题及 导致的市场前景，致使原型系统迟迟未能达到实用而不能推向市场。 八十年代，随着o r a c l e 数据库管理系统在多个平台上的运行和广泛流行，其商业的成 功致使o r a c l e 也涉足分布处理领域，o r a c l e5 0 实现了多个场地o r a c l e 间的互连并可进行单 点远程访问，o r a c l e6 0 发展到多点查询和单点修改，o r a c l e7 0 可做到多点查询和多点修改。 八十年代初，美国c c a 公司又开始研制异构型分布式数据库系统的原型m u l t i b a s e ，随 后又有d d t s ，h d d b m s ，i m d s ，p r o t u s 等原型系统，促进了异构型分布式数据库系统 在理论和实现技术上的发展，并主要弄清了以下问题： 不同数据模式的集成，在异构型分布环境下，若按同构分布式数据库采用的自 项向f 方法，由起全局模型作用的全局同一模式分解成节点物理库的局部模式， 可获得分布的透明性，但将可能失掉局部自治性。 开放式体系结构。为了解决异构型分布式数据库的互连和集成共享，没有开放 式的结构是难以做到的。近来来，s y b a s e 系统的开放式体系结构和c l i e n t s e r v e r 结构在此方向上迈出了可喜的步伐。 事务模型及并发控制策略。现在已发展了各种数据复制技术，可望解决传统事 务模型和两阶段提交对资源的长期占用导致的低效问题。 全局字典比同构环境更能建立和管理【3 1 。 根据广泛的原型系统的设计、实现和理论研究，c j d a t a 于1 9 8 7 年指出了分布式数据 库系统设计的1 2 项理想指标，成为众多系统设计的指南。它们是： 1 各节点上的数据库具有自治性。 2 各子节点不依赖于中心节点。 3 分布式数据库中节点物理库的变动对应用的影响应该尽可能少。 4 具有位置透明性。 5 具有分片透明性。 6 具有复制透明性。 7 可进行分布式查询处理。 8 可进行分布式事务处理。 9 具有硬件的独立性。 1 0 具有o s 的独立性。 2 第一章绪论 i 具有网络独立性。 2 ，局部映射具有透明性。 1 3 分布式数据库技术的现状 目前儿家主要的数据库厂商均推出了其分布式数据库，特别是异构型分布式数据库的 有关产品；在结构上，都在不同程度上走向开放，支持互操作和数据集成：复制器技术的研 究和实用，可有效地减少网络传送，提高节点地自治性和数据可获得性，从而提高分布式环 境下的执行速度。节点数据库管理系统内核新技术的采用，性能明显提高，致使数据库厂商 在商业竞争上愈演愈烈。 互操作技术 要达到分布式数据库的统一视图，实现数据库间的互操作是前提，现在，数据库间的互操作 大都是通过网关实现的。异构环境下，各厂家提供的网关在透明性和可连接性等方面有不同 的品质：如s y b a s e 现在所提供的网关不限于p o i n t - - m - - p o i n t 连接，可同时存取多个库中的 数据，相当于具备分布查询的能力【”。 数据集成 数据集成与网关密切相关，要有分布式数据库的统一视图，就要有全局数据字典，它支 持分布式查询优化。网关实现不同数据库间的通信，而且前厂家提供的网关仅对少数异构数 据库完成透明【6 】。 i n g r e s 和l n g r e s s t a r 是一个用于数据集成的主要产品，它用一个协调数据库来维护一个 中间数据字典，并记录分布式子事务中涉及到的节点和表。可用它来实现分布操作。o r a c l e 数据集成采用了比较新的技术，它没有全局字典概念，它把管理全局字典的功能下摆到节点 数据库管理系统中，增强了节点独立性以及全局字典信息的可获得性。目前，对于异构数据 库的修改与全局字典的同步问题仍处于研究中。 复制器技术 复制器技术已成为分布式数据库的重要技术之一，主要控制和维护冗余，提高节点的事 务处理能力和系统可用性。 数据完整性 分布式数据库的数据完整性是一个相当复杂的问题，目前大多采用2 p c 机制来保证数 东南大学硕士论文 据充整性。大多数厂商可保证同构数据库的完整性、但对于异构环境，由于各厂家2 p c 协 议的不一致，目前发展缓慢，基于这一情况，i b m d b 2 和s y b a s e 公开了部分的2 p c 协议f ”。 1 4 论文研究内容及章节安排 本文在集中式医学图像数据库的基础上研究构建分布式的数据库，利用m s s q l s e r v e r 数据库系统上实现了分布式数据库的一般性质，并讨论了分布式查询优化和分 布式事务处理，给出了分布式数据库安全的实现模块。 论文共分七章，安排如f ； 第一章介绍了分布式数据库系统的背景和发展现状。 第二章给出了医学图像分布式数据库系统的系统结构，分析了数据分割的方法。 第二章分布式查询优化的方法，并对实际系统的查询进行优化实现。 第四章介绍了分布式事务管理的体系结构，讨论了分布式事务的故障恢复和并发控 制的算法，并实践在具体系统上。 第五章给出了分布式系统的各个功能模块的实现方法。 第六章分析了分布式数据库的安全性能，在实际系统上设计实现分布式数据库的安 全控制。 第七章总结了系统设计方面的工作，并对分布式数据库系统的发展方向做了展望。 4 第二章系统体系结构与数据分布 第二章系统体系结构与数据分布 2 。1系统开发方案设计 本实验室已经开发l 出c b i r ( 基于关键字查询) 和k b i r ( 基于内容查询) 的三层“s 结构的集中式医学图像数据库系统【8 】。需要在此基础上重新进行数据库的设计，分割，编写 分布式系统的管理模块。 后台数据库管理系统采用m ss q l s e r v e r 。s q l s e r v e r 2 0 0 0 对于分布式开发提供了 一定的支持。在s q l s e r v e r2 0 0 0 中提供了链接服务器功能来实现数据库之间的通信。通过系 统存储过程s p _ a d d l i n k e d s e r v e r ，s ps e r v e r o p t i o n 等添加管理链接服务器。当在一个节点上设 置了链接服务器，就可以在这个节点上使用s q l 语句进行远程数据库上的数据操作。 系统结构图如下： 用 户 一 接 口 其中，网络数据目录记录关系裂片在每个节点上的存储信息。 基于关键字查询和基于内容查询用到的主要的表如下： p a t i e n tl n f o r ：储存病人姓名，性别等信息和对应的病人编号p a i e n t _ l d 。 东南大学硕士论文 p a t i e n i _ i m a g e ：存储病人编号p a t i e n t _ i d 和该病人的医学图像编号i m a g e i d 之间的关系。 l m a g e _ f e a t u r e ：存贮每幅图像编号i m a g e _ i d 和该图像的数个图像特征，以及特征向量 的大小。基于内容杏询止是通过计算待查询图像的这些图像特征值，计算特征向量的模，来 和该表中数据做比较，找出特征最相近的图像的编号。 l m a g e _ c o n t e n t ：存储图像编号和该图像内容的关系。 2 2 分布式数据库的设计结构 对于集中式数据库的设计包括： ( 1 ) 设计“概念模式”，概念模式描述了综合数据库。 ( 2 ) 设计“物理数据库”，即完成概念模式到存储空间的映射，确定合理的访问方式。 在分布式数据库设计中，上述两个问题可以演变成全局设计模式以及在各个节点上的局 部数据库的物理设计。可以用同集中式数据库中相同的方法技术来解决这些问题。分布式数 据库还有其特有的新的两个问题； ( 3 )设计数据分段，即决定如何将全局关系化为横向，纵向或纵横混合的分段。 ( 4 )设计分段分配，即决定如何将分段映射为物理映象，用这种方法同时决定了分 段的重复吼 虽然设计应用程序是在模式设计之后进行的，但是应用请求的知识会影响模式设计，显 然，在分布式数据库设计中，只对那些重要的应用请求才需要这些知识，这些关键的应用请 求知识包括： ( 1 ) 应用请求的发出节点。 ( 2 ) 应用请求的启动频率，对于一般的可以从多个节点发起应用请求的情况中，需 要知道每个应用请求的启动频率。 ( 3 )每个应用请求对所需的每个数据目标进行访问的次数，类型和统计分布情况 【1 0 l 。 2 2 1 数据分布的设计目标 】数据处理的局部性 数据分布达到最大的处理局部性相当于这样一个简单原理，就是使数据尽可能靠近使用 6 第二章系统体系结构与数据分布 他们的应用请求。表示处理局部性的最简单方法是考虑对数据的两种类型的访问，即“局部” 访问和“远程”访问，显然当应用请求源节点决定后，访问的局部性和远程性只取决与数据 分布。 为使处理局部性达到最大( 或相反地使远程访问最少) ，可以通过增加对应于各个候选 分段存储和分段分配的局部和远程访闯数目，并从它们中选出展佳解来完成。 当应用具有完全局部性时必须考虑扩展这个简单的标准。我们使用这个术语表示在它们 的源节点能够完全执行的应用请求。完全局部性的优点不仅是减少远程访问，而且还简化了 控制应用请求的执行。 2 分布式数据库的有效性和可靠性 有效性和可靠性是分布式数据库系统优于集中式之处。用相同信息的多复本存贮方式使 只读应用请求能够取得高度的有效性，在正常条件下：对某个副本访问无效使，系统必须能 转换到另一个副本。 3 工作负荷分布 在各节点上分布工作负荷是分布式计算机系统的重要特性。工作负荷还有利于充分利用 各个节点上的计算机功能并可提高执行应用的并行程度。由于工作负荷分布会反作用于 处理局部性，所吼在设计数据分布时有必要考虑他们之间的折中方案。 4 存储费用和有效性 数据库的分布反映不同节点存储的费用和有效性。般来说，如果与c p u ，i o 和应用 请求传输费抖j 相比，数据存储的费用是很小的。但是必须考虑每个节点的有效存储的局限性。 同时使用上述的所有规则是很困难的，因为这样做会导致很复杂的优化模型。把上述某 些特点只视为约束而不是目标是可以的。换言之，在初始设计阶段只考虑最重要的几条规则， 而其它准则则放到以后的优化过程中加入是n - ， i z i 。 2 2 2 数据分段的设计 分布式数据库的所有数据是分布在不同节点上的，一个全局关系可以储存在一个节点 j ：，也可以将数据分片以映射到不同的节点上，有许多分片方式，但不管哪种分片方式都应 当遵循下列规则： 完整性。全局关系的所有数据都必须分配到各个片断中，不允许某些数据属于全局关系 但不属于任何片断。 7 东南大学硕士论文 重构性。分裂后的各个片段可以重构原来的全局关系。实际上只有片段存储在分布式数 据库中，只有通过重构才能得到原来的全局关系。 不相交性。全局关系中的每个元组仅属于一个片段，不能在多个片段中重复出现。改规 则；f 是必须的，因在冗余分布式数据库系统中数据可以有多个副本”】。 1水平分片 水平分片是指把个全局关系中的元组分裂成多个子集，每个子集为个片段。分片条 件由关系中的属性值表示。 令p = p i ，p 2 ，p n 是一简单谓语的集合。为了正确而有效地表示分段，p 必须 是“完整的”和“最小的”。 ( 1 )只有当属丁同一段中的任意两个元组被任应用以同等概率进行访问时，我 们才称谓语的一个集合p 是完整的。 ( 2 )如果一集合p 中的全部谓语是相关的，我们称此p 是最小的。 2 垂直分片 垂直分片是将全局关系按列分成多个子集。垂直分片也应满足不相交性，但关键字除外 这足显然的，否则将不能重构原来的关系。 3 导出分片 导出分片也是中水平分片，但关系分片的限定条件不是该关系中的属性，而是由于该关 系有联系的其它关系导出的【1 4 】。 2 3医学图像数据库数据分段的设计与实现 2 3 1 设计模式采用自顶向下的设计 田为本课题是在已有的基于关键字查询( k s i r ) 和基于内容查询( c b i r ) 的医学图像 数据库基础上构建分布式的结构，因此从已有的全局模式开始，根据应用设计数据库的分段， 然后把段分配到各节点，建立物理图像。最后在每个站点进行分配给它的数据的物理设计， 从而完成自顶向下的设计。 已有的主要全局关系有： 病人信息关系p a t i e n t _ l n f o r ( p _ i d ，p n a l o e ，p a g e ，ps e x ，p _ 即i b e ，p _ o e s c r i p t i o n ) 第二章系统体系结构与数据分布 病人图像关系p a t i e n t _ i m a g e ( i m a g e i d ，p _ i d ) 图像内容关系i m a g ec o n t e n t ( i m a g e _ l d ，i m a g e _ c o n ) 图像特征关系i m a g e f e a t u r e ( i m a g e d ，f e a t h e r1 ，f e a t h e r2 0 ，s c o r e ) 2 3 2 数据分段的实现 对于全局关系p a t i e n ti n f o r 采用水平分段，这个关系是基于关键字查询的主要关系。一 般的分布式应用，病人的信息存储在以医院为单位的节点上。对于重要的应用，即按照给定 的病人的i d 号来查询病人的信息和图像。这个应用的s q l 查询如下： s e l e c tp n a m e ，p a g e ， p j e x ，l m a g e _ c o n f r o mp a t i e n tl n f o ra sa p a t i e n t _ i m a g ea sb ，i m a g e _ c o n t e n t a sc w h e r e m p i d = i n p u t a n da p 一1 d 。b p i d a n d b 1 m a g e _ l d 。c 1 m a g e _ i d 该应用可由任一站点发出：在医院a 发出的该查询，以很大概率访问的是存储在本节 点的病人设医院a 病人i d 范围为：1 1 0 0 0 ；在医院b 发出的该查询，同样以很大概率 访问b 节点的病人信息，设b 节点病人i d 范围为1 0 0 1 - - 2 0 0 0 ；等等。这是因为每个医院 的奄询更倾向于在本医院登记的病人。 所以产生的谓语为： p l ：1 p i d 1 0 0 0 p 2 ：1 0 0 1 p1 d 2 0 0 0 因为集合p p l ，p 2 ，) 是完整的和最小的，所以该分段是合适的分段方法。 对于病人图像关系，图像内容关系，图像特征关系，采用导出式水平分段。设病人信息 关系通过水平分段为分片：p a t i e n t i n f o r 一1 ，p a t i e n t _ i n f o r _ _ 2 。病人图像关系由病人信息关 系的分片导出： p a t i e n t _ i m a g e _ l = p a t i e n t _ _ i m a g e j o i n p a t i e n t i n f o r 一1 p a t i e n ti m a g e _ 2 = p a t i e n t _ i m a g e j o i n p a t i e n t l n f o r 一2 9 东南大学硕士论文 图像内容关系和图像特征关系由病人图像关系的分片导出： i m a g e c o n t e n t 1 2 i m a g e _ c o n t e n t j o i n p a t i e n t i m a g e _ l i m a g e _ c o n t e n t2 = i m a g e _ c o n t e n t j o i n p a t i e n t l m a g e _ 2 i m a g e f e a t u r e 一1 2 i m a g e _ f e a t u r e j o i n p a t i e n t i m a g e 一1 i m a g e f e a t u r e2 = i m a g e _ f e a t u r e j o i n p a t i e n t _ l m a g e _ 2 2 3 3 分布式数据目录的设计与分段 分布式数据库系统中对数据库的正确有效访问都离不开目录，如把对数据库的访问如何 映射为对物理数据的操作，如何选取有效的存取路径以及确认用户是否有访问权限等都需要 目录信息。因此目录如何构造，分布和管理都会影响系统的效率。数据目录的分布策略有： ( 】)集中式。系统目录集中存放在一个节点上，其它节点都需要访问该节点上的 目录数据。实现简单，易于管理。 ( 2 )全复制式。在每个节点都有一个目录的副本，因而无需访问其它节点上的目 录。但是带来了数据冗余。 ( 3 )部分复制式。可有不同的复制策略，如一个节点采用集中式目录，其余节点 存放与本节点数据有关的目录；或者一部分目录全复制，一部分目录仅存储 在相关节点上。如全局模式描述，分片和分布信息全复制，而其余目录数据 可局部存储”1 。 对于本系统，设计数据目录为三张表，分别进行数据划分条件管理和用户管理。 表s i t e 储存每个节点的信息 【字段名字段类型字段意义 l s i t e n a m e v c h a r ( 2 0 ) 节点标示名 s 让e p v c h a t ( 2 0 )节点i p s i t e d l 3 m s v c h a r ( 2 0 )节点运行的局部数据库系统类型 1 0 第二章系统体系结构与数据分布 表f r a g m e n t s 表示数据分段的划分条件 字段名字段类型字段意义 it a b l e n a m e v c h a r ( 2 0 ) 表名 f r a g c o n d i t i o n _ m i n i n l 划分区间下限 f r a g c o n d i t i o n _ m a x i n t划分区间上限 i s i t e 】dv c h a r ( 2 0 )节点名 r e c o r d c o u n ti n t该节点的记录数目 表u s e r s 存储整个分布式系统的用户权限等等 字段名 字段类型字段意义 u s e r n a m e v c h a r ( 2 0 ) 用户名 p a s s w o r d v c h a r ( 2 0 ) 用户密码 p e r m i s s i o ni n t访问权限 由于分布式数据库系统的节点自治性要求，集中式的数据目录存储方法，如果中央服务 器发生故障，所有其它节点都无法正常工作。而且数据目录大小有限，大部分的操作都是查 淘，所以采用全复制式的分布方法，即每个节点有一个副本：当查询时，只要查询本节点的 数据目录。当一个节点发生数据目录的更新时。所有的节点都要更新。只有在加入用户或者 增加或删除数据时才会发生数据目录的更新，所以修改目录的频率相对于读取目录的频率要 小得多，所以这个方法可取。 东南大学硕士论文 第三章分布式查询优化 3 1关系代数的等价变化 考虑关系代数的两个表达式e 1 和e 2 。每个表达式中出现的关系名对应于关系变量。如 果在两个表达式中把相同的关系代入相同的名字而得到相等的结果，那么我们说这两个表达 式是等价的。 对于简单的表达式，如只有两个或三个操作数关系的表达式，可以有如下的等价变换。 令u 和b 分别代表一元代数运算和二元代数运算。 其中一元代数运算有：投影p j ，选择s j 。 主要的二元运算有：并集u n ，结合j n ，半连接s i n 。等等。 一元运算的交换律： u 1 u 2 r。u 2u l r 二元运算的操作数的交换律： r bs=sbr 二元运算的结合律： r b ( s b t ) = ( r bs ) b t 一元运算的幂等； ur 2 u l u z r 一元运算相对于二元运算的分配律： u ( r bs ) = u ( r ) b u ( s ) 一元运算的因子分解： u ( r ) b u ( s ) = u ( r bs ) 应崩这些规则，在集中式数据库中有如下的一般优化准则，对于分布式数据库也同样重 要：使用选择和投影的幂等性来为每个操作数关系产生相应的选择和投影，并把查询树里的 选择和投影操作尽可能的向下推移。这些准则来源于二元运算( 特别是结合) 运算是数据库 系统中最昂贵的常用运算，所以在执行这些运算之前先减, b 2 元运算操作数的大小是很可取 的。在分布式数据库中这些准则甚至更为重要，因为二元操作运算需要比较的操作数甚至可 第三章分布式查询优化 能分布在不同的节点上。而数据的传输是于执行查询有关的费用和延迟中的一个重要组成部 分。因此减少二元操作数的大小是一个主要的要求。 3 2 分布式查询优化的基本要求 在分布式查询处理技术中，查询优化的基本类型包括两类：针对查询执行代价的优化和 针对查询响应时间的优化。查询响应时间即查询开始提交至获得第一个结果之间的时间。一 般情况下，查询响应时间多少往往就意味着执行代价的大小。因此在这里主要讨论查询执行 代价。 针对查询执行代价进行优化的目标是，是查询执行所使用的系统资源的总和尽量的少， 从而降低系统开销，整个系统的开销可以从各个系统资源的开销表达式中推出。 在集中式数据库系统中，对查询执行代价进行评估的最关键资源有： ( 1 )c p u ( 2 ) i 0 通道 ( 3 )通信线路 分布式数据库系统中，网络速度比c p u 和u o 通道的速度低几个数量级，因此，网络 代价成为分布式数据库执行速度的主要瓶颈，也是查询优化要主要考虑的。 3 3 分布式查询树的优化和分解 对于本应用系统的一个代表性查询，需要查询给定病人i d 的图像相应的全局关系表 达式如f ： p j c 。s l p 一) ： w ( ( p a t i e n t _ l n f o rj n p 一dp a t i e n t _ i m a g e ) i n p 一l m a g ec o n t e n t ) 其中的关系用全局关系表示这是一个全局查询。查询树如下： 东南大学硕士论文 j n h n 一d i n p ，d i m a g e _ c o n t e m p a t i e n ti n f o r p a t i e n t _ i m a g e 图3 1 第一步：对初始的查询树按照关系等价变换应用以下变换： 把选择变换下移，产生两个新的投影运算并把它们相对于结合运算进行分配。 p j pm s l p t 3 | i f p a r l e n ti n f o r p j f j n i i n w 一d s l p 一d ；“ p a t i e n t _ i r a a g e 图3 2 第二步：把全局查询变换成段查询 p j h l l 一d ，n l m a g e _ i c o m e n t 第三章分布式查询优化 这是分布式数据库查询优化的独特之处。上面进行的是对全局关系进行的优化分析，田 为将分段进行重构可以形成全局关系，同样现在把全局关系用关系的片段来表示。假设将全 局关系分布在两个节点上： p j f j n i i n w d j n p dp k o 口一n c 。n t j p 3 pf d s l n 一“f。l l 岫； 。呼 i u nu n p a t i e n t i n f o r ip a t i e n t l n f o r 2 i m a g e - c o n t e n t 2 p a t i e n t _ l m a g e _ 1p a t i e n t _ m a g e 2 图3 3 其中， p a t i e n t i n f o r 一1 的戈分规贝0 为【o p _ i d 1 0 0 0 p a t i e n t l n f o r 一2 的划分规则为 1 0 0 0 p _ i d 2 0 0 0 p a t i e n t _ i m a g e 一1 的戈0 分规4 为田一i d = pi n f o r p i d a n d0p i n f o r p _ i d 1 0 0 0 】 p a t i e n t _ i m a g e _ 2 的划分规则为 p j d 冲j n f o l p a d a n d 1 0 0 0 p _ i n f o r p _ i d 2 0 0 0 】 l m a g ec o n t e n t _ l 的划分规则为 【i m a g e _ i d = p _ i m a g e i m a g e i da n d p _ i m a g e c a d = p _ t n f o r p _ i d a n d 0 p _ i n f o r p i d 1 0 0 0 】 i m a g e c o n t e n t _ 2 的划分规则为 i m a g e _ i d = p _ i m a g e i m a g ei d a n d 一 东南大学硕士论文 p _ i m a g e p - i d = p _ l n f o r p i d l0 0 0 p - j n f o r p i d 2 0 0 0 同样，将选择和投影运算下移联台运算上移 p j 。h f # n r 州i m 一 j n pi d a n d p j i m i d ，c m f “f p j h * 一i d ，。m f i m a g e _ c o n t e n t _ 1i m a g e - c o n m n t _ 2 p j p _ d p j l , 一p j l m a g e 一1 d ，一1 dp j i m 一d ，p 一d s l e j d ：h ，s l e 。d ：| t p a t i e n tt n f o rlp a t i e n ti n f o r2 s l pf d ： l “吼p ! d ：i t p a t i e n t _ i m a g e _ lp a t i e n t _ i m a g e _ 2 图3 4 第三步：采用推论方法进一步化简 1 6 第三章分布式查询优化 假设本查询输入的病人i d 为i n p u t ，0 i n p u t 1 0 0 0 。并由几个表之间的关系推出，在 o p 一1 d 1 0 0 0 时，p a t i e n t _ i m a g e 表中l m a g e _ i d 的范围为0 i m a g e _ l d 5 0 0 01 0 0 0 p _ i d 2 0 0 0 时，p a t i e n t _ i m a g e 表中i m a g e _ i d 的范围为5 0 0 0 i m a g e i d 1 0 0 0 0 。并且按照此规则给 p a t i e n t _ l m a g e 表和i m a g e _ c o n t e n t 表分段为p a t i e n t _ i m a g e 一1 ，p a t i e n t _ i m a g e _ 2 以及 i m a g e _ c o n t e n t _ 1 和i m a g e _ c o n t e n t _ 2 。 所以可以推出下面的蕴含式： 0 i n p u t 1 0 0 0 得到n o t ( 5 0 0 0 i m a g ei d 1 0 0 0 0 ) 把对i n p u t 的选择操作运用到各个分段，得出其中由三个分段式永假式，因此只有每个 分段的个需要运算，其它的分段抛弃： p lp m p 1c b w j n “一i d j n p 一d p j h 口d ，c r p j i “w i d ，p i d s l e 一。f i m a g e _ c o n t e n t _ l p a t i e n ti m a g e1 图3 5 这是最终优化后的查询树。可见经过合理的优化，只对查询需要的分片进行运算，省去了对 无效分片进行的运算。 1 7 东南大学硕士论文 3 4 连接算法的优化 连接方法在分布式查询优化中起着重要作用。在没有优化的分布式数据库系统中，如果 参加连接运算的表在不同节点上，就要把远程节点的表整个传送到本地节点再连接，带来了 沉重的网络负担。而半连接运算可以大大简化异地连接所传送的数据量。 半连接是由投影和连接运算导出的一种关系代数运算。两个关系的半连接表示为： r s j n a = b s 5 r j n h 。8 ( s lbs ) 运用半连接运算，连接运算可以表示为：r j n a = b s = ( r s j n a = bs ) j na = b s 对于位_ 丁不同节点的r 和s ，连接运算需要将关系r 或s 送到对方节点，而运用半连 接运算，首先在s 所在节点对连接属性投影，将投影结果送到r 所在节点执行半连接，然 后把半连接后的结果送回s 所在节点完成连接。仅执行连接和运用半连接的连接操作其通信 代价分别为t 1 ，t 2 ： t 1 = c o + s i z e ) + c a r d + c 1 t 2 = 2 c 0 + s i z e ( b ) + c a r d ( s 1 ) + c 1 + s i z e ( r ) + c a r d ( r 1 ) + c i 其中，s i z e 表示元组的长度，c a r d 为元组数，s 1 为关系s 在属性b 上投影的结果关系，r l 为执行半连接后的结果关系。 运用半连接实现连接操作需要二次数据传输，但在一般情况下，属性投影和半连接结果 的数据量要远小于一个关系的数据量，因此，一般得t 2 远小于t i ，从而降低了通信代价。 这里没有考虑在本节点执行的操作。采用半连接需增加投影和半连接运算，而不用半连接时 参加连接的操作关系其元组数量要比半连接后的元组数量多。 半连接不具有交换性：r s j ns!=ss j nr 半连接具有可分配性：( r i u n r 2 ) s j ns = ( r 1 s j n s ) u n ( r 2 s j n s ) 在两个关系r 和s 连接运算之前运用半连接可除去r 中不可连接的元组，称为对r 的 约简。对多元连接。若每个参加连接的操作数都可以约简称为完全约简，其半连接程序称为 约简器 1 ”。 3 5 优化结果的讨论 通讯翻络一次传输的费用可甩下式表示 1 8 第三章分布式查询优化 t ( x ) = c o + x + c l 其中，c o ，c 1 是和系统有关的常数，x 表示传输的数据量。因为只是相对比较结果的 好坏，而不是得出费用的精确量，为了简单起见，设常数c o 为零。 关系运算结果的概貌估算方法如下： 其中，t 表示关系r 和s 的二元操作结果。 c a r d ( r ) ：r 中含有的元组数。 s i z e ( a ) ：属性a 的字节数 v a 】( a r 】) ：r 中属性a 可能取值的个数。 选择率p = v a l ( a r ) v a l ( d o m ( a ) )其中d o r a ( a ) 为a 取值域中不同值的个数。 半连接结果估算方法： c a r d ( t )