（计算机软件与理论专业论文）支持关系查询的xml视图物化选择系统.pdf

支 持关系 查询的x m l 视图物化选择系 统第2页共6 2 页 x v ms : 支持关系查询的x ml视图 物化选择系统 摘要 我们的数据库系统是国家数字图书馆项目的 x ml元数据存储和查询的一部 分。 x ml数据往往海量，实际中又需要对其进行复杂的查询，查询的响应时间一 般要求在用户交互的级别上，这样，查询效率就成为一个突出的问题，它的存储 和查询技术也己 成为一个重要的研究方面。 本文在考察了目 前的一些 x ml存储查询技术、o o d b及关系库技术后，重 点集中在使用关系库进行x ml数据的存储和物化选择， 构造了一个新的群体遗传 算法来选择适合关系查询的物化视图集合，并在此过程中完成查询重写。并据此 考察了x m l各种技术的应用比较，如d o m与s a x ，索引技术和查询优化及物 化视图集维护等等。 本文中引入了群体的概念， 将x ml的树型结构信息完整的引 入关系表，并构造出群体中的染色体，以期以物理存储冗余为代价，基于用户查 询的频繁度，通过遗传自然选择机制获得全新的视图集合，从而形成更合理的映 射模式，提高查询效率。模式树是一种树状结构，它用于表示用户的查询需求， 也 用于 表示x m l 数据。 本文 是为了 使用 模式树 所解析的x q u e ry表示的 查 询语句， 以及关系查询语句进行查询而做准备。 我们的工作主要解决了以下问题: ( 1 )如何将x m l 文档映射成关系数据并用合适的 数据结构存储它们; ( 2 )如何根据元素的查询频度选择适当的元素集，并执行优化来生成物化视图; ( 3 )如何选择最合适的 物化视图 和查询计划( 即查询重写方案) 回答用户的查询。 关键字: x ml物化视图关系库查询效率物化收益 x v ms : a x ml ma t e r i a l i z e d v i e w s s e l e c t i n g s y s t e m wh i c h s u p p o r t s r a l a t i o n a l q u e r i e s o u r p r o j e c t i s a p a rt o f t h e n a t i o n a l f u n d p r o j e c t 一 d i g i t a l l ib r a ry , f o r s t o r i n g a n d q u e ry i n g x ml m e t a d a t a . w e h a v e s t u d i e d a l o t o f t e c h n o l o g i e s a b o u t x ml d a t a s t o r a g e a n d r d b , t h e n c e n t r a l i z e d o n t h e m e t h o d o f s t o r i n g a n d s e l e c t x ml m a t e r i a l i z e d v i e w s . t h i s p a p e r p r o v i d e s a n e w m e t h o d 一c o l o n y - g e n e t i c a l g o r i t h m . i t i s f o r s e l e c t i n g m a t e r i a l i z e d v i e w s , a n d d o e s t h e q u e ry r e w r i t i n g w o r k d u r i n g t h e p r o c e d u r e . we b r in g i n a n e w c o n c e p t i o n 一c o l o n y , a n d m a p t h e x m l t r e e - m o d e l e d i n f o r m a t i o n t o r d b i n t e g r a l l t y , a n d b u i l d u p t h e s t r u c t u r e o f a c h r o m o s o m e t o g e t a n e n t i r e l y n e w v i e w s e t w i t h b e t t e r q u e ry e f f i c i e n c y . o u re w o r k i s a p r e p a r a t i o n f o r t h e 支 持关系查询的x m l 视图 物化选择系统第 3页共6 2 页 x q u e ry a n d r e l a t i o n a l q u e r i e s . i t s o lv e s t h e f o l l o w i n g p r o b l e m s : ( 1 ) h o w t o m a p t h e x ml d o c u m e n t s t o r d b a n d s t o r e t h e m w i t h a n a p p r o p r i a t e d a t a s t r u c t u r e ; ( 2 ) h o w t o s e l e c t a n a p p r o p r i a t e e l e m e n t s e t r e l y i n g t h e e l e m e n t s q u e ry f r e q u e n c y a n d t o c r e a t e m a t e r i a l i z e d v i e w s t h r o u g h s o m e o p t i m i z i n g m e t h o d s ; ( 3 ) h o w t o s e l e c t t h e b e s t q u e ry p l a n s ( q u e ry r e w r it i n g s c h e m e s ) a n d t h e r e l e v a n t m a t e r i a l i z e d v i e w s f o r a q u e ry t o r e p l y t h e u s e r s r e q u i r e m e n t . k e y wo r d s : x ml ma t e r i a l i z e d v i e w r d b q u e ry e f fi c i e n c y ma t e r i a l i z e d i n c o m e n il 吕 w3 c在 1 9 9 8 年制定了x ml的标准， 启动了整个i n t e rn e t 信息标准化的进程。 x ml以其自 描述性、 可扩展性以及计算机易处理性迅速取得了学术和企业界的广 泛认同，它日 益超出其标注语言的初衷而成为i n t e rn e t 上数据表示和交换的标准。 四年来， 成千上万的x m l a p p l i c a t i o n 被定制， 许多 专业领域都有了各自 满足不同 需求的x m l 描述标准，数字图 书馆元数据描述标准d u b l i n g c o r e 就是其中之一。 x ml定义为一种可根据文档的内容需要以不同的方式来描述内部的格式和 逻辑结构的 元语言( m e t a l a n g u a g e ) 。 这种通用的、 可扩展的方法， 使得 x m l 具有 非常大的使用范围，从字处理、电子商务到协议数据交换， x ml的数据格式都具 有非常大的优势。同样， 利用x ml 数据， 我们可以使不同平台或受系统限制的软 件能够彼此相互沟通。我们相信，随着电子商务的日渐兴起和网络信息交流的发 展， x m l 格式的数据将越来越多。 x m l数据的有效存储和查询给数据库研究和商用系统开发提出了令人兴奋 的 挑战和机遇。 随着x ml 应用中信息的数量级不断加大， 同时众多商用领域对系 统稳定性要求的不断提高， 对x ml的存储系统提出了更高的要求。 如何才 能有效 地存储x ml文档中包含的信息?不同于h t ml的关键字检索， x ml文档的一个 重要特征是具有结构， 并且能对其进行基于内容的结构化检索。 随着x ml 应用服 务用户的不断增加， 查询的实时响应对许多应用来说也成为系统成功的必要条件。 如何才能结合 x ml文档的存储模型来设计高效的查询执行算法?与此同时，很 多实际应用不但对查询的实时响应有较高的要求，而且具有其相对固定的应用特 征( 包括x m l 文档的数据分布和查询模式等) ， 数字图书馆元数据的存储和查询 就是此类应用之一。如何才能充分地利用应用的数据分布和查询模式特征有效的 提高存储和查询效率?这些都是我们要着重考虑的问 题。 支持关系查询的x ml 视图物化选择系统第4页共6 2 页 1研究目的及成果 对于任何一种数据，当它的数据量超过人力检索的能力范围后，必然要求计 算机协助进行存储管理和查询。 随着x ml数据的增多， 它的存储和查询也就成为 一个研究的热点。对于信息的存储和检索，目 前最重要和最成功的系统应该是关 系数据库系统。 而关系数据库之所以能够成为一个最成功的应用最广泛的数据库， 有一个最重要的因素，就是有一个非常简练有效的代数系统来表现数据并表达对 数据的操作，这样我们可以在这个系统上研究各种不同的查询优化技术。 在本文的系统中， 自 动化的完成了“ x ml数据到关系库的映射一 物化选择 / 查询重写一 数据导入一视图集维护” 的整个过程。 在第3 到第7 章中分别详 细介绍了各个步骤的原理和实现，在第 8章中对系统原型的实现和使用及实验结 果作出了描述。下面作一简要陈述: 本文比较了各种新老选择方案，并给出了一种新型物化选择及查询重写的算 法。 在此基础上， 本文还提出 使用d a g u p d a t e 算法来完成物化视图集日 后的 维 护工作。 通常来说， x q u e ry查询语句需要被解析为模式树， 将经常被查询的x m l 文档节点信息存储到物化视图中。利用物化视图和用户查询的交叉部分，直接从 物化视图中获取用户的查询内容。 那么将x ml数据映射为关系表之后物化视图的 选择问 题变成为完成这一工作的首要要素。 文章中， 我们针对x m l物化视图选择 的特殊性针对遗传算法的各个算子进行了大幅度的改造。提出了动态变异等约束 进化方向的新算子等。并且进一步的，我们将贪心算法结合进来，以经典的映射 方 法b a s ic , s h a r e d , h 夕 b ri d 算 法为 基 础， 提出了 崭 新的 群体 遗传 算法， 解决了 局 部优化解及查询重写的问题，为关系查询语言及半结构化查询语言的进一步查询 优化提供了基础和必要条件。 对于x ml的存储， 我们找出了一个合适的模型， 可以定量的分析查询的时间 代价以及x ml数据的存储代价， 并在此基础上探讨查询优化。 关系代数中定义了 泛关系模型，根据在这个模型，我们可以把整个数据库视为一张表，然后对于关 系中每个元组的所有属性，可以进行查询 ( 仅用 s e l e c t 就可以)。对于不在同一 个元组中的数据单元 ( 属性) ， 则需要通过j o i n操作得到一个所有元组与所有元 组的笛卡儿乘积的表 ( 如此任何两个数据单元之间都有了关系)后查询。同样对 于不同的两个x ml 文档 ( 或者文档中的不同x ml子树)内的数据关联，当我们 需要查询时， 也要通过j o i n操作把他们放在一起 ( 使两个时间单元产生关联) 刁 - 可以 进行查询。因此在我们的系统中， 这种关系查询也需要得到支持。 最后， 我们实现了一个可以 进行关系查询和半结构化查询的 对d t d和x m l 文 档 数 据进 行关 系 存储 和 进行 物化 选 择的 原 型 系 统x v m s s y s t e m ， 在 这 个系 统中 ， 支 持关系 查询的x m l 视图 物化选择系 统第 5页 共6 2 页 使用将传统的算法如排序算法， 贪心算法， 爬山 法，遗传算法，解答树算法等应 用到物化选择问题上，并给出了详细的参数及函数定义。系统将这些算法运行的 结果与新提出的群体遗传算法结果集依据我们的数据模型导入关系库中，并以查 询效率的改进程度作为主要标准对其进行了系统的对比。 2相关技术 2 . 1 xm l 随 着因 特网 的 快速发展， x m l e , ， e 2 . ;( e i ,e 2 ) ? 一 e , ? ,e 2 ? ;( e l 1e 2 ) 一 e ,? ,e 2 ? 规则二: 减多余操作符， 即简化变换， 将多个一元操作符规约为一个一元操作符; e , ” 一 e l . ;e , . ? - e , * ;e , ? 一 e , ; e l ? ? 一 e l ? 规则三:合并同名元素，即组合变换，将多个有相同标签名的子元素合并为一个 子元素，另外所有甲操作符都被转化为1* ，操作符。 自申巾 二。 一a， 一 a ? , ， a ? , a ? ， ， a , ?， . 一 a， a , . . . , a， . . . - a， 二 这些变换保持了一对一还是一对多关系和是否可以为空的语义区别。但也丢 失了一些关于元素间的相关顺序的信息， 但在具体处理某一x ml文档时可以根据 文档中元素间的具体位置来重获。 支持关系查询的x ml 视图物化选择系统第 1 3页 共6 2页 3 .3 .2映射d t d及x ml文档为图的形式 接下来就要将一个简单的d t d转换到关系模式。将d t d中的每一个元素映 射到关系库并将元素的属性映射为关系属性。而实际上 d t d 中的元素和属性与 e r模型中的实体和属性并没有一致性的关系。e r模型中的属性在大多数情况下 在d t d中是由元素来表示的。目前的主要问题便是不可直接映射，因为会产生碎 片问题，比如导致明明应该在同一张表中的元素或属性被切碎到不同表中了。下 面的部分中通过图3 .3 中具体的d t d实例来描述映射的方法。 gat t l i s t c o n t a c t a u t h o r a u t h o r l d i dr e f i mp l i e d g a t t l i s t e d it o r n a m e c d a t a # r e q u i r e d 图3 . 3 d t d实例 作为实例， 图3 .4 给出了图3 .3 中d t d的图形表示: d t d图显示了一个d t d 的结构，其中的节点表示元素、属性及操作符。而为了表示由某一元素而得出的 一组关系 ( 关系表) 又引入了e l e m e n t 图。 从当前想要为其构造关系表的那个元素 节点开始对d t d图进行深度优先的遍历， 每个节点第一次被遍历到时便被标记为 v i s i t e d ， 直到它的孩子都被遍历过时则被取消标记。 当d t d图中的一个未标记 节 点被遍历到时， 便在相应的e l e m e n t 图中产加入一个与之同名的新节点。 并且， 一 条从之前 最后产生的 节点 到新节点的r e g u l a r 边被加 入到e l e m e n t 图中， 其名 字与 d t d图中当前节点与其按深度优先的父亲节点之间的边同名。若遍历到一个己 经 被 标记了 的d t d节点则 加入一条b a c k p o i n t e r 边， 此边由e l e m e n t 图中 最新产生的 节点指向与d t d中被标记过的节点同名的e l e m e n t 图中的那个节点。图3 . 5 为由 e d i t o : 元素生成的相应的e l e m e n t 图。很明显，e l e m e n t 图将d t d图中的相关部分 建树。 接下来为了为x ml 文档数据的导入做准备，引入x ml 文档图。 支持关系查询的x ml 视图物化选择系 统 第 1 4 页 共 6 2页 e d i 拍t 二 川i s i r / b xk 山h 人 a ml - 一 。、，1 name,ancsmri, 1 卜le a u l l roi / 丈二一 n s n x a d d - a u th c r i d / 产 图3 .4 d t d图 下面给出一个文档实例及其对应的 f i r s h sn , t l a s u u n m 图3 . 5 e l e me n t 图 x ml文档树，分别如图3 .6 , 3 .7 所示。 s t o r i n g s e m i s t r u c t u r e d d a t a w i t h s t o r e d j u n e 1 9 9 9 al i n d e u t s c h a d e u t s c h g r a d i e n t . c i s .u p e n n .e d u ma ry f e m a n d e z a n a m e m ff r e s e a r c h .a t i . c o m r . mi c h a e l qa u t h o r 图 3 .6描述出 版信息的 x m l 文档 支 持关系 查询的x m l 视图物化选择系 统 第 1 5 页 共 6 2 页 x ml文档树 一 湘 u 一 -t h ie 汤、 , d a t e - 吕 2 a u l h o r 2 _ _ 几 _ 刁1 b . 具 有 b a c k p o in t e r 边的 节点 也需 被 分 离出 来另 建 新 表，以 处 理 循环的 情 况。 这两种情况是要在为每一个元素都建了表之外再添加的表，如下图中的 a r t i c l e .a u t h o r ， 在生成元素a r t i c le 相应的表时就无法表达其下的a u t h o r s 元素的多值信 息。 于是 使用传 统工具再为 a u t h o r 创建一个 表而并 使用f o r e i g n k e y *联接到父表 a r t i c l e 表。 但也就是因此而导致表的数目 极多。 对于递归关系， 则因要中止其无休 止的 迭代在存储时要强行切断，因 此表达递归关系时要使用关系表主键及关系迭 代的处理来重获这种信息。 图3 .8 给出了对应图3 .3 中d t d 的关系模式。 其中， 关系表中的属性以从此关系 的根元素起到此元素的路径来命名。每个关系表都有一个名为i d 的域来作为此关 支持关系查询的x ml 视图物化选择系统第 1 6页 共 6 2页 系表的主键。如果此关系表所对应的元素节点在d t d 图中是有父节点的，那么在 此表中 则必有一p a re n t l d 域作为 f o r e i g n k e y 。 例如， a r t i c l e .a u t h o r 表就有一个f o r e i g n k e y 名为 a r ti c l e .a u t h o r .p a r e n t i d 的域用来联接a u t h o r s 与a r t i c l e s 表。 1 . b o o k ( b o o k i d:i n t e g e r , b o o k . b o o k t i t l e :s tr i n g , b o o k . a u t h o r . n a m e . f i r s t n a m e : s t r i n g , b o o k . a u t h o r . n a m e . la s t n a m e : s t r i n g , b o o k . a u t h o r . a d d r e s s : s t r i n g , a u t h o c a u t o r i d : s t r i n g ) 2 . b o o k t it l e ( b o o k t it l e i d : i n t e g e r , b o o k t i t l e : s tr i n g ) 3 . a rt i c l e ( a rt i c l e d : i n t e g e r , a rt i c l e . c o n t a c t a u t h o r .a u t h o r e d :s t r i n g , rt i c l e .t it l e : s t r i n g ) 4 . a rt i c l e .a u t h o r ( a rt i c l e .a u t h o r e d :i n t e g e r , a rt i c l e . a u t h o r .p a r e n t e d :i n t e g e r , a rt i c l e .a u t h o r . n a m e .f i r s t n a m e : s tr i n g ,a r t i c l e .a u t h o r . n a m e . l a s t n a m e :s t r i n g , a rt i c l e .a u t h o r .a d d r e s s : s t r i n g , a rt i c l e .a u t h o r .a u t h o r e d : s t r in g ) 5 . c o n t a c t a u t h