基于粗集的关系型联机分析优化技术研究.pdf

华中科技大学 博士学位论文 基于粗集的关系型联机分析优化技术研究 姓名：李文海 申请学位级别：博士 专业：计算机软件与理论 指导教师：冯玉才 20070604 I 华华 中中 科科 技技 大大 学学 博博 士士 学学 位位 论论 文文 摘摘 要要 随着数字时代的到来，企业积累的数据呈爆炸式增长，在海量数据上的分析决 策已成为当前数据库领域的一大难题；而与此同时，分布式计算的飞速发展则为解 决这一难题带来了机遇和新的挑战构建一个具有分布式特征的关系型数据仓库， 并辅之以高效的联机分析优化手段，成为依托已有成熟技术解决这一难题的首选 多维作为联机分析中最本质的特征，在关系型数据仓库中以视图的形式体现，因此 在满足一定数据实时性的前提下，高效地维护视图成为关系型联机分析优化的最根 本任务基于这一应用背景，在自主研制的企业加速引擎基础上集成了联机分析处 理功能，构建了一个关系型的分布式数据仓库系统 DMWS利用四层架构达到了 DMWS 的高可扩展性，借助粗集的相对不可辨识聚类在自治站点上实现了数据粒度 可控的事实垂直分区，基于粗集约简的分层视图更新有效地提高了大规模负载下 DMWS 更新视图的效率。

提出了一种基于层次外关键字引用搜索加选择率度量的负载水平分布方法该 方法首先基于广度优先搜索一组查询和更新代价较高且存在单向外关键字传递引用 的单亲关系构成联合集； 然后依据查询选择率水平传递划分联合集； 最后基于 DMWS 的四层仓库架构，采用 round-robin 方法均匀分布联合水平分区利用分布于数据源 和自治站点上的触发系统，DMWS 能够保证仓库视图的强一致性更新；通过将联合 集水平分布于自治站点，该方法实现了自治站点对更新负载的有效分摊，因而大大 增强了 DMWS 的可扩展性；在此基础上，依据选择率划分水平分区，使得联合集的 元组具有站点凝聚特性，且凝聚优先考虑与高代价视图相关的更新数据 为有效支持关系型联机分析优化，通过粒计算描述粗集理论及其相关扩展，并 提出三种与知识发现相关的粗集扩展新方法基于概率思想的两层近似方法通过阀 值控制对象集的近似边界以线性比率变化，有效提高了知识获取的容错性；基于相 对不可辨识类的偏序结构利用邻域对象建立特征集，有利于解决非三角距离的对象 聚类问题；在这两种粒化扩展方法之上，既约特征集有力地揭示了特征集内部的层 次关系，为特征集的分层类化提供了一条极具启发意义的途径。

II 华华 中中 科科 技技 大大 学学 博博 士士 学学 位位 论论 文文 在联合水平分布前提下，提出了一种针对自治站点上事实关系的时态垂直分区 划分方法利用对每个查询样本的分解，该方法首先将事实关系划分为一个由阻塞 算子界定的属性访问特征集；然后基于全部查询样本下的特征集构建一个聚类模型 为求解这个对象距离不满足三角不等式的聚类模型，在粗集不可辨识关系的基础上， 基于偏序结构迭代收敛的特性，构造了一个粒度可控的聚类求解模型面向复杂多 样的查询时，基于查询分解构造聚类模型并依据有效性函数选取候选聚类，可以有 效克服传统事务划分方法分区粒度过小的缺点，因此该方法能够更加有效地发掘联 机分析查询访问事实关系属性的时态局部性 关系型联机分析中查询的复杂性和多样性增加了视图维护的难度，同时也为发 掘视图依赖提供了必要条件针对多连接视图提出了一种基于辅助视图的粗分层增 量维护方法依据局部更新负载在集成器上合并的时机，弱局部合并和强局部合并 对集成器负载的影响被放到 DMWS 环境下分别加以分析 由于强局部合并下全局查 询的主要负载集中在各自治查询上，因而通过选择下推，SPJ 视图被转换为自治站点 间的多连接视图进行优化。

在此基础上，首先基于查询视图两两之间的共享关系构 造辅助视图的候选空间；然后将查询视图和中间视图分别作为对象集和特征集，利 用粗集约简构造一个中间视图候选集的层次生成方法，并证明了各层中任意候选集 内的视图相互独立且高层单向依赖于低层视图集；最后在层内选取有效代价最低者 作为待选视图集，并淘汰待选视图集中造成联合代价增加的视图具有独立和依赖 特性的待选视图集改进了已有估算选取方法局部考量跨度小的不足，基于有效代价 确定待选视图集显著减少了估算时间复杂度 除了能够有效支持垂直分区求解和分层视图选取外，基于粗集的相关求解思路 同样适用于其他具有类聚或层次特征的关系型联机分析优化问题 关键词：关键词：数据仓库，联机分析处理，一致性维护，实化视图，增量更新，粗集理论 III 华华 中中 科科 技技 大大 学学 博博 士士 学学 位位 论论 文文 Abstract With the coming of digital era, the data accumulated by corporations are increasing explosively, so the analysis and decision based on numerous data have nowadays become one of the puzzles in the field of database. Meanwhile, the rapid development of distributed computing has offered chances and new challenges as well for the solution of this problem. It has become the optimal choice relied on the existing mature technique for this problem to construct a relational distributed data warehouse and aided with highly-powered optimization of on-line analytical processing. As the most essential character of on-line analytical processing, multi-dimension is exhibited by the materialized views. Under the assumption of real-time restriction to some extent, the basic task of on-line analytical optimization is to maintain the views effectively. Under all the above background, this paper integrates the on-line analytical functions into a self-developed accelerating engine for industrial application. Besides, it constructs a relational data warehouse DMWS with the character of distributed computing. And with a suite of optimization methods proposed for updating views, the maintenance efficiency of DMWS is sharply upgraded under the application of large-scaled workloads. This paper proposes a horizontal distributing technology hierarchically based on foreign keys searching and the measurement by selectivity. Firstly, in a breadth-first manner, a group of single-parent schemas linked by unilateral key referencing is detected either with high query frequency or at a heavy updating cost. Thus, the schema union is partitioned horizontally according to selectivity. Based on the trigger sub-system of the four-layer data warehouse, the strong consistency is achieved via round-robin placement. By sharing the schemas union among the autonomous sites with a horizontal manner, the proposed method obtains equilibration to guarantee the scalability of DMWS. And more importantly, due to the horizontal partitions obtained by selectivity, the system endows the updating relative to the complex views with conglomeration. IV 华华 中中 科科 技技 大大 学学 博博 士士 学学 位位 论论 文文 Under the horizontal distribution of the union set, this paper also gives a vertical partitioning method on the fact table among the autonomous sites. Via the decomposition of all the query patterns, a clustering model is constructed by the blocking operators. Therefore, the vertical partition acquired by both the relatively indiscernibility cluster and validity index, can exhibits a controllable partition granularity. And the temporal localization can be realized in the on-line analytical queries accordingly. The complexity and diversity of the queries in the on-line analytical processing not only increases the hardness of the view maintenance, but also provides the requirement of digging the view dependencies. This paper proposes a hierarchically updating method for the multi-join view by the use of auxiliary view. The weak and strong combination are deeply analyzed in the view of the。