（计算机软件与理论专业论文）利用分层位图索引进行子集查询.pdf

山东大学硕士学位论文 摘要 对集值属性数据库进行查询与检索有赖于高效的检索机制。因此，如何 将基于集值属性的数据库数据进行合理的分类，从而建立相应的索引机制并 进行子集查询就成为了一个亟待解决的问题。本文提出了一种有效的支持集 值属性数据库查询的分类位图索引算法，从建立高效的索引结构和选择恰当 的实现机制两方面入手，对数据库的查询作了进一步的研究，所做主要工作 及其取得主要成果如下： 1 提出一种新的索引结构 本文在位图索引结构基础上，提出分层位图索引，对该索引的效率问题 进行了分析。 2 提出一种新的查询方法 本文提出运用分层位图的优势，在高效索引的基础上，自顶向下，进行 有筛选的查询，以适合对数据仓库快速查询的需要。 3 给出算法的代码实现 本文对所提出的索引结构、查询方法都给出了具体算法和代码实现，主 要包括：数据库索引结构的算法、位图索引查询的算法，其中采用的技术具 有一定的实用参考价值。 4 试验分析 本文对所提出的分层位图索引查询技术进行了试验。通过分析试验结 果，指出了该方法对查询效率的显著提高和仍然存在的问题。 关键词：集值属性数据库；分层；位图索引；子集查询 山东大学硕士学位论文 a b s t r a c t w i t ht h er a p i dd e v e l o p m e n ta n d p o p u l a r i z a t i o no f d a t a b a s et e c h n o l o g y p e o p l ec s t o r a g el a r g en u m b e ri n f o r m a t i o ni nd a t a b a s ea n dq u e r yal a r g e n u m b e ro f i n f o r m a t i o nf r o md a t a b a s e b u ta l lo u t s t a n d i n gp r o b l e me x i s t sw h i l e w em e e ts e t - v a l u e da t t r i b u t e sd a t a b a s e ，a l s o ，q u e r y i n ga n di n d e x i n gs e t - v a l u e d a t t r i b u t e sd a t a b a s en e e dh i 曲e f f e c t i v ei n d e xa n dq u e r ym e t h o d h o wt 0a s s o r tt h e s e t - v a l u e da t t r i b u t e sd a t a b a s ea n ds e t u pe f f e c t i v ei n d e xf o rq u e r y i n gi sa l l i m p e r i o i l sp r o b l e m t h i sa r t i c l ee x p o u n da ne f f i c i e n tm e t h o d - - a s s o r th i e r a r c h i c a l b i t m a pi n d e xs u b s e tq u e r y i n gw h i c hc a nd i s s o l v et h ep r o b l e mt a l k e da b o v e ， a n d a c c o r d i n gt e s t t h em e t h o d i sv e r i f i e da ne f f e c t i v ew a yt oa c c e l e r a t ei n d e xs p e e d t h em a i nw o r d sa n da c h i e v e m e n t sw eh a v e d o n ea sf o l l o w s ： 1 p r o p o s e dan e w i n d e xs t r u c t u r e b a s e do nt h eh i 鲫c h i c a lb i t m a pi n d e xf o rd a t a b a s e 2 p r o p o s ean e wq u e r yp r o c e s s i n gm e t h o d i nt h i sp a p e r , w ep r o p o s e dan e ws o l u t i o nw h i c ht a k ea d v a n t a g eo f t h e m u l t i t h r e a dm e c h a n i s m , u t i l i z et h eh u g e - e f f e c ti n d e xs t r u c t u r eb u i l ti nt h i sp a p e r , f r o mt h eb u t t o no f a p a t he x p r e s s i o nt ot h eu p ，t op r o c e s sa s u b s e tq u e r y s i m u l t a n e o u s l y t os u p p o r t t h em u l t i t h r e a dm e c h a n i s m s ， 3 p r e s e n t e dt h ek e ya l g o r i t h m sa n dt h e i rp r o g r a m m i n gc o d e s i nt h i sp a p e r , w ep r e s e n t e dt h ek e ya l g o r i t h m sa n dt h e i rp r o g r a m m i n gc o d e s o n h o w t o b u i l d t h e d e s i r e d i n d e xs t r u c t u r e a n d h o w t o q u e r y , a sa r t i c l e 1 】s a y s m a i n l y i n c l u d e ：t h e a l g o r i t h m o f p a r s i n g d a t a b l e d o c u m e n t t o b u i l d as p e c i a l i n d e xs t r u c t u r e ，t h ea l g o r i t h mo f p a r s i n gp a t he x p r e s s i o nt ob u i l dt h er e l e v a n t o b j e c t sa n dt h ea l g o r i t h mo f p r o c e s s i n gaq u e r ym u l t i t h r e a d i n g s i m u l t a n e o u s l y t h et e c h n o l o g i e sa d o p t e da m o n g t h i sp a p e ra l s oh a v es o m e p r a c t i c a lr e f e r e n c ev a l u e sf o rp r o g r a m m e r s 4 e x p r e i m e n t w ec o m p a r e dt h et r a d i t i o n a lm e t h o d 谢t l io u rm e t h o do nt h eq u e r y e f f i c i e n c yo ns o m es e t - v a l u e dd a t a b a s ed o c u m e n t so fd i f f e r e n ts i z ei na n e x p e r i m e n t t h r o u g ha n a l y z i n gt h ee x p e r i m e n t a lr e s u l t , w ep o i n t e do u tt h e r e m a r k a b l ei m p r o v e m e n to f q u e r ye f f i c i e n c yb y0 1 1 1 m e t h o da n dp o i n t e do u tt h e p r o b l e m s t i l le x i s t i n gi ni t k e yw o r d ：s o t v a i u a da t t r i b u t a sd a t a b a s e ；s u b s e tq u e r y ； h i e r a r o h i o a ib i t a m p i i 原创性声明和关于论文使用授权的说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本 论文不包含任何其他个人或集体已经发表或撰写过的科研成果。 对本文的研究做出重要贡献的个人和集体，均已在文中以明确方 式标明。本声明的法律责任由本人承担。 论文作者签名：3 11 生 日 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同 意学校保留或向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅；本人授权山东大学可以将本学位论 文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印或其他复制手段保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：蛆新签名：墟丛蛋期：卫纽! r jl 山东大学硕士学位论文 1 1 引言 第1 章绪论 数据库系统在现实生活中广泛使用，已经成为衡量一个国家信 息化程度的重要标志。现在大部分关系数据库中的表属性是单值的 ( a t o m i cv a l u e d ) ，即符合规范化理论的最低要求i n f i 。设有 关系s t u d e n t ( n a m e ，a g e ，s c o r e ) ，其中s c o r e 代表某一学生的考试 成绩，在一条记录中s c o r e 只能取一个值；然而如果这个学生考了 很多门课，s c o r e 所对很多条记录，这样同一个学生的n a m e 。a g e 就要重复存储多次，产生冗余。因此就有这样一种需求：让s c o r e 字段能够表示所有考试成绩，如f 7 6 ，8 0 9 5 ) ) 分别代表了该学生的 语文、数学、英语考试成绩。此时，s c o r e 由a t o m i c - v a l u e d 属性 变成了s e t v a l u e d ( 集值或叫多值) 属性，即取值是一个集合。 目前大部分数据库系统提供了对集值( s e t - v a l u e d ) 属性的存储方 案，比如可以通过嵌套表或者用户自定义数据类型来存储。但是， 使用集值属性进行存储又带来了新的问题。 现考虑当前税务系统的“一户式”管理系统。税务系统“一户 式管理系统融征管系统( c t a i s ) 、防伪税控系统、出口退税系统等 系统的信息于一体。它的核心是利用现有资源将征管系统( c t a i s ) 、 增值税管理信息系统和出口退税系统等在数据层进行整合，将分散 在各个不同系统、不同业务模块中的数据按要求进行整理、筛选、 归并，使其能够在同一个窗口进行查询。 税务机关工作人员可以依据纳税人名称或识别号的线索，利用 计算机系统查询出该纳税人的全方位的涉税信息。这样，一是满足 基层税务机关人员执法的需要，使基层税务机关人员能够全面、快 速和准确地查询出纳税人的有关涉税信息，为基层执法服务。二是 满足税务管理机关管理工作的需要，对纳税人的涉税活动进行监 山东大学硕士学位论文 控，提供查询分析功能。 现在考虑当前税务系统中的“一户式”管理数据库。其中有关 系t a x o f f e r ( t a x n a m e ，t a x i d ，t a x a f f a i r s ) ，t a xa f f a i r s 是集 值属性，代表了某纳税人在一次纳税中的所有涉税信息，显然其取 值应是一个集合。现在要进行如下查询：在一次纳税中同时为零负 申报s h e n b a o = o 而且有欠税s u b t a x o 的纳税人的数目。使用非标 准的s q l 语句可以表述成如下形式： s e l e c tc o u n t ( d i s t i n c tc u s t i d ) f r o mt a x o f f e r w h e r et a x o f f e r 包含( s h e n b a o = o ，s u b t a x o ) 这种查询我们称之为子集查询。但标准s q l 语句不支持这种查 询，只能以一种复杂的表述来进行子集查询，可以有如下两种表达： s e l e c tc o u n t ( d i s t i n c t a t a x i d ) f r o mt a x o f f e r a ，t a x o f f e r b w h e r ea t a x i d = b t a x i d a n da s h e n b a o = 0 a n db s u b t a x 0 或者：s e l e c tc o u n t ( 水) f r o m ( s e l e c ti t e ai n s h e n b a o = 0 ，s u b t a x ”0 ” g r o u pb yt a x i d h a v i n gc o u n t ( ) = 2 ) ： 从上面我们可以看到，这两种查询的效率是很低的，需要使用 大量的内存和c p u 资源。第一种查询要进行自连接，显然作为一个 税务部门，尤其是市、省级税务部门，每个征收期要有大量的纳税 人的纪录，连接后记录数目会成倍增长，而且如果在查询子集中再 添加一个取值，那么连接所生成的记录数目会更多，所以这种方式 不适合于大型数据库；第二中方法要进行分组也是很浪费资源的， 同样，再引入一个取值会带来很多麻烦，所以这种方式也不适合于 2 山东大学硕士学位论文 大型数据库。那么，如何解决这类查询的效率问题? 在这篇论文中 我们利用分类位图索引进行子集查询，这种技术可以很好的解决子 集查询的效率问题。分层位图索引可以对任意大的属性域的子集 ( 即集合) 进行索引的技术，它的主要特点是： ( 1 ) 可伸缩性，支持较大域的子集索引 ( 2 ) 很好的支持集合查询，包括子集查询，超级查询和相似 查询 ( 3 ) 存储索引只需消耗少量的存储空间 ( 4 ) 可以唯一的标志一个被索引集合 本节将就位图索引的定义、起源、特点及优点作简要介绍。 1 1 1 什么是位图索引 位图索引和b , t r e e 是两大索引机制。默认情况下大多使用 b , t r e e 索引，该索引就是通常所见唯一索引、聚簇索引等等， b , t r e e 用在o l t p ，加快查询速度。位图索引主要用在o l a p ( 联机 数据分析) 方面，也就是数据仓库方面用到，目的是在加快查询速 度是，节省存储空间。通常情况下，索引都要耗费比较大的存储空 间，位图采用了压缩技术实现磁盘空间缩减。b , t r e e 用在高基数 ( 即列的数据相异度大) ，位图用在低基数列。位图索引的基本原理 是在索引中使用位图而不是列值。通常在事实表和维表的键之间有 很低的集的势( c a r d i n a l i t y ) ，使用位图索引，存储更为有效，与 b , t r e e 索引比较起来，只需要更少的存储空间，这样每次读取可 以读到更多的记录，而且与b , t r e e 索引相比，位图索引将比较。连 接和聚集都变成了位算术运算，大大减少了运行时间，从而得到性 能上的极大的提升。一般来说，在数据仓库环境中，位图索引的性 能要好于b , t r e e 索引。但要注意位图索引不是为o l t p 数据库设计 的，不应该在o l t p 数据库中大量的使用它，尤其是对那些有更新 山东大学硕士学位论文 操作的表。 1 i 2 位图索引的特点 1 b i t m a p 索引的存储空间 相对于b , t r e e 索引，位图索引由于只存储键值的起止r o w i d 和位图，占用的空间非常少。 b i t m a p 的空间占用主要跟以下因素相关： a 表的总记录数。 b 索引列的键值多少，列的不同值越少，所需的位图就越少。 c 操作的类型，批量插入比单条插入所需的位图要少得多。 d 索引列相同键值的物理分布 2 b i t m a p 索引创建的速度 位图索引创建时不需要排序，并且按位存储，所需的空间也少。 b , t r e e 索引则在创建时需要排序，定位等操作，速度要慢得 多。 3 b i t m a p 索引允许键值为空 b , t r e e 索引由于不记录空值，当基于i sn u l l 的查询时，会使 用全表扫描，而对位图索引列进行i sn u l l 查询时，则可以使用索 引。 4 b i t m a p 索引对表记录的高效访问 当使用c o u n t ( x x ) ，可以直接访问索引就快速得出统计数据。 当根据位图索引的列进行a n d ，0 1 或i n ( x ，y ，) 查询时，直接 用索引的位图进行或运算，在访问数据之前可事先过滤数据。 5 b i t m a p 索引对批量d m l 操作只需进行一次索引。 由于通过位图反映数据情况，批量操作时对索引的更新速度比 4 山东大学硕士学位论文 b , t r e e 索引一行一行的处理快得多。 1 1 3 位图索引存储原理 位图索引对数据表的列的每一个键值分别存储为一个位图，数 据每行提交方式，与上面的情况相似，但有一点不一样，每提交一行， 拷贝原来的位图，生成新的位图，并标记原来的位图为已删除，标记 为已删除的位图，只有索引块需要分配新的位图时，才会清除标记 为已删除的位图，重用这些空间。 在8 i ，9 i 上实验的结果，与文献 2 中所述实验结果一致。 如果1 0 0 0 条相同键值的数据插入，将生成1 2 5 个包括8 条记录 的位图行。 批量插入数据t a x o f f e r ( t a x _ n a m e ，t a x i d ，t a x a f f a i r s ) ， s e l e c t 半术水方式，同一键值，只生成次位图，只有一个位图。可以 看出，1 0 g 对位图索引的存储进行了优化，一个键值在索引块中只 有一个位图。关于位图索引的一些信息，可以参考：b i t m a p 的一点 探究h t t p ：w w w i t p u b n e t 1 1 4 0 2 3 h t m l 。不同的版本，结果有差异。 1 2 位图索引查询技术及研究现状 位图索引的应用给数据仓库查询带来了一场革命，如何在浩如 烟海的数据中快速、准确地检索到所需要的信息，已经成为数据库 应用领域的一项重要课题和迫切任务。本节将对相关主要概念和位 图索引技术的研究进行扼要介绍。 分层位图索引非常适合对集值属性进行索引，可以用在本文提 到的税务系统数据库中、超市数据库系统中、学生成绩管理系统中， 也可以在多媒体数据库中对幅图像所包含的多个对象进行索引， 在网络服务器之中，还可以对一个用户所访闯的页面进行分层位图 山东大学硕士学位论文 索引。文章 3 中指出，在挖掘关联规则中，a p o r i o 是找频繁象集 的典型算法，该算法中一个候选象集的频繁度通过依次扫描整个数 据库表来计算，在每一步扫描中，每个元组被测试是否含有候选象 集，这其实就是一个子集查询，我们也可以把分层位图索引引入到 该算法中。 1 2 1 数据仓库 1 2 1 1 数据仓库的产生和发展 计算机系统的功能从数值计算扩展到数据管理距今已有三十 多年了。最初的数据管理形式主要是文件系统，少量的以数据片段 之间增加一些关联和语义而构成层次型或网状数据库，但数据的访 问必须依赖于特定的程序，数据的存取方式是固定的、死板的。到 了1 9 6 9 年，e f c o d d 博士发表了他著名的关系数据模型的论文。 此后，关系数据库的出现开创了数据管理的一个新时代。 二十多年来，大量新技术、新思路涌现出来著被用于关系数据 库系统的开发和实现：客户服务器体系结构、存储过程、多线索 并发内核、异步i 0 、代价优化，等等，这一切足以使得关系数据 库系统的处理能力毫不逊色于传统封闭的数据库系统。而关系数据 库在访问逻辑和应用上所带来的好处则远远不止这些，s q l 的使用 已成为一个不可阻挡的潮流，加上近些年来计算机硬件的处理能力 呈数量级的递增，关系数据库最终成为联机事务处理系统的主宰。 整个8 0 年代直到9 0 年代初，联机事务处理一直是数据库应用的主 流。然而，应用在不断地进步。当联机事务处理系统应用到一定阶 段的时候，企业家们便发现单靠拥有联机事务处理系统已经不足以 获得市场竞争的优势，他们需要对其自身业务的运作以及整个市场 相关行业的态势进行分析，而做出有利的决策。这种决策需要对大 量的业务数据包括历史业务数据进行分析才能得到。在如今这样激 6 山东大学硕士学位论文 e ! | ! ! ! 目! ! ! ! ! 自! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! 目! ! 自! ! ! ! 自! | | ! ! 自! ! ! ! 目! ! ! ! ! s ! ! ! 曼曼i i 烈的市场竞争环境下，这种基于业务数据的决策分析，我们把它称 之为联机分析处理，比以往任何时候都显得更为重要。如果说传统 联机事务处理强调的是更新数据库一一向数据库中添加信息，那么 联机分析处理就是从数据库中获取信息、利用信息。因此，著名的 数据仓库专家r a l p h k i m b a l l 写道：“我们花了二十多年的时间将数 据放入数据库，如今是该将它们拿出来的时候了。” 事实上，将大量的业务数据应用于分析和统计原本是一个非常 简单和自然的想法。但在实际的操作中，要获得有用的信息并非如 想象的那么容易：第一，所有联机事务处理强调的是密集的数据更 新处理性能和系统的可靠性，并不关心数据查询的方便与快捷。联 机分析和事务处理对系统的要求不同，同一个数据库在理论上都难 以做到两全；第二，业务数据往往被存放于分散的异构环境中，不 易统查询访问，而且还有大量的历史数据处于脱机状态，形同虚 设；第三，业务数据的模式针对事务处理系统而设计，数据的格式 和描述方式并不适合非计算机专业人员进行业务上的分析和统计。 以前查询不到数据是因为数据太少了，而今天查询不到数据是因为 数据太多了。针对这一问题，人们设想专门为业务的统计分析建立 一个数据中心，它的数据从联机的事务处理系统中来、从异构的外 部数据源来、从脱机的历史业务数据中来这个数据中心是一个 联机的系统，它是专门为分析统计和决策支持应用服务的，通过它 可满足决策支持和联机分析应用所要求的一切。这个数据中心就叫 做数据仓库。这个概念在9 0 年代初被提出来，如果需要给数据仓 库一个定义的话，那么数据仓库就是一个作为决策支持系统和联机 分析应用数据源的结构化数据环境。数据仓库所要研究和解决的问 题就是从数据库中获取信息的问题。 那么数据仓库与数据库( 主要指关系型数据库) 又是什么关系 昵? 当初，人们固守封闭式系统是出于对事务处理的偏爱，人们选 择关系数据库是为了方便地获得信息。我们只要读一读文献 4 便 会发现：今天数据仓库所要提供的正是当年关系数据库要所倡导 的。然而，由于关系数据库系统在联机事务处理应用中获得的巨大 成功，使得人们已不知不觉将它划归事务处理的范畴；过多地关注 山东大学硕士学位论文 于事务处理能力的提高，使得关系数据库在面对联机分析应用时又 显得“老革命遇到新问题”一一今天的数据仓库对关系数据库的联 机分析能力提出了更高的要求，采用普通关系型数据库作为数据仓 库在功能和性能上都是不够的，它们必须有专门的改进。因此，数 据仓库与数据库的区别不仅仅表现在应用的方法和目的方面，同时 也涉及到产品和配置上的不同。 以辨证的眼光来看，数据仓库的兴起实际上是数据管理的一种 回归，是螺旋式的上升。今天的数据库就好比当年的层次数据库和 网型数据库，它们面向事务处理：今天的数据仓库就好比是当年的 关系数据库，它针对联机分析。所不同的是，今天的数据仓库不必 再为联机事务处理的特性而无谓奔忙，由于技术的专业化，它可更 专心于联机分析领域的发展和探索。 数据仓库的概念一经出现，就首先被应用于金融、电信、保险 等主要传统数据处理密集型行业。国外许多大型的数据仓库在 1 9 9 6 1 9 9 7 年建立。那么，什么样的行业最需要和可能建立数据 仓库昵? 有两个基本条件：第一，该行业有较为成熟的联机事务处 理系统，它为数据仓库提供客观条件；第二，该行业面临市场竞争 的压力，它为数据仓库的建立提供外在的动力。 1 2 1 2 数据仓库的关键技术 那么，数据仓库都有哪些组成部分和关键技术呢? 与关系数据 库不同，数据仓库并没有严格的数学理论基础，它更偏向于工程。 由于数据仓库的这种工程性，因而在技术上可以根据它的工作过程 分为：数据的抽取、存储和管理、数据的表现以及数据仓库设计的 技术咨询四个方面。在此，我们将分别讨论每一个环节。 1 数据的抽取 数据的抽取是数据进入仓库的入口。由于数据仓库是一个独立 的数据环境，它需要通过抽取过程将数据从联机事务处理系统、外 山东大学硕士学位论文 部数据源、脱机的数据存储介质中导入数据仓库。数据抽取在技术 上主要涉及互连、复制、增量、转换、调度和监控等几个方面。数 据仓库的数据并不要求与联机事务处理系统保持实时的同步，因此 数据抽取可以定时进行，但多个抽取操作执行的时间、相互的顺序、 成败对数据仓库中信息的有效性则至关重要。 在技术发展上，如文献 5 所述，数据抽取所涉及的单个技术 环节都已相对成熟，其中有一些是躲不开编程的，但整体的集成度 还很不够。目前市面上所提供的大多是数据抽取工具。这些工具通 过用户选定源数据和目标数据的对应关系，会自动生成数据抽取的 代码。但抽取工具支持的数据种类是有限的；同时数据抽取过程涉 及数据的转换，它是一个与实际应用密切相关的部分，其复杂性使 得不可嵌入用户编程的抽取工具往往不能满足要求。因此，实际的 数据仓库实施过程中往往不一定使用抽取工具。整个抽取过程能否 因工具的使用而纳入有效的管理、调度和维护则更为重要。从市场 发展来看，以数据抽取、异构互连产品为主项的数据仓库厂商一般 都很有可能被其他拥有数据库产品的公司吞并。在数据仓库的世界 里，它们只能成为辅助的角色。 2 存储和管理 数据仓库的真正关键是数据的存储和管理。数据仓库的组织管 理方式决定了它有别于传统数据库的特性，同时也决定了其对外部 数据表现形式。要决定采用什么产品和技术来建立数据仓库核心， 则需要从数据仓库的技术特点着手分析。 数据仓库遇到的第一个问题是对大量数据的存储和管理。这里 所涉及的数据量比传统事务处理大得多，且随时间的推移而累积。 从现有技术和产品来看，只有关系数据库系统能够担当此任。关系 数据库经过近3 0 年的发展，在数据存储和管理方面已经非常成熟， 非其他数据管理系统可比。目前不少关系数据库系统已支持数据分 割技术，能够将一个大的数据库表分散在多个物理存储设备中，进 一步增强了系统管理大数据量的扩展能力。采用关系数据库管理数 百个g b 甚至到t b 的数据已是一件平常的事情。一些厂商还专门考 9 山东大学硕士学位论文 虑大数据量的系统备份问题，好在数据仓库对联机备份的要求并不 高。 数据仓库要解决的第二个问题是并行处理。在传统联机事务处 理应用中，用户访问系统的特点是短小而密集；对于一个多处理机 系统来说，能够将用户的请求进行均衡分担是关键，这便是并发操 作。而在数据仓库系统中，用户访问系统的特点是庞大而稀疏，每 一个查询和统计都很复杂，但访问的频率并不是很高。此时系统需 要有能力将所有的处理机调动起来为这一个复杂的查询请求服务， 将该请求并行处理。因此，并行处理技术在数据仓库中比以往更加 重要。大家可以注意一下，在针对数据仓库的t p c - d 基准测试中 1 0 ，比以往增加了一个单用户环境的测试，称为“系统功力” ( q p p d ) 。系统的并行处理能力对q p p d 的值有重要影响。目前，关 系数据库系统在并行处理方面已能做到对查询语句的分解并行、基 于数据分割的并行、以及支持跨平台多处理机的群集环境和m p p 环境，能够支持多达上百个处理机的硬件系统并保持性能的扩展能 力。 数据仓库的第三个问题是针对决策支持查询的优化。这个问题 主要针对关系数据库而言，因为其他数据管理环境连基本的通用查 询能力还不完善。在技术上，针对决策支持的优化涉及数据库系统 的索引机制、查询优化器、连接策略、数据排序和采样等诸多部分。 普通关系数据库采用b 树类的索引，对于性别、年龄、地区等具有 大量重复值的字段几乎没有效果。而扩充的关系数据库则引入了位 图索引的机制，以二进制位表示字段的状态，将查询过程变为筛选 过程，单个计算机的基本操作便可筛选多条记录。由于数据仓库中 各数据表的数据量往往极不均匀，普通查询优化器所得出的最佳查 询路径可能不是最优的。因此，面向决策支持的关系数据库在查询 优化器上也做了改进，同时根据索引的使用特性增加了多重索引扫 描的能力。以关系数据库建立的数据仓库在应用时会遇到大量的表 间连接操作，而连接操作对于关系数据库来说是一件耗时的事儿。 扩充的关系库中对连接操作可以做预先的定义，我们称之为连接索 引，使得数据库在执行查询时可直接获取数据而不必实施具体的连 山东大学硕士学位论文 接操作。数据仓库的查询常常只需要数据库中的部分记录，如最大 的前5 0 家客户，等等。普通关系数据库没有提供这样的查询能力， 只好将整个表的记录进行排序，从而耗费了大量的时间。决策支持 的关系数据库在此做了改进，提供了这一功能。此外，数据仓库的 查询并不需要像事务处理系统那样精确，但在大容量数据环境中需 要有足够短的系统相应时间。因此，一些数据库系统增加了采样数 据的查询能力，在精确度允许的范围内，大幅度提高系统查询效率。 总之，将普通关系数据库改造成适合担当数据仓库的服务器有许多 工作可以做，它已成为关系数据库技术的一个重要研究课题和发展 方向。可见，对于决策支持的扩充是传统关系数据库进入数据仓库 市场的重要技术措施。 数据仓库的第四个问题是支持多维分析的查询模式，这也是关 系数据库在数据仓库领域遇到的最严峻的挑战之一。用户在使用数 据仓库时的访问方式与传统关系数据库有很大的不同。对于数据仓 库的访问往往不是简单的表和记录的查询，而是基于用户业务的分 析模式，即联机分析。如附图所示，它的特点是将数据想象成多维 的立方体，用户的查询便相当于在其中的部分维( 棱) 上施加条件， 对立方体进行切片、分割，得到的结果则是数值的矩阵或向量，并 将其制成图表或输入数理统计的算法。 附图 关系数据库本身没有提供这种多维分析的查询功能，而且在数 据仓库发展的早期，人们发现采用关系数据库去实现这种多维查询 模式非常低效、查询处理的过程也难以自动化。为此，人们提出了 多维数据库的概念。多维数据库是一种以多维数据存储形式来组织 数据的数据管理系统，它不是关系型数据库，在使用时需要将数据 从关系数据库中转载到多维数据库中方可访问。采用多维数据库实 山东大学硕士学位论文 现的联机分析应用我们称之为m o l a p 。多维数据库在针对小型的多 维分析应用有较好的效果，但它缺少关系数据库所拥有的并行处理 及大规模数据管理扩展性，因此难以承担大型数据仓库应用。这样 的状态直到“星型模式”在关系数据库设计中得到广泛应用才彻底 改变。几年前，数据仓库专家们发现，关系数据库若采用“星型模 式”来组织数据就能很好地解决多维分析的问题。“星型模式”只 不过是数据库设计中数据表之间的一种关联形式，它的巧妙之处在 于能够找到一个固定的算法，将用户的多维查询请求转换成针对该 数据模式的标准s q l 语句，而且该语句是最优化的。“星型模式” 的应用为关系数据库在数据仓库领域大开绿灯。采用关系数据库实 现的联机分析应用称为r o l a p 。目前，大多数厂商提供的数据仓库 解决方案都采用r o l a p 。 在数据仓库的数据存储管理领域，从当今的技术发展来看，面 向决策支持扩充的并行关系数据库将是数据仓库的核心。在市场 上，数据库厂商将成为数据仓库的中坚力量。 3 数据的表现 数据表现是数据仓库的门面。这是一个工具厂商的天下。它们 主要集中在多维分析，数理统计和数据挖掘方面。 多维分析是数据仓库的重要表现形式，由于m o l e p 系统是专用 的，因此，关于多维分析领域的工具和产品大多是r o l a p 工具。这 些产品近两年来更加注重提供基于w e b 的前端联机分析界面，而不 仅仅是网上数据的发布。 数理统计原本与数据仓库没有直接的联系，但在实际的应用 中，客户需要通过对数据的统计来验证他们对某些事物的假设，以 进行决策。与数理统计相似，数据挖掘与数据仓库也没有直接联系。 而且这个概念在现实中有些含混。数据挖掘强调的不仅仅是验证人 们对数据特性的假设，而且它更要主动地寻找并发现蕴藏在数据之 中的规律。这听起来虽然很吸引人，但在实现上却有很大的出入。 市场上许多数据挖掘工具其实不过是数理统计的应用。它们并不是 真正寻找出数据的规律，而是验证尽可能多的假设，其中包括许多 山东大学硕士学位论文 毫无意义的组合，最后由人来判断其合理性。因此，在当前的数据 仓库应用中，有效地利用数理统计就已经能够获得可观的效益。 1 2 2 相关技术 位图索引查询加速了对大型数据仓表格的查询效率。这种新的 方法，要求创建一个索引，有这个索引在它被创建的时候进行合并 操作，然后为连接中用到的关键字创建一个位图索引。 位图连接索引背后的技术其实是把低基数数据列预先连接在 一起，这样就让整体的连接( 操作) 进行得更快。在本文的例子里， 我们将使用一个零件和供应商之间的多对多关系。每个零件都由多 个供应商供应，而每个供应商能够提供多种零件。这个数据库里有 2 0 0 种不同类型的零件，供应商可以在( 美国) 所有6 0 个州供应 零件。 要创建一个位图连接索引，我们要使用下面的s q l 。要注意 c r e a t ei n d e x 句法里的f r o m 和w h e r e 子句。 c r e a t eb i t m a pi n d e x p a r t s u p p li e r s s t a t e 0 n i n v e n t o r y ( p a r t s p a r t t y p e ，s u p p l i e r s t a t e ) f r o m i n v e n t o r yi ， p a r t sp ， s u p p l i e r s w h e r e i p a r t i d = p p a r t i d a n d 山东大学硕士学位论文 i s u p p li e r i d = p p a r t i d ： 尽管b - t r e e 索引被用在标准的交叉记录( j u n c t i o nr e c o r d ) 里，但是我们能够提高o r a c l e 9 i 查询的性能，在这些查询里判断 述词( p r e d i c a t e ) 会用到低基数数据列。例如，看看下面的查询， 我们可以通过这个查询来获得北卡罗来纳的所有火花塞供应商： s e 】e c t s u p p l i e r n a m e f r o m p a r t s n a t u r a lj o i n i n v e n t o r y n a t u r a lj o i n s u p p l i e r s w h e r e p a r t t y p e2 p i s t o n a n d 在o r a c l e 9 i 之前的版本里，这个查询会需要一个对所有三个 表格进行嵌套循环连接( n e s t e dl o o pj o i n ) 或者散列连接( h a s h j o i n ) 。而在o r a c l e 9 i 里，我们可以根据低基数数据列将这三个表 格预先连接。 当所有的查询数据都驻留在索引之内的时候，使用这种索引方 法能够把表格连接的速度提高7 倍以上。然而在很多情况下，传统 的散列连接或者嵌套循环连接可能会比位图连接做得更好。 1 4 山东大学硕士学位论文 1 2 3 位图索引的局限性 位图连接不是一副万能药。下面就是索引的一些局限性： 被索引的数据列必须是低基数的一一通常要少于3 0 0 个完全 不同的值。在w h e r e 子句里，查询绝对不能索引那些没有包含在索 引里的数据列。 更新位图连接索引所需要的代价是相当高的。从实用的角度 讲，位图连接索引被抛弃，而在每天晚上进行每日批量加载任务的 时候才被重建。只有对于那些在处理的时候保持只读的o r a c l e 数 据仓库，位图连接索引才会起作用。 总而言之，位图连接索引会极大地提高特定数据仓查询的速 度，但是其代价是在为图索引创建的时候，需要预先连接表格。 1 3 本文所做主要工作 在借鉴前人研究成果的基础上，本文对位图索引数据查询技术 作了进步研究，为简化讨论，本文研究了分层位图索引查询技术， 所做工作及其主要成果如下： 1 、提出一种新的研究思路 从建立高效的索引结构和选择恰当的实现机制两方面入手，研 究了提高位图索引子集查询效率的问题。 2 、提出一种新的索引、查询方法 本文提出运用分层位图的优势，在高效索引的基础上，自顶向 下，进行有筛选的查询，以适合对数据仓库快速查询的需要。 3 、给出相关实现技术的算法代码实现 本文对所提出的索引结构、查询方法都给出了具体算法代码实 现，主要包括：解析数据库索引结构的算法、解析位图索引查询的 山东大学硕士学位论文 算法，其中采用的技术具有一定的实用参考价值。 4 、试验分析 本文对所提出的分层位图索引查询技术同传统的查询技术进 行了对比。通过分析试验结果，指出了该方法对查询效率的显著提 高和仍然存在的问题。 山东大学硕士学位论文 2 1 索引结构 第2 章分层位图索引 分层位图索引是基于签名结构的，它使用分层结构压缩签名结 果，减小它的稀疏性。分层位图索引在给定的集值属性上进行索引 得到一系列索引关键字，每一个索引关键字唯一地代表一个集合， 其中的每一个索引关键字由若干个长度为l ( 即有l 个取值位，每 个位置只能取0 或1 ) 的节点( 包括内部节点和叶子节点) 组成的 一颗深度为d 的树，树的根结点被称为索引关键字的根。 2 2 索引结构的算法 在对给定的集值属性进行索引之前，要把该属性所在的域的每 一个可能的取值映射为一个唯一的正整数。若v i d o m a i n ( a ) ( 这 里v i 是单值的，而不是集合) 则用i 替换。现在假设我们要对集合 s = v 1 ，v 2 ，v n 进行索引，可按如下过程进行： 若v i s 那么在树的叶子层中的第k 个结点中的第j 位置成1 ， 其中k = ( i l ) ，j = i 一( i l 一1 ) 水l ，i 即为v i 所映射成的整数。 在所有的叶子生成完了以后，生成叶子层的父层结点，依照同样的 办法，先把所有的叶子结点映射成整数1 ，2 ，3 ，然后再利用公式 k = ( i l 】，j = i 一( i l 一1 ) 木l 计算出叶子所对应的父结点中的 位置，如果叶子结点中的所有位置都为0 ，那么将其在父结点中的 对应位置置为0 ，否则只要有一个位置为l ，就将其父结点中的对 应位置置成1 。如此下去( 即重复d 步，d 为我们定义的树的深度) ， 直到生成分层位图索引关键字的根，这是一个自底向上递归的过 程。其中，我们称那些所有位置全为0 的结点为空结点，至少有一 个位置为1 的结点为非空结点。分层位图索引只保留那些非空结点 山东大学硕士学位论文 作为关键字的结点，这相对位图索引进行了较好的压缩，至此一个 集合对应的分层位图索引关键字建好了。 2 3 构建索引结构 下面通过示例具体说明本文所提出并构建索引结构。 现在我们以以上实例来说明这个过程：现在假定纳税人共有 2 7 ( 为了举例方便) 项涉税事项，这些涉税事项先被映射成“，2 ，3 2 7 ) 这些整数，有一纳税人有其中四项涉税事项存在问题( 比如不 申报、零负申报、存在欠税、违规使用发票等问题) ，这4 种涉税 事项对应的整数集合为s = ( 2 ，9 ，1 3 ，1 4 ) ，即是关系 t a x o f f e r ( t a x n a m e ，t a x i d ，t a x a f f a i r s ) 中t a x a f f a i r s 的取 值。 囡 j - ：一、 因由囱 图1 集合s 的分层位图索弓 f i g 1b i t m a pi n d e xo fa g g r e g a t i o ns 令l = 3 ，d = 3 则集合s 对应的分层位图索引关键字如图所示。 可以看到，在叶子层共有2 7 个o 1 比特位，分别对应了2 7 种事项， 其中1 代表了该纳税人与此项涉税事项有关或者在此项涉税事项 中存在问题。例如，纳税人在1 3 这个涉税事项中存在问题，利 用公式k = ( i l ) ，j = i 一( i l 一1 ) $ l 可计算出k = 5 ，j = 1 ， 说明在关键字中叶子层的第五个结点的第一个比特位应置为l 。在 生成叶子层的父