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

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