物化视图研究

发表于 |

研究物化视图(materialized view)相关技术。

Maintenance of Materialized Views: Problems, Techniques, and Applications

什么是view，是从base (stored) relation衍生出来的relation。可以理解为从base table到derived table的函数，因此在访问时会涉及重复计算。
什么是materialized view？materialized view类似于一个cache，避免重复计算。materialized view上允许构建索引。
什么是view maintainance？在更新base relation的同时，更新view。
什么是incremental view maintainance？在某些情况下，只更新一部分view，而不是全部view。

Introduction

  1. Information
  2. Modification
    我们是直接处理update，还是将它作为先delete再insert来处理呢？
  3. Language
    这个view是如何表示的？是传统的SPJ？是否有聚合函数？有没有UNION？是Set还是Duplicate(即没有DISTINCT语义)？有没有Recursion？
  4. Instance

Information和Modification

考虑如下relation

1
part(part_no,part_cost,contract)

我们创建一个view，列出所有distinct的part_cost大于1000的part_no。注意，这里的Projection带Distinct语义。

$$
expensiveParts (partNo) = \Pi_{partNo} \sigma_{partCost>1000} (part)
$$

考虑insert下面条目情况

1
part(p1,5000,c15)
  1. 如果只有materialized view
    可以用老版本的判断part_no是否在view中。
  2. 如果只有base relation
    用relation part去查看是否存在同样的part_no，但是part_cost更大的，如果有，那么就不要更新了。
  3. 如果part_no is the key
    可以推断出part_no肯定不在view中。
    因为key保证了唯一性，因为我们insert成功了，所以肯定之前没有part_no。

考虑delete下面条目情况

1
part(p1,2000,c12)

显然p1在materialized view里面，但是不能断定是否还有类似于part(p1,3000,c13)这样的存在，因此不能直接从view中删除p1。事实上不能仅依赖materialized view来处理delete的情况。但如果有下面的，则可以：

  1. relation part
  2. key constraint
    【Q】How
  3. counts of number of view tuple derivations

考虑update情况，在某些算法中归结为先delete再insert，这种方式会丢失信息。Ref BCL89 UO92 GJM94。

Language和Instance

我们创建一个supp_parts，它是supp和part这两个relation的equijoin。列出了至少有一个supp的part的number，并且已经经过了distinct。

$$
suppParts(partNo) = \Pi_{partNo} (supp \bowtie_{partNo} part)
$$

现在考虑仅适用supp_parts，insert下面条目

1
part(p1,5000,c15)

如果supp_parts里面已经有了p1，那么无变化。但是如果view中没有p1，并不能仅通过这个view推断是否要insert。

Idea

使用数学语言来描述。
考虑link(a,b)表示从a到b的一个link，定义hop(X,Y)表示从X经过两个link能到达Y，有

$$
hop(X,Y) = \Pi_{X,Y} (link(X,V) \bowtie_{V=W} link(W,Y))
$$

Full Information

Comments

Reference

  1. https://en.wikipedia.org/wiki/Relational_algebra
    关系术语
  2. https://www.dotnettricks.com/learn/sqlserver/difference-between-inner-join-and-equi-join-and-natural-join
    介绍Natual join，equijion和inner join。