上一篇我们读了vldb的 index selection 综述之后，自然想到看一下有没有视图选择的综述，检索发现 sigmod 2012年有一篇，于是我们来看一下两个问题具体有哪些不同。
MAMI I, BELLAHSENE Z. A survey of view selection methods[J]. Acm Sigmod Record, 2012, 41(1): 20-29.
同样，Abstract 和 Intro 都是说明本文是一篇视图选择的综述，看下本文剩下的章节组织：
- sec 2 问题定义
- sec 3 讨论视图选择问题的 dimension 和归类
- sec 4 survey，大致概括了二十多篇视图选择文献，所以基本都是比较简略的介绍，主要在于分类
- sec 5 conclusion & open issue
sec 2 是视图选择问题的形式化定义，本来应该详细的介绍的，但是感觉这样我只是在搬运论文的内容。总结一下比索引选择综述里额外提及的内容吧。
本文还提到了分布式环境下的视图选择，但没有给出形式化定义；除了 Query Cost 的计算方式之外，还提到了视图的维护开销和分布式场景中需要考虑的通信开销。
现在看来（指写博客时我的知识水准），分布式环境下的视图选择很不好做，可借鉴的相关研究也少（没什么特别的创新点？），我是没什么头绪能做。
另外就是，sec 2.4 提到了 Static View Selection 和 Dynamic View Selection。二者的区别在于面向的工作负载不同，静态视图选择面向的工作负载是静态的，指算法在运行前就能拿到完整的 workload，并且验证时 workload 也不会发生改变；而动态负载则是算法并不能在一开始获取 workload 的所有 queries，查询可能在算法运行过程中不断到达，或者在某个时间段整体发生改变。
但是动态工作负载并没有统一的定义，这可能需要根据实际的应用场景确定什么是“动态”。而且相关的研究也仅有二十多年前零星几篇，本文大部分介绍的算法都属于静态。所以我后来编问题定义的时候真是掉了不少头发。
sec 3 的标题和小节标题整得我有点迷惑（3.2 constraints 还好理解，3.1 framework 是什么啊）。实际上 3.1 介绍了视图选择方法通常分为两步，第一步是产生 view candidates，第二步是应用选择方法在 candidates 中选出解决方案。只不过接下来几个 subsubsection 直接介绍了四类生成 view candidates 的方法，而不包括视图选择算法，感觉与 framework 这个标题有些不太搭，或者说上下文逻辑有些不够连贯。
sec 3.2 Resource Constraints 大概介绍了 Space Constraints 和 Maintainance Constraints，但是考虑维护开销的比较难做，很多研究设置的场景也是只考虑空间限制的。
sec 4 就是大篇幅的对之前研究的分类和综述了，具体内容这里也不提，来看下大致的分类。sec 4 下分有4个小节，将之前的工作分为4类：
- Deterministic Algorithm Based Methods. 穷举、贪心、heuristic方法都归在 “确定性” 方法类别下，也是2000年前后大部分工作采用的研究方法。以贪心居多，几篇看上去比较重要的论文贴在下面。
[1] BARALIS E, PARABOSCHI S, TENIENTE E. Materialized view selection in a multidimensional database[C]//VLDB: vol. 97. 1997: 156-165 // 贪心
[2] GUPTA H, MUMICK I S. Selection of views to materialize under a maintenance cost constraint[C] //International Conference on Database Theory. 1999: 453-470 // 考虑维护开销的贪心方法
[3] YANG J, KARLAPALEM K, LI Q. Algorithms for materialized view design in data warehousing environment[C]//VLDB: vol. 97. 1997: 136-145 //介绍MVPP候选生成方法 - Randomized Algorithm Based Methods. 这一类别下主要有各种爬山算法、遗传算法和模拟退火算法等，根据我粗浅的了解，这些方法就是按照某个概率以一定随机性选择 solution，直到算法慢慢收敛。但是一般都不能保证收敛于全局最优。后续的应用似乎也少，没深入再看。
- Hybrid. 混用确定性和随机方法的方法，通过确定性方法找到随机方法的初始解，再开始迭代。只有一篇，不看。
- Constraint Programming Based Methods. 把视图选择问题建模为约束规划问题，也没细看，Integer Linear Programming（ILP）应该也属于这类别。但我知道的是有部分文章的确转为 ILP 进行处理。 // TODO：贴一下文章引用
最初我看完之后，总结得出几条信息：
- 2012年SIGMOD综述中，大多数算法都是对静态的 workload 进行视图选择，即运行算法需要获取 workload 包含的所有查询；几乎没有能够进行动态视图选择的。
- 在分布式场景下的选择算法研究较少（只有3篇文献提及，具体内容还没看；
- 论文也没有对各种算法的性能进行统一的对比，仅仅分析了算法特点和缺陷（可以考虑实现算法做一些对比实验，如果能力可及）
以及有一个疑问：如何看该综述之后，view selection 还有没有新的研究？
师兄告诉我说，你按照被引去查一下几个顶会在这之后还有没有相关文章，没有的话就是没有了。 然后我去看了，ICDE近几年还有几篇基于RL做视图选择的，其他非顶会就只有一些乱七八糟的文章，质量一眼看上去就不行，所以似乎可以说基本没有了。
The End