数据库实验室林子雨老师小组第六次小组会议会议纪要
会议时间：2012年08月24日14时30分到17时30分
会议地点：厦门大学海韵园科研二号楼303室
与会者：林子雨、赖明星、刘颖杰、殷耀明、韩静
会议内容：
厦门大学计算机系数据库实验室林子雨老师小组第六次小组会议如期召开，会议首先由刘颖杰同学作题为《A Hidden Markov Model Approach to Keyword-Based Search over Relational Databases》的论文阅读报告，随后由赖明星同学作题为《Flashing Up the Storage Layer》的论文阅读报告，最后由林子雨老师作题为《数据库领域前沿研究调研报告》的报告，此次报告补充的主要内容是面向缓存的替换策略。下面是详细内容。
- 刘颖杰同学作题为《A Hidden Markov Model Approach to Keyword-Based Search over Relational Databases》的学习汇报
在此次会议中刘颖杰同学作论文阅读报告，该报告的主要内容是分析在无法获得数据库实例细节的情况下，如何利用有限的数据实现关系数据库上的关键词查询功能，此次报告探讨了通过隐式马尔科夫模型的架构，分析有序关键词序列得到SQL语句形式的解释并返回查询结果，同时利用HITS算法，根据返回结果的权威值进行排序的实现方式。
- 隐式马尔科夫模型（Hidden Markov Model）
隐马尔可夫模型（Hidden Markov models，HMM）是马尔可夫链的一种，它的状态不能直接观察到，但能通过观测向量序列观察到，每个观测向量都是通过某些概率密度分布表现为各种状态，每一个观测向量是由一个具有相应概率密度分布的状态序列产生。所以，隐马尔可夫模型是一个双重随机过程，具有一定状态数的隐马尔可夫链和显示随机函数集。其中马尔科夫链描述了状态的转移, 一般用转移概率矩阵描述；而一般随机过程描述状态和观测序列间的关系，用观察概率矩阵描述。
在本例中，将用户输入的有序查询序列作为可观察到的向量，将关键词对应的数据库部件作为需要推测的输出，通过隐式马尔科夫模型中提出的推测方式，即transition概率和emission概率寻找最大可能的序列，从而得到所要的SQL语句。
- HITS算法
HITS算法常用于分析网页的重要性。
算法对返回的匹配页面计算两种值,一种是枢纽值(Hub Scores)，另一种是权威值（Authority Scores）这两个值是相互依存、相互影响的。所谓枢纽值，指的是页面上所有导出链接指向页面的权威值之和。权威值指的是所有导入链接所在的页面的枢纽值之和。
本例中由于数据库模型中的表与网页有想通之处，即数据库中各个表也存在作为枢纽指向其他表以及本身内容的权威性两个性质，所以将HITS算法引入，以此对每张表的权威性做一个计算从而优化HMM模型中的相关数据。
- 赖明星同学作题为《 Flashing Up the Storage Layer》的论文阅读报告
赖明星同学此次的论文报告可以分为四个部分，先是开门见山的提出论文思想和解决的问题，其后对论文中解决相应问题的算法进行了详细分析，最后给出实验结果，具体内容如下：
- 论文思想
论文作者通过对闪存的读写操作和硬盘的读写操作进行比较分析发现，闪存虽然读操作非常快，但是它的随机写操作还不如硬盘。论文的主要思想就是将读密集的数据存储于闪存之中，将写密集的数据存储于硬盘当中，如此形成了闪存和硬盘位于存储结构同一层的存储方式。由于论文采用了闪存和硬盘共同作为第二存储设备，所以论文的关键就在于页的存放，如何判断页放置于闪存还是硬盘是论文的讨论重点。
- 页的存放
页的存放是指将页存放于闪存之中，还是存放于硬盘之中，并且根据之后的工作负载进行相应的调整，页的调整就是一个典型的双状态转移模型。论文提出的三种页的存放算法分别是：(1)保守算法(2)乐观算法(3)混合算法。其中，保守算法只考虑页的物理操作，对每一次的物理操作进行记录，当代价超过某一上限，就将其转移到另一种存储设备上，乐观算法只考虑页的逻辑操作，对页的读写操作进行计数，最后根据读写计数器，以及不同存储设备的读写代价判断将该页存储于那种存储设备。混合算法则是上面两种算法的结合，不仅考虑物理操作还考虑逻辑操作。
- 页的替换
页的替换用于管理缓冲，与传统的缓冲管理策略不同的是，论文中提出的缓冲管理策略不仅考虑到页的新旧（时间戳），还考虑了页的替换代价。其基本思想是将缓冲区分为按时间戳排序的时间区和按替换代价排序的代价区，每次新来一页都将该页插入到时间区，每次替换一页，都从代价区进行替换，在代价区进行替换的时候，按照代价的大小，从小到大进行替换。
- 实验结果
论文对这种闪存与硬盘共同作为第二存储的存储结构进行的广泛的实验，包括对使用硬盘、闪存和两者都使用的时间开销进行评估，以及对不同的页存放算法进行比较，最后讨论了时间区和代价区的分配比例。
- 林子雨老师作题为《数据库领域前沿研究调研报告》的报告
林老师此次报告的副标题为《面向缓存的替换策略》，此次报告详细介绍了基于闪存的存储结构中，面向缓存的替换策略，具体内容如下：
- 基于闪存存储结构中面向缓存的替换策略的考虑因素
- CFLRU 缓存替换策略
- CFDC 缓存替换策略
因为闪存的读写效率不一致，所以在基于闪存的存储结构中，缓存的替换策略不能像以前一样只考虑命中率，需要考虑缓存替换时，不同数据的替换代价。随后林老师介绍了一种缓存替换策略CFLRU，分析了CFLRU的缺点，并介绍了它的改进替换策略CFDC。