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

• 作者: 宗传玉 李金旭 杨晓春 王斌 贺丹
• 来源期刊: 计算机科学与探索
• 学科: 工学
• 关键词: 近似图查询 why-not问题 回溯法 剪枝策略
• 年，卷（期）: 2017,（12）
• 所属期刊栏目: 数据库技术
• 页码范围: 1871-1885
• 页数: 15页
• 分类号: TP311.1
• 字数: 10597字
• 语种: 中文
• DOI: 10.3778/j.issn.1673-9418.1608050

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	杨晓春	东北大学计算机科学与工程学院	65	1090	16.0	32.0
2	王斌	东北大学计算机科学与工程学院	101	945	14.0	28.0
3	贺丹	东北大学计算机科学与工程学院	1	1	1.0	1.0
4	宗传玉	东北大学计算机科学与工程学院	1	1	1.0	1.0
5	李金旭	东北大学计算机科学与工程学院	1	1	1.0	1.0