数据仓库中多数据源物化视图的一种有效更新算法

数据仓库中存储着大量的汇总数据以支持查询和相关决策的制定，这些汇总数据常常是定义在若干数据源上的物化视图．当数据源发生变化时，物化视图也需要相应的更新，这必然给数据仓库带来庞大的开销，因而如何有效地对物化视图进行更新成为一个非常重要的问题．利用BinPartition算法可以使计算费用达到最低，随后证明了该算法的正确性并分析了其时间复杂性．     

面向查询集覆盖的物化视图选择算法

为了解决大容量物理存储条件下数据仓库的物化视图选择问题,提出一种面向查询集覆盖的物化视图选择算法.首先给出了一些概念和定义,然后从视图集的多维数据格中抽取和裁剪出候选视图集,并定义视图物化的效益模型,最后在存储容量的限制下逐步淘汰收益最小的应答查询的冗余视图,得到覆盖所有查询的最优物化视图集.实验结果表明,该算法在较大物理存储条件下的物化视图选择效率优于以往算法,且能够消除物化视图在应答查询时存在的时延“抖动”现象,应答用户查询的平均时间也大为缩短.     

数据仓库中物化视图选择策略

为了提高决策支持和OLAP查询的响应效率,数据仓库多采用物化视图的思想.因此,物化视图的选择策略是数据仓库研究的重要问题之一.其目标是选出一组存储、维护代价与查询代价的总和为最小的物化视图.提出一个以MVPP(multi-view processing plan)为视图选择的搜索空间的物化视图选择新算法--VSMF(views selection base on multi-factor)算法.该算法在存储空间约束下同时实现多查询最优化和视图维护最优化.     

使用模式树和物化视图进行XML查询

使用模式树解析XQuery查询，将经常被查询的XML节点信息存储到物化视图中，利用物化视图和用户查询的交叉部分，直接从物化视图中获取用户的查询内容。对于两者不完全匹配的部分，使用补充规则，使得能部分使用物化视图，以提高查询效率。文章还给出了模式树的匹配算法。     

数据仓库中物化视图的选取策略

数据仓库中用存储大量的物化视图来加速OLAP的查询响应，物化视图的选取是数据仓库设计中的一个重要问题。论文提出了一个有效的物化视图选取算法，采用基于数据立方体层次搜索的方式选取视图。经分析与测试表明，该算法取得良好的效果和效率。     

一种改进的物化视图动态批量调整算法

针对物化视图集实时调整容易出现"抖动",物化视图集不稳定的缺点,本文提出一种改进的物化视图动态批量调整算法,根据在一个统计周期内收集到的查询调整物化视图集.算法先判断查询集合是否满足调整条件,若满足则根据视图访问频率生成候选视图,再调用物化视图批量选择算法;若不满足则调用物化视图集动态调整算法.该算法不需要频繁计算,而且查询集合能反映用户的查询趋势,调整后的物化视图集对用户查询具有较高的适应性.文中实验从执行时间、物化视图集整体性能等方面验证了该算法的有效性.     

NDSMMV——一种多维数据集物化视图动态选择新策略

物化视图的选择策略是数据仓库研究的重要问题之一.通过深入研究提出了一种多维数据集中物化视图动态选择的新策略--NDSMMV,包括候选视图生成算法CVGA、物化视图选择算法IGA、物化视图调整算法MAMV和物化视图动态调整算法DMAMV.CVGA基于多维数据格生成候选视图集,对候选视图数量进行压缩以减少后续算法的视图空间搜索代价和时间复杂度;IGA基于视图查询、视图维护和存储空间三元评价标准在候选视图集上进行物化视图的选择;MAMV基于物化视图选择过程已选视图的收益变化情况对物化视图进行进一步调整以提高查询的响应性能;DMAMV定时地判断查询视图类型分布是否变化来决定是否进行物化视图的动态调整,从而避免了物化视图集的"抖动".理论分析和实验结果表明该策略是有效可行的.     

基于时间段查询的物化视图策略

物化视图是减少数据仓库中查询响应时间的有效方法.现有的物化视图选择策略主要考虑物化视图的初始选择方法以及动态更新方法.针对某时间段内查询进行物化视图更新的情况考虑不足,在贪心算法以及动态更新算法的基础上,提出了基于时间段内查询的物化视图更新策略.基于时间段查询的物化视图更新策略可充分适应用户需求,提高查询效率.     

基于多维护策略的物化视图选择方法

物化视图是数据仓库环境中提高OLAP查询效率的重要手段，因此，物化视图的选择是数据仓库设计中重要的决策之一。本文提出的物化视图选择方法目标是选择合适的视图进行物化，使得查询处理的总代价和物化视图的维护代价最低，提出了物化视图收益模型，并在此基础上基于视图的多维护策略提出了物化视图选择的方法：基于增量和重计算的物化视图选择算法IRMVS、基于增量策略的物化视图选择算法IMVS和基于重计算策略的物化视图选择算法RMVs和基于增量策略的物化后代视图选择算法IMDVS，理论分析和实验表明这些算法是有效可行的。     

基于查询和相对收益的物化视图选择算法

为了改进数据仓库中物化视图选择策略,提出了基于查询和视图相对收益的动态选择算法BWCC.算法根据视图的尺寸,视图相对收益以及物化视图每项属性的权重构造初始选择集,并可以由用户设定初始视图权重.用户查询触发算法动态更新视图价值,对物化视图集按照视图相对收益大小排序并进行局部调整,到达全局更新周期时参考历史价值对物化视图集进行重新计算.实验结果表明,该算法相比于传统算法具有更高的查询命中率和适应性.     

PMC: Select Materialized Cells in Data Cubes

QC-Tree is one of the most storage-efficient structures for data cubes in an MOLAP system. Although QC-Tree can achieve a high compression ratio, it is still a fully materialized data cube. In this paper, an improved structure PMC is presented allowing us to materialize only a part of the cells in a QC-Tree to save more storage space. There is a notable difference between our partially materialization algorithm and traditional materialized views selection algorithms. In a traditional algorithm, when a view is selected, all the cells in this view are to be materialized. Otherwise, if a view is not selected, all the cells in this view will not be materialized. This strategy results in the unstable query performance. The presented algorithm, however, selects and materializes data in cell level, and, along with further reduced space and update cost, it can ensure a stable query performance. A series of experiments are conducted on both synthetic and real data sets. The results show that PMC can further reduce storage space occupied by the data cube, and can shorten the time to update the cube.     

Efficient approaches for materialized views selection in a data warehouse

View materialization is an effective method to increase query efficiency in a data warehouse and improve OLAP query performance. However, one encounters the problem of space insufficiency if all possible views are materialized in advance. Reducing query time by means of selecting a proper set of materialized views with a lower cost is crucial for efficient data warehousing. In addition, the costs of data warehouse creation, query, and maintenance have to be taken into account while views are materialized. In this paper, we propose efficient algorithms to select a proper set of materialized views, constrained by storage and cost considerations, to help speed up the entire data warehousing process. We derive a cost model for data warehouse query and maintenance as well as efficient view selection algorithms that effectively exploit the gain and loss metrics. The main contribution of our paper is to speed up the selection process of materialized views. Concurrently, this will greatly reduce the overall cost of data warehouse query and maintenance.     

数据仓库中用于视图选择的增强遗传算法

物化视图选择问题是数据仓库设计中最重要的问题之一,为了高效地解决这一问题.提出了一个如何选择物化视图集的增强遗传算法,以便在存储空间约束的条件下,取得较好的查询性能和较低的视图维护代价.这一算法的核心思想在于,首先,运用一个基于单位空间最大收益值的预处理算法来生成初始解,然后,该初始解经采用了多种优化策略的遗传算法进行提高,这些优化策略包括:基于改进的锦标赛和精英选择相结合的选择算子、基于半均匀交叉算子及自适应变异算子.并且,在进化过程中产生的无效解用损失函数加以修补.试验结果表明,该算法在寻优性能上优于启发式算法和经典遗传算法.     

数据仓库中新型动态实视图选择调整算法

现有的静态实视图选择算法存在搜索空间太大、时间复杂度高以及未考虑查询的概率和分布等诸多缺点,并且当源数据发生变化时,这种变化不能立刻反映到数据仓库,不适合在线运行。针对上述问题在候选视图生成算法和IGA算法的基础上,对算法进行了动态调整,从而得出了新型物化视图动态调整算法CNUMV。经实验证明该算法降低了视图的搜索空间和时间复杂度,更重要的是该算法考虑到了各视图之间相互依赖关系对视图收益的影响,从而使算法能够动态地在线调整,并且用实验证明了CNUMV算法的优越性,达到了预期的目的。     

物化视图选择的预处理算法

现有的静态物化视图选择算法的视图搜索代价较大，而导致算法的时间复杂度偏高，不能用于对物化视图进行在线动态调整．提出了一种物化视图选择的预处理算法——PMVS，其中包括用户查询集动态调整算法QSDM、候选视图格构造算法CVLC和候选视图筛选算法CVF，该算法可用做预处理过程对视图数量进行在线压缩，从而降低了静态算法的视图空间搜索代价和时间复杂度．理论分析和实验结果表明该算法是有效可行的．     

ROLAP中星型模型的索引优化策略

目前主要有三种方法来提高ROLAP查询效率：聚集策略、即席查询策略以及采用高性能软硬件并行计算机系统结构。文中以暂住人口数据仓库为例，阐述如何利用索引来提高ROLAP的查询效率。主要讨论了位图索引和数据索引对ROLAP的查询优化，并从查询时间的长短以及数据占用存储空间的大小来比较这两种方法的优缺点。     

Web数据集成系统基于QC模型的物化视图选择

在Web数据集成系统中,物化视图能够有效地减少网络传输代价,提高系统的查询效率．如何选择查询进行物化,使得选中的查询满足集成层的空间限制,同时获取最大物化收益,成为集成系统中一个迫切需要解决的问题．传统方法没有考虑到海量XML查询之间的包含关系,其选择的物化视图中可能包含冗余的信息．针对上述问题,提出了①Web数据集成系统中海量查询集合的QC(query containment)模型,该模型能够捕捉查询之间最常见的包含关系;②基于QC模型的物化视图选择算法,算法考虑了物化视图选择相关的主要因素,包括查询提交的频率、空间代价、查询重写能力和查询结果的完备性,提出了查询位图的物化视图组织方式,从而获取更加合理的物化视图选择方案．实验结果证明了该方法的有效性．     

Incremental Design of a Data Warehouse

A data warehouse (DW) can be seen as a set of materialized views defined over remote base relations. When a query is posed, it is evaluated locally, using the materialized views, without accessing the original information sources. The DWs are dynamic entities that evolve continuously over time. As time passes, new queries need to be answered by them. Some of these queries can be answered using exclusively the materialized views. In general though new views need to be added to the DW.In this paper we investigate the problem of incrementally designing a DW when new queries need to be answered and possibly extra space is allocated for view materialization. Based on an AND/OR dag representation of multiple queries, we model the problem as a state space search problem. We design incremental algorithms for selecting a set of new views to additionally materialize in the DW that: (a) fits in the extra space, (b) allows a complete rewriting of the new queries over the materialized views, and (c) minimizes the combined new query evaluation and new view maintenance cost. Finally, we discuss methods for pruning the search space so that efficiency is improved.