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

作     者：贺丹 宗传玉 王斌 李金旭 杨晓春 HE Dan;ZONG Chuanyu;WANG Bin;LI Jinxu;YANG Xiaochun

作者机构：东北大学计算机科学与工程学院沈阳110819 

基　　金：国家自然科学基金Nos.61572122 61322208 61272178 61532021 国家重点基础研究发展计划(973计划)Nos.61572122 61322208 61272178 61532021~~ 

出 版 物：《计算机科学与探索》 (Journal of Frontiers of Computer Science and Technology)

年 卷 期：2017年第11卷第12期

页      码：1871-1885页

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

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

学科分类：08[工学] 0835[0835] 081202[081202] 0812[工学-测绘类] 

核心收录：

D　O　I：10.3778/j.issn.1673-9418.1608050

馆 藏 号：203279961...