摘要
在当今竞争激烈的现代经济中，战略性业务决策制定变得更加复杂、富有挑战性和重要性。（战略性业务决策：战略决策。按决策的范围和决策的重要性划分，决策可以分为战略决策、战术决策、业务决策。）因此，管理者一直在使用决策支持系统来帮助他们做出准确、高效和有效的决策。
这些系统需要花费数小时和数天的时间来处理大量的数据集，以便找到回答分析型查询的相关信息。因此，查询响应时间很长。
通过选择和物化可以为分析型查询提供答案的预计算视图，可以大大缩短响应时间。
本文试图选择最佳视图集，这将大大缩短分析型查询的响应时间。
为此，提出了一种基于蜜蜂繁殖优化模型的视图选择算法（HBMOVSA），该算法在多维晶格中从所有可能的视图中选择Top-K视图。
实验结果表明，与最基本的视图选择算法HRUA相比，HBMOVSA能够更好地选择出质量更好的视图。
1引言
在当今高度竞争和快速波动的经济形势下，战略型业务决策变得比以往任何时候都复杂、富有挑战性和重要性。
为了实现高效、有效的决策，人们开发了决策支持系统（DSS）。他们的相对成功已经导致许多组织采用DSS，以便了解他们的业务，以便做出基于事实的、准确的、经济的和及时的决策，以更好地维持其业务可行性。DSS是一种基于计算机的交互式系统，方便管理人员、分析员或知识工作者使用模型和分析工具分析数据，以便更准确、及时地获取有关其业务的信息和知识，以帮助他们做出战略决策。提供给DSS的数据质量至关重要。
数据仓库（DW）是为DSS提供大量历史的、面向主题的、集成的、非易失的、时变的和高质量数据的基础数据体系结构，以便于数据分析以实现高效决策。DW包含详细的数据和汇总数据。
管理者使用在线分析处理（OLAP）工具，这些工具具有嵌入模型，执行复杂的业务分析，以获得有关其业务的新信息和知识。一般来说，OLAP查询本质上是即席的和复杂的；它们是计算密集型的。OLAP查询，当直接针对DW的基表提出时，需要花费数小时和数天的时间来处理它，以获得所需的信息。这些信息可能会导致分析员触发另一个OLAP查询，并且这个过程会重复，直到分析员觉得已经获得了决策所需的所有信息。这种分析不仅速度慢、效率低，而且降低了由此获得的信息的价值。
如今，获取新的业务信息和知识不仅很重要，而且获得这些信息和知识的速度对于做出战略性和竞争性决策也变得至关重要。信息的价值随着获取时间的推移而减少。许多公司甚至开始每小时更新一次DW，以获得最新的实时信息。为了缩短OLAP查询处理时间，加快分析处理速度，人们开发了物化视图、索引技术、查询评估技术、查询优化器等技术。
本文主要研究如何使用物化视图来减少OLAP查询处理时间，从而减少分析过程中获取信息的时间延迟。
视图是DW的一个或多个维度表的子集，由OLAP查询定义，以便从中获取某些必需的信息。它是从一个或多个大规模维度表中临时计算的，并且由于大量昂贵的连接操作，计算非常昂贵。它大大增加了查询处理时间，使分析过程效率下降和降低了从中获得的信息。视图是虚拟的和不稳定的，每当再次提出过去的查询时，都必须重新计算视图；这种查询处理方法显然非常低效。
如果识别出频繁出现的查询，并且由这些查询定义的视图被预先计算并存储在DW中，则OLAP查询处理性能可以大大提高。由于视图的这种一次性计算，查询可以直接使用这种预先计算的视图，避免在大型维度表上重新计算昂贵的连接操作。此外，这些预先计算和存储的视图中的一些不仅可以用于回答针对它们的查询，还可以用于回答正在访问其子集的其他查询。这种预先计算和存储的视图称为物化视图。
随着维度表数量的增加，可能的视图数量呈指数级增加。为了提高给定OLAP查询工作负载的查询性能，只需要从中选择一组适当的视图进行物化，因为物化整个视图集会违反磁盘空间限制。数据仓库中通常有大量的维度表，选择一组视图可以大大减少给定查询工作量的查询处理时间，这是一个NP完全问题。
关于物化视图的其他挑战包括使用物化视图来回答查询、有效地更新物化视图等。
本文的重点是计算适当的视图集，这些视图集在物化后将显著减少给定查询工作负载的OLAP处理时间。
这称为视图选择，将在下面讨论。
1.1视图选择
视图选择被正式定义为“给定一个数据库模式R、存储空间B和查询工作负载Q，选择一组视图V在R上进行物化，其组合大小最多为B”。
视图选择是文献中广泛研究的一个问题，人们提出了几种解决视图选择问题的方法。这些方法要么基于经验，要么基于启发式，如贪婪、进化、随机等。
Harinarayanetal.给出的算法（HRUA算法）被认为是最基本的视图选择算法。Harinarayan给出的贪婪视图选择算法，在多维晶格框架中从所有可能的视图中选择Top-K视图。HRUA考虑了一个线性的成本模型，该模型假设了一个视图的处理成本。利用视图的大小来计算每个视图的效益，并在每次迭代中选择效益最高的视图进行物化。
Gupta提出了一个解决视图选择问题的理论框架，当每个查询只有一种计算方式时，通过考虑“和视图”图来选择视图，当任何查询可以从其任何一个相关父视图计算时，考虑“或视图”图来选择视图。。贪婪算法用于从这些图中选择视图。考虑到维护成本，该算法在（GuptaandMumick，）中进行了扩展。
Serna-EncinasandHoya-Montano提出基于贪婪算法使用依赖关系的数量以及基关系的更新频率来计算物化视图的成本。这些依赖关系可以利用相同的物化视图，从而在没有临时更新的情况下节省成本。
Chanetal.提出了一种混合贪婪算法，它选择那些能带来成本效益的物化视图，而剩余的视图是虚拟的，并且是动态计算的。
Yangetal.提出了多视图处理计划（MVPP）框架来解决视图选择问题。一个数据仓库可能包含许多视图，如果其中一些以重叠的方式定义在基础数据上，然后通过仅物化基表的重叠部分来获得一些计算增益，而不是将所有视图具体化。MVPP用于标识给定查询工作负载的数据和操作的重叠部分。选择并物化一组表示数据重叠部分的节点，以最小化总体查询处理成本。
Shuklaetal.提出了一种按大小选择（Pick-By-Size，PBS）算法，克服了HRUA在运行时遇到的问题。此外，还引入了基于块的预计算来选择视图集，并进一步扩展HRUA和PBS来使用它。
Agrawaletal.提出了一个基于成本驱动和基于查询工作负载经验的工具，用于自动选择一组合适的视图和索引。
Shuklaetal.研究了从多立方体数据模型中选择视图的问题，提出了SimpleLocal、SimpleGlobal和ComplexGlobal三种从多立方体模式中选择实体化视图的算法。
NadeauandTeoreyNadeau提出了一种多项式贪婪算法（PGA），它的运行时间与维度数有关。PGA分两个阶段选择视图，即提名阶段和选择阶段。提名阶段提名潜在的观点，然后在选择阶段从中选出最有益的。
Aouicheetal.提出了一种基于聚类的视图选择策略，提出从查询工作负载中选择物化视图。密切相关的查询被分组到簇中。对于每一个这样的簇，构建了一个由包含视图所组成的晶格，并且从中贪婪地选择有益的视图。
AouicheandDarmont扩展了“一种基于聚类的视图选择策略”，通过使用数据挖掘来确定候选视图和索引，从中贪婪地选择视图。
VijayKumaretal.a,提出了一种能有效地对高维数据集进行视图选择的贪婪视图选择算法。该算法可扩展到高维数据集。
HaiderandVijayKumar；VijayKumarandHaider，a，b，H提出了视图选择算法，除了考虑视图的大小外，还考虑了视图的查询响应能力，即查询频率。这些算法能够选择不仅在大小方面有益的视图，而且能够回答大多数分析查询。
VijayKumarandHaider提出了一种视图选择算法，该算法在选择物化视图时兼顾了可扩展性和查询响应能力。
上述算法大多集中在多维晶格框架中选择视图。
随机算法和进化算法也被用来从多维晶格中选择视图。
这些算法使用迭代改进（VijayKumar和Kumara）、模拟退火（VijayKumar和Kumarc）、两阶段优化（VijayKumar和Kumar）、遗传算法（VijayKumar和Kumarb）、模因算法（VijayKumar和Kumar）和差分进化（VijayKumar和Kumar）。
本文将群体智能技术应用于蜜蜂繁殖优化(HBMO)(Haddadetal.,)，用来解决视图选择问题。
因此，提出了基于HBMO的视图选择算法(HBMOVSA)，从多维格中选择Top-K视图。
该算法的目标是在选择物化视图时，使评价所有视图的总代价最小，称为总视图评价代价（TVEC）。
与HRUA相比，HBMOVSA能够选择TVEC相对较低的视图。
1.2本文结构
第2节=介绍了使用HBMO的视图选择。
第3节=给出了一个例子，说明如何使用HBMO选择视图。
第4节=实验结果
第5节=结论
2使用HBMO选择物化视图
为了方便快速的多维分析，数据仓库中的数据是使用数据立方体存储的。数据立方体是由一组维度和度量值组成的。维度是描述维度的一组属性。度量是某些业务事件/事实的量化值。维度构成数据立方体及其单元的边缘，度量是数据立方体单元格的内容。数据立方体的单元就是视图。
管理者提出OLAP查询，根据数据立方体的维度分析单元格（视图）的度量，以获取信息。数据立方体的所有单元（视图）及其度量都可以用多维晶格表示。
本文提出的方法从多维晶格中选择视图，这将在下面讨论。
2.1多维晶格
视图由晶格的节点表示，并用括号内的整数索引；这种情况下的度量是图1所示的三维网格中给定的视图的大小（行数）。晶格表示数据立方体上的整个查询工作负载。根节点ABC是数据立方体，中间节点AB、AC、BC、A、B、C是数据立方体的单元。
一个视图可以直接依赖于另一个视图，也可以间接依赖于另一个视图。视图“Vi”依赖于视图“Vj”，如果对视图“Vi”提出的查询可以使用视图“Vj”来回答。直接视图依赖关系由任意两个节点之间的一条边表示，而间接依赖关系可以通过跟踪任意两个节点之间的多条边来识别。视图A直接依赖于视图AB和AC，视图B直接依赖于视图AB和BC，视图C直接依赖于AC和BC，而A、B和C则间接依赖于根视图ABC。
随着数据立方体维数（n）的增加，晶格的中间节点数（2n）呈指数增长。从晶格中物化一组Top-K视图可以最小化查询处理成本。然而，对于具有大量维度的数据立方体来说，计算这样一组视图在计算上是昂贵的。群体智能技术已被广泛应用于解决此类复杂的组合优化问题。
本文利用群体智能技术HBMO从多维晶格中选择视图。接着讨论了HBMO，然后提出了视图选择算法HBMOVSA。
2.2HBMO
在自然界中，在遗传和行为上更健康的个体成功地与其他个体和环境竞争和相处，以此来吃、生存和从遗传的角度上来说繁殖比自己更健康的后代。这些后代比其他病态的后代更能适应环境。正是因为每一代都有这些基因上更健康的后代，这样的物种才能继续生存到现在。
许多物种灭绝的原因是它们未能在基因上进化和繁殖出更健康的后代。蜜蜂在数千年的竞争、食物和生存的挑战中幸存下来。通过这些年的竞争，他们已经进化出一种智能的方法来繁殖基因上更健康的后代，这些后代进一步遗传进化和行为上的适应的可能性很高。
自然界中的蜂群只有一只大的蜂王，它是蜂群中唯一能繁殖的蜜蜂。蜂群中还包括雄蜂（称为雄蜂）和不育的雌性蜜蜂（称为工蜂）。蜂王和雄蜂专门从事繁殖，而工蜂则专门从事育雏、觅食和家政工作。为了满足蜂群的所有需要，蜂王应该能够繁衍出更适合遗传的工人，这些工人擅长专门的工作（如育儿护理、觅食和家务工作），并且有能力与其他蜂群和其他食花蜜和花粉的昆虫竞争。
由于工蜂寿命较短，蜂王承担着繁衍后代更好工蜂的更大责任。年轻的蜂王一生只交配一次。在蜜蜂交配季节，来自不同蜂群的蜂王和雄蜂会飞到空中一个叫做雄蜂聚集区（DCA）的交配空间。这显示了蜜蜂之间的一种社会合作，以帮助彼此成功交配，意图繁殖它们的物种。蜂群的蜂王和雄蜂，在DCA有着不同的基因组成，构成了遗传非常丰富的蜂群。
如果在交配过程中耗尽了能量，蜂王会飞回蜂巢觅食，因此它们必须进行一次或多次交配飞行才能交配，直到它们的精子储存器官（精子储存器官）被填满。蜂王通常在它们的精囊中收集和储存精子。雄蜂与蜂王交配后立即死亡，这种策略起到了积极的反馈作用，使蜂王与不同的雄蜂交配，以提高精囊中收集的精子的丰富性。
当它们的精子充满后，蜂王飞回蜂巢，开始在蜂巢的格子里产卵。蜂王一生都是用储存在精囊中的精子都用来繁殖一代又一代的雄蜂和工蜂。作为一次性交配策略的结果，蜂王的大部分时间都呆在蜂房里，当她在野外飞行交配时，被捕食者捕食的可能性大大降低，生存的可能性大大增加。因此，蜂王的一次性交配和精子收集策略对蜂群的生存和存在也起到了积极的反馈作用。
蜂王一天能产大量的卵。蜂王有两套染色体（36个基因），她是二倍体，而她的卵细胞有一套她的染色体（16个基因）。她的卵子各不相同，有着独特的蜂王基因组合。另一方面，雄蜂是单倍体的；与动物的不完全相同的精子不同，雄蜂的精子是相同的。她从自己的受精囊中随机挑选精子，并用它使卵子受精。这种随机的遗传信息共享方式，通过随机受精，增加了一些高度专业化工蜂的出生概率。然后这些卵由工蜂照料。
受精卵变成工蜂，未受精卵变成雄蜂。新的一代由工蜂喂养。蜂王浆喂养的小蜂成长为新蜂王。当新的年轻蜂王到来时，老王后带着一些雄蜂和工蜂飞向一个新的蜂巢。
老蜂王的这种合作使新蜂王能够轻松舒适地繁殖新一代更健康的蜜蜂。由于它们的集体和合作的繁殖机制，蜜蜂已经成功地存活了几千年，甚至今天大量存在。
将蜜蜂交配繁殖过程中遗传信息共享机制的计算环节建模并在算法上采用蜜蜂交配优化（HBMO）算法，求解高度非线性的基准数学函数，制定一个接近最优的操作策略。HBMO的伪码如图2所示。
Start：
首先计算一组代表蜂群的随机解。
种群的最佳解被识别并记为蜂王。
For蜂王开始她的交配飞行，飞行次数是预定义的。
蜂王能量和速度被初始化。
随机生成一个雄蜂。
计算每次交配蜂王能量损失。
While蜂王能量0。
评估每个雄蜂的健壮性。
If若雄蜂比蜂王健壮and蜂王的精囊未满。
将雄蜂精子装入蜂王精囊。
Else蜂王依概率选择雄蜂。
更新蜂王的能量
计算蜂王每次交配的速度损失
更新蜂王的速度
EndWhile
For
从蜂王的精囊中随机选择一个精子
将蜂王的染色体与选定精子的染色体交叉，产生一个幼蜂
使产生的后代的基因突变
EndFor
If最好的幼蜂强于蜂王
用最好的幼蜂取代蜂王
杀死所有幼蜂
EndFor
End：
自诞生以来，HBMO已成功地应用于学术界和工业界的广泛问题。本文采用HBMO来解决视图选择问题。为此，提出了基于HBMO的视图选择算法（HBMOVSA），并对其进行了讨论。
2.3HBMOVSA
视图选择问题是一个组合优化问题，它的目标是从给定的多维视图晶格框架中计算出一组Top-K视图，使其TVEC最小，从而有效地处理给定的OLAP查询工作量。
这个解是一组Top-K视图，可以用整数染色体表示法，用K个不同的基因来表示，每个基因都代表多维晶格中的一个不同视图，如图3所示。
Top-K视图的适应度可以用TVEC来度量。TVEC基于线性成本模型，其中处理视图的成本取决于视图的大小。它被定义为评估所有视图的总成本，计算如下：
N是晶格中的视图总数。
SMVi是Vi的物化状态，如果已物化，则SMVi=1，否则SMVi=0。
Size（Vi）是视图Vi的大小。
SizeSMA(Vi)是视图Vi最小的物化祖先的大小。
由于视图选择问题是一个最小化问题，所以TVEC值较小的Top-K视图比TVEC值较高的Top-K视图更可取。
图4的HBMOVSA算法相应地调整了HBMO元启发式算法，来搜索解空间，以找到具有近似最优TVEC值的Top-K视图集。
Input：待选视图数量K、Top-K幼蜂视图数量NB，Top-K蜂王视图的精囊大小SS，多维视图晶格L。
Output：一系列Top-K视图//利用给定的多维视图晶格随机生成一组Top-K蜜蜂视图（解决方案），最佳的Top-K蜜蜂视图（解决方案）就是Top-K蜂王视图，而剩余的Top-K蜜蜂视图被视为Top-K雄蜂视图。
Method：
Step1：//初始化//
TEVCmax=(L的根视图大小)╳(L的视图总量)
TEXCmin=TEVCnax/2
QSmax=TVECmin+(TVECmax-TVECmin)*rand()//Top-K蜂王视图可以进行配对飞行的最大速度QSmax被随机分配为TVECmax和TVECmin之间的值。/，这样她就可以进行多次交配飞行来填充她的精囊。
QSmin=TVECmax/10
speed=QSmax//蜂王起飞
α=0.98//Top-K蜂王视图速度削减系数
Step2：使用晶格L随机生成Top-K蜜蜂视图的总体
Step3：将最佳解决方案指定为Top-K蜂王视图Q，其余的作为Top-K雄蜂视图。
For预先指定的婚飞数量
Step4：//Top-K蜂王视图配对阶段//
从Top-K雄蜂视图的总体中随机选择Top-K雄蜂机视图D
Repeat
IfTVEC(D)TVEC(Q)//如果Top-K雄蜂视图比Top-K蜂王视图更适合，则她成功地与之交配并将Top-K雄蜂视图添加到她的受精囊中。否则她将使用如下所示的退火函数与Top-K无人机视图匹配
将D添加到Q的受精囊中，并从Top-K雄蜂视图中删除D
Else
计算
产生随机数0r1
//P（D）是Top-K雄蜂视图D的解加到Top-K蜂王视图的精囊中的概率
IfP(D)r
将D添加到Q的受精囊中，并从Top-K雄蜂视图中删除D//这种Top-K雄蜂视角的策略保证了在精囊中积累的解决方案的多样性和丰富性。
Endif
Endif
QS=QS*α//Top-K蜂王视图的当前速度
IfQSQSmin//如果Top-K蜂王视图的速度降低到指定的最小速度以下，则Top-K蜂王速度将用最大速度重新初始化
QS=QSmax
Endif
UntilQ的精囊装满
Step5：//受精期
Fori=1toNB
从Q的受精囊中随机选择Top-K雄蜂视图，通过单倍体杂交获得Top-K孵卵视图（Q的精确副本）以使其受精。
EndFor
Step6：//用变异算子改进Top-K幼蜂视图
改变新生成的Top-K幼蜂视图
Step7：//更新Top-K蜂王视图
确定相对于TVEC的最佳Top-K幼蜂视图
If最佳Top-K幼蜂视图的TVEC小于Q的TVEC
将Q替换为最佳Top-K幼蜂视图
Else
Q仍为最佳Top-K幼蜂视图
Step8：丢弃Top-K幼蜂视图的总体，随机生成新的Top-K雄蜂视图。
Endfor
与自然界中不完全相同的蜂王蛋不同，这里考虑的Top-K卵子视图是Top-K蜂王视图的精确复制品。她将自己的Top-K卵子视图与随机选择的Top-K雄蜂视图从精巢中随机选择，产生一个Top-K幼蜂视图。受精是通过单倍体杂交完成的。由于Top-K雄蜂视图是单倍体的，因此随机选择一半的基因与Top-K卵子视图进行交叉，以产生Top-K幼蜂视图。Top-K雄蜂视图的新群体是随机生成的。
这就完成了HBMOVSA的第一次交配飞行。
以上的交配、受精和突变阶段都是在预先指定的交配飞行次数下进行的，以获得一个Top-K蜂王视图，即一组具有近似最优TVEC值的Top-K视图。
接下来，给出了一个使用HBMOVSA从多维晶格中选择Top-K视图的例子。
（此处略）
3结论
本文提出了一种从多维视图晶格中选择Top-K视图的视图选择算法HBMOVSA。
HBMOVSA相应地调整了HBMO来解决视图选择问题，目的是大大提高在线分析查询的响应时间。
实验结果表明，与基本的视图选择算法HRUA相比，HBMOVSA计算的Top-K视图的TVEC相对较小，表明HBMOVSA计算的视图质量更好。
此外，可以推断，HBMOVSA可以扩展到更高维的数据集。
因此，HBMOVSA选择用于物化的视图，这些视图可以极大地提高分析查询的处理速度，并有助于加速数据分析，从而提高信息可用性。
这些信息将使管理者能够实时做出战略决策，从而在竞争对手中占据优势。
此外，HBMOVSA可以并行化，以便有效地选择Top-K视图进行物化。
转载请注明：http://www.0431gb208.com/sjslczl/1779.html
