维护成本约束下物化视图的选择

### 维护成本约束下物化视图的选择 #### 1. 相关工作 近年来，数据仓库中物化视图的选择问题备受关注。不同的研究工作从不同角度对该问题进行了探讨： - 部分研究致力于在给定空间约束下，最小化总查询响应时间来选择物化视图。例如，Harinarayan 等人针对数据立方体或其他 OLAP 应用，提出了多项式时间的贪心算法，能给出接近最优的解决方案；Gupta 等人将研究结果扩展到数据立方体中视图和索引的选择；Gupta 还对数据仓库中一般视图选择问题进行了理论阐述，并将结果推广到多种视图图类型。 - 还有一些研究提供了各种框架和启发式方法，以优化查询响应时间和视图维护时间之和，且不考虑资源约束。但这些启发式方法大多是穷举搜索，或者对解决方案的质量没有性能保证。 而本文是首次解决在给定总视图维护时间约束下，选择物化视图的问题。 #### 2. 动机与贡献 以往设计多项式时间近似算法解决视图选择问题的工作，大多仅适用于磁盘空间约束的情况。然而在实际应用中，磁盘空间成本较低，真正限制我们物化所有视图的因素是维护物化视图的时间。通常，源数据的更改会被排队，并在大型批量更新事务中定期传播到仓库视图，更新事务一般在夜间进行，以确保白天仓库可用于查询和分析。因此，存在对物化视图维护时间的约束。 本文考虑的是维护成本视图选择问题，即在维护时间约束下，选择一组视图进行物化，以最小化查询响应时间。该问题是 NP 难问题，因为磁盘空间约束下的视图选择问题是其特殊情况，而已知磁盘空间约束下的视图选择问题是 NP 难的。 磁盘空间约束和维护成本视图选择问题存在显著差异： - **磁盘空间约束**：视图的查询收益不会随其他视图的物化而增加，未选择视图的单位空间查询收益会随其他视图的选择单调递减，这一特性被定义为收益函数的单调性。 - **维护成本视图选择**：视图的维护成本可能随其他视图的物化而降低，导致视图的单位维护成本查询收益可能增加。两个“依赖”视图的总维护成本可能远低于单个视图维护成本之和，使得依赖视图的单位维护成本查询收益有时远大于单个视图。这种查询收益函数的非单调行为使得维护成本视图选择问题难以处理。 本文的贡献包括： - 识别了维护成本视图选择问题及其难点。 - 开发了几种算法来解决该问题，对于一般 OR 视图图中的维护成本视图选择问题，提出了贪心启发式算法，并证明该算法能给出接近最优的解决方案。 - 为一般 AND - OR 图提出了 A* 启发式算法，性能研究表明，贪心启发式算法在 OR 视图图中几乎总能返回最优解。 #### 3. 预备知识 为了更好地理解后续内容，下面给出一些相关定义： - **表达式 AND - DAG**：视图或查询 V 的表达式 AND - DAG 是一个有向无环图，以基本关系（和物化视图）为“汇点”（无出边），节点 V 为“源点”（无入边）。若节点 u 有出边指向节点 v1, v2, ..., vk，则 u 可由 v1, v2, ..., vk 计算得出，这种依赖关系通过绘制一个半圆（AND 弧）连接边 (u, v1), (u, v2), ..., (u, vk) 表示。每个 AND 弧都有一个运算符和查询成本。 - **表达式 ANDOR - DAG**：视图或查询 V 的表达式 ANDOR - DAG 是一个有向无环图，以 V 为源点，基本关系为汇点。每个非汇点节点 v 都有一个或多个 AND 弧，每个 AND 弧绑定节点 v 的一部分出边。每个 AND 弧都有一个运算符和成本，节点处的多个 AND 弧表示计算该节点的多种方式。 - **AND - OR 视图图**：以基本关系为汇点的有向无环图 G，若对于每个视图 Vi，G 中都有一个子图 Gi 是 Vi 的表达式 ANDOR - DAG，则称 G 为视图（或查询）V1, V2, ..., Vk 的 AND - OR 视图图。AND - OR 视图图中的每个节点 v 都有查询频率 fv、更新频率 gv 和读取成本 Rv 等参数，并且图 G 关联一个维护成本函数 UC，用于计算在一组物化视图 M 存在的情况下，维护视图 v 的成本。 - **评估成本**：嵌入在 AND - OR 视图图 G 中的 AND - DAG H 的评估成本是 H 中 AND 弧的成本之和，加上 H 中汇点/叶子节点的读取成本之和。 - **OR 视图图**：OR 视图图是 AND - OR 视图图的特殊情