基于快速排序和huffman树的物化视图增量保持算法

物化视图是一种提高查询响应的有效方法,其核心问题在于如何与基表保持数据同步。目前已经有很多算法用于物化视图增量保持,各算法的效率不同,因此也出现了很多提高物化视图增量保持效率的算法。在构造最优Delta传播树的BinPartition算法的基础之上提出了一种基于快速排序和huffman树的物化视图增量保持算法,并通过实验证明了该算法可以提高物化视图增量保持的效率。     

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

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

基于遗传算法的物化视图优化方法

物化视图是提高数据仓库执行效率的有力方法,但是物化视图的保存会占用存储空间。本文把查询需要扫描的物化视图或事实表的空间大小作为查询时间开销,以查询的时间开销和物化视图的存储开销作为衡量标准建立代价估算模型,设计基于遗传算法的物化视图优化算法。目的是使系统在物化视图方面的存储开销和查询时间开销的和最小。试验结果表明算法可行。     

OODB中连接视图的物化和增量保持技术

提出了一个实现OODB中连接视图物化和增量保持的算法，基本思想是扩充了文献[1]中的OODB模型，使其便利于连接视图的物化和增量保持，为每个类中的对象增加一个视图标识，用来标记该对象是否在相应视图中，以减少连接运算，最后，开发出一系列算法来实现由两个类做连接运算生成一视图的物化及保持工作。     

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

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

数据仓库中物化视图的选择

物化视图是数据仓库中提高查询效率的有力方法，物化视图的选择一直是数据仓库领域的研究热点。通过对星型模型的研究，根据对数据仓库的常用查询及其执行概率，设计出一个候选视图的算法，并详细介绍了线性代价模型，在该模型和候选视图算法基础上，参照文献[4]提出一个改进的物化视图选择贪心算法。     

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

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

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

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

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

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

数据仓库物化视图选择的混合算法

物化视图是提高数据仓库的查询响应能力以高效支持决策分析的重要手段，但物化视图集选选择是一个复杂问题。结合启发式算法的快速收敛能力和遗传算法的全局优化能力的两层物化视图求解方案提供了物化视图选择问题求解的可行途径。     

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

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

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.     

实视图动态选择算法中重叠实视图的处理

当采用实视图来提高OLAP系统效率时，由于实视图往往并不恰巧是一个完整的格节点，即实视图是多维数据切片（MRFs），因此系统中会出现大量有重叠数据的实视图，这不仅占用了过多的存储空间。也使得系统根据已有实视图响应用户提交的多维查询变得复杂。以往的实视图动态选择算法没有考虑这种情况的处理。文章结合格模型的概念，提出了合并数据重叠实视图的算法，包括如何判定实视图之间有重叠数据、如何合并有数据重叠的实视图等。     

A*算法在物理视图维护中的应用

数据仓库是集中了多个远地数据源数据复本的单一数据库,包含有基本关系和物理存储的视图。数据源数据的变化会导致数据仓库中数据不一致,维护视图和基本关系的一致增加了额外的维护代价。有选择地存储一些视图和索引是降低维护成本的有效途径。本文讨论视图索引地选择问题,通过例子提出了利用Ａ＾＊算法寻找最优解的算法。     

Detecting redundant materialized views in data warehouse evolution

A data warehouse (DW) can be abstractly seen as a set of materialized views defined over a set of remote data sources. A DW is intended to satisfy a set of queries. The views materialized in a DW relate to each other in a complex manner, through common subexpressions, in order to guarantee high query performance and low view maintenance cost. DWs are time varying. As time passes new materialized views are added in order to satisfy new queries, or for performance reasons, while old queries are dropped. The evolution of a DW can result in a redundant set of materialized views. In this paper, we address the problem of detecting redundant materialized views in a given DW view selection, that is, materialized views that can be removed from DW without negatively affecting the query evaluation or the view maintenance process. Using an AND/OR dag representation for multiple queries and views, we first formalize the process of propagating source relation changes to the materialized views by exploiting common subexpressions between views and by using other materialized views that are not affected by these changes. Then, we provide an algorithm for detecting materialized views that are not needed in the process of propagating source relation changes to the DW. We also show how trivially redundant views can be identified in this process. Finally, we use these results to provide a procedure for detecting materialized views that are redundant in a DW. Our approach considers a broad class of views that includes grouping/aggregation views and is not dependent on a specific cost model.     

View adaptation in the fragment-based approach

View adaptation relies on adapting a set of materialized views in response to schema changes of source relations and/or after view redefinition. Recently, several view selection methods that are based on materializing fragments of the view rather than the whole view have been proposed. We call this approach the fragment-based approach. This paper presents a view adaptation method in the fragment-based approach, which is aimed at exploiting the opportunities to share not only materialized data, but also computation between the different views. In order to do this, the views are modeled using the so-called multiview materialization graph, which represents the views as a bipartite directed acyclic graph whose nodes are operations and fragments of the views. Then, the adaptation is performed regarding all materialized views and not solely the old materialization of the view. However, the data independence is preserved for the views that are not affected by the change. On the contrary, in related work, the adaptation technique is based solely on the old materialization of the same view. We studied the impact of the fragmentation on the adaptation techniques and showed the advantages and drawbacks of this approach.     

静态物化视图的动态Cache优化算法

针对静态物化视图集动态适应能力的不足,提出一种动态cache优化算法DCO(dynamic cacheoptimization).它在保持静态算法获取最优物化集能力的基础上,将cache机制直观、快速的动态特性结合进来,以提高数据仓库的动态自适应性能.在cache机制具体实现中提出了一种新颖的空间申请方法,可以充分利用系统剩余空间提高查询响应性能.实验结果在表明算法有效、可行的同时,也显示出该算法可以在一定程度上克服静态物化集存在的空间-性能饱和效应(space-performance saturation effect,简称SPSE),使通过增加物化空间进一步提高数据仓库对查询的响应速度成为可能.     

考虑更新频率等因素的物化视图有效更新算法

For the materialized views in the fast LAN or computing grid environment, it is a very important problem that how to refresh them efficiently when data sources have changed. In this paper, we take the update frequencies and the size of source relations into account and present a partition strategy and an efficient algorithm by creating auxiliary views. Our algorithm may decrease the cost of join operation and communication on network as low aspossible.     

多物化视图并行增量保持三阶段模式

文章提出了一种基于并行流水线处理方式的多物化视图(materialized views)增量保持方法,即在先进行筛选的条件下,利用归类拓扑排序,将所有物化视图进行分类,使每一类中的视图之间没有嵌套定义关系.最后对每一类中的所有视图利用基于信号量控制机制的流水线模式并行处理,以达到对多物化视图实现增量保持的目的.     

基于多实化视图增量维护的基库生成算法

数据仓库的维护是数据仓库应用中的一个十分重要的问题,近几年产生了很多的维护算法。已有的维护算法多是针对单个实化视图的维护;或只针对简单SPJ视图的维护;或只针对聚集函数的维护;而实际的数据仓库大多是由包含聚集函数的多个实化视图组成。因此综合考虑包含聚集函数的多个实化视图的维护问题是必然的。文章正是在此情况下提出了一种基于多实化视图增量维护的基库生成算法,在《基于基库的多实化视图增量维护算法》中提出了包含聚集函数的多实化视图的维护算法。