基于关系数据库的ROLAP实视图的选择

基于关系数据库的ROLAP实视图的选择：0 引 言

ROLAP是OLAP(联机分析处理)中使用最广泛的一种类型，其主要功能是管理决策所需要的总结数据。总结数据一般都涉及多表连接和分组聚集操作，提高这些操作的性能成为提高OLAP操作响应速度的关键，而总结数据一般以实视图(Materialized View，MV)的形式出现在数据库中。

目前主要有三种方法来提高ROLAP查询的效率。一是实化(预计算并存储)模拟视图集中的一些视图，聚合预先计算好的数据汇总，改进查询响应时间。考虑到不破坏源数据库的完整性，可以把聚合数据存储在与源数据库同构的另一个关系数据库中。二是即席查询策略，这种针对OLAP查询处理的方法主要是通过在基表和实视图上使用一些快速存取结构来实现，可参考利用一些专门针对数据仓库和OLAP的索引技术，如标准B＋树索引、位图索引等。三是采用高性能软硬件并行计算机系统结构，实现采样和并行计算技术。使用最广也最实用的就是第一种方法。在查询时，可用不同的实视图实现同一查询，而选用哪一个实视图查询最有效就存在查询优化问题。

基于关系数据库的ROLAP实视图的选择：1 实视图的选择

实视图选择问题(View Selection Problem，VSP)已经被证明为NP完全问题，获得全局最优解的唯一办法就是遍历所有可能解。从理论上来讲，全局最优算法求得的解应是全局最优的，但由于在实际中对实视图选择问题参数估算存在不可避免的误差，所以尽管全局最优算法付出的搜索代价十分庞大，也不一定能得到全局最优解。在许多具体应用中，只希望系统能较快地给出一个较优集合，即在系统资源(存储器、CPU)有限的条件下为了最大限度地提高OLAP查询分析效率如何选择一部分总结数据作为视图实体化存储。

由基表可以计算出不同聚集程度的视图，这些视图之间也可以相互推导计算。所有这些由基表计算出的不同聚集程度的视图集合上的推导计算关系是严格意义上的格关系。定义集合A＝{x︱x是所有可由基表计算出的不同聚集程度的视图}，在集合A上的二元关系R＝{＜v1，v2＞}v1∈A∧v2∈A∧实视图v1可以由实视图v2计算得到}，记R为≮，称＜A，≮＞为格。从基表可计算出的视图个数如式(1)所示：

Ni——设有维D1，D2，…，Dm，各个维的维层次个数分别为N1，N2，…，Nm。

在维和维层次数量较大的情况下，视图个数将会很大，要实化每个视图是不现实的，否则查询效率得到显著提高的代价是实视图存储空间膨胀以及实视图构建和维护的效率急剧下降。因此选择一定量的视图实化，在存储空间、CPU时间和查询分析响应时间上达到一个最佳平衡点是提高ROLAP系统查询效率的关键。综合考虑实视图所占存储空间及实视图的维护时间做为评价标准，考虑新选择的视图对已选视图的相对效益值产生的影响及查询的分布，文中提出了一种改进的实视图选择算法，实现简便而且保证了实视图的使用效果。

VSP问题严格定义为：给定一格关系＜A，≮＞(其中集合A＝{x︱x是所有可由基表计算出的不同聚集程度的视图}，≮为集合A上的二元关系，≮＝{＜v1，v2＞}v1∈A∧v2∈A∧实视图v1可以由实视图v2计算得到})、约束条件集CS和系统效益评价函数B(v，MV)，选择A的子集合MV，得MV＝{v1，v2，…，vk}，对MV中的所有视图实体化，使得在满足CS中所有条件下，系统的整体查询响应时间最优。

其中B(v，MV)是MV中的视图实体化后ROLAP系统查询效率、构建和修改代价及存储空间代价的综合评价函数。为了保证＜MV，≮＞仍然是格关系，最粗粒度视图或最细粒度视图中的一个必将包含在MV中。为了减少计算量，本算法选择最细粒度进行预先计算。

对于系统效益评价指标B而言，考虑到如下因素：

(1)事实表定义为F，其属性集A(F)＝{d1，d2，…，dn，m}，其中di(1≤i≤n)为外键，m为度量字段，度量字段的个数对于问题的研究结果没有影响，因此在文中只列出1个作为代表。n个维表定义为Di(1≤i≤n)，其属性集A(Di)＝{di，di1，di2，…，dih}，其中di为各维表主键，dij(1≤j≤h)为维表各列字段。

视图定义为V，属性集A(V)＝{m，d1i，d2j，…，dnk}，其中m代表该视图的聚合数据，dij(1≤i≤n)(1≤j≤h)表示该视图在维度i上聚集到j层次。

(2)查询定义为Q，查询Q所形成的视图记为R(Q)。给定视图u和v，u∈v当且仅当仅利用视图v即可计算出视图u，这意味着视图v在各维上的级别均低于或等于视图u在相应维上的级别；对于查询p和q，若查询q的结果可以用来响应查询p，则有p∈q。显然，若p∈q，即要求R(p)∈R(q)。

(3)视图Vi的查询频率记为fq(Vi)，每次查询后Vi的访问频率都进行更新。Vi的更新频率记为fr(Vi)，Vi更新所涉及到的记录大小记为Lr(Vi)，fr(Vi)和Lr(Vi)均在增量更新操作发生时改写。

(4)视图Vi的大小记为L(Vi)。由于实视图是由事实表和维表相连接并通过在某些维属性上聚合而成，故实视图的大小必定小于源事实表的大小，如果事实数据在聚合维属性上的分布是稠密的，那么实视图的大小一般小于等于多个聚合维属性大小的乘积。

(5)视图从的父视图记为P(Vi)，P(Vi)是视图格关系哈斯图中可以直接推导出Vi的视图中最小的一个，在元数据设计中记为“已实体化视图的推导关系(哈斯图结构)”，P(Vi)的大小为L(P(Vi))。

(6)当选择视图从进行实化时，给查询代价带来的影响由以下两部分组成：一是对查询Qi(R(Qi)＝A(Vi))而言，其查询结果就是实化视图从，而不必从视图P(Vi)产生。

(7)A的子集合MV中视图个数为常数C，本系统在创建聚合时参考了微软的Analysis Services工具，首先由用户选择聚合预期达到的目标，为聚合指定存储空间限制，可输入以兆字节(MB)或千兆字节(GB)为单位的最大存储大小或指定要预先计算的聚合数量，这样可以估算得到常数C。

(8)视图从的效益评估值记为B(Vi)。

综上给出一个相对综合的效益评价指标：B(Vi)＝B1＋B2－Lr(Vi)fr(Vi)，即：

由式(2)可以看出视图Vi的存储空间越大、查询频率越低、更新频率越高则B(Vi)值越小。该算法虽然不能得到全局最优解，但是实现相对简单且兼顾了存储、查询、更新等诸多方面从而可以在一定条件下得到较优解。

在具体实现时，首先将视图可能用到的所有维度和级别按序编号，记录在维度信息表中。其次，对于每个可能实例化的视图Vi(Vi∈A)计算其大小，记录在视图实体化信息表中。视图实体化信息表记录了可由事实表导出的所有视图的基本信息，包括视图名称、视图构成(记录在每个维度上的聚合程度，具体用维度级别表示)、视图大小、使用频率、更新频率、相对效益以及是否实化等信息。

随着系统的不断运行，视图的效益评估值不断变化，系统也将重新选择视图进行实体化，即保证被实体化的视图始终是效益评估值最高的前几个视图。实视图动态调整方案的实质是贪心算法，虽然不能保证求得最优解，但一般能求得近似于最优方案的较好方案。

基于关系数据库的ROLAP实视图的选择：2 算法性能评估

算法性能评估实验在本地IntelPentiurn 4 1.80 GHz，256M内存，运行Windows Server20OO Server Enterprise Editlon操作系统的PC机上进行。实验案例共涉及到1个事实表，3个维表，其中事实表有168553条记录，实际数据存储在ACCES 2000格式数据库中。实验结果如表1所示。

表1 性能评估表

从表1可以看出，数据存储空间的大小随实视图的个数增加而增长，ROLAP查询平均响应时间随实视图个数增加而减少。在实视图个数为0～15个时，存储空间基本呈线性增长；而在实视图个数为15个以上时，存储空间增长比例显著加大。存储空间增长呈现出增长—快速增长趋势，而查询响应时间的降低则呈现出降低—快速降低—较缓慢降低的过程，这种变化过程在维度较小的情况下尤其明显。

当实视图数量较少时，ROLAP查询响应时间无明显改善。同时，当实视图数量达到一定数目后，再增加实视图数目对提高查询效率的作用也越来越小。由此可见添加了一定数量的实视图并采用改进的VSP算法提供OLAP服务，虽然存储空间随着实视图个数的增加有所上升，但是平均相应时间却有明显改善。因此只要设定恰当的实视图的个数，在存储空间和查询效率之间取一个恰当的平衡点，完全可以在系统资源允许的范围内提供高效的OLAP服务。