《XML数据的存储、索引和查询优化技术及其性能评价》由会员分享，可在线阅读，更多相关《XML数据的存储、索引和查询优化技术及其性能评价（4页珍藏版）》请在金锄头文库上搜索。
1、计算机科学2 0 0 2 V 0 1 2 9 N O - 8X M L 数据的存储、索引和查询优化技术及其性能评价S t o r a g e ，I n d e x i n g ，Q u e r yO p t i m i z a t i o nT e c h n i q u e sf o rX M LD a t aa n dP e r f o r m a n c eE v a l u a t i o n s吕建华王国仁于戈( 东北大学信息学院软件研究所沈阳1 1 0 0 0 4 )* )A b s t r a c tX M Ld o c u m e n t sc a nb es t o r e
2、da n da c c e s s e dt h r o u g hD O Mi n t e r f a c e sa n dX M Lq u e r i e sc a r lb ee v a l u a t e db a s e dO F tD O M I nt h i sp a p e r ，ap e r s i s t e n tD O Ms t o r a g em e t h o di sd e s i g n e dw i t ht w ok i n d so fc l u s t e r i n gs t r a t e g i e s ，f i l i a t i o n c
3、l u s t e r i n ga n ds i b l i n g c l u s t e r i n gt Oi m p r o v e D O Mi n t e r f a c e - b a s e dq u e r yp e r f o r m a n c e An e wp a t hc o m p u t i n ga p p r o a c hn a m e de x t e n tj o i ni sp r o p o s e di nt h i sp a p e r ，a n ds e v e r a li n d e xs t r u c t u r e sa r ea
4、 l s op r o p o s e dt Os u p p o r ti t ，i n c l u d i n gf o u r s t r u c t u r a li n d e x e sa n dt w ov a l u ei n d e x e s M o r e o v e r ，s o m ep a t he x p r e s s i o no p t i m i z a t i o nr u l e sa r ep r o p o s e db yu s i n gt h ep a t h s h o r t e na n dp a t h c o m p l e m e
5、 n t i n gp r i n c i p l e s P a t h s h o r t e nr e d u c e st h en u m b e ro fj o i n sb ys h o r t e n i n gt h ep a t ha n dp a t h - c o m p l e m e n t i n gi sat e c h n i q u et ou s ead i f f e r e n tp a t he x p r e s s i o nt Os u b s t i t u t et h ep a t hs p e c i f i e di nau s e
6、rq u e r y K e y w o r d sX M Ld a t a ，S t o r a g e ，I n d e x i n g ，Q u e r yo p t i m i z a t i o n ，P e r f o r m a c ee v a l u a t i o n1 。引言X M L ( e X t e n d e dM a r k u pL a n g u a g e ) 语言是W 3 C 组织提出的一个I n t e r n e t 上数据表示和数据交换的新标准。随着网络应用技术的飞速发展，X M L 由予自身的特点正在成为被众人所接受的描述和传递网络信息的工具。针
7、对X M L 数据的存储、索引和查询技术现在变得越来越重要并且日渐成为数据库界的研究热点 1 3 j 。在本文中，我们将介绍一些新的X M L 数据存储方案、索引结构以及路径表达式查询的优化策略。它们都是在一个X M L 文档数据库系统X B a s e t 4 上实现的。X B a s e 使用文档对象模型( D O M ) 作为存储模型，并且采用X Q u e r y s 3 作为查询语言。本文的主要贡献如下：基于一个可持久化的D O M 存储模型，提出了两种不同的聚类存储方案。我们设计了一个新颖的R P E 查询算法外延连接法( E x t e n tJ o i n ) 来计算X M L
8、 查询中的路径表达式。这个算法需要得到一些索引的支持。本文设计了四个结构化索引以及两个值索引来支持外延连接算法。根据外延连接法的特性，我们提出了两个路径表达式优化规则。进行了最后基于两个模拟测试集和两个实际数据集性能测试。2 物理存储的聚类方法文档对象模型( D o c u m e n tO b j e c tM o d e l D O M 是一个X M L 和H T M L 文档的应用编程接口，它定义了X M L 文档的逻辑结构以及访问和操作X M L 文档的方式。然而实际上，D O M 可以被视作一个存储模型，也就是说X M L 文档可以在物理 上被存储成为一棵D O M 树。在D O M
9、 树上有两类基本操作，一类是根据父子关系遍历子树，另一类是访问当前节点的兄弟节点。为了加快这两类基本操作的速度，我们设计了两种聚类存储算法：父子聚类( F C ) 和兄弟聚类( S C ) 。父子聚类方法就是把两个具有父子关系的元素属性尽可能地存储到一个物理页面上去；与父子聚类相似，兄弟聚类是把两个具有兄弟关系的元素属性尽可能地存储到一个物理页面E 去。5 外延连接与索引技术3 1 相关概念为了更好地介绍索引技术的细节，下面先给出一些基本概念。图1 所示为一个X M L 文档的D T D( D o c u m e n tT y p eD e f i n i t i o n ) 图型结构，它是测
10、试集* ) 本文得到教育部高等学校优秀青年教师教学和科研奖励基金，教育部高等学校骨干教师资助计划资助。吕建华博士研究方向为X M L数据库。X M a r k 使用的D T D 的一个片断。图1X M a r k 的D T Da n n o t a t i o nd e s c r i p i o n图2 一个D O M 数据树例子定义1 ( 祖孙对)对于一个祖孙对a d p a i r ( a i d ，d i d ) ，在a i d 和d i d 之间存在一个祖先后代关系，即a i d 是d i d 的祖先，例如a d p a i r ( 1 ，& 3 ) 就表明& 1是& 3 的一个祖先
11、。祖孙对的一个特殊情况是父子对( p c p a i r ( p i d ，c i d ) ) ，父子对中的两个元素之间存在的是一个父子关系而不仅仅是祖孙关系，例如p c p a i r ( & 1 ，8 L 2 ) 。另外，我们假设在元素和它的属性之间存在着一个父子关系。 定义2 ( X M L 外延( X M Le x t e n t ) )类似对象数据库中对象外延的概念，我们定义了X M L 外延来表示a d p a i r 的集合，写作E x t ( a n ，d n ) 。E x t ( a n y ，E l e m e n t N a m e ) 可定义为 p c p a i r
12、( p i d ，i d ) I i di sa ni n s t a n c eo fE l e m e n t N a m e ) 。通常情况下，E x t ( p n ，c n ) 互E x t ( a n y ，c n ) 这个 关系总是成立的。即如果在D T D 中元素C 可以有 两个父亲A 和B ，那么E x t ( a n y ，C ) = E x t ( A ，C ) UE x t ( B ，C ) 。定义5 ( 过滤器( F i l t e r ) )F i l t e r ( S e t ，P r e d i c a t e ) 一 a d p a i r ( a i d
13、，d i d ) la d p a i r ( a i d ，d i d ) S e t A P r e d i c a t e ( a d p a i r ( a i d ，d i d ) ) 。5 2 外延连接( E x t e n tJ o i n ) 法路径表达式的通常计算方法是由顶向下( T o p d o w n ) 、由底向上( B o t t o m u p ) 和网格策略( H y b r i d ) ，其中B o t t o m - u p 和H y b r i d 方法需要值索引( V a l u eI n d e x ) 和标签索引( L a b e lI n d e
14、x ) 的支持。R 外延连接法的主要思想就是将一个路径表达式分割成若干个原子路径片断( A t o m i cp a t hf r a g m e n t ) ，即路径表达式的一个单步导航操作。每个路径片段可以被视作一个子查询，查询的结果就是对应的外延或者经过谓词过滤的外延片断。最后的查询结果通过这些中间结果之间的一个基于父子关系的多路连接操作( M u l t i w a yJ o i n ) 得到。由于D O M 接口不支持针对元素名字取得相应的外延的操作，因此需要一些特殊的索引结构来支持外延连接算法。下面将分别介绍这些索引结构。5 5 结构索引为了支持外延连接算法，我们提出了四种结构索引
15、：父子元素索引( P C X ) 、元素属性索引( E A X ) 、引用索引( R X ) 和路径索引( P X ) 。这些索引或者可以代替或者可以补充D O M 接口提供的功能。 给定一个元素名字C n a m e 和它的一个父元素 名字P n a m e ，父子元素索引用来索引集合E x t( P n a m e ，C n a m e ) 。这个索引可以更快地实现D O M接口：E l e m e n t ：g e t E l e m e n t B y T a g N a m eti nD O M S t r i n gn a m e ) 提供的功能。元素属性索引( E A X ) 用
16、 来索引E x t ( T N a m e ，A n a m e ) 。它可以完成D O M 接口E l e m e n t ：g e t A t t r i b u t et i nD O M S t r i n gn a m e ) 的 部分功能。引用索引( R X ) 的功能是描述X M L 元素实例之间的引用关系。而路径索引【P X ) 则用来索引一个路径表达式的结果以节省计算代价。5 4 值索引由于路径表达式中谓词可以是基于元素值的，也可以是基于属性值的，因此值索引相应地也分为两种：元素值索引( E V X ) 和属性值索引( A V X ) 。它们都是用来辅助计算含有谓词的路径表达式查询的工具。 元素值索引E V X ( E l e m e n t N a m e ，P r e d O n E l e m V a l ) 可以用来索引F i l t e r 【E x t ( a n y ，E l e m e n t N a m e ) ，P r e d O
