物化视图研究

研究物化视图(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

术语表:

  1. π,表示Projection
    在实现中,Projection并不是返回DISTINCT的值,需要DISTINCT关键字来返回真正的DISTINCT的值。
  2. ρ,表示Rename
  3. σ,表示Selection
  4. ⋈,表示Natual Join
  5. ⋉和⋊
    当某行在另一个表中没有匹配行时,则另一个表的选择列表列包含空值。
  6. ÷
  7. θ-join和equijoin

概念表:

  1. equi join/inner join/natual join
    equijoin是用等于号连接的join,而inner join可以用<这样的符号join。
    equijoin可能是inner join,也可能是Left Outer或者Right Outer Join。
    Natual Join是一种equijoin,他会比较所有的同名列。

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。