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

摘要

经过多年发展，数据仓库已广泛应用于各行业，随着时间的推移，数据仓库中的数据量迅猛增长，为了解决查询响应所需时间越来越长的问题，物化视图技术应运而生，并已成为数据仓库中的一个研究热点。物化视图技术将视图所对应数据加以实际物理存储，通过预计算的方式加快查询响应速度，然而，其本身也需要耗费大量的资源，因而如何选择一组合适的视图进行物化就成为数据仓库查询中的一个重要问题。现有的物化视图选择技术多为静态选择算法，在一定程度上与决策支持应用系统的动态特性相矛盾，而动态物化视图选择算法研究较少，且存在系统开销过大的缺点。针对这两者的不足，在前人研究的基础上，本文提出并实现了一个基于聚类的动态物化视图选择算法，该算法结合使用了所提出的静态物化视图改进算法与聚类改进算法。 本文在探讨了数据仓库、物化视图选择及聚类分析等技术的基础上，进行了基于聚类的动态物化视图选择方法研究，提出了一种基于聚类的动态物化视图选择算法CBD—MVS。该算法利用聚类技术来对数据仓库中的用户查询语句进行聚类，再对聚类后的各个簇中的用户查询语句进行合并，得到数量较少的候选物化视图，然后再选择一种合适的静态物化视图选择算法来得到最终的物化视图。 本文的主要研究内容为： 1．针对现有聚类算法在对用户查询语句进行聚类处理的不足，把频繁闭项目集应用到聚类分析技术中，通过对用户查询语句执行频繁闭项目集挖掘算法，得到基于属性字段的关联规则，并根据这些规则求得属性字段的关联度矩阵和特征向量，计算出属性字段集相似度，执行k均值聚类算法获得聚类结果。实验表明该方法得到了较好的聚类结果。 2．探讨了数据仓库技术及物化视图技术，着重研究了静态物化视图选择算法Greedy、BPUS和PBS，并分析其不足之处，提出了一种改进算法BGA。该算法使用启发式搜索算法的思想搜索格图，利用数据立方体格图之间存在的依赖关系，结合代价模型筛选出具有最大效益的物化视图，并将存储空间与新增效益共同作为阈值，在获得了与BPUS算法相同视图查询代价效果时，所耗费的时间明显少于后者。实验证明该算法是十分有效的。 3．研究了数据仓库中物化视图的动态选择问题，针对现有物化视图选择算法的不足，提出了一种基于聚类的动态物化视图选择算法CBD—MVS。该算法采用基于频繁闭项目集的聚类算法对用户查询语句进行聚类，应用视图合并算法建立候选物化视图，利用改进的静态选择算法BGA生成最终应该被物化的视图。实验表明该算法是有效可行的。

目录

文摘

英文文摘

声明

第一章绪论

1.1研究背景及意义

1.2国内外研究现状

1.3本文的主要工作

1.4本文的结构安排

第二章 数据仓库与物化视图技术

2.1数据仓库的定义及特点

2.2数据仓库的体系结构

2.3多维数据模型

2.3.1星型模型

2.3.2雪花模型

2.4.物化视图技术

2.4.1物化视图的选择

2.4.2物化视图的维护

2.4.3物化视图的利用

2.5本章小结

第三章 基于频繁闭项目集的聚类算法研究

3.1聚类分析基本概念

3.1.1聚类分析定义和分类

3.1.2距离和相似系数

3.1.3聚类分析的过程

3.2频繁闭项目集挖掘算法研究

3.3基于频繁闭项目集的聚类算法

3.3.1算法流程设计

3.3.2关联度计算

3.3.3相似度计算

3.3.4执行k均值聚类算法

3.4实验结果与分析

3.5本章小结

第四章 静态物化视图选择算法研究

4.1数据立方体格图

4.2代价模型

4.2.1 代价估算

4.2.2效益公式

4.3静态物化视图选择算法

4.3.1 Greedy算法

4.3.2 BPUS算法

4.3.3 PBS算法

4.4静态物化视图选择算法改进

4.4.1算法思想概述

4.4.2算法伪代码描述

4.5实验结果与分析

4.6本章小结

第五章 基于聚类的动态物化视图选择算法研究

5.1候选物化视图的获取

5.2物化视图的选择算法

5.2.1代价模型

5.2.2目标函数

5.2.3物化视图的选择

5.3算法流程设计

5.4实验结果与分析

5.5本章小结

第六章 总结与展望

6.1总结

6.2展望

参考文献

致谢

附录