目录
第 一章 绪论 1
研 究问题的背景 1
研 究问题的挑战 2
当 前研究工作的不足之处 2
本 文的工作要解决的问题以及方法 2
本 文的贡献 3
章 节安排 3
第 二章 系统/方法框架 3
第 三章 Multi-Dimensional Lattice 3
第 四章 Multi-objective Genetic Algorithm 4
4.1 .1 多目标遗传算法 4
4.2 .2 Pareto-ranking approaches 4
4.3 .3 种群多样性：Fitness sharing, niching 5
4.4 .4 MOGA 6
第 五章 实验 6
实 验设计 6
实 验结果 8
第 六章 相关工作 8
第 七章 结论 8
参 考文献 9
第 一章 绪论
物化视图用作减少针对数据仓库提出的分析查询的响应时间的替代方法。由于无法物化所有视图，
并且最佳视图选择是 NP 难问题，因此需要选择合适的视图子集进行物化，以减少分析查询的响应时间。本文使用多目标遗传算法(MOGA)解决了同时最小化两个成本的双目标优化问题。提出的基于 MOGA 的 MVS 算法从多维点阵中选择 Top-K 视图，目的是在上述两个目标之间实现最佳权衡。实现这些选定的 Top-K 视图将减少分析查询的响应时间，从而导致有效和高效的决策制定。
研 究问题的背景
如今，有关客户购买行为、营销、销售和产品的数据分析已成为日常业务的重要组成部分。跨国公
司利用这些数据分析结果做出关键的业务相关决策，以保持在全球市场上的竞争力。这些公司收集日常 交易信息数据，来自遍布全球的多个不同位置，用于分析。
有两种方法可以从这些不同的数据源访问这些数据，即在查询时（按需方法）或通过预先积累数据以供 将来查询（提前方法）。后一种方法更方便，因为考虑到数据是在本地累积和存储的，因此可以高效地 回答查询。但是，每当源数据库发生更改时，需要频繁更新这些聚合数据。在这种方法中，数据需要存 储在中央存储库中，以便进行查询和分析。该中央存储被称为数据仓库。数据仓库存储从多个不同数据 源积累的相关数据，用于回答分析问题决策者提出的查询。分析性查询为决策制定而提出的问题庞大而 复杂，当针对不断增长的数据仓库提出问题时，这些问题的响应时间很长。减少此查询响应时间的一种 方法是具体化数据仓库中的一组适当的视图，可以为决策查询提供答案。与虚拟视图不同，物化视图包 含预先计算和聚合的数据及其定义。物化视图比数据仓库小得多，如果选择得当，可以在缩短响应时间 的情况下为大多数分析性查询提供答案，从而实现高效决策。MVS 问题与选择这些明智的视图集有关。这个问题可以描述为从所有可能的视图中为给定的数据库模式选择一组适当的视图，以减少查询响应时 间，同时将维护和查询处理成本降至最低。视图选择的另一种定义是，针对给定的查询工作负载，在可 用存储空间内选择数据库模式上的一组视图。
大多数视图选择算法遵循经验或启发式方法。在经验方法中，视图选择基于过去的查询模式。在基于启
发式的方法中，对可能视图的大搜索空间进行修剪，以选择接近最优的视图子集进行具体化。广泛用于 选择视图的框架有多维晶格（Multi-Dimensional Lattice, MDL）、和/或视图图（AND/OR view graph）和多视图处理计划（Multi-View Processing Plan, MVPP）。在本文中，视图选择考虑了 MDL 框架。
研 究问题的挑战
由于可以物化的可能视图的数量随着维度数量的增加呈指数增长，而且对于更高维度，由于存储空
间的限制，不可能物化所有视图。此外，最佳视图选择是一个 NP 难问题。因此，唯一的替代方法是物化一个近似的视图在满足资源约束（即存储空间、视图维护成本等）的同时，适当减少查询响应时间的 视图子集。从所有可能的视图中选择这样的视图子集进行物化称为物化视图选择（MVS）。MVS 问题是数据仓库设计中最具挑战性的问题之一。
当 前研究工作的不足之处
最基本的视图选择算法，即（Harinarayan et al. 1996）中给出的贪婪算法，以下称为
,从 MDL 中选择 Top-K 视图。但是对于高维度来说 无法从 MDL 中选择 Top-K 视图。
本 文的工作要解决的问题以及方法
由于贪婪算法在高维中不可行，因此选择基于启发式的方法，如 randomized, evolutionary 和
swarm，通过最小化系统的总成本来解决 MVS 问题。本文选择多目标遗传算法（MOGA）解决同时最小化两个成本的双目标优化问题，其中成本分别是物化视图评估的总成本 与非物化视图评估的总成本 。
