论文部分内容阅读
关系数据库上关键词检索研究如何在关系数据库系统中提供类似搜索引擎的关键词检索能力，使用户可以不用了解关系数据库的模式信息，也不用掌握SQL语言就能方便的检索数据库信息。这种功能可以极大地提高数据库系统的可用性、易用性。同时，在Internet环境中，不用再开发专门的用户接口，只需要提供一个类似搜索引擎一样的关键词检索的简单接口，方便在Web上发布数据库中的数据，使得Web上数据库的集成变得更容易。 关系数据库上关键词检索系统一般分为在线系统和离线系统，离线系统预处理时间比较长，不能及时反应数据的更新变化，但效率比较高;在线系统没有预处理时间，实时执行转换而来的SQL查询，可以及时反映数据的最新变化，但是在线系统要把关键词查询转化成许多SQL查询，而这种查询中往往含有很多JOIN操作，所以执行效率比较低。 因此，主要研究关系数据库上基于模式图的在线关键词检索系统的性能优化，以提高这种实现技术的效率，使得数据库上关键词检索技术最终能够真正走向实用。 研究是基于EfficientIR系统来做改进工作，研究如何在原有系统中加入PreCN和CNSela模块，提高系统的性能。系统中查询主要包括三部分时间:元组集生成时间，候选网生成时间和SQL查询时间，要提高查询效率，就要想办法缩短这三部分的时间，由于元组集生成时间与数据库系统搜索引擎相关，一般很难优化，因此工作重点就落在如何缩短候选网生成时间和SQL查询时间上面，也就是PreCN和CNSela模块实现的功能。 考虑到Efficient IR系统支持的是OR语义的查询模式——这意味着为每个关系生成一个Tuple set（具有文本属性的关系），对于给定数据库模式，给定查询来说，可以生成的元组集组合数tuple sets就是可以确定的。因此可以对 CN生成进行预处理，称为PreCN，对查询进行模式归类，对最大的查询模式进行预处理，生成候选网预存在数据库中，遇到相同的查询模式，从DB中直接提取候选网，而不用再通过图的宽度优先搜索算法来重新生成了，就避免了重新扩展的浪费。这样可以大大提高生成 CN的速度，减少Tcn，从而提高系统效率。 CNSela算法主要采用基于静态和动态混合的学习方法来建立 CN的语言模型，采用向量空间模型VSM计算查询和CN之间的相似性，从而可以选择最有可能产生TOPK查询结果的那些CN，提交TOPK算法执行模块执行。根据学习算法建立的 CN语言模型对CN进行选择，可以有效解决由于 MPFS盲目估计而产生的无效CN执行和参数组合爆炸问题，大大提高TOPK算法执行效率，减少Tsq(l)，从而提高整个KSORD系统的效率。 还对已有的 SPARSE算法进行了改进。在做 SPARSE算法的实验过程中，我们遇到了比较严重的信息爆炸问题。SPARSE算法是基于最大可能分数(Maximum Possible Future Score，MPFS)估计来选择下次执行的CN，以实现TOPK查询。但是MPFS估计比较盲目，往往估计过高，导致可能根本没有查询结果的CN也要被大量执行。尤其是算法采用参数化SQL语句，要求每个CN至少执行一次，由于多表做连接会生成巨大的元组结果集，占用大量系统资源，发生信息爆炸问题，使得TEMP表空间迅速膨胀啊，最后甚至根本得不到结果。采用SPARSE算法与SA算法相结合的方法，可以有效的改善信息爆炸问题，尤其是表空间的占用问题。在单个CN内部，执行算法不采用原来的Na(i)ve算法，而是用Single Pipelined算法。用这种方法可以有效的解决临时表空间的占用问题，提高算法的效率。 原来的程序中，关键字的抽取是随机的，并不知道，下一个关键字的组合会生成什么样的元组集图。对一个固定的数据库来说，查询会相对集中在几个固定的模式上。因此设计查询关键字的组合，使得查询生成的元组集图符合需要的模式。 最后修改已有的EfficientIR系统，并建立了IMDB数据集，将实验从DBLP数据集移植到IMDB数据集上，使得系统与数据库模式独立，并用实验验证了优化算法与数据库模式的独立性。