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

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

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

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

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

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

一种空间数据仓库动态物化视图选择算法

物化视图能够有效地提高空间数据仓库的查询效率,但由于空间操作的复杂性,传统数据仓库中物化视图的选择算法不能很好地应用于空间数据仓库。为了在存储空间约束下选择查询进行物化,并动态调整物化视图集,以适应用户查询的时变性和即席查询,提出了空间物化视图选择算法SMVS。实验结果表明该算法是有效可行的,不仅能够提高查询性能,而且解决了查询响应性能随用户查询分布变化而下降的问题。     

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

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

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

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

基于聚类的动态物化视图选择研究

物化视图选择方法大多是静态的,违背了联机分析处理和决策支持系统的动态本质.现有的动态算法也不能实现完全的动态化,为此提出了一种数据仓库中基于聚类的动态物化视图选择算法CBD-MVS(clustering-based dynamic materialized view selection),该算法采用层次聚类技术对用户查询语句进行聚类,提出视图合并算法建立候选物化视图,利用BPUS(benefit per unit space)算法生成最终应该被物化的视图.实验结果表明该算法是有效可行的,由于采用聚类技术,实现了完全的动态化.     

数据仓库环境中可扩展的动态物化视图选择方法

数据仓库通常要对大量的数据进行运算,以精简的结果来回答用户的查询,这一特点使得物化视图技术在数据仓库中尤为重要.然而现有支持物化视图自动选择的方法是静态的,它违背了联机分析处理(OLAP)和决策支持系统(DSS)的动态本质.本文提出了可扩展的动态物化视图方法,通过将整个物化视图选择问题(MVS)分解为三个阶段,降低了问题的复杂度,提高了物化视图的有效性.通过动态调整,物化视图能即时适应查询需求.算法复杂度分析证明了方案的可扩展性.动态调整算法模拟实验验证了方案具有很好的自适应性.     

新型物化视图选择算法

针对现有物化视图选择算法无法很好解决OLAP随机查询的问题,提出了一种新型的两阶段物化视图选择算法(2-PMVS),将传统的静态选择算法与动态选择算法相结合,使其可以动态矫正用户随机查询与预估查询之间的偏差。经实验证明,该算法切实有效。     

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

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

实体化视图动态选择预处理算法的研究

实体化视图是数据仓库中提高查询效率的有效手段，数据仓库运行期间，需要对其中的实体化视图进行维护，从而保证用户查询的响应时间较短。针对用于实体化视图动态选择的遗传算法收敛速度慢，运行时间长的问题，提出一种预处理算法来计算动态选择实体化视图时遗传算法的初始群体。理论分析和宴验结果表明，该算法可以有效地提高实体化视图动态选择时的寻优收敛速度。     

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.     

多维数据实视图的动态选择

提出了多维数据中实视图的动态选择方案.其基本思想是由系统跟踪查询的分布情况,并据此动态地调整实视图集合.具体实现了该方案,并证明了在一定条件下,单次选择算法的效果与最优效果的差具有一定的上限.实验结果表明,动态方案的效果优于已有的其他选择方案.     

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

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

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.     

Finding an efficient rewriting of OLAP queries using materialized views in data warehouses

OLAP queries involve a lot of aggregations on a large amount of data in data warehouses. To process expensive OLAP queries efficiently, we propose a new method to rewrite a given OLAP query using various kinds of materialized views which already exist in data warehouses. We first define the normal forms of OLAP queries and materialized views based on the selection and aggregation granularities, which are derived from the lattice of dimension hierarchies. Conditions for usability of materialized views in rewriting a given query are specified by relationships between the components of their normal forms. We present a rewriting algorithm for OLAP queries that can effectively utilize materialized views having different selection granularities, selection regions, and aggregation granularities together. We also propose an algorithm to find a set of materialized views that results in a rewritten query which can be executed efficiently. We show the effectiveness and performance of the algorithm experimentally.     

Efficient keyword search over virtual XML views

Emerging applications such as personalized portals, enterprise search, and web integration systems often require keyword search over semi-structured views. However, traditional information retrieval techniques are likely to be expensive in this context because they rely on the assumption that the set of documents being searched is materialized. In this paper, we present a system architecture and algorithm that can efficiently evaluate keyword search queries over virtual (unmaterialized) XML views. An interesting aspect of our approach is that it exploits indices present on the base data and thereby avoids materializing large parts of the view that are not relevant to the query results. Another feature of the algorithm is that by solely using indices, we can still score the results of queries over the virtual view, and the resulting scores are the same as if the view was materialized. Our performance evaluation using the INEX data set in the Quark (Bhaskar et al. in Quark: an efficient XQuery full-text implementation. In: SIGMOD, 2006) open-source XML database system indicates that the proposed approach is scalable and efficient.     

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

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