支持近似图查询的Why-Not问题解释方法

摘要：

why-not问题是为查询结果中的缺失元组找到合理的解释.解决数据库查询中的why-not问题不仅能够帮助用户更好地理解查询,而且能够提高数据库的质量和可用性.为了提高图数据库的可用性,提出了支持近似图查询的why-not问题解释方法.该解释方法不仅阐明了为什么why-not问题没有出现在查询结果中,而且给出了一些修改初始查询图的建议,使得why-not问题能够出现在修改后的查询图的查询结果中.该算法分两部分完成:第一部分为候选修改操作生成阶段,首先利用边频率信息提出候选操作集生成基本算法,接着利用图分解操作提出候选操作集生成改进算法,得到修改初始查询图的候选操作集;第二部分基于对查询图修改操作数最少的代价模型,分别采用贪心算法和回溯法选取候选操作,贪心算法设计了合理的贪心函数,回溯法构建了回溯剪枝树,并提出三种剪枝策略执行剪枝操作,最终选取的候选操作集即为支持近似图查询的why-not问题的合理解释.实验表明,该方法可以快速有效地为近似图查询中的why-not问题提供合理解释.

关键词：近似图查询、why-not问题、回溯法、剪枝策略

所属期刊栏目：11

分类号：TP311.1(计算技术、计算机技术)

资助基金：The National Natural Science Foundation of China under Grant Nos. 61572122, 61322208, 61272178, 61532021;the National Basic Research Program of China under Grant No. 2012CB316201 国家重点基础研究发展计划973计划

在线出版日期：2017-12-26（万方平台首次上网日期，不代表论文的发表时间）

页数：共15页

页码：1871-1885