（计算机软件与理论专业论文）集合索引结构及其在XML查询中的应用.pdf

集合索引结构及其在x m l 查询中的心用 摘要 集合类型是一种很常见的数据类型，现实t h = 界中的很多关系均可以用集合类型描述，为 此数据库界一直在研究这种关系的存储和表示方法，在关系数据库模式设计中将其作为嵌套 关系进行处理或将其分解成多个关系进行存储，面向对象数据库系统和对象关系数据库系统 出现以后，集合类型被直接加入到数据模型和查询语言中。由于集合类型结构同原子类型有 很大的著别，原来的查询和索引技术对集合类型数据都不适用了，而目前还没有成熟的索引 结构，所以目前在数据库应用中很少使用集合类型。 另外，x m l 已经成为i n t c r n e t 上描述数据的主要标准。由于x m l 保存了大量有用数据 对x m l 的查询显得愈加重要。为了提高x m l 查询的性能，使用关系数据库来存储和查询 x m l 数据，理由是关系数据库经过2 0 多年的发展，其技术已经相当成熟。x m l 中的多值 元素可以看作集合。为了避免数据冗余，关系数据库需要单独的关系表存储这些多值元素， 并通过外键与存储其祖先的关系表关联起来。于是为了查询某个多值元素是否包含了某个 集合首先需要把存储该元素的关系表白身作联接，才能与集合进行比较并得到结果。集合 的基数越大，所需联接的次数也越多。而联接是关系数据库中代价最高的操作。因此关系 数据库不能保证具有集合包含语义的x m l 查询的高效性。 本文提出了集合类型数据的一种索引结构：s e t _ t r e e ，s e t _ t r e e 通过合并集合数据的公 共前缀组织数据，这种方法可以减少重复数据和重复模式的存储空间，第三章介绍的基于 s e tt r e e 的集合联接算法提高了集合数据上的联接操作的性能。在第四章，我们把s e t _ t r e e 应用到x m l 查询系统中，针对关系数据库存储x m l 中的集合元素时，将月= 有集合包含语 义的x m l 查询转换成若系数据库上的查询需要做联接查询效率不高的问题，提出了一种 新的解决方案，即将x m l 查询分解成非集合包含语义和集合包含语义两部分，井由关系数 据库查询引擎和集合包含算法分别执行，最后将两部分的结果加以综合。 关键字：集合索引；s e t _ t r e e ；联接操作； 塞鱼鲞! ! 堕塑墨基垄兰些奎塑! 堕堕旦 a b s t r a c t s e t v a l u e dd a t ai sav e r yp o p u l a r c o n c e p tt om o d e le n t i t i e si nt h er e a lw o r l d f o r e x a m p l e ，t h e r ei sas e to fk e y w o r d sf o re a c hp a p e rp u b l i s h e di nj o u r n a l ；t h e r ea r ea s e to fc h i l d r e nf o re a c hf a m i l y s oi ti sa ni m p o r t a n td a t at y p ei nd a t a b a s em a n a g e m e n t s y s t e m t h es e m a n t i co fq u e r yo ns e ti ss t u d i e di no b j e c t _ o r i e n t e dd a t a b a s e b u tt h e r e i ss t i l ln oe f f i c i e n ti n d e xs c h e m at om a n a g ei ta n dh e l pt oi m p r o v et h ep e r f o r m a n c eo f q u e r yo p e r a t i o n s ， o nt h eo t h e rh a n d ，t h er i s eo fx m la sa ni m p o r t a n td a t as t a n d a r di n c r e a s e st h e n e e df o rs e t v a l u e da t t r i b u t e s ，s i n c ei ta p p e a r st h a ts e t - v a l u e da t t r i b u t e sa r ek e yi nt h e n a t u r a lr e p r e s e n t a t i o no fx m ld a t ai nr e l a t i o n a ls y s t e m s i no r d e rt oi n c r e a s et h e p e r f o r m a n c eo fe v a l u a t i n gx m lq u e r i e s ，x m ld a t aa r eu s u a l l ys t o r e di nr d b m sa n d r e t r i e v e db ys q l ，b e c a u s et h et e c h n i q u e so fr d b m sa r ev e r yw e l lt h r o u g h o u tt w e n t y y e a r sd e v e l o p m e n t m u l t i v a l u e de l e m e n t si nx m ld o c u m e n tc a nb es e e n a s s e t - v a l u e da t t r i b u t e s t h o s eo p e r a t i o n so ns e t v a l u e da t t r i b u t e ss u c ha st h es e t c o n t a i n m e n tj o i na r ei m p o r t a n tf o re v a l u a t i n gx m l q u e r i e s ， t h i sp a p e r p r e s e n t sa ni n d e xs t r u c t u r eo ns e tt y p e ：s e t _ t r e e i ns e t t r e ea 1 1s e t sa r e o r g a n i z e da sat r e e ，a n dt h es e t sw i t hc o m m o np r e f i xa r em e r g e d s ot h es i z eo f t h e i n d e xw i l lb ed e c r e a s e df o rt h ed a t as e tw i ml a r g en u m b e ro f r e p e a t e dd a t aa n d f r e q u e n tp a t t e m s b a s e do ns e tt r e e ，t h i sp a p e rp r e s e n t sa na l g o r i t h mo nj o i n o p e r a t i o nw h i c hg e t sb e t t e rp e r f o r m a n c et h a no t h e rm e t h o ds u c ha sp s j i nc h a p t e r4 ， w ep r e s e n tan e wr e s o l u t i o nt oh a n d l ex m l q u e r i e sw h i c h a r ed i v i d e di n t ot w o p a r t s ： x m l q u e r i e sw i t hs e tc o n t a i n m e n ts e m a n t i ca n do t h e r s t h ep e r f o r m a n c e so f e v a l u a t i n gx m lq u e r i e sw i t hs e tc o n t a i n m e n ts e m a n t i ca r ei n c r e a s e db yu s i n g a n a l g o r i t h mo n j o i no p e r a t i o np r e s e n t e di nt h i sp a p e r k e yw o r d s ：i n d e xo fs e t ；s e tt r e e ；j o i no p e r a t i o n 4 集合索引结构及其在x m l 查询中的应用 1 1 研究背景 第一章引言 集合类型是一种很常见的数据类型，现实世界中的很多关系均可以用集合类 型描述，如一对父母有若干个孩子，一篇文章有若干个关键词等。同时实体建模 中的很多关系也是用集合类型描述的，如实体问p a r t - o f 的关系等。为此数据库 界一直在研究这种关系的存储和表示方法，在关系数据库模式设计中将其作为嵌 套关系进行处理或将其分解成多个关系进行存储，面向对象数据库系统和对 象- 关系数据库系统出现以后，集合类型被直接加入到数据模型和查询语言中 【2 ，3 ，4 ，并在这方面进行了比较深入的研究。由于集合类型结构同原子类型有很 大的差别，原来基于原子类型的查询和索引技术对集合类型的数据都不适用了， 目前还没有成熟的、用于提高集合类型数据查询性能的索引结构。所以目前在数 据库应用中很少使用集合类型。 另外，x m l 已经成为i n t e r n e t 上描述数据的主要标准。由于x m l 保存了大 量有用数据，对x m l 的查询显得愈加重要。为了提高x m l 查询的性能， 5 ，6 中提出了使用关系数据库来存储和查询x m l 数据，因为关系数据库经过2 0 多年 的发展，其技术已经相当成熟。 x m l 中的多值元素可以看作集合。如 5 所述，为了避免数据冗余，关系数 据库需要单独的关系表存储这些多值元素，并通过外键与存储其祖先的关系表关 联起来。于是，为了查询某个多值元素是否包含了某个集合s ，首先需要把存储 该元素的关系表白身作联接，爿。能与集合s 进行比较并得到结果。集合s 的基 数越大，所需联接的次数也越多。而联接是关系数据库中代价最高的操作。因此， 关系数据库不能保证具有集合包含语义的x m l 查询的商效性。 集合数据上的联接操作主要包括两种： 一种是相交联接，对两个关系r 和s ，和分属于两个关系的列a 和b ，其联 接条件为。r af 3s b 中。例如在查找文章间的关系时，经常用关键词集间的相 交关系来判断两篇文章的相似程度。 另一种是包含联接，其联接条件为。r a _ c s b 。例如在生物数据库中在进行 冗余数据的清理时需要找到功能有包含关系的基因。 同常规数据的联接操作相同。在集合数据中连接操作的计算量也是非常大 的。 本文针对集合数据提出一种集合数据索引结构：s e t t r e e ，它利用集合数据 集合索引结构及其和x m l 查询中的应用 中的结构信息和集合数据的次序信息建立一棵树型结构，同时还包括一条反向链 表。接着本文基于s e t t r e e 提出了集合数据连接操作的实现算法。它具有较高的 执行效率。并且将这个联接算法应用到x m l 查询处理，来提高具有集合包含语 义的x m l 查询的效率。 1 2 预备知识 下面我们将解释基本的概念和术语。 1 2 1 数据库的描述 假设一个数据库包含了有限个数据项o ，其中l i r t 。我们只考虑包含集 合属性4 的数据项。o i a 表示数据项o ，的集合属性a 的值。不失一般性，我们假 设数据库中的所有数据项都有集合属性爿，共有r 1 个数据项。集合属性一定义在 域d 翻j 中，也就是说，集合的任意元素都属于d ，d 。4 d 妙。假设一个数 据库，包含学生，教师，课程。学生可以选修不同主题的多个课程，每一个学生 已选修的课程可以用一个集合属性来保存。同样，每一个教师教授的课程也可 一个集合属性来保存。一般来讲，所有实体间一对多( 或者多对多) 的关系都可 以用一个( 两个) 集合来表示。 1 2 2 集合查询 一个查询的定义包括查询集合q 和谓词0 ，0 包含集合属性a 的域d 似j 中 的任意一个元素。正式地说，q 是d 例的幂集的一个元素，假设p p 以砂是d 妙 的幂集，则q 尸r d 圳。给定两个集合m 和，一个谓词0 表示m 和j v 之间 的关系，由m o n 定义。现在我们看下面的谓词： 0 = “= ”：如果m 刚好包含中的所有元素，那么m = n 成立。这 个称作相等谓词。 0 = 匕”：如果肘中的所有元素可以在中找到，那么m n 成立 这个称作子集查询谓词。 口= 一3 ”：如果n 中的所有元素可以在m 中找到，那么m 三n 成立。 这个称作超集查询谓词。 0 ：t n ”：如果m * un 至少有一个共同的元素，这个元素属于d 以j ， 那么m n ( ) 成立。这个称作交集查询谓词。 6 集合索引结构及其往x m l 查询中的应用 一个完整的查询，包含查询集合q 和谓词臼( = ，2 ，n ) ，查询满足下 面谓词的所有数据项0 f ( 1 i n ) ： 1 o o t a 2 q 互。一a 3 q 2 0 1 a 4 q n o j 一( 庐) 查询其集合属性a 包含一个d 例中的元素e 的所有数据项，这是情况2 的一个 特殊情况。可以写成一个查询a = e ) ，0 = ”掣，也就是，e o i as 纠o i a 。 对于上面定义的几种查询类型，我们给出在1 2 1 节提到的数据库上的查询 例子。 1 查询只教授“d a t a b a s es y s t e m s ，”和“o p e r a t i n gs y s t e m si ”两门课程 的教师( q = “d a t a b a s es y s t e m s1 ”，“o p e r a t i n gs y s t e m s1 ”) ，02 “一) s e l e c tf n a m e f r o m ，i na l l l e c t u m r s w h e m1 g i v e s = s e t ( “d a t a b a s es y s t e m si ”“o p e r a t i n gs y s t e m si ”) ： 2 假定如果要选“m a t h 肼”，必须先修完“m a t h1 ”和“m a t h ”两门课 程。现在查询能够选修“m a t h 肌”的学生。( q ： “m a t h ，”，“m a t hh ”j ， 0 = “”) s e l e c t n a m e p o msi na l l s t u d e n t s w h e r es e t ( “m a t h1 ”，“m a t hh ”) = s a t t e n d s ： 3 查询只选修了“c o m p u t e rs c i e n c e ，”，“m a t h ，”和“p r o g r a m m i n gj ”当 中的课程的学生。( q = “c o m p u t e r s c i e n c e l ”，“m a t h ，”，“p r o g r a m m i n g ，” ， 0 = “三”) s e l e c ts n a m e f r o msi na l l s t u d e n t s w h e r es a t t e d s $ 2 ，则存在i ，对所有 的， f ，有a j = 巧，且a t 。 定理2 1 可以很容易地从树的前序遍历的性质中得到。 反向链表 & f 押e 的另一部分是一个反向链表，该链表记录了集合数据集中的每个元 素：( f p r e f i x 树中所出现的位置。 集合索弓i 结构及j e 在x m l 查询中的应用 例如对图2 6 中的p r e f i x 树对应的链表为： a ：l b ：2 ，9 c ：3 ，7 1 0 ( f ：4 e ：5 8 ，6 反向链表在选择和联接操作中将起到重要的作用。 2 5 集合索引的查询操作 联接操作是数据库中的主要操作之一，同时也是数据库管理系统中最耗费代 价的操作，在第三章将重点联接操作的实现方法，但为了说明索引结构的实用性， 首先简单介绍基于s e tt r e e 实现选择和修改操作的方法。 2 5 1 选择操作 选择操作主要有两种，子集合选择查询和超级和选择查询。 1 、子集合选择查询操作 其查询为给定集合蹄伽j a 2 ，口0 ，查找数据库中所有包含s 的纪录，例如 查询所有包含集合“6 ) 的记录。查询步骤为： 1 将集合s 中每个元素对应的反向链表取出建成一个链表，设a ，对应的链 表为厶，每个链表厶设立一个扫描指针p o i n t e r ；，开始时指向b 的头，若 p o i n t e r f 指向的结点为n o d e ，其标号为n o d e ，1 a b e l 。 2 若对n o d e ，n o d e 2 ，n o d e 。均有n o d e l a b e l n o d e h l 1 a b e l 。n o d e n 的所有子孙结 点构成查询结果。 3 否则，从n o d e l , n o d e 孙n o d e 。中取出相邻兄弟结点的标号最小的结点 n o 出i ，将p o i n t e r j 向后移一位。若p o i n t e r j ：n u l l 则算法结束，否则转 向1 ) 。 例如，若查询所有包含集合以6 ) 的记录，图2 6 中a 对应的序列为1 ，b 对应 的序列为2 ，9 ，其中1 ，2 满足2 ) 中的判断条件，所以2 的子树中的所有结点 构成查询结果。 2 、超集合选择查询操作 集合索引结构及 e 在x m l 查询中的应用 假设查询为找到所有包含于集合h6 j e 的集合，其方法是首先生成缸b , e 。_ 7 的所有子集，然后查找树中结点对应的集合值等于这些子集的结点，将这些结点 对应的数据库中的元组进行合并，就得到了最终的结果。 2 5 2 插入、删除操作 插入和删除操作均由两个阶段构成的，第一个阶段定位插入的集合在p r e f i x 树中的位置，并根据操作的不同，对p r e f i x 树进行修改。第二个阶段在反向链表 中增加或删除结点。 插入操作的基本方法为，首先从根结点开始，沿着插入集合所代表的路径向 下搜索，如果发现相应的结点不存在，则在相应的位置生成新结点，并将新的结 点插入反向链表。最后将新的集合对应的元组加入数据域。 删除操作的执行过程同插入操作相似，只是将增加结点改为删除结点。 依上所述不难看出，s e t _ t r e e 结构对可以有效地减少选择和修改操作的搜索 空问。 2 6 本章小结 本章介绍了几种集合数据索引结构： i n v e r tl i s t 、s e q u e n t i a ls i g n a t u r ef i l e 、 s i g n a t u r et r e e 和e x t e n d i b l es i g n a t u r eh a s h i n g 四种集合索引结构，并重点介绍了 本文提出的树型集合索引结构：s e t t r e e ，这种结构对集合数据库进行了合理的组 织，可有效地管理数据集中的重复模式和重复数据。在2 5 节我们讨论了几个几 种基本操作即选择、插入和删除的实现方法进行简单的描述。 2 1 集合索引结构及其在x m l 查询中的应用 第三章集合索引的联接操作 联接操作是数据库中的主要操作之，同时也是数据库管理系统中最耗费代 价的操作，所以联接操作一直是数据库界研究的重点，并产生了很多方法，如基 于块的嵌套循环的方法、基于索引的嵌套循环的方法、m e r g es o r t 方法 2 3 等， 并对如何利用索引提高查询性能方面进行了深入的研究，这些方法对常规数据具 有很好的效果。 3 1 介绍 许多真实世界里的查询用集合联接来表示十分容易，我们来看下面的例子。 s t u d e n t ( s i d , c o u r s e s ) ) c o u r s e d ( e i d , ( p r e r e q u e s t s ) 上面两个关系中的属性 c o u r s e s 和( p 地一r e q u e s t s 是集合属性。通常会查询已 经修完指定的课程，有资格选某门课程的学生。用集合联接表达这个查询很简单： s e l e c tj s i d , nc i d f r o ms t u d e n ts ，c o u r s e sc w h e r ec p r e r e q u e s t s s c o u r s e s 下面再举个和网络有关的例子，假定一个简单的关系，描述文档和指向这些文档 的超链接： d o c u m e n t ( d i d , h y p e r - l i n k s i n ，a c t u a l - d o c u m e n t ) 假定如果链接文档d l 的那些文档是链接到文档d 2 的文档的超集，就说明文 档d l 比文档d 2 重要。我们查询( 洲，d 2 ) ，其中d l 比加重要。 s e l e c td 1 d i d , d 2 d i d f r o md o c u m e n td l ，d o c u m e n td 2 w h e r ed 2 h y p e r - l i n k s i nc d l h y p e r l i n k s i n 实现集合联接算法还要考虑集合在数据库中的存储情况。根据1 3 的描述集 合属性在数据库中用下面两种存储方式： 集合索引结构及其在x m l 查询中的应用 嵌套内部( n e s t e di n t e r n a l ) ：集合的所有元素都存在起，并和元组的其他 属性保存在一起。 非嵌套外部( u n n e s t e de x t e r n a l ) ：集合属性的数据存储在一个单独的关系表 中，对于一个关系表中的每一个集合属性创建两