（计算机软件与理论专业论文）频繁项集技术在olap中应用的研究.pdf

频繁项集技术存o l a p 中府用的研究 摘要 近年来，随着数据仓库在商业运作中的日益广泛的应用，联机分析处理( o l a p ， o n l i n ea n a l y t i c a lp r o c e s s i n g ) 作为数据仓库系统的核心组成部分，越来越受 到人们的重视，引发了o l a p 技术的研究热潮，也带动了o l a p 的进一步发展。然而， 到目前为止，仍然存在着一些问题没有得到很好的解决。 在本文中将着重讨论其中的两个问题：1 ) 为提高查询响应速度进行物化视图 选择时必须考虑的视图大小的估算问题；2 ) 与m o l a p 制定存储策略( 多维数组或 压缩存储方式) 密切相关的维度间相关性的分析问题。 上述两个问题都与数据集的分布情况密切相关。o l a p 的元数据信息只能反 映数据集在单个属性上的分布，忽略了属性之间的联系和数据集的整体分布。而 频繁项集挖掘能够找出数据集在给定维度上多次出现的项集的信息，更好的刻画 数据集的分布和属性维度间的关联，因此破用于本文的研究当中。 本文中将主要探讨频繁项集技术在o l a p 的上述两大问题中的应用： 为了估算数据立方中所有候选视图的大小，本文提出了一种新的方法f s c 。 f s c 将o l a p 中的视图看成是包含给定列上项集的集合，把o l a p 视图大小的估算 问题转换为给定列上项集个数的估算。它将视图中包含的项集划分为频繁项集和 非频繁项集两类，结合频繁项集技术和传统的数学估算方法，对给定数据立方中 包含的所有候选视图的大小进行估算。实验证明，与同类算法相比，f s c 的精度 有较大的提高，特别是针对倾斜度较大的数据集。 在对o l a p 中的维度组合进行相关性分析时，本文将分析维度间的相关性转 换成分析维度组合中包含的项集的相关性。定义了项集的相关度和基于前者之上 的维度问的相关性度量，并提出了针对倾斜度较大的数据集估算维度间相关度的 c m m 算法。c 栅算法将维度组合中包含的项集分成频繁项集和非频繁项集两类， 通过将计算频繁项集相关度和采样估算非频繁项集相关度相结合的方法估算维 度间相关性的度量。实验证明，该度量的提出能够有效的衡量维度间关联的紧密 程度，c m m 算法对维度问相关度的估算具有一定的准确度，特别是针对倾斜度较 大的数据集。 本文的最后介绍了由笔者参与开发的一个基于国产关系数据库的o l a p 系统 的结构和各部分的功能。f s c 算法将被集成到该系统的物化模块以获得更好的物 化视图选择方案。 关键词：频繁项集，o l a p ，视图大小，相关性分析 分类号：t p 3 1 1 复旦大学硕士学位论文 频繁项集技术d - o l a p 中脚用的研究 a b s t r a c t r e c e n t l yw i t ht h ew i d e ra n dw i d e ra p p l i c a t i o no fd a t aw a r e h o u s e ，o l a p ( 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 ) ，b e i n gt h ec e n t r a lp a r to fd a t aw a r e h o u s e ，h a sb e e np a i d m u c ha t t e n t i o nw h i c hs u r g e st h er e s e a r c ho fo l a pt e c h n o l o g y h o w e v e r , s o m e p r o b l e m ss t i l lr e q u i r em o r er e s e a r c ht of i n dab e t t e rs o l u t i o n i nt h i st h e s i st w oo ft h ep r o b l e m sw i l lb em a i n l yd i s c u s s e d 1 n h ef i r s to n ei st h e p r o b l e mo fv i e ws i z ee s t i m a t i o nd u r i n gt h ec o n s i d e r a t i o no fv i e ws e l e c t i o nf o r p r e a g g r e g a t i o n n es e c o n do n ei sa b o u tt h ec o r r e l a t i o na n a l y s i so fd i m e n s i o n s w h i c hh a sac l o s er e l a t i o nt ot h ed a t as t o r a g ei nm o l a r b o t hp r o b l e m sa r ec l o s e l yr e l a t e dt ot h ed i s t r i b u t i o no ft h ed a t a s e t 1 n h em e t a d a t a c a no n l yt e l lu st h ed i s t r i b u t i o no ft h ed a t a s e to ns i n g l ea t t r i b u t e ，b u tm i s st h e i n f o r m a t i o no ft h ec o r r e l a t i o nb e t w e e na t t r i b u t e s f r e q u e n ti t e m s e tm i n i n gc a l lf i n d t h ef r e q u e n ti t e m s e t s i n f o r m a t i o ni nt h ed a t a s e to ht h eg i v e nd i m e n s i o n sa n dc a n b e t t e rr e f l e c tt h ed i s t r i b u t i o no ft h ed a t a s e ta n dt h ec o r r e l a t i o nb e t w e e nd i m e n s i o n s t h e r e f o r ei ti su s e di nt h i st h e s i s t h i st h e s i sw i l lm a i n l yf o c u so nt h ea p p l i c a t i o no ff r e q u e n ti t e m s e tt e c h n i q u ei n t h ea b o v et w op r o b l e m s i no r d e rt oe s t i m a t et h es i z eo fa l lt h ec a n d i d a t ev i e w si nt h ec u b e ，w ep r e s e n tn n o v e ls c h e m en a m e df s c f s ct r e a t st h ev i e w si nt h ec u b ea st h ee n s e m b l e so ft h e i t e m s e t so nt h eg i v e nd i m e n s i o n sa n dt u r n st h ev i e ws i z ee s t i m a t i o np r o b l e mi n t ot h e i t e m s e t sn u m b e re s t i m a t i o no ng i v e nd i m e n s i o n s t h e ni td i v i d e st h ei t e m s e t si n t o f r e q u e n ti t e m s e t sa n dn o n f r e q u e n ti t e m s e t s , c o m b i n e sf r e q u e n ti t e m s e tt e c h n i q u ea n d m a t h e m a t i c a le s t i m a t i o nt og i v et h ee s t i m a t i o n so fa l lc a n d i d a t ev i e w si nac u b e 1 n h e r e s u l t si n d i c a t et h a tt h ep r o p o s e ds c h e m ea p p r o x i m a t e sm o 坨a c c u r a t e l yt h a no t h e r s c h e m e s ，e s p e c i a l l y f o rs k e w e dd a t a s e t u p o nt r y i n gt od ot h ec o r r e l a t i o na n a l y s i sb e t w e e nd i m e n s i o n s ，w et u r nt h e p r o b l e mi n t oa n a l y z i n gt h ei t e m s e t s c o r r e l a t i o no nt h eg i v e nd i m e n s i o n sa n dd e f i n e t h ec o r r e l a t i o nm e a s u r ef o rt h eg i v e nd i m e n s i o n sb a s e do i lt h ed e f i n i t i o no ft h e c o r r e l a t i o nm e a s u r eo fi t e m s e t s an o v e la p p r o a c hn a m e dc m mi s p r e s e n t e dt o e s t i m a t et h ec o r r e l a t i o nm e a s u r eo fg i v e nd i m e n s i o n s ，w h i c hi se s p e c i a l l yf o rs k e w e d d a t a s e t c m md i v i d e st h ei t e m s c t so nt h eg i v e nd i m e n s i o n si n t of r e q u e n ti t e m s e t sa n d 复旦大学硕士学位论文 i v 频繁项囊技术有o l a p 中j 1 y 用的研究 n o n - f r e q u e n ti t e m s e t s t h e ni tc o m p u t e st h ec o r r e l a t i o nm e a s u e o ff r e q u e n ti t e m s e t s a n de s t i m a t e st h ec o r r e l a t i o nm e a s u r eo fn o n f r e q u e n ti t e m s e t sb ys a m p l i n g , a n d f i n a l l yg e t st h ee s t i m a t i o no ft h ec o r r e l a t i o nm e a s u r eo ng i v e nd i m e n s i o n s r e s u l t s i n d i c a t et h a tt h ec o r r e l a t i o nm e a s u r ec a ne f f e c t i v e l ym e a s u r et h ec o r r e l a t i o nd e g r e e b e t w e e nd i m e n s i o n sa n dc m mi sa c c u r a t ef o rt h em e a s u r ec o m p u t a t i o n ，e s p e c i a l l y f o rh i g hs k e w e dd a t a s e t s f i n a l l y , w eg i v eab r i e fi n t r o d u c t i o nt ot h es t r u c t u r ea n df u n c t i o n so far o l a p s y s t e mb a s e do n ah o m e m a d er e l a t i o n a ld a t a b a s e ，w h i c hi sd e s i g n e da n dd e v e l o p e db y o u r s e l v e s f s cw i l lb ei n t e g r a t e di n t ot h ev i e wm a t e r i a l i z a t i o nm o d e lt og e tab e t t e r v i e ws e l e c t i o ns c h e m e k e y w o r d s ：f r e q u e n ti t e m s e t ，o l a p , v i e ws i z e ，c o r r e l a t i o na n a l y s i s 复旦大学硕士学位论文 v - 频繁项集技术台o l a f 中j y 用的研究 第一章引言 数据挖掘，又称数据库中的知识发现( k n o w l e d g ed l s c o v e r yi n d a t a b a s e ) ， 是指从大量的、不完全的、有噪声的、模糊的、随机的数据中，提取隐含在其 中的、人们事先不知道的、但又是潜在有用的信息和知识的过程 3 1 。关联分 析作为数据挖掘的重要功能之一，一直是非常活跃的一个研究分支。频繁项集挖 掘技术作为关联分析引发的研究课题，也受到研究学者们的广泛关注，并被用于 分类 3 2 ，3 3 ，3 4 、聚类 3 5 等其他数据挖掘研究领域中。 随着信息技术的飞速发展，数据库技术和数据库管理系统越来越广泛的在 各个行业和领域得到应用。e f c o d d 所提出的关系数据库模型 3 7 3 促进了关系 数据库及联机事务处理( o l t p ) 的发展。数据量越来越大，用户的查询需求也越 来越复杂，传统的操作型数据库系统己不能完全满足这些要求。因此c o d d 提出 了多维数据库和多维分析的概念，即o l a p ( o n l i n ea n a l y t i c a l p r o c e s s i n g ) 4 。作为数据仓库的核心，o l a p 被用于支持复杂的分析操作，侧 重对决策人员和高层管理人员的决策支持，可以应分析人员的要求快速、灵活 的进行大数据量的复杂查询处理，并以一种直观易懂的形式将查询结果提供给 决策人员，以便他们准确地掌握信息，制定i f 确方案，增加效益。因此o l a p 一 经提出，就在业内引起了巨大的反响，并引发了o l a p 技术的研究热潮。研究学 者们就其中的许多问题进行了较为深入的研究，取得了大量的研究成果，但仍 有一些问题存在很大的研究和发展空间： 问题一：o l a p 中的视图大小估算 0 u 心的全称是o n l i n ea n a l y t i c a lp r o c e s s i n g ，其中的o n - l i n e 一词体现了 o l a p 一个非常重要的特征，即快速性，用户对o l a p 的快速反应能力有很高 的要求，系统应能在很短的时间内( 如5 秒内) 对用户的大部分请求做出响应。 然而，要对大量的数据进行分析并且达到这个速度要求是很困难的。为了提高 查询分析的响应速度，一个通常的策略就是事先计算并存储一些聚集结果( 又 称物化视图) 。通过存储这些预先计算好的视图，o l a p 系统在处理某些查询时， 不需要每次都对数据量庞大的原始表格进行聚集计算，而直接访问已经计算完 成的这些聚集结果，在其基础之上再进行一些简单的计算便可以回答用户提出 的复杂查询，从而大幅度的提高系统快速响应用户查询的能力，满足用户对 o l ”系统快速性的要求。 由于存储空间的限制，只能从候选视图中选出部分视图进行物化，于是引出 一个问题：在给定的空间限制下，如何选择物化哪些视图? 对于该问题，已经有不少研究人员提出了各种解决办法，如g r e e d y 5 ， 复旦大学硕士学位论文 频繁项集技术冉o l a p 中脚用的研究 p b s 6 ，a n n e 7 等。但是，使用这些算法计算时都有一个前提条件：必须知 道所有候选视图的大小。实际的计算每个视图的大小是不切实际的，因此我们 必须寻找一种合适的方法，对候选视图的大小进行估算。 问题二：o l a f * 中的维度间相关性分析 在m o l a p 系统中，多维数据以多维数组的方式存储在数据仓库当中。这种 存储方式简单直观，而且能够对聚集数据快速索引，提高查询效率。但是如果 数据集是稀疏的，存储的利用率可能很低，必须采用压缩技术，提高存储的利 用率。 为了解决这一问题，人们提出了稀疏矩阵压缩技术，对于密集的数据仍然 使用多维数组存放，对于稀疏数据则使用压缩的结构进行存储。压缩存储能够 节省空间，但是却会破坏m o l a p 的自然索引结构。因此在选择是否采用压缩技 术时必须进行一定的权衡，当数据达到一定的稀疏程度时，才采用压缩技术。 于是产生了如何判断数据的稀疏程度的问题。 事实上，数据集是稠密或是稀疏，与它所包含的维度之间的相关程度有着 非常密切的关系。如果维度间没有任何关联，相互之间是独立的，在数据量足 够大的情况下，所有的组合都将出现，因此在多维数组中所有的存储空间都将 是存有数据的，数据集是完全稠密的。相反的，如果维度之间的关联度很高， 每个维度的每种取值只与其他维度的少数几个值关联，则在这些维度上的属性 取值组合数就会很少，多维数组中的很多存储空间都将为空，将造成存储空间 的浪费，这时候就应当采取压缩存储的方式。因此，维度间相关性的分析对我 们决策m o l a p 中数据的存储方式具有非常重要的意义。 上述两个问题都与数据集的分布情况密切相关。这里所指的分布不仅仅指 数据在单个维度上的分布情况，更包含数据在多个维度上的联合分布和属性值 之间的关联。对于前者，0 l a p 的元数据库中保留了一些数据集的基本信息，如数 据集中包含的维度个数，每个维度上的取值个数和分布情况等。但这些信息往往 只能反映数据集在单个属性上的分布，忽略了属性之间的联系和数据集的整体 分布情况。因此，我们必须寻找一种方式，获得更为完整的数据集的分布信息。 频繁项集技术给了我们一个很好的启示。频繁项集挖掘能够找到数据集在给定 维度上多次出现的项集的信息，实现了某种意义上的数据集的不完全的“压缩” 表示，更好的刻画出数据集的分布信息和属性维度间的关联。因此，我们尝试将 频繁项集技术引入上述问题的研究中，以期获得理想的效果。 复旦大学硕士学位论文 频繁项集技术存o l a p 中脚用的研究 1 1 本文的主要内容和成果 本文将试图把频繁项集技术引入到o l a p 技术的研究当中，着重探讨将该技术 用于解决o l a p 中视图大小估算和维度问相关性分析两个问题，其主要内容和研究 成果如下： 在估算视图大小时，将o l a p 中的视图看成是包含给定列上的项集的集合，把 o l a p 中视图大小的估算问题转换为给定列上项集个数的估算，并提出了一 种新的视图大小估算方法f s c 。f s c 将视图中包含的项集划分为频繁项集和 非频繁项集两类，结合频繁项集技术和传统的数学估算方法，对给定数据 立方中包含的所有候选视图的大小进行估算。实验证明，与同类算法相比， f s c 的精度有较大的提高，特别是针对倾斜度较大的数据集。 将维度问相关性的分析问题转换成分析维度组合中包含的项集的关联性，定 义了项集的相关度和基于前者之上的维度之间的相关性度量，并提出了针 对倾斜度较大的数据集估算维度间相关性的c m m 算法。c m m 算法将维度组合 中包含的项集分成频繁项集和非频繁项集两类，通过将计算频繁项集相关 度和采样估算非频繁项集相关度相结合的方法估算维度间相关性的度量。 实验证明，该度量的提出能够有效的衡量维度间相互关联的紧密程度，c m m 算法具有一定的准确度，特别是针对倾斜度较大的数据集。 作为8 6 3 项目基于w e b 服务的数据库新技术的一部分，完成了一个基于 国产数据库的r o l a p 系统的一期开发，估算视图大小的f s c 算法将在后续 开发中被集成到物化模块，以获得更好的物化视图方案。 1 2 本文组织结构 本文是对频繁项集技术在o l p 中应用的研究和探索。第二章中对频繁项集 挖掘技术和o l a p 的相关知识进行了简要介绍，并回顾了视图大小估算和维度间 相关性分析两个问题的研究现状。第三章讨论了o l a p 系统中物化视图时必须解 决的视图大小估算的问题，提出了将视图大小估算分解为视图中包含的频繁项 集个数统计和非频繁项集个数估算的f s c 算法。第四章讨论m o l a p 中数据存储 时应考虑的一个问题：维度间的相关性分析。本文定义了维度间的相关性度量， 并提出了估算维度间相关度的c 删算法。c m l v t 算法通过将计算频繁项集相关度 和采样估算非频繁项集相关度相结合的方法估算维度问相关性的度量。第五章 对笔者参与研发的一个8 6 3 项目中的r o l a p 系统进行了简单的介绍，f s c 算法将 在后续开发中被集成到物化模块中。第六章对本文的工作进行总结和展望。 复旦大学硕士学位论文 3 频繁项集技术订o l a p 中廊用的研究 第二章研究背景 本章将主要回顾频繁项集挖掘技术、0 l a p 的相关知识，并介绍本文的研究 课题视图大小估算和维度间相关性分析的研究现状，这些将为后续章节提 供基础。 2 1 频繁项集挖掘技术和0 l a p 简介 2 1 1 频繁项集挖掘技术简介 于1 9 9 3 年提出的关联规则是当前数掘挖掘研究的主要模式之一 1 。所谓 关联规则挖掘，其目标是从数据库中找出形如由a 的发生而引起的b 的发生的 规则。这些从大量的数据中找到的项集之间的有趣的关联关系可以帮助许多商 务决策的制定和科学研究，如分类设计、交叉购物、基因组分析等等。 关联规则挖掘通常被划分为两个子问题解决： 频繁项集挖掘：找出所有满足条件的频繁项集集合。 由频繁项集产生强关联规则，这些规则满足最小支持度和最小置信度阈值。 由于第二个问题相对比较简单，大量的研究工作集中在第一个子问题 频繁项集挖掘上面。 以下给出频繁项集挖掘的相关定义： 定义2 1s 设i = i l ，i ：，i 。 为项的集合，d = 1 ：i t l i ) 为任务相关的数据库事务 的集合，设a 是一个项集，事务t 包含a 当且仅当a t 。项集a 的出现频率是 d 中包含该项集的事务个数1d 1 。包含k 个项的项集被称为k 一项集。 定义2 2 ：给定交易集d 和d 上的项集a ，项集a 的支持度s ( a ) = ld i f d i 。给 定最小支持度m i ns u p ，如果项集a 的支持度大于或等于m i n _ s u p ，则称a 为频 繁项集。 在实际运用中，m i n _ _ s u p 也往往使用支持度的绝对定义，即d 中包含a 的 交易数量id l ，也即项集a 的出现频率。在本文的后续算法中，一般使用出现 频率代替支持度，我们也不严格区分这两个概念。 定义2 3 ：频繁项集挖掘是在交易集d 中找出所有满足给定支持度阈值m i n _ s u p 的频繁项集集合l = a l a i a a ，西as ( a ) 七m i n s u p 复旦大学硕士学位论文 频繁项棠技术存o l a p 中m 用的研究 十多年以来研究学者们进行了大量的研究，提出了各种挖掘频繁项集的算 法。本文在这里将对两个最具代表性的算法进行简单的描述。它们的主要区别 在于它们对结果空间的构造方式不同，一个是基于广度优先思想，采取自底向上 逐层构造的a p r i o r i 算法，另一个是以数据压缩为基础，采取转换处理对象方式 的f p - g r o w t h 算法。 a p r i o r i a p r i o r i 2 4 算法由r a g r a w a l 等人提出，该算法也是挖掘频繁项集的最经 典和最有影响力的算法。在a p r i o r i 算法的基础上，为了提高效率和伸缩性， 人们研究出了很多改进算法，如 2 3 6 等，使得以a p r l o r i 为基础的频繁项集 挖掘算法日趋成熟实用。 a p r i o r i 的基本思想是通过对数据集d 的多次扫描来发现所有的频繁项集。 在第k 次扫描时只考虑长度为k 的所有项集。第一次扫描时计算d 中所有单个 项的支持度，生成所有长度为1 的频繁项集，后续扫描中，以上一次发现的所 有频繁k 一项集为基础，生成新的候选项集，即所谓的潜在频繁项集。然后扫描 数据库，计算这些候选项集的支持度，找到真正满足最小支持度闽值的频繁k + l 一 项集的集合。逐层迭代，直到不能找到更长的频繁项集。算法高效的关键在于 尽可能不生成和计算那些不可能成为频繁项集的候选项集，使候选项集的集合 较小。 f p g r o w t h f p - g r o w t h 3 是一种不产生候选项集挖掘频繁项集的算法，它采用分治策 略，将数据库中包含的项集信息压缩到一棵频繁模式树( f p - t r e e ) 中，并保留项 集间的关联信息。然后将这些压缩的信息分成一组条件数据库( 一种特殊的投 影数据库) ，每个条件数据库关联一个频繁项集，并对该数据库进行挖掘。 f p - t r e e 的每条路径代表一条交易，节点在路径中出现的次数按照节点所 代表的项在交易集中出现的次数排序。为方便树的遍历，创建一个项头表，每 个项通过一个节点链接指向它在树中的出现。扫描所有交易后得到一棵 f p - t r e e ，频繁项集挖掘问题转换成挖掘f p - t r e e 的问题。 f p - t r e e 挖掘过程如下：由长度为1 的频繁模式( 初始后缀模式) 开始， 构造它的条件模式基( 由f p - t r e e 中与后缀模式一起出现的前缀路径集组成) 。 然后构造它的条件f p _ t r e e ，并递归的在该树上进行挖掘。模式增长通过后缀 模式与条件f p - t r e e 产生的频繁模式连接实现。 复旦大学硕士学位论文 频繁项榘技术在o l a p 中廓用的研究 2 1 2o l a p 简介 o l a p ( o n - l l n ea n a l y t i c a lp r o c e s s i n g ) 4 技术是构建在数据仓库之上 的一项重要的数据分析技术。与传统的执行联机事务和日常查询处理的o l t p 系 统不同，o l a p 管理的是大量的历史数据，并提供汇总和聚集机制，支持复杂的 分析操作和对数据的多维视图，侧重对决策人员和高层管理人员的决策支持， 可以应分析人员的要求快速、灵活的进行大数据量的复杂查询处理，并以一种 直观易懂的形式将查询结果提供给决策人员，以便他们准确地掌握信息，制定 正确的方案，增加效益。 o l a p 的技术核心是“维”，通过把一个实体的多项重要的属性定义为维，使 用户能从不同角度对数据进行比较。因此o l a p 也可以说是多维数据分析工具的 集合。 2 1 2 1o l a p 中的多维数据模型 实体一联系数据模型广泛的应用于关系数据库设计之中，在此，数据库模式 由实体的集合和他们之间的联系组成。这种数据模型适用于o l t p 。然而，数据 仓库和o l a p 需要简明的面向主题的模式来进行数据分析。最流行的数据仓库模 型便是多维数据模型。 1 数据立方及其相关概念 数据立方：在多维数据模型中，数据被看作数据立方( d a t ac u b e ) 的形式。 数据立方允许从多个维度对数据建模和观察。数据立方由维和事实表定义。 维：维是关于一个组织想要记录的实体，是观察数据的特定角度。每一个维 都有一个表与之关联，称之为维表，描述维的具体信息( 维层次，成员类别等) 。 一个维往往存在细节程度不同的多个描述，这多个描述称为维的层次。多维数据 模型围绕中心主题组织。该主题用事实表表示，存放与维度相关的数值度量的信 息。 度量：度量是数据的实际意义，即描述数据是什么一般情况下，度量总 是一个数值指标，如人数，单价，销售量等，而1 0 0 0 则是该度量的值。 多维数组：一个多维数据可以表示为( 维1 ，维2 ，维n ，度量值1 ，度 量值n ) 。如某商品的销售数据就是按时间，地区和销售渠道组织起来的三维立方 体，加上度量销售额，就组成了一个多维数组( 地区，时间，销售渠道，销售额) 。 数据单元：多维数据集的取值称为数据单元。当多维数组的各个维都选中 一个维层次，这些维层次的组合就唯一确定了一个数据单元。 复且大学硕士学位论文 频繁项集技术no l a p 中应用的研究 2 多维数据库模式 多维数据模型可以以多种形式存在，最常见的是星型模式( s t a rs c h e m a ) 和雪花型模式( s n o w f l a k es c h e m a ) 。雪花型模式和星型模式的主要不同在于， 雪花型模式的维表是规范化形式，减少了冗余，节省了存储空间。由于执行查 询需要更多的连接操作，雪花型模式可能降低浏览的性能，因此不如星型模式流 行。 3 多维数据操作 o l a p 中包含的多维数据基本操作有：上卷( r o l l u p ) 、下钻( d r i l l d o w n ) 、 切片( s l i c e ) 、切块( d i c e ) 、转轴( p i v o t ) 等。它们使得用户能够从不同的角度、 不同的细节层次查询和浏览数据立方中包含的信息。 2 1 2 2o l a p 系统分类 根据数据的物理存储方式的不同，可以将o l a p 系统划分为三类：r l a p 、m l a p 和h o l a p 。r o l a p 使用关系数据库存放数据，将多维结构划分为维表和事实表， 完全用二维表示了多维的概念；m o l a p 通过基于数组的多维存储引擎支持数据 的多维视图；h o l a p 结合了上述两种技术，将大量的详细数据放置于关系数据 库中，而把聚集的结果以分离的m o l a p 方式存储。 2 2 研究现状 本小节中将主要介绍目前o l a p 中视图大小估算和维度间相关性分析这两 个问题的研究现状。 2 2 1 视图大小估算研究现状 对于o l a p 中视图大小的估算问题，前人已经做了不少的工作： 8 最早对于数据集中的属性值个数进行了研究，并提出当数据集均匀分布 时，可使用如下公式估算属性值个数：e = v ( 1 一( 1 1 v ) 。其中，v 为可能出 现的属性个数的最大值，n 为数据集大小。该公式被称为c a r d e n a s f o r m u l a ， 并在之后被广泛应用于视图大小的估算之中：当数据均匀分布时，m s ( v ) 为视图 的最大大小，i f l 为数据集大小，则视图估计大小为： e j ，( y ) - ms ( v ) ( 1 一( 1 一三页) 。7 ) ( 2 1 ) 爪j 1 7j 【9 】研究了实际应用中的数据集分布，指出大部分数据集分布都是非均匀的。【1 3 】 指出，如果数据在各个点上的频率分布变化很大，则称该数据集是倾斜的；数 复旦大学硕士学位论文 频繁项集技术柏o l a f 中琦用的研究 据的倾斜度对于视图的大小有着较大的影响，在数据集大小相同时，倾斜度越 大，则视图的大小越小。对于非均匀分布的数据集，【1 0 首先提出在采样估算 时应考虑到数据的倾斜情况。 1 1 提出的p s e 算法使用采样和a a r d e n a s f o r m u l a 相结合的方法，把从 样本集中计算得到的子视图的真实大小直接放大到数据集的全体对视图的大小 进行估算。 1 2 提出了影响数据立方大小的几个参数，如视图个数，视图最大 大小，数据集密度和数据倾斜度等，并提出了基于数学估算和无重复采样的s f 算法。s f 算法在将样本集中获得的子视图大小推广到整个数据集上时，统计样 本集中各个不同元组出现的次数，将其按一定的比例放大至整个数据集上，进 一步提高了估算的准确度。 1 4 针对满足二项式多分形分布( b i n o m i a lm u l t i f r a c t a ld i s t r i b u t i o n ) 的数据集提出了f m s 算法。f m s 以采样的方式获得分布的参数，再将该分布推 广到整个数据集上估算视图的大小。 1 5 对f m s 进行了改进，使用两个样本集 确定二项式多分形分布的参数，提高了估算的精度。 1 6 则假设数据集符合一 个更复杂的分布p a r e t o 分布，与 1 4 类似，通过采样获得p a r e t o 分布的参数， 并将其用于整个数据集上视图大小的估算。这类方法的共同点都是假设数据集 符合一个事先设定的分布，通过采样获得该分布的各项参数，再将该分布用于 整个数据集上视图大小的估算。虽然对于某些符合假设分布的数据集具有很好 的估算效果，但是并不具有普适性。 2 2 2 维度间相关性分析研究现状 关于维度间的相关性分析，其起源来自于统计学中事件的相关性。在统计学 中，设两个事件a ，b 发生的概率分别是p ( a ) ，p ( b ) ，a b 同时发生的概率为p ( a b ) 。 若p ( a b ) = p ( a ) p ( b ) ，则事件a 和b 是相互独立的，否则a 和b 是相关的。 目前在维度间相关性分析的研究方面，最深入的一块是函数依赖和近似函 数依赖关系的查找。函数依赖反映了现实世界中属性问的关联和数据的完整性 约束，对关系数据库的设计和分析起着重要的作用。通过发现函数依赖，数据 库管理员能够方便的对数据库进行维护，以及对它们的关系模式进行重新的设 计组织。其定义如下： 定义2 4 设有一关系模式r ，x r ，爿r 如果r 上的关系r 中的所有元组 满足：v t ，s r 若t i x 卜j 陋】，必有t a 】- s a 】，则称x ，a 之间存在函数依赖 ) 【_ a 。 函数依赖表明了属性维度间最强的关联程度，它不仅应用于数据库规范化 复旦大学硕士学位论文 - 8 - 频繁项集投术竹o l a p 中廊用的研究 设计，还在数据库管理、查询优化 2 0 、反向工程 2 1 等领域有着重要的应用 价值。 在实际应用中，某些属性维度可能近似的满足一方决定另外一方的情况，但 是数据集中可能存在一些噪声或者例外的情况导致不满足严格意义的函数依赖， 如西方人的名字( f i r s tn a m e ) 可以大致决定其性别，我们称其为近似函数依赖。 近似函数依赖也被用于数据库设计当中 2 5 。为了查找数据集中存在的函数依 赖和近似函数依赖，研究者们进行了大量的研究，提出了很多的方法 2 5 ，2 6 ，2 7 ，2 8 ，2 9 ，3 0 用以提高算法的效率。 对于数值类的属性，可以使用 3 1 介绍的相关性分析计算彼此之间的关联。 给定数值属性a 和b ，a ，b 之间的相关系数： r 柚一，( a - 至a ) ( b - 一b ) ( 2 2 ) ”一 o _ o o 其中n 为数据集条目数，a 和盼别是a 和b 的平均值，a 。和分别是a 和b 的 标准差： ( 2 4 ) 如果。结果大于0 ，则a ，b 之间一个随着另一个值的增加而增加，它们之间 是正相关的。_ ，越大，则一个蕴含另一个的可能性越大。如果_ j 等于0 ，则a ，b 之闻的取值是独立的。如果。小于o ，一个属性的取值随着另一个属性的取值 的增加而减小，a ，b 之间是负相关的。 但是等式2 2 仅仅适用于数值类属性相关性的分析，它只能计算两个维度问 的相关系数，且它所给出的正相关或负相关的概念是两个属性取值问互相依赖 增加或减少的关系。 对于维度间的相关性分析，现有的研究中没有相关性度量的统一标准，相 关性分析仍然局限在函数依赖分析、数值属性问的依赖关系分析方面，有待进 一步的发掘。 2 3 小结 本章简要介绍了频繁项集挖掘技术和o l a p 的概念，给出了频繁项集挖掘的 基本定义和求解思想以及o l a p 的相关知识。另外，我们还回顾了视图大小估算 和维度间相关性分析两个问题的研究现状。在后续的章节中，我们将在前人工 作的基础上对这些问题做较为深入的研究。 复旦大学硕士学位论文 频繁项集技术存0 l a p 中脚用的研究 第三章基于频繁项集技术的视图大小估算 为了提高o l a p 系统中查询的响应速度，我们往往要预先存储一些聚集的结 果( 也称物化视图) 。然而在进行物化视图选择时必须了解所有候选视图的大 小。为了阐述问题，举一个简单的例子： 例3 1 ：考虑一个关于某公司销售数据的关系表，其模式为：s a l e s ( i t e m ，s t o r e ， r e g i o n ，q u a n t i t y ) ，表中的每一行代表在某一地区的某种商店出售的某种商品 的销售数量。如表3 1 所示： i t e ms t o r e r e g l o nq u a n t i t y i 1s l r l q 1 1 1s 3r 2 q 2 i 2s 1 r l q 3 1 2s lr l q 4 i 3s 2r 3 q 5 i 1s lr 1 q 6 1 3s 2r 3 q 7 i 3s 2r 2 q 8 i 1s lr l q 9 i 3s 2r 3 q l o 表3 1s a l e s 数据集 从数据立方体的角度看，该c u b e 中包含三个维度：i t e m ，s t o r e ，r e g i o n 和一个度量：q u a n t i t y 。如果我们考虑该c u b e 上的所有聚集，可以得到八个视 图。按照它们g r o u pb y 的属性并列出其大小为( ) ：1 ：( i t e m ) ：3 ：( s t o r e ) ：3 ： ( r e g i o n ) ：3 ：( i t e m , s t o r e ) ：4 ：( i t e m ，r e g i o n ) ：5 ：( s t o r e ，r e g i o n ) ：4 ：( i t e m ， s t o r e ，r e g i o n ) ：5 。 基于该数据立方用户可能提出各种查询。例如：分析人员可能想要知道名 为i 1 的i t e m 在s t o r es l 的销售总量，该查询可用如下s q l 语句表示： s e l e c ts u m ( q u a n t i t y ) f r o ms a l e s w h e r ei t e m = i 1 a n ns t o r e = s l 为了提高该查询的响应速度，决定进行视图的物化并规定物化视图的存储 空间不能超过4 。在8 个视图中，( i t e m ，s t o r e ) 和( i t e m ，s t o r e ，r e g i o n ) 都 复旦大学硕士学位论文 1 0 频繁项集技术靠o l a p 中府用的研究 能够回答上述查询，但是由于后者需要的存储空间为5 ，超过了要求，因此选 择( i t e m ，s t o r e ) 进行物化。这样系统在响应查询时就不必从事实表中计算，而 直接从物化好的视图中计算i t e m = i l ，s t o r e = s l 的元组的q u a n t i t y 之 和即可。 可见，了解视图大小对于正确选择合适的视图进行物化以提高系统性能是 非常重要的。将每个视图实际物化然后计算其精确大小是不切实际的。因此， 我们必须找到一个合适的方法对视图的大小进行估算。 目前对视图大小估算这一问题，主要的方法有两类：第一类对数据集分布 情况没有要求，利用概率统计和数学估算的方法，计算相对简单但精度较低； 第二类是基于特定的数据分布模型，通过采样确定分布的参数进而估算，具有 较强的针对性。 不同于以往的视图估算技术，我们将尝试引入频繁项集挖掘的思想，较好 的解决数据立方中所有候选视图大小的估算问题。 3 1 问题定义 已知一个多维数据立方的基本表r 中包含n 个维度( 假设不考虑维层次) 。 则该c u b e 上的每个候选视图可用如下语句表示： s e l e c t4 ，4 ，4 ，o p t ( b ) f r o mr g r o u pb y 4 ”以 其中，a ，a s ，a k 为视图聚集的k 个维( 1 k n ) ，o p r 是s h i l l , a v g ，c o u n t 之类的聚集操作运算符，b 为度量属性。视图大小估算就是在给定c u b e 的情况 下，得到c u b e 中所有该类聚集的估计大小。 设多维数据立方中包含的总的维度数为n ，则该数据立方中包含的聚集视 图的个数为： l u r e = o