1、 本课题得到福建省自然基金资助 (A0310008)和福建省高新技术研究开放计划重点项目资助 (2003H043)。 黄宗毅 硕士，主要研究方向为数据仓库、数据挖掘、分布式数据库等。 薛永生 教授，主要演就 方向 为数据仓库理论与应用、分布式数据库、数据仓库、数据挖掘等。 翁 伟 硕士，主要研究方向为数据仓库、数据挖掘。 文 娟 硕士，主要研究方向为数据仓库、数据挖掘。 DSSMV-多维数据物化视图的动态选择策略 黄宗毅 薛永生 翁伟 文娟 蔡劲 (厦门大学计算机科学系 福建 厦门 361005) （ ） 摘 要 提出了多维数据中物化视图的动态选择策略 -DSSMV，其中包括候选视图选择算法
2、CVSA、改进的BPUS算法 -IGA算法 、物化视图集调整算法 MAVM和物化视图的动态调整算法 DMAVM。该策略削减算法的搜索空间，降低算法的复杂度 ，同时通过改进 BPUS算法，并增加调整算法从而提高了物化视图集对查询的响应性能，该策略还通过定时地判断查询视图类型分布是否变化来决定是否进行物化视图的动态调整，从而避免了物化视图集“抖动”的发生。通过分析和实验对比可以看到，该算法通过定时地执行可以显著降低管理员的工作的复杂度，保持物化视图集具有较好的响应性能。 关键词 物化视图； OLAP；动态选择；多维数据；数据仓库 Dynamic Selection Strategy of Mate
3、rialized Views of Multi-Dimensional Data Huang Zongyi， Xue Yongsheng， Weng Wei， Wen Juan， Cai Jin (Department of Computer Science, Xiamen University, Xiamen 361005, China) Abstract This paper presents DSSMV(Dynamic Selection Strategy of Materialized Views),an approach composed of four algorithms: CV
4、SA（ Candidate Views Selection Algorithm） ,IGA(The Improved Greedy Algorithm),MAVM(Modulation Algorithm of View Materialization),DMAVM(Dynamic Modulation Algorithm of View Materialization). CVSA is in charge of producing candidate view set, which is proven to be sufficient and necessary for selecting
5、 the best set of materialized views. IGA and MAVM are based on the Greedy Algorithm. DMAVM used the sample space to judge whether it is necessary to change the view set and restrain the number of views at very low cost. The comparative experiment indicates that DSSMV can be employed by the static al
6、gorithms to reduce effectively the amount of views beforehand, and the cost of static algorithms on space and time can be cut down to fit for online demand. Key words materialized view； OLAP( Online Analytical Processing)； dynamic selection； multi-dimensional data； data warehousing 1 引言 从某种角度看 , 数据仓
7、库是一组视图的集合。这些视图是从数据库或基库中分组聚集而成的 ， 其中在物理意义上实际存在的视图称为实视图 ； 而物理上不存在，当需要时从其他视图或基库中导出的视图称为虚视图。所谓视图的物化就是指以表的存储形式将虚视图转化为实视图。视图的物化策略对数据 仓库的查询响应时间有重要影响。 到目前为止，已存在许多物化视图的选择算法，这些算法通过不同的途径实现对物化视图的选择提高系统的整体效率 。 但总的来说都没有取得理想的效果 。 可以说，对多维数据物化视图选择仍然是一个有待于更深入研究的问题 。 2 相关工作 斯坦福大学的 Harinarayan在文献 1中首先提出数据立方体的格模型 ， 以此来描
8、述视图间的相互依赖关系 并 给出了简单的 BPUS算法来解决视图的选择问题 。 这一算法的效果和最优解的比值不小于 1-1/e， 在此基础上，文献 2讨论了带有 B-树索引的物化视图的选择问题；文 献 3提出了以物化视图的尺寸为选择标准，其算法时间复杂度为O(nlgn)的选择算法 PBS；文献 4提出了一系列启发式视图选择的算法框架；而文献 5， 6将遗传算法获取最优解的能力用于最优物化集的选择，并在降低算法复杂度方面进行了研究。 这些方案均基于查询的分布情况是已知的 。 由于 OLAP系统中的查询是随机的，选择物化视图不可能确知系统中的查询集合，因而现有 OLAP系 统中物化视图的选择方案均
9、假设这些查询在综合数据上是均匀分布的，或者用户可以提供其分布概率 。 实际上，均匀分布的假设常常不能成立，由用户提供查询的 分布概率也是强人所难 。 文献 7提出的基于单位空间上的查询频率的视图选择方法 (FPUS)，以系统收集的查询集合及其频率为选择物化视图集合，能较好地反映查询的需求 。 但 FPUS算法没有考虑视图间的依赖关系 并且 即时调整策略导致物化集存在频繁的“抖动”。因此该算法仍没有有效地提高系统的效率。 以上算法都忽略了实视图的维护时间 ， 仅考虑实视图所占存储空间大小这一外部限制条件 。 在实际应用中 ， 实视图的维护时间同样限制了我们不能将所有的视图实体化 。 于是 Gup
10、ta和 Mumick给出了一种在给定的约束条件为总的视图维护时间 S下 进行视图选择的 ITGA(Inverted-Tree Greedy Algorithm)算法 8。 综上所述， 目前提出的方法多采用一元评价标准 ， 或者以实视图所占存储空间为标准 ， 或者以实视图的维护时间为标准 ， 当性能评价标准是二元或二元以上时 ， 没有给出相应的 选取原则 。 本文在以上方面进行了更为深入的探索，基于用户查询分布和 多维数据格， 提出了物化视图动态选择的处理策略 DSSMV，包括候选视图选择算法CVSA、改进的 BPUS算法 -IGA算法 、物化视图集调整算法 MAVM和物化视图的动态调整算法 D
11、MAVM。策略依 据用户查询分布稀疏性特点对视图节点进行合理有效的筛选，有效地提高算法的效率；在选择物化视图时综合考虑了 存储空间、维护开销和查询性能三种因素 ；最后在运行中挑选最佳的调整时机，防止 物化集出现频繁的“抖动”。 3相关概念 定义 1(多维数据格 1). 不同综合程度的多维数据集合称为一个数据结点。一个多维数据模式中的所有数据结点构成一个格，其中 (1) 数据结点间的偏序 ( )定义为：给定结点u和 v， u v当且仅当仅利用 v即可计算出 u。这意味着 v的各维上的级别均低于或等于 u的相应维上的级别； (2) 格中最大元记 为 Vbase。 Vbase上各维的级别为该维中最低
12、的。一般假定 Vbase的数据是已知的，可利用它计算格中任意结点的数据。 例 1考虑销售业绩的多维数据模式 9，其中的维有两个：产品和销售地点，其度量数据为销售量。两个委的层次结构分别如图 1所示。其中 ALL表示对维中所有成员的综合。 Dimension Product :ProductID Category ALL Dimension Location : StoreID Area All 产品维， 产品， 种类， 地点维， 商店， 地区 图 1 维的 层次结构 例 1中多维数据的格如图 2所示，其中 P， S， C，R ， A 分 别表 示 ProductID, StoreID， Are
13、a ， Category， Area和 ALL， Vbase=(P， S)。 图 2 例 1种多维的数据的格 在实视图的选择过程中，需要再估计一个数据结点 v的尺寸 |v|。文献 10讨论了解决该问题的多种方案。 定义 2(多维数据上的查询 6). 多维数据集合MD上的查询 q是对 MD中某一数据结点的切片或切块。可以将 q表示为由 d个二元组组成的 d组：(l1,R1),(l2,R2), ,(ld,Rd)，其中 d为 MD的维数，li表示维 di的某一级别， Ri表示在 li上的选择范围。若没有对 li的范围进行限制，可以将 (li,Ri)简记为li。若 li=ALL，则维 i的二元组可以不
14、出现在查询中。 查询 q所访问的数据结点称为 q的基，记为 q。若 q=(l1,R1),(l2,R2), ,(ld,Rd) ，则q=l1,l2, ,ld。 查询间的偏序关系 定义为：对于查询 p和 q，若 q的结果可以用来响应 p，则有 p q。显然，若p q，不但要求 p q，而且用来生成 p的数据均应包含在 q中。 定义 3(实视图的选择问题 ). 实视图的选择问题就是在给定存储空间 Space的限制下，选择哪些视图物化可以最大限度地提高查询和维护的综合效率。 4 物化视图动态选择的处理策略 4.1 候选视图选择算法 CVSA 在系统构建阶段，我们粗略地给出一个初始用户查询集 Q0=q1,
15、q2, ,qn；在没有统计数据条件下，可以根据用户需求和管理员的经验确定。 相对P,S P,R CS P,A C,R A,S A,A C,A A,R 于所有的视图结点用户查询集 Q0在多数情况下只是对应其中的一小部分，查询稀疏性这一特点表明使物化视图总代价取得最小的相关视图只是所有视图中的一部分。 定义 4(影响视图） .一个查询 qi的查询结果通常可以从多维数据格图的多个视图结点计算出来，其中计算代价最小的视图称为查询 qi的影响视图vi。 对数据仓库的每一个查询 qi,可以按其 group by子句在多维数据格图上找到相应的影响视图 vi，设 vi和 vi的所有父结点构成的集合为 fath
16、er(vi)， qi可以从 father(vi)中的任何一个视图得到查询的结果。 定义 5(视图的查询概率 ). 以视图 v为其影响视图的查询的概率之和称作该视图的查询概率，用p(v)表示。 定义 6 (子视图 ). 对于视图 v，若 u与 v至少满足 下列条件之一： (1)u v,即 u与 v满足偏序关系且 |u|0 CV=CV vi； return (CV,p)； 通过该算法得到候选视图集 CV以及每个候选视图的查询概率 p。 之所以选择访问概率大于零的视图作为候选视图，是因为当该视图 vi查询概率和访问概率都为零时，若 vi物化，则显然 vi和 Q0的成员没有相互关系，所以对查询收益没有
17、影 响，但是 vi既然属于物化视图集 V，则必然增加了更新代价，同时也不会对 Q0的成员更新提供任何帮助（不会降低它们的更新代价），所以势必造成视图总代价的增加，从而与实视图的选择问题定义矛盾。 4.2 多维数据物化视图选择算法 4.2.1 代价模型 预先物化一部分视图虽然可以达到加速查询处理效率，降低存储空间的目的。但另一方面 ,当数据源更新时需要更新物化视图。因此物化视图选择是查询性能和维护开销间的复杂权衡问题。本文将二者的加权和称为操作开销 。 定义 8(访问者集合 ). 对于实视图 v，为响应其上的查询而访问 v但不 同于 v的那些视图的集合称为 v的访问者集合，记为 Q(v)。显然，
18、若 u Q(v)，则 u没有实化， u v且不存在另外的实视图 w，使得u w但 |w|=1)，时间复杂度变为22( / )On ，即 2 2 2 2lim ( / ) / 1 /n nn ，随着 的增加，算法时间复杂度呈指数趋势急剧下降，极大的降低时间复杂度。 4.2.3 物化视图的调整 BPUS算法的主要缺陷是每一步选取的视图都作为将来要物化的视图，没有考虑每选择一个新的视图后，已选视图的效益值出现衰减，而这一变化可能会使其应从已选视图集中删除。所以需要根据查询概率对算法 2得到的物化视图集 进行调整，用查询概率高的视图替代已选出的物化视图集 V中收益减少太多的视图。 算法 3. 物化视图
19、集的调整算法 MAVM MAVM(Space,CV,V) Search=True； Vtemp=； Vremove=； while (CV null& V null & Search=True) v=CV中 f(v)/|v|最大的视图； u=V中 f(u)/|u|最小的视图； if (f(v)/|v|)|v| if C(V v)C(V-w) V=V-w ；Space=Space+|w|； else Vremove=Vremove w； If V=Vremove Search1=False； else Vtemp=Vtemp w； V=V-w； if (Search1=True and V=nu
20、ll) or (Search1=False and Vremove null ) CV=CV-v； V=V Vtemp； return V； MAVM算法的时间复杂度为 O(nlog2n)。如果采用适当的辅助存储， MAVM的时间复杂度可以大大降低。当系统中经过算法 1筛选后的候选视图数量还是比较多时，可以为这些候选视图按照 p(v)/|v|建立索引。这样其时间复杂度仅相当于所选择的物化视图的个数。 4.3 物化视图的动态调整 由于数据仓库的时变性特点，随着用户的使用，新的查询的增加，系统中的查询的分布情况亦可能发生变化，使得原有的物化视图集合不再适应新的查询分布情况，从而导致查询响应性能的下
21、降，为此要求物化视图集及时做出必要的调整，以往常见的方法需要数据仓库管理员根据经验和需求的变化以 及相关的统计信息，选择适当的时机（一般在数据仓库离线状态下）重新执行视图选择算法。然而各种因素制约了这一机制，由此对物化视图在线动态调整提出了更为迫切的要求。研究人员从动态的角度提出了一些时间复杂度较低适合在线的算法，文献 11提出一种建立于 cache机制的 DynaMat系统，但其最优集的选择显得较为粗糙，缺乏相应的理论依据；而文献 7采用一种实时调整策略 -基于动态的 FPUS算法，所谓实时调整，就是在计算查询后立即调整物化视图集合，这种实时调整发生在执行一个查询之后。但是这种实时调整策略会
22、导致物化集存 在频繁的“抖动”。 所以我们选择在一定的统计周期内，观察多维数据格模型中视图集合的查询分布概率有没有变化，若当前的统计周期与上一统计周期内视图集合的查询分布概率没有发生变化，则无须进行物化视图的动态调整；否则调用物化视图动态调整算法进行物化视图的调整。本文以固定的查询发生次数作为一个统计周期。查询概率 pi(n)指的是在第 n个统计周期 T(n)里视图 vi发生查询的频率（查询次数 /统计周期）。 定义 11 （有效样本空间） 在当前的统计周期T(n)内，发生的 n个查询事件集合 q1,q2, qn，称为有效样本空间， 记作 Qset(n)。 Qset(n)用来描述当前的查询趋势
23、，预示未来可能发生查询趋势。因为对于随机分布的查询，选取最新的数据才能反映出查询变化，并可以用来预测未来可能发展的趋势。 定义 12 （有效样本集合）在 Qset(n)内，查询事件相对应的影响视图集合为 v1,v2, ,vk，称为有效样本集合，记作 Vset(n)。 通过观察 Qset(n)内查询代价的数学期望的变化，对查询视图类型分布变化来进行定量的估计，数学期望为：1( ) ( )nn i iiE V p n v。但 E(V)并不能完全判断视图分布 情况，同时还需要通过计算均方差来判断查询代价同 E(V)的偏离程度。有效样本空间 Qset(n)内的方差公式： 21( ) ( ( ) ) (
24、 )nn i n iiD V v E V p n 但是在两个相邻的样本空间内若两个视图 vi和 vj， |vi|=|vj|，在 T(n-1)周期中 pi(n-1)=p1， pj(n-1)=p2， p1p2但在 T(n)周期中， pi(n)=p2， pj(n)=p1，而其他的视图的查询概率在两个周期中都不改变，则其查询代价的数学期望和方差都相等，但是其视图集合的查询分布概率也发生了本质变化，可能原本在物化视图 集中的 vi因为查询概率的减少应该被 vj替换出物化视图集，所以还需要通过计算相邻两个样本空间中视图查询概率变化约束条件： 21( ) ( ( ( ) ( 1 ) ) )ni i iiG
25、v p n p n v 所以在两个相邻样本空间内如果数学期望En(V) En-1(V)，且 Dn(V) Dn-1(V)，且 G(v)up_ limit，则两个样本空间查询视图分布基本一致，反之，实体化视图就需要调整。 物化视图的动态调整算法首先根据最近的统计周期中的有效样本空间 Qset(n)作为输入，调用算法 1，计算出有效样本集合中的每个视图查询概率，之后计算数 学期望 En(V)和方差 Dn(V)，并同上一个样本空间 Qset(n-1)的数学期望 En-1(V)和方差 Dn-1(V)比较，此外还要计算 G(V)并与约束 up_limit比较。如果没有达到上限 up_limit，则无须对物
26、化视图进行调整；反之，实体化视图就需要调整，并调用动态调整算法。 算法 4.物化视图动态调整算法 DMAVM 输入：用户查询集 Qset(n)，统计出的该周期内各查询集的查询概率 fq，多维数据格图 V0，可用空间 Space，样本空间 Qset(n-1)的数学期望 En-1(V)和方差 Dn-1(V) 输出：调整 后的物化视图 V Procedure DMAVM(Space,Qset(n),fq,V0,En-1 (Vset(n-1),Dn-1(Vset(n-1) (Vset(n),p(n)=CVSA(Qset(n),fq,V0)； If Check_Modify(Vset(n),p(n),
27、En-1(Vset(n-1), Dn-1(Vset(n-1) /根据上述思想判断是否要动态调整 IGA(Space, Vset(n)； Return V； 5 实验与性能 分析 5.1 实验设计 目前各种视图选择算法中，较具代表性的选择算法有 BPUS和 PBS，其中 PBS算法较快达到 O(nlgn)，然而该算法需要一定的前提条件（要求其格图属于SR-hypercube lattice） ，使该算法在实际应用中受到较大的限制。为了使算法对比更具有普遍性，实验采用 DSSMV策略与单纯的 BPUS相比较。 测试环境中的硬件平台为 DELL OPTIPLEX GX270(P4 2.60GHz C
28、PU， 512M RAM)，运行 Windows 2000 Sever操作系统，数据库平台为 Oracle 8，算法用 Microsoft Visual C+ 6.0实现。 5.2 性能分析与对比 BPUS算法的时间复杂度为 O(kn2)，在允许物化视图数 k相同的条件下，算法的时间消耗与结点总数 n的平方成正比，所以减少 n，对于降低算法的开销意义重大。 DSSMV策略的开销包括 4部分： 候选视图集合 CV的构造为 O(d2)， d为与用户查询直接对应的视图数量。 IGA算法第一步进行初步物化视图选择为 O(km2)， m为生成候选视图的数量， m=n/ 。 MAVM算法对初步选择的物化视
29、图集进行调整O(mlog2m) 物化视图动态调整算法 DMAVM中 判 断是否要动态调整的 Check_Modify算法 O(m)。 我们测试数据集都有 1个事实表，每个维表都有 3个层次。在三个实验中我们都利用模拟的查询发生器产生 2000次查询事件，统计周期为 100次，其查询的分布满足 2 8原则，即 80%查询量产生于20%的查询。 实验一中我们将数据集的维数从 3个维逐渐增加到 5个维。每次统计周期结束后分别调用 BPUS算法和动态调整算法 DMAVM进行比较。 BPUS算法所面对的视图数量分别为 64， 226， 974，经过 候选视图选择算法 CVSA处理后候选视图的平均数量为：
30、62， 167， 398。参与选择算法的 视图数得以大幅减少。因为每个统计周期中的候选视图数量不同，我们取其平均值作为代表。具体的对比实验如图 3所示： 图 3 算法时间开销比较0501003 4 5维数/ 个时耗/sBPUSDSSMV由上图可见， DSSMV策略相对于单纯的 BPUS算法其算法时间开销很低，完全可以适用于物化视图的在线动态调整。此外，在维数较少时两种算法的时间开销差别不是非常明显，但是随着维数的增加， BPUS算法的时间开销成指数增加，而 DSSMV策略的时间开销增加有限。这是因为当数据集维数较少时如 3个维时，待筛选的视图总数不大仅为 64个，在统计周期内（ 有效样本空间
31、Qset(n)执行了 100个查询），大部分视图都属于 有效样本集合 Vset(n)，所以 经过候选视图选择算法得到的候选视图数量为62，和 BPUS算法相差不大，甚至 DSSMV算法的时间开销还要大于 BPUS，因为它包括了候选视图算法CVSA和 MAVM算法等算法的开销。但是当数据集维数增加后， DSSMV算法的优势就体现出来，由于候选视图算法对视图的筛选作用，以及在统计周期内有限的查询数量对应的 有效样本集合 Vset(n)有限 ，使得参与 DSSMV算法选择的视图数得以大幅度减少，从而大大降低 了算法的时间开销。 虽然二者选择算法中都包含有 BPUS算法的思想，但是他们面临的视图空间有
32、很大差异，而且DMAVM算法在进行改进的 BPUS算法的选择后还对物化视图集进行了适当的调整， 所以两种算法选择的物化视图集会有不同，为此有必要对其物化视图集实际的查询响应性能进行比较。在此本文采用平均响应时间来衡量查询响应能力。实验二中我们在每500次查询后，计算其平均响应时间并进行比较。具体结果如下图所示。 图 4 查 询响应时间比较05101520500 1000 1500 2000查询次数/次平均响应时间/sBPUSDSSMV由上图可见， DSSMV策略所选择的物化视图集在对查询的响应性能方面优于 BPUS算法，其主要因为 DSSMV策略中 物化视图集调整算法 MAVM将 收益值出现大
33、幅度衰减的视图从已选视图集中删除，取而代之以能使总体查询代价减少的视图。 实验三中我们 希望判断 当查询类型分布发生变化时，算法对物化视图集的调整是否改善了查询代价。 实验中我们 在每次统计周期结束时执行 物化视图的动态调整算法 DMAVM，为方便 结果显示，我们仅列出了前 1000次的结果。如下图所示。 图 5 调 整算法前后查询代价比较100120140160100 200 300 400 500 600 700 800 9001000查询次数/次查询代价调整前调整后我们发现调整后的数学期望总是比调整前要小，说明 算法有效地降低了查询代价。图中三个查询区间没有对物化视图进行调整，分别在 4
34、00500， 700 800和 800 900三个查询区间，这是因为在这几个区间查询视图分布同上一个查询区间的分布近似，所以没有进行物化视图调整。 6 结论 本文的提出的 DMAVM算法通过削减算法的搜索空间，降低了算法的复杂度，同时通过改进 BPUS算法，并增加调整算法提高了物化视图集对查询的响应性能，该策略通过定时地判断视图查询分布是否变化来决定是否进行物化视图的动态调整，避免了物化视图集的“抖动”。通过分析和实验可以看到，该算法通过定 时地执行可以显著降低管理员的工作复杂度，保持物化视图集具有较好的响应性能。 参考文献 1 V Harinarayan, A Rajaraman ,J D
35、Ullman. Implementing data cubes efficiently.In: H V Jagadish, I S Mumick eds. Proc of the 1996 ACM SIGMOD Int l Conf on Management of Data. New York: ACM Press,1996.205216 2 H Gupta, V Harinarayan, A Rajaraman,et al. Index selection for OLAP. In: A Gray, Larson,Per-ke eds. Proc of the 13th Int l Con
36、f on Data Engineering. Los Alamitos, CA: IEEE Computer Society Press, 1997. 208 219 3 A Shukla, P M Deshpande,J F Naughton. Materialized view selection for multidimendional datasets. In: Proc of the 24th Int l Conf on VLDB. San Francisco: Morgan Kaufmann,1998.488 499 4 H Gupta. Selection of views to
37、 materialize in a data warehouse. The 6th ICDT,Delphi,Greece,1997 5 J Yang, K Karlapalem, Q Li. Algorithms for materialized view design in data warehousing envirionment. In: Proc of the 23rd Int l Conf on VLDB. San Francisco: Morgan Kaufmann, 1997.136 145 6 C Zhang, X Yao, J Yang. An evolutionary ap
38、proach to materialized views selection in a data warehouse environment. IEEE Trans on Systems, Man and Cybernetics, Part C,2001,31(3):282 294 7 谭红星，周龙骧。多维数据实视图的动态选择。软件学报，2002， 13(6):1090 1096 8 Gupta H, Mumick IS. Selection of views to materialize under a maintenance cost constraint. In: Lecture Not
39、es In Computer Science 1540: 1999.453 470 9 R Agrawal, A Gupta, S Sarawagi. Modeling multidimensional databases. In: A Gray, Larson Per-ke eds. Proc of the 13th Int l Conf on Data Engineering. Los Alamitos, CA: IEEE Computer Society Press, 1997. 232 243 10 A Shukla, P Deshpande, J F Naughton,et al.
40、Storage estimation for multi-dimensional aggregates in the presence of hierarchies. In: T M Vijayaraman, A P Buchmann, C Mohan eds. Proc of the 22nd Int l Conf on Very Large Data Bases. San Francisco: Morgan Kaufmann,1996.522 531 11 Y Kotidis, N Roussopoulos. DynaMat: A dynamic view management system for data warehouses. The 1999 ACM SIGMOD Int l Conf on Management of Data, Philadelphia,Pennsylvania,1999
