Abstract: Why-not questions aim to seek clarifications on the missing tuples for query results. Answering why-not questions on database queries not only helps user better understand the query, but also improves data quality and the availability of database. To enhance the availability of graph database, this paper proposes an efficient explaining technique for why-not questions on approximate graph queries. This technique gives explanations for missing graphs, as well as some suggestions how to modify the initial query graph to let the missing graphs appear in the query result set. Algorithm for answering approximate graph queries includes two parts: the first part is a candidate generation phase, which proposes the basic algorithm according to frequency information of edges, and the improved algorithm by graph decomposition operation to acquire candidate operation set. And in the second part, in order to minimize the cost of modifying initial query graph, greedy algorithm and backtracking are proposed separately to select candidate operations. Reasonable greedy function is designed for greedy algorithm. The pruning trees based on candidate selection are built and three strategies for selecting candidate operations from the candidate set are proposed. The final candidate operation set includes the reasonable explanations for why-not questions on graph queries. According to experiments, the algorithm proposed in this paper can efficiently generate reasonable explanations for why-not questions on approximate graph queries.

Key words: approximate graph queries, why-not questions, backtracking, pruning strategy

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

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