（计算机应用技术专业论文）xcube的计算和查询.pdf

山东建筑大学硕士学位论文 捅要 随着b 2 b 等应用的普及，越来越多的数据以x m l 文档的形式出现，如何对x m l 文档中的数据进行联机分析引起了研究工作者的关注。传统的做法是先将x m l 中数据 转换为关系的元组，再进行计算。本文中，我们通过直接对x m l 文档进行操作，避免 了数据转换过程，提高了运算效率。x c u b e 是关于x m l 的一个立方体结构，在实际应 用过程中，当输入数据量太大时，受内存限制，无法完成运算。若把数据分批输入进行 运算，则会产生许多重复的中间结果，要形成最终结果需从磁盘中把这些中间结果读入 内存再进行大量的合并工作。因为涉及磁盘的读操作及大量的合并操作，使运算时间增 加好几个数量级。通过分析和实验，我们对x c u b e 算法进行了改进，提出了“分批输 入分次计算 的方法。当数据量很大时，按照新改进的方法进行分批输入计算时，我们 只生成最终结果的分支，对于中间结果的分支不予计算，避免了对中间结果中某些分支 的合并过程。通过对数据进行分次计算的方法，生成剩余分支，使运算顺利完成。因为 运算中没有涉及到从磁盘中读中间结果进行分支合并的过程，所以提高了运算效率。 b l o o mf i l t e r ( 布隆过滤器) 是1 9 7 0 年由b l o o m 提出的，它利用h a s ht a b l e ，通过h a s h 函数将元素映射成b i ta r r a y 中一个点。当检索时，只要查看相应点的值是否为1 就可知 这个元素是否在集合中。为了增加准确度，b l o o mf i l t e r 中可以利用多个h a s h 函数。通 过对相关查询算法研究，我们发现x c u b e 的点查询为一个从根节点到叶子节点的路径匹 配过程，于是我们按照b l o o mf i l t e r 的思想提出了一个新的压缩查询算法：b x c u b e 算 法。把x c u b e 算法中产生的每条从根节点到叶子节点的路径作为整体，通过多个( 两个 或三个) h a s h 函数进行计算，分别产生多个h a s h 值。我们只存储由h a s h 值、度量值及 t a g 域构成的结构，称为b l o o m 元组。相对于存储整条路径，存储b l o o m 元组，节省 了存储空间并对机密数据提供了一定的安全保障。路径长度越长，效果越明显，更适用 于高维数据。由于h a s h 函数本身的问题，当数据量太大时，不可避免的会出现h a s h 冲 突。为了消除因为h a s h 冲突而使查询结果错误的问题，我们设计了一个过滤结构：过 滤器表。在运算时，把同一棵子树的所有路径经过运算，放入过滤器表中，经排序后， 若相邻的临时b l o o m 元组h a s h 值相同，而度量值不同，则需要把这两个路径字符串经 过一个新的h a s h 函数进行h a s h 计算，当产生的h a s h 值可区分时，把第一个路径字符串 产生的h a s h 值、两条路径对应的度量值及所用的h a s h 函数i d 放入冲突表中，而在查 询表中，只存储一个b l o o m 元组，其t a g 域的值指明如何解决冲突。若相邻的三个元 山东建筑大学硕士学位论文 组间存在冲突时( 概率极小) ，则通过路径表处理。当冲突检测完后，把结果放在查询表 中，同时在索引表中记录该棵子树产生的b l o o m 元组在查询表中的位置。当查询时， 首先通过查询路径的根节点的值在索引表中查找查询范围。若值在索引表中，则可通过 查询得到在查询表中的查询范围。把整条查询路径作为一个整体经过相应h a s h 函数计 算，生成临时元组。把临时元组在查询范围内进行折半查找，返回查询结果。因为与 d w a r f 结构类似，都是树形结构，所以我们和d w a r f 算法进行了比较。实验结果表明 b x c u b e 算法在存储空间和查询响应时间方面都优于d w a r f 算法。 关键词：o u 心，数据立方体，x m l ，x c u b e 山东建筑大学硕士学位论文 t h ec o m p u t a t i o na n dq u e r yo fx c u b e x u ez h o n g b i n ( c o m p u t e ra p p l i c a t i o nt e c h n o l o g y ) d i r e c t e db yl is h e n g e n a b s t r a c t w i t ht h ed e v e l o p m e n to fb 2 ba n do t h e rc o m m e r c i a la p p l i c a t i o n s ，m o r ea n dm o r ed a t a a r er e p r e s e n t e di nt h ef o r mo fx m l h o wt oa n a l y z et h ed a t ai nx m ld o c u m e n t sr a i s e sg r e a t c o n c e r nf o rt h er e s e a r c h e r s t r a n s f o r m i n gx m ld a t ai n t or e l a t i o nt u p l e s ，a n dt h e nc a l c u l a t e d o nt h et u p l ei st h et r a d i t i o n a lo p e r a t i o n i nt h i sa r t i c l e , w e d i r e c t l yo p e r a t et h ex m l d o c u m e n t s ，a v o i d i n gt h ed a t ac o n v e r s i o np r o c e s sa n di m p r o v i n gt h eo p e r a t i o n se f f i c i e n t l y x c u b ei sac u b es t r u c t u r ef o rt h ex m l w h e nt h ea m o u n to fi n p u td a t ai st o ol a r g et o b e y o n dt h em e m o r yc o n s t r a i n t s ，x c u b ew i l lb eu n a b l et oc o m p l e t et h eo p e r a t i o n i ft h ei n p u t d a t ao p e r a t i o ni nb a t c h e s ，i tw i l lp r o d u c em a n yd u p l i c a t ei n t e r m e d i a t er e s u l t s i no r d e rt o f o r m i n gt h ef i n a lr e s u l t s ，i th a st or e a di n t e r m e d i a t er e s u l t sf r o mt h eh a r dd r i v ea n dt od oal o t o fc o n s o l i d a t i o nw o r ki nm e m o r y b e c a u s ei ti n v o l v e st h er e a do p e r a t i o nf r o mt h eh a r dd i s k a n dal a r g en u m b e ro fc o m b i n e do p e r a t i o n s ，s ot h ec o m p u t a t i o nt i m e sw i l lb ev e r yl o n g a n a l y z i n gt h ex c u b ea l g o r i t h mc a r e f u l l y , a n db a s e do nal a r g en u m b e ro fe x p e r i m e n t s ，w e p r o p o s ean e wm e t h o dw h i c hu s ed i v i d ea n dc o n q u e rs t r a t e g yt oc o m p u t i n gx c u b e w e d i v i d et r e eb yt h ev a l u eo ft h ef i r s td i m e n s i o ni n t os u b - t r e e s f o re a c hs u b - t r e e ，w eo n l y g e n e r a t et h ef i n a lb r a n c ha n dd o n tc a l c u l a t et h ei n t e r m e d i a t er e s u l t s ，t h u sa v o i d i n gt h e m e r g e ro p e r a t i o no fc e r t a i nb r a n c h e si ni n t e r m e d i a t er e s u l t s t og e tt h er e m a i n i n gb r a n c h e s ， w ei n p u ta n dc a l c u l a t eo ns u b t r e em a n yt i m e s b e c a u s et h eo p e r a t i o nd o e sn o ti n v o l v e r e a d i n gf r o mt h eh a r dd r i v ea n dm e r g i n gt h eb r a n c h ，s ot h ec o m p u t a t i o no fx c u b ei s e f f i c i e n t b l o o mf i l t e ri sp r o p o s e db yb l o o mi n19 7 0 ，w h i c hu s e sh a s ht a b l et om a pe l e m e n ti n t oa c e l lo fa na r r a y w h e t h e rt h es e a r c h e de l e m e n ti si nas e tc a nb ec e r t a i nb y c h e c k i n gw h e t h e r t h ec o r r e s p o n d i n gc e l li ss e tt oo n eo rz e r o , t oi n c r e a s et h ea c c u r a c y , m u l t i p l eh a s hf u n c t i o n s c a nb eu s e di nb l o o mf i l t e r a f t e rr e s e a r c h i n go nr e l a t e ds e a r c ha l g o r i t h m s ，w ef o u n dt h a ta p o i n tq u e r yi nx c u b ei sam a t c h i n gp r o c e s sf r o mt h er o o tt oal e a fn o d ei nt h ep a t h a c c o r d i n gt ot h eb l o o mf i l t e r , w ep r o p o s ean e wq u e r ya n dc o m p r e s s i o na l g o r i t h mn a m e d b x c u b e t h ep a t hg e n e r a t e db yx c u b ef r o mt h er o o tt oal e a fn o d e 豳aw h o l ei sc a l c u l a t e d i ! i 山东建筑大学硕士学位论文 i nm u l t i p l e ( t w oo rt h r e e ) h a s hf u n c t i o n ，a n dp r o d u c i n gm u l t i p l eh a s hv a l u e w eo n l ys t o r et h e h a s hv a l u e s ，t h em e a s u r ea n dat a ga sab l o o mt u p l e c o m p a r i n gt os t o r et h ew h o l ep a t h , s t o r i n gt h eb l o o mt u p l ec a ns a v et h es t o r a g es p a c ea n dp r o v i d es o m ee x t e n ts e c u r i t yf o rt h e d a t a t h el o n g e rt h ep a t h ，t h em o r et h es p a c ew i l lb es a v e d w h e nd a t ai st o ol a r g et h eh a s h c o l l i s i o nw i l la p p e a ri n e v i t a b l e i no r d e rt oe l i m i n a t et h ew r o n gq u e r yr e s u l t sr a i s e db yt h e h a s hc o l l i s i o n ，w eu s e ad a t as t r u c t u r ec a l l e df i l t e rt a b l e i nc a l c u l a t i o np r o c e s s ，a l lp a t h so fa s u b - t r e ew i l lb eo p e r a t e da n ds o r t e di nf i l t e rt a b l e i ft h ea d j a c e n tb l o o mt u p l ew i t hs a m eh a s h v a l u e s ，b u td i f f e r e n tm e a s u r e ，t h e nh a s hc o l l i s i o nt a k ep l a c e w eu s e an e w h a s hf u n c t i o nt o r e h a s h w h e nt h eg e n e r a t e dh a s hv a l u e sc a nb ed i s t i n g u i s h e d ，t h eh a s hv a l u e , t h em e a s u r e a n dt h eh a s hf u n c t i o na r ep u ti n t oac o n f l i c tt a b l e o n ec o l l i s i o nt u p l e si sd e l e t e df r o mf i l t e r t a b l e ，t h eo t h e r st a gf i e l di s s e tt oas p e c i a lv a l u et oi n d i c a t eh o wt os o l v ec o l l i s i o n i f c o l l i s i o nt a k ep l a c ea m o n gt h r e eo rm o r et u p l u e s ，t h ep r o b a b i l i t yo ft h i sc a s ei sv e r ys m a l l ，w e e m p l o yp a t ht a b l et os e t t l ec o l l i s i o n w h e nf i n i s h e dc o l l i s i o nd e t e c t i o n ，t h et u p l e si nf i l t e r t a b l ea r ep u ti n t oq u e r yt a b l ei ns e q u e n c e t h ep o s i t i o no ft h ef i r s tt u p l ei nt h eq u e r yt a b l ei s p u ti n t oi n d e xt a b l e t oa n s w e raq u e r y , f i r s t l y , t h ev a l u eo ft h ef i r s td i m e n s i o ni su s e da sa k e y t os e a r c hi nt h ei n d e xt a b l et og e tar a n g ei nt h es e a r c ht a b l e , w h i c ht h ea n s w e rm a yl a y t h e n ，t h eq u e r yi sh a s h e dt og e n e r a t eah a s hv a l u e f i n a l l y , t h eh a s hv a l u ei s a sak e yt o l o c a t et h ea n s w e ri nt h es e a r c ht a b l eb yb i n a r ys e a r c h w ec o n d u c tas e r i e so fe x p e r i m e n t st o c o m p a r eb x c u b ew i t hd w a r f , w h i c he m p l o yt r e et or e p r e s e n td a t ac u b e t h ee x p e r i m e n t s h o w st h a tb x c u b eo u t p e r f o r md w a r fi ns t o r a g es p a c ea n dq u e r yt i m e k e yw o r d s ：o l a p ，d a t ac u b e ，x m l ，x c u b e i v 原创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立进行研究 取得的成果。除文中已经注明引用的内容外，论文中不含其他人已经发表或撰 写过的研究成果，也不包含为获得山东建筑大学或其他教育机构的学位证书而 使用过的材料。对本文的研究作出重要贡献的个人和集体，均已在文中以明确 方式标明。本人承担本声明的法律责任。 学位论文作者签名：莲害速日期塑1 9 ：! ：王 学位论文使用授权声明 本学位论文作者完全了解山东建筑大学有关保留、使用学位论文的规定， 即：山东建筑大学有权保留并向国家有关部门或机构送交学位论文的复印件和 磁盘，允许论文被查阅和借阅。本人授权山东建筑大学可以将学位论文的全部 或部分内容编入有关数据库进行检索，可以采用影印、缩印或其它手段保存、 汇编学位论文。 保密论文在解密后遵守此声明 学位论文作者签名： 导师签 名： 薛圭斌 日期兰幽，e 日期垫盟! ：2 山东建筑大学硕士学位论文 第一章绪论 1 1 课题背景 随着计算机在商业中的普及应用，在企业中积累了大量的内部和外部数据，如何从 这些数据中挖掘出有用的信息并进行预测分析成为技术人员和决策者关心的问题。为了 更好的管理和决策，许多企业选择数据仓库( d a t aw a r e h o u s e ) 作为决策支持系统 ( d e c i s i o ns u p p o r ts y s t e m ) 的核心。数据仓库概念的创始人w h i n i i l o n 在 1 中对数据仓库 的定义为：数据仓库是面向主题的、集成的、不可更新的( 稳定性) 、随时间不断变化( 不 同时间) 的数据集合，用以支持经营管理中的决策制定过程。利用数据仓库，对元数据 经过提取、转换、加载形成统一的数据格式后，再利用数据挖掘( d a t am i n i n g ) 和联机分 析( o n l i n e a n a l y t i c a lp r o c e s s i n g ) 分析工具为决策者提供所需的信息。 o l a p 已在很多领域得到了广泛深入的应用，成为现代商务智能的核心组成部件之 一。商务智能是软件行业中下一个利润丰厚的领域，得到了o r a c l e 、s a p 、m i c r o s o f t 和i b m 等软件巨头的重视。目前，联机分析处理软件的数据基本来自于关系数据库， 因为从上世纪7 0 年代末开始，关系数据库占据了主导位置，几十年来，企业大量的数 据都保存在关系数据库中。但自1 9 9 8 年x m l 面世后，由于其简洁性、自说明性以及 一系列标准的制定，x m l 引起了工业界和学术界的重视，应用面不断扩大，产生了大 量的x m l 文档。为了满足存储和查询x m l 文档的需要，数据库界研究了x m l 文档 的存储机制、查询优化和索引技术。目前，x m l 已经成为数据库系统中的标准数据类 型，很多商用系统( 如：i b md b 2v i p e r 、o r a c l e 9 i 、m i c r o s o f ts q ls e r v e r 2 0 0 5 ) 都以自 然的方式存储x m l 文档，使用s q l x m l 作为查询语言。 1 2 研究内容及意义 随着x m l 使用的日益增多，如何对其中的数据进行分析引起了研究工作者的关注。 文 1 提出可以通过直接对x m l 文档进行操作，从而避免先将x m l 中数据转换为元组， 再对元组进行计算的传统做法。在此基础上，文 2 中提出了一个对x m l 文档进行数 据立方体计算的算法- x c u b e 算法。但是，当输入数据量太多时，由于受内存限制，无 法完成计算；当把数据分批输入，计算产生中间结果后，需要再对这些结果的某些分支 进行合并，浪费了时间。 本文对x c u b e 算法进行了改进，提出一个“分批输入分次计算 的方法，当数据量 山东建筑大学硕士学位论文 太大时，通过这个方法避免了对某些分支进行合并的过程，使运算顺利完成，减少了运 算时间，提高了计算效率。 随着x m l 在数据交换领域使用的不断增多，在对其内容的查询方面研究者做了大 量的工作，提出了一系列的查询算法，如多谓词连接查询( m p m g j n ) 3 、基于缓存的 归并结构连接算法系列、t w i gp a t t e r n 等。同时w 3 c 提出了x q u e r y 查询语言。 本文采用b l o o mf i l t e r ( 布隆过滤器) 的思想，提出了一种新的x c u b e 存储和索引结 构：b x c u b e ( b l o o mx m l c u b e ) 。b l o o mf i l t e r 是1 9 7 0 年由b l o o m 提出的，它利用h a s h t a b l e ，通过h a s h 函数将元素映射成b i ta r r a y 中一个点。当检索时，只要查看相应点的 值是否为l 就可知这个元素是否在集合中，为了增加准确度，b l o o mf i l t e r 可以利用多 个h a s h 函数。在b x c u b e 算法中每次处理一棵子树，它把? ( c u b e 算法产生的每条路径 进行h a s h ，只存储h a s h 值，从而使存储空间得到压缩。b x c u b e 采用了顺序存储结构， 我们根据其特点添加了索引表结构，用于存储每棵子树产生的b l o o m 元组在查询表中 的位置。在查询过程中，通过索引表使查询的范围缩小，并在查询范围内通过折半查找， 进一步提高查询效率。 综上所述，本文通过对x c u b e 算法进行改进，在运算过程中按照“分批输入分次计 算 的思想，使x c u b e 算法能对大规模数据顺利完成计算。同时按照b l o o mf i l t e r 的思 想，提出了一种新的x c u b e 存储和索引结构：b x c u b e ，把产生的每条路径进行h a s h ， 存储产生的h a s h 值，从而对机密数据提供了一定的安全保障，压缩了存储空间。当查 询时，把整条路径作为一个整体进行h a s h ，按其值进行查询，通过相应的索引结构和折 半查找方法，提高了查询响应时间。 1 3 论文组织结构 论文主要研究x c u h e 计算和查询方法，共分为五章： 第一章为绪论，主要介绍了课题背景、研究内容和意义以及论文的组织结构。 第二章简要介绍了联机分析、数据立方体、x m l 和x o l a p 相关知识。 第三章给出了? ( c u b e 算法、b x c u b e 算法，并用一个简单的例子进行了阐述。 第四章对x c u b e 算法和b x c u b e 算法进行了实验验证，并将其与相关算法进行了比 较和分析。 第五章对本文的研究工作进行了总结并对下一步的工作进行了展望。 山东建筑大学硕士学位论文 第二章联机分析和x m l 2 1 联机分析 关系数据库之父e e c o d d 在1 9 9 3 年提出了联机分析( o l a p ) 的概念，o l a p 是使管 理人员、执行人员或分析人员能够从多角度对信息进行一致、快速、交互地存取，从而 能够对数据进行更深入了解的一类软件技术，其技术核心是”维”。“维一般包含着层 次关系，通过把一个实体的多项重要的属性定义为多个维( d i m e n s i o n ) ，使用户能对不 同维上的数据进行比较。所以o l a p 也可以说是多维数据分析工具的集合。 2 1 1 基本概念 o l a p 最基本的概念有三个：多维观察、数据分析和c u b e 运算。 ( 1 ) 多维观察 平时遇到问题后分析问题时对于同样的现象，会从不同角度去分析考虑，有时候还 会几个角度综合进行分析。这就是o l a p 分析最基本的概念：从多个观察角度灵活组合 来观察数据，从而发现数据内在规律。 o l a p 将数据分为两种特征，一种为表现特征，比如一个销售分析模型中的销售额 等；还有一种为角度特征，比如销售分析中的客户、销售渠道、产品数量、销售时间等。 前者是被观察的对象，o l a p 术语称之为“度量数据”，后者为观察视角，o l a p 术语 称之为“维数据”。 ( 2 ) 数据分析 在分析过程中可能需要在现有数据基础上，将数据进一步细化，以获得更为精确的 认识。比如，在销售分析中，当以产品类型和销售地区为维、以销售额为度量进行分析 的时候，可能希望进一步观察某类产品的不同销售模式在各个销售地区的表现，这时就 可以在产品大类这个数据维下面，再加上一个销售模式维，从而获得相应的信息。o l a p 的基本多维分析操作有钻取( r o l lu p 和d r i l ld o w n ) 、切片( s l i c e ) 和切块( d i c e ) 、以 及旋转( p i v o t ) 等。钻取是改变维的层次，变换分析的粒度。它包括向上钻取( r o l lu p ) 和向下钻取( d r i l ld o w n ) 。向上钻取是在某一维上将低层次的细节数据概括到高层次的 汇总数据，或者减少维数：而d r i l ld o w n 则相反，它从汇总数据深入到细节数据进行观 察或增加新维。切片和切块是在一部分维上选定值后，关心度量数据在其它维上的分布。 旋转是变换维的方向，即在表格中重新安排维的放置( 例如行列互换) 。 山东建筑大学硕士学位论文 ( 3 ) 创建数据立方体( d a t ac u b e ) o l a p 分析时所需的原始数据量非常庞大。一个分析模型，往往会涉及数千万条、 甚至更多；并且分析模型中有多个维数据，这些维又可以作任意的提取组合。其结果就 是大量的实时运算导致的时间延滞。针对这种情况，就需要o l a p 中一个非常重要的技 术：数据立方体预运算。 2 1 2 分类方法 o l a p 比较流行的划分方法是按照存储结构划分，有三类：m o l a p ( m u l t i d i m e n s i o n o l a p ) ，r o l a p ( r e l a t i o no l a p ) 和h o l a p ( h y b r i do l a p ) 。 ( 1 ) m o l a p m o l a p 使用多维数组存储多维数据，由于多维数组的特点，可以实现对多维数据 的快速访问。在实际应用中，维值的很多组合是空值或零值。因此，m o l a p 必须具有 高效的稀疏数据处理能力，能略过零元、缺失和重复数据。 ( 2 ) r o l a p r o l a p 将多维数据存储在关系数据库中，由关系数据库管理系统负责管理，多维 查询语言翻译、多维计算、元数据管理由o l a p 服务器负责。由于采取关系数据库存储 数据，可以有效的处理海量数据，但对于多维数据的处理涉及到大量费时的连接运算， 查询速度较慢，必须采用预计算和索引技术加以克服。 ( 3 ) h o l a p m o l a p 采用多维数据结构存储多维数据，综合数据计算较快，但是，在高维时， 必须有效的解决数据稀疏的问题。r o l a p 使用关系数据库管理多维数据，可以处理海 量数据，灵活性好，需要一些特殊技术才能保证较快的查询相应时间。由于联机分析一 般是对综合数据进行分析的多，而访问细节数据的概率比较少，因此，出现了一种折中 的实现方法h o l a p 。它把细节数据存储在关系数据库中，把综合数据存放在多维数组 中，发挥了关系数据库处理海量数据的能力和多维数组查询计算快的特点，具有更好的 灵活性。 2 2 数据立方体 o l a p 查询需要对大量数据进行聚集运算，运算时间较长。为了提高查询响应时间， j i mg r a y 4 提出了d a t ac u b e ，其基本思想是离线计算出全部的可能聚集查询，从而提 高查询的响应速度。由于d a t ac u b e 的重要性，人们提出了很多计算方法和存储结构， 如，b e y e r 5 中的b u c 算法，在此算法中先通过计算一个维上的g r o u p - b y 然后再计算 山东建筑大学硕士学位论文 两个维上，在此基础上构建c u b e ；冯建华 6 提出的多维存储结构，这个存储结构 以多维数组为基础，同时结合关系存储优点来存储组织数据仓库中的数据。在用多维数 组进行存储时，考虑到数据偏斜对数组的影响，它在逻辑划分的基础上，又进行了物理 划分，即将逻辑划分得到的子多维数据集合进行划分，得到若干大小固定的物理块，从 而同时进一步提高了磁盘i o 效率。随着研究的深入，人们发现d a t ac u b e 中存在很多 冗余数据，于是提出了c o n d e n s e dc u b e 【7 】、q u o t i e n tc u b e 8 、封闭数据立方体 9 、 d w a r t l l o 】。c o n d e n s e dc u b e 7 】中提出了一个b s t 的概念，即在对关系中的元组在某些 属性上进行划分时，当划分结果中只包含一个元组时，该元组就称为在当前划分下的基 本唯一元组( b a s es i n g l e t u p l e ) ，同时因为某些元组可以是多个划分的b s t 于是提出了 一个s d s e t 的概念。基于以上两个概念c o n d e n s e dc u b e 在建立时对于b s t 只存储基 本元组和s d s e t 从而大大减小了c u b e 大小。q u o t i e n tc u b e 8 采用关系作为存储结构， 在保持r o l lu p d r i l ld o w n 语义的前提下，把所有具有相同聚集的元组找出来放在同一个 类中，从而形成c u b e 。而d w a r i 1 0 ，则是一个采用链表结构的c u b e ，通过前缀和后 缀共享，大大减少了c u b e 的体积，同时又十分巧妙的保持了c u b e 中原有的元组。d w a r f 的计算过程是将事实表中的记录不断插入到一棵前缀树并进行后缀结合的过程。为了解 决此类c u b e 的查询效率问题，l a k s h m a n a n y 11 提出了q c t r e e ，首先在关系数据上采 用b u c 算法计算出所有的等价类，然后将等价类表示成树，再加以辅助的查询路径， 在此基础上提出了高效的查询算法。显然，q c t r e e 可以采用x m l 文档作为存储，树 中节点之间的父子关系用x m l 的元素子元素表示，辅助查询路径使用i d i d r e f 或者 x l i z l l ( 机制表示。 3 4 图2 1q c - t r e e s 【1 1 】 山东建筑大学硕士学位论文 王晓玲和董逸生 1 2 提出了一种用x m l 表示c l a p 数据的方法。李睿 1 3 利用文 7 提出的基本元组的概念，给出了用x m l 表示和计算c o n d e n s e dc u b e 的方法。 2 3x m l x m l 1 4 是从1 9 9 6 年开始有其雏形，并向w 3 c ( 全球信息网联盟) 提案，在1 9 9 8 年二月发布为w 3 c 的标准( x m l l o ) 。x m l 的前身是s g m l ( 1 1 1 es t a n d a r dg e n e r a l i z e d m a r k u pl a n g u a g e ) 1 5 ，是i b m 从6 0 年代就开始发展的g m l ( g e n e r a l i z e dm a r k u p l a n g u a g e ) 标准化后的名称。 1 9 7 8 年，a n s i 将g m l 整理规范，发布了s g m l ，1 9 8 6 年被i s o 所采用( i s o8 8 7 9 ) ， 并广泛地运用在各种大型文件计划中，但s g m l 是一种非常严谨的文件描述法，致使 其过于庞大复杂( 标准手册就有5 0 0 多页) ，难以被理解和学习，进而影响其推广与应 用。 为了解决以上问题，专家们使用s g m l 精简制作，并参照h t m l 的发展经验，发 展出一套使用上规则严谨，但是简单的描述数据语言：x m l 。 与w e b 上已有的最普遍的数据表现形式h t m l 相比，x m l 具有如下的一些特点： ( 1 ) 更多的结构和语义。x m l 侧重于对文档内容的描述，而不是文档的显示。用户自定 义的标签描述了数据的语义，便于对数据的理解和机器的自动处理。 ( 2 ) 可扩展性。x m l 允许用户自己定义标签和属性，可以有各种定制的数据格式。 ( 3 ) 简单易用。与通用标签语言s g m l 相比，x m l 简单易用，便于掌握，这是它得以 推广的重要原因。 ( 4 ) 自描述性。x m l 将对数据的语义描述和数据内容本身都包含在x m l 文档中，使数 据具有很大的灵活性。 ( 5 ) 数据与显示分离。x m l 所关心的是数据本身的语义，而不是数据的显示方式，所以 可以在同样的x m l 数据上定义多种显示形式，非常灵活。 x m l 的这些特点使得它不但迅速成为了网络数据交换的事实标准，而且正在逐渐 成为数据表示的标准。随着x m l 的流行，一系列相关的标准( 如x m ls c h e m a 1 6 ， x q u e r y 1 7 ，x m ld a t am o d e l 1 8 等) 也不断出现，形成了围绕x m l 的标准集合， 这反映了工业界对x m l 的巨大支持。随着x m l 应用面的不断扩展，产生了大量的x m l 文档，直接对x m l 文档进行查询处理显得日益突出。 2 3 1x m l 模型 不同的x m l 文档在内容和结构上千差万别，为了能按照统一的方式操纵所有的 山东建筑大学硕士学位论文 x m l 文档，x m l 文档被抽象为一棵树。x m l 文档中的元素、属性、文本、注释、处 理指令和命名空间作为树中的节点，元素之间的嵌套关系在树中用节点之间的父子关 系和祖先后裔关系表示。另外，树中有个特殊的节点叫做根节点，它是树中所有节 点的祖先，文档中的根元素不是树的根节点，而是根节点的孩子节点。对于树模型要注 意以下几点： ( 1 ) 树是有序树，节点之间的父子关系、兄弟关系必须同它们在文档中的次序一致， 采用深度优先对树进行遍历，可以得到原始的文档。 ( 2 ) 根据树的术语，如果节点p 是节点c 的父亲，则节点c 一定是节点p 的孩子节点。 但是，x m l 的树模型有一点例外，即，如果c 的节点类型是属性，则c 不是父亲节点 的孩子节点。 ( 3 ) 文档中元素的开始标签和结束标签之间的文本在书中用一个节点表示，并作为元 素的孩子节点。但是，却不为属性的值建立节点，属性的值作为属性节点的一部分被保 存。 ( 4 ) 每种节点类型是一个类，有若干个属性和方法，节点是节点类型的实例。 ( 5 ) 各节点通过i d i d r e f 或者x l i n k 机制使其成为一个有向无环图( d a g ) 。 2 3 2 路径表达式 x p a t h 1 9 路径表达式有以下两种形式： l o c a t i o n s t e p l l o c a t i o n s t e p 2 ( 1 ) l o c a t i o n s t e p l l o c a t i o n s t e p 2 ( 2 ) 形式( 1 ) 为绝对路径表达式，表示从树模型的根节点开始，如何走到目标节点。形 式( 2 ) 为相对路径表达式，表示从当前节点( 又叫做上下文节点) 如何走到目标节点。 x p a t h 定义了1 3 个轴。如表2 1 所示。 表2 1x p a t h 定义的13 个轴 轴名称结果 s e l f选取当前节点。 c h i l d选取当前节点的所有子元素。 a t t r i b u t e 选取当前节点的所有属性。 n a m e s p a c e 取当前节点的所有命名空问节点。 d e s c e n d a n t选取当前节点的所有后代元素( 子、孙等) 。 f o l l o w i n g 选取文档中当前节点的结束标签之后的所有节点。 山东建筑大学硕士学位论文 d e s c e n d a n t - o r - s e l f选取当前节点的所有后代元素( 子、孙等) 以及当前节点本身。 a n c e s t o r - o r - s e l f选取当前节点的所有先辈( 父、祖父等) 以及当前节点本身选。 p r e c e d i n g 选取文档中当前节点的开始标签之前的所有节点。 p a r e n t 选取当前节点的父节点。 p r e c e d i n g - s i b l i n g 选取当前节点之前的所有同级节点。 a n c e s t o r 选取当前节点的所有先辈( 父、祖父等) 。 n o d e s e l e c t o r 可以是节点名称，节点类型或者是通配符木。 s e l e c t i o n c o n d i t i o n 是一个选择条件，对由定位步所确定的节点集合作进一步的筛 选。 路径表达式语义为： 从当前节点出发，找出所有l o c a t i o n s t e p l 到达的节点，对于其中每个节点n ，找出 所有从n 出发，经过l o c a t i o n s t e p 2 到达的节点，然后将所有经过l o c a t i o n s t e p 2 到达的 节点合并，再对合并后的每个节点，应用l o c a t i o n s t e p 3 直到最后一个步骤，最后一 步得到的节点集合就是路径表达式的结果。 典型的表达式有下面两种： 简单路径表达式：a b c ( i a b c ) 、i a i b i c ( i i a i b i i c ) 分支路径表达式：a 路径表达式 b 其中，元素名可以出现通配符牢 对路径表达式求解的方法根据定位轴的不同有自项向下、自底向上或者二者结合的 方法。 2 3 3 查询算法 ( 1 ) 多谓词连接查询( m p m g j n ) 为了有效的回答形如a 8 或者a b 的查询，c 。z h a n g 和j n a u g h t o n 等提出 了一种有效的计算包含关系的查询算法m p m g j n 2 ( m u l t i p r e d i c a t em e r g ej o i n ) 。其基本 思想是：设参加连接的两个关系表为a l i s t 和d l i s t ，对外表a l i s t 中的第一个元组a l ， 首先在内表d l i s t 中顺序搜索到可能与a i 进行连接的第一个元组( 即b e g i n a 1 b e g i n 的 第一个元组) ，称为扫描始点( s c a ns t a r tp o i n t ) ，然后在内表d l i s t