利用SPJ视图设计全局数据仓库

### 利用SPJ视图设计全局数据仓库 #### 1. 引言 在数据仓库方法中，数据会提前从多个分布式异构数据库和其他信息源中提取出来，存储在数据仓库（DW）中。当针对DW发出查询时，可以在本地进行评估，而无需访问原始信息源。DW常用于公司的决策支持应用，因此确保高查询性能是实现DW时的重要挑战之一。 DW可以抽象地看作是一组基于源关系定义的物化视图。当源关系发生变化时，物化视图需要更新，这可以采用不同的维护策略，如延迟或立即维护，以及增量或重新物化策略，具体选择取决于应用对数据时效性和视图维护性能的需求。 典型的DW架构包含三层。底层是分布式操作数据源，中间层是全局或主数据仓库，上层是本地DW或数据集市。全局DW整合分布式数据源的数据，数据集市包含高度聚合的数据，用于广泛的分析处理，且更新频率可能低于全局DW。 在本文中，我们关注给定一组输入查询时，如何选择视图进行物化的问题，这是实现DW的重要决策，而当前商业产品并未提供自动设计DW的工具。该问题复杂的原因之一在于输入查询可能包含公共子表达式，检测和利用这些公共子表达式可以显著降低视图维护成本和物化所需的空间。 我们提出了一种设计全局DW的通用方法，该方法能检测和利用查询之间的公共子表达式，并保证查询可以在所选视图上完全重写。我们还提供了一组针对选择 - 投影 - 连接（SPJ）查询的转换规则，从输入查询开始，生成用于物化的替代视图选择，并实现查询在所选视图上的完全重写。这些转换规则是合理、最小且完整的，所有“重要”的视图选择都能非冗余地生成。 我们要解决的DW设计问题如下：给定一组要由DW满足的查询，选择一组视图进行物化，使得： 1. 物化视图能适应DW可用的空间。 2. 所有查询都可以使用这组物化视图在本地回答。 3. 查询评估成本和视图维护成本（运营成本）的组合最小。 基于转换规则，我们将DW设计问题建模为状态空间搜索问题，并设计了算法来显著修剪搜索空间。 #### 2. 相关工作 视图选择问题在不同上下文中被许多作者研究过： - [5]提供了在聚合和多维分析上下文中，在空间约束下最小化查询评估成本的视图选择算法。 - [4]在此基础上扩展，提供了选择视图和索引的贪心算法。 - [3]在查询以AND/OR表达式有向无环图表示时，提供了视图选择问题的贪心算法。 - [9]针对物化SQL视图，提出了穷举方法和启发式方法来选择额外视图以优化总视图维护成本。 - [6]考虑了选择 - 连接视图和索引的相同问题，并讨论了空间因素。 - [8]利用键和引用完整性约束，为SPJ视图导出一组辅助视图，使视图能够自我维护。 - [10, 14]旨在优化查询评估和视图维护的组合成本，[10]在视图被视为指针数组集且有空间约束的情况下提供了A*算法，[14]考虑了无空间约束的物化视图问题，[3]对在空间约束下最小化组合成本的视图选择问题进行了形式化，但未提供通用解决方案。 然而，之前的方法都没有要求查询只能从物化视图中回答，而[12, 13]考虑了这个要求，但仅针对一类选择 - 连接查询。 #### 3. DW设计问题的正式陈述 假设给定一个非空查询集Q，定义在一组源关系R上。DW包含一组基于R的物化视图V，使得Q中的每个查询都可以在V上完全重写。令Q是一个基于R的查询，QV表示Q在V上的完全重写。给定Q，DW配置C是一个对 < V, QV >。 对于DW配置C = < V, QV >，查询评估成本E(QV)是QV中每个查询重写评估成本的加权和，视图维护成本M(V)是V中每个视图在其他视图存在时的维护成本的加权和，运营成本T(C) = cE(QV) + M(V)，其中参数c表示查询评估成本和视图维护成本的相对重要性。物化视图所需的存储空间S(V)是V中每个视图物化所需空间的总和。 DW设计问题的输入包括： - 一组查询Q。 - 函数E（查询评估成本）、M（视图维护成本）和S（物化视图空间）。 - DW可用于物化的空间t。 - 参数c。 输出是一个DW配置C = < V, QV >，使得S(V) ≤ t，且T(C)最小。 #### 4. 转换规则 为了将DW设计问题建模为状态空间搜索问题，我们引入了一组针对一类SPJ视图的DW配置转换规则，这些规则基于多视图的图表示。 ##### 4.1 多查询图 我们考虑一类关系表达式，它们等价于标准形式πXσF (R1 × ... × Rk)的关系表达式。其中Ri表示关系，F是原子公式的合取，形式为A op B + c或A op B，op是比较运算符（=, <, ≤, >, ≥），c是整数值常量，A和B是Ri的属性。涉及一个关系属性的原子称为选择原子，涉及两个关系属性的原子称为连接原子。所有Ri都是不同的，X是Ri的非空属性集。查询和视图都属于这一类。 视图可以用查询图表示。对于视图V = πXσF (R1 × ... × Rk)，其查询图GV是一个节点和边带标签的多重图，定义如下： 1. GV的节点集是关系R1, ..., Rk。每个节点Ri用视图V的属性标签标记，即Ri在X中的属性集（可能为空），前缀为V。如果节点Ri上的属性标签为V : *，表示在视图V的定义中，Ri的所有属性都被投影出来。 2. 对于F中涉及关系Ri的一个或两个属性的每个选择原子p，在GV中Ri上有一个标记为V : p的环。 3. 对于F中涉及关系Ri和Rj属性的每个连接原子p，在GV中Ri和Rj之间有一条标记为V : p的边。 一组视图V可以用多查询图表示，它通过合并每个视图的查询图来紧凑表示多个视图。对于视图集V，对应的多查询图GV是一个节点和边带标签的多重图，通过合并V中视图查询图的相同节点得到。GV中节点Ri的标签是V中视图查询图中