Fri 9 Nov 2018 11:15 - 11:37 at Studio 2 - Program Synthesis Chair(s): Jens Palsberg

The ability to reason about relational queries plays an important role across various types of database applications, such as test data generation, query equivalence checking, and computer-assisted query authoring tools. Unfortunately, scaling up query reasoning can be challenging as relational tables contains tuples of different types, and relational query languages such as SQL can introduce complex interactions among tuples.In this paper, we propose a new space refinement algorithm to make reasoning of relational queries efficient.Our refinement procedure is independent of the specific database application, and exploits the structural features of queries along with the provenance of tuples in the output table to soundly refine the space of tables that such applications need to consider. As a result of our refinement, the application only needs to consider a small fragment of the original space of tables in order to complete the reasoning process. We have implemented our refinement algorithm, and evaluated it using three different reasoning tasks for SQL:bounded equivalence checking of queries, test generation for applications that manipulate relational data, and concolic testing of database applications. Using real world benchmarks, our study shows that our refinement algorithm can provide significant speedup for reasoning a large class of challenging SQL queries (e.g., queries with aggregations), and can improve the performance of applications that perform relational query reasoning by up to 100×as compared to the original.

Fri 9 Nov

Displayed time zone: Guadalajara, Mexico City, Monterrey change

10:30 - 12:00
Program SynthesisOOPSLA at Studio 2
Chair(s): Jens Palsberg University of California, Los Angeles
10:30
22m
Talk
Relational Program Synthesis
OOPSLA
Yuepeng Wang University of Texas at Austin, Xinyu Wang UT Austin, Isil Dillig UT Austin
10:52
22m
Talk
Robust Relational Layout Synthesis from Examples for Android
OOPSLA
Pavol Bielik ETH Zürich, Marc Fischer ETH Zurich, Martin Vechev ETH Zürich
11:15
22m
Talk
Speeding up Symbolic Reasoning for Relational Queries
OOPSLA
Chenglong Wang University of Washington, USA, Alvin Cheung University of Washington, Rastislav Bodik University of Washington
11:37
22m
Talk
Automatic Diagnosis and Correction of Logical Errors for Functional Programming Assignments
OOPSLA
Junho Lee Korea University, Dowon Song Korea University, Sunbeom So Korea University, Hakjoo Oh Korea University