Example-guided Synthesis of Relational Queries

The goal of program synthesis is to automatically generate programs that meet user intention. While a number of methods for expressing user intention has gained traction over the last five decades, programming-by-example has proven to be useful in domains where the user may not be able to articulate the desired program behavior as a logical specification but can describe it through demonstrative input-output examples. This dissertation studies programming-by-example in the context of relational queries. It is a challenging and foundational problem; ideally, we would like a technique that is simultaneously: (a) scalable enough to be applicable to real-world instances, (b) expressive in terms of the kinds of queries that it can synthesize, and (c) fully automatic, so it requires minimal guidance from non-expert users. Significant progress has been made on this problem in recent years, and a variety of algorithms have beenproposed, including algorithms based on evolutionary search, numerical relaxation, constraint solving, and counterexample-guided search. Each of these approaches require additional supervision in the form of templates to restrict the space of candidate programs and accelerate the search. In this line of work, we propose example-guided synthesis, a paradigm of techniques to eliminate the need for such instance-specific supervision by leveraging the underlying structure of the input-output examples. We present an example-guided algorithm for conjunctive queries, and then extend it to support expressive features such as disjunction, recursion, and comparison predicates, as well as learning in presence of noise. We implement this technique and demonstrate that it outperforms the state-of-the-art tools on a diverse set of benchmarks in terms of both, running time and the quality of examples.