  To assist non-specialists in formulating database queries, multiple
frameworks that automatically infer queries from a set of examples have been
proposed. While highly useful, a shortcoming of the approach is that if users
can only provide a small set of examples, many inherently different queries may
qualify, and only some of these actually match the user intentions. Our main
observation is that if users further explain their examples, the set of
qualifying queries may be significantly more focused. We develop a novel
framework where users explain example tuples by choosing input tuples that are
intuitively the "cause" for their examples. Their explanations are
automatically "compiled" into a formal model for explanations, based on
previously developed models of data provenance. Then, our novel algorithms
infer conjunctive queries from the examples and their explanations. We prove
the computational efficiency of the algorithms and favorable properties of
inferred queries. We have further implemented our solution in a system
prototype with an interface that assists users in formulating explanations in
an intuitive way. Our experimental results, including a user study as well as
experiments using the TPC-H benchmark, indicate the effectiveness of our
solution.
