  We propose a novel approach to program synthesis, focusing on synthesizing
database queries. At a high level, our proposed algorithm takes as input a
sketch with soft constraints encoding user intent, and then iteratively
interacts with the user to refine the sketch. At each step, our algorithm
proposes a candidate refinement of the sketch, which the user can either accept
or reject. By leveraging this rich form of user feedback, our algorithm is able
to both resolve ambiguity in user intent and improve scalability. In
particular, assuming the user provides accurate inputs and responses, then our
algorithm is guaranteed to converge to the true program (i.e., one that the
user approves) in polynomial time. We perform a qualitative evaluation of our
algorithm, showing how it can be used to synthesize a variety of queries on a
database of academic publications.
