Write a Blog >>
Tue 20 Jun 2017 11:40 - 12:05 at Actes, Civil Engineering - Synthesis Chair(s): Sasa Misailovic

SQL is the de facto language for manipulating relational data. Though powerful, many users find it difficult to write SQL queries due to highly expressive constructs. While using the programming-by-example paradigm to help users write SQL queries is an attractive proposition, as evidenced by online help forums such as Stack Overflow, developing techniques for synthesizing SQL queries from given input-output (I/O) examples has been difficult, due to the large space of SQL queries as a result of its rich set of operators.

In this paper, we present a new scalable and efficient algorithm for synthesizing SQL queries based on I/O examples. The key innovation of our algorithm is development of a language for abstract queries, i.e., queries with uninstantiated operators, that can be used to express a large space of SQL queries efficiently. Using abstract queries to represent the search space nicely decomposes the synthesis problem into two tasks: 1) searching for abstract queries that can potentially satisfy the given I/O examples, and 2) instantiating the found abstract queries and ranking the results.

We have implemented this algorithm in a new tool called Scythe and evaluated it using 193 benchmarks collected from Stack Overflow. Our evaluation shows that Scythe can efficiently solve 74% of the benchmarks, most in just a few seconds, and the queries range from simple ones involving a single selection to complex queries with 6 nested subqueires.

Tue 20 Jun

Displayed time zone: Amsterdam, Berlin, Bern, Rome, Stockholm, Vienna change

10:50 - 12:30
SynthesisPLDI Research Papers at Actes, Civil Engineering
Chair(s): Sasa Misailovic University of Illinois at Urbana-Champaign
10:50
25m
Talk
Component-based Synthesis of Table Consolidation and Transformation Tasks from Examples
PLDI Research Papers
Yu Feng University of Texas at Austin, USA, Ruben Martins , Jacob Van Geffen UT Austin, Isil Dillig UT Austin, Swarat Chaudhuri Rice University
Media Attached
11:15
25m
Talk
Network Configuration Synthesis with Abstract Topologies
PLDI Research Papers
Ryan Beckett Princeton University, Ratul Mahajan Microsoft, Todd Millstein University of California, Los Angeles, Jitendra Padhye Microsoft, David Walker Princeton University
Media Attached
11:40
25m
Talk
Synthesizing Highly Expressive SQL Queries from Input-Output Examples
PLDI Research Papers
Chenglong Wang University of Washington, USA, Alvin Cheung University of Washington, Rastislav Bodik University of Washington
Media Attached
12:05
25m
Talk
Synthesizing Memory Models from Framework Sketches and Litmus Tests
PLDI Research Papers
James Bornholt University of Washington, Emina Torlak University of Washington, USA
Pre-print Media Attached