This paper studies the problem of answering Why-questions for graph pattern queries. Given a query Q, its answers Q(G) in a graph G, and an exemplar E that describes desired answers, it aims to compute a query rewrite Q', such that Q'(G) incorporates relevant entities and excludes irrelevant ones wrt E under a closeness measure. (1) We characterize the problem by Q-Chase. It rewrites Q by applying a sequence of applicable operators guided by E, and backtracks to derive optimal query rewrite. (2) We develop feasible Q-Chase-based algorithms, from anytime solutions to fixed-parameter approximations to compute query rewrites. These algorithms implement Q-Chase by detecting picky operators at run time, which discriminately enforce E to retain answers that are closer to exemplars, and effectively prune both operators and irrelevant matches, by consulting a cache of star patterns (called star views). Using real-world graphs, we experimentally verify the efficiency and effectiveness of qchase techniques and their applications. |