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

pldi-2017-papers
10:50 - 12:30: PLDI Research Papers - Synthesis at Actes, Civil Engineering
Chair(s): Sasa MisailovicUniversity of Illinois at Urbana-Champaign
pldi-2017-papers149794860000010:50 - 11:15
Talk
Yu FengUniversity of Texas at Austin, USA, Ruben Martins, Jacob Van GeffenUT Austin, Isil DilligUT Austin, Swarat ChaudhuriRice University
Media Attached
pldi-2017-papers149795010000011:15 - 11:40
Talk
Ryan BeckettPrinceton University, Ratul MahajanMicrosoft, Todd MillsteinUniversity of California, Los Angeles, Jitendra PadhyeMicrosoft, David WalkerPrinceton University
Media Attached
pldi-2017-papers149795160000011:40 - 12:05
Talk
Chenglong WangUniversity of Washington, USA, Alvin CheungUniversity of Washington, Rastislav BodikUniversity of Washington
Media Attached
pldi-2017-papers149795310000012:05 - 12:30
Talk
James BornholtUniversity of Washington, Emina TorlakUniversity of Washington, USA
Pre-print Media Attached