物化视图通过将预计算的结果存下来，能极大地减少查询的开销和时间。物化视图的查询优化问题是一个视图的匹配问题，即给定一个Query和一系列的物化视图，我们需要找到与之匹配的物化视图，并从物化视图中计算出相应的结果。

注意这里的Query不是指的一条SQL对应的整个Query，而是指其中的一部分，也包括查询优化过程中生成的各种等价的变换。

问题描述

首先，我们假设优化器是cascades style的transformation based的优化器，这个也是目前CBO优化其的主流pattern。

其次，我们主要考虑的问题是怎么使用单个的View来计算出Query。对于从多个View来计算Query一般有2中情况：通过join或者union。多个view来join的情况，由于优化器针对原始Query做各种变换，因此会最终还是会落到单个View来计算。而通过Union多个View的情况则比较复杂，通用的算法比较难，只能针对单独的case来落地，比如时间窗口等。

selection条件的改写

SPJ Query: A query which consists of selection, projection, and inner joins of base tables. By base table we mean direct reference to table, derived table from subquery not included.

SPJG Query: A SPJ query with a final group by operation.e

SPJ Query通常可以看作笛卡尔积后面跟着selection和projection，为了方便后续的计算，我们需要将selection的条件$P$做一些改写，来方便后续的计算。首先需要将e改写成CNF的形式：

$$ P = P_1 \land P_2 \ldots \land P_n $$

我们将每个条件$P_i$划分到一下三类中去：

• 等值条件PE: $T_i.C_j = T_m.C_n$，其中$i$和$m$可能一样。
• 范围比较PR: $T_i.C_j\ op\ c$，其中$op$是$\le, \lt, \ge, \gt, =$几个操作符之一，$c$是一个常量。
• 其他条件PU

那么我们可以将selection条件改写为如下形式：

$$ P = PE \land PR \land PU $$

Column Equivalence Class

通过将PE中的条件进行聚类，我们可以得到column equivalence class。举个例子假设PE由以下条件组成：