贺 丹，宗传玉，王 斌，李金旭，杨晓春

东北大学 计算机科学与工程学院，沈阳 110819

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

贺 丹，宗传玉，王 斌，李金旭，杨晓春+

东北大学 计算机科学与工程学院，沈阳 110819

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

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

1 引言

目前，数据库系统在资源存储和查询处理方面都十分高效。然而，随着用户需求的不断提升，一方面，用户对最终的查询结果不够满意；……