Component-based synthesis of table consolidation and transformation tasks from examples
Abstract
This paper presents a novel component-based synthesis algorithm that marries the power of type-directed search with lightweight SMT-based deduction and partial evaluation. Given a set of components together with their over-approximate first-order specifications, our method first generates a program sketch over a subset of the components and checks its feasibility using an SMT solver. Since a program sketch typically represents many concrete programs, the use of SMT-based deduction greatly increases the scalability of the algorithm. Once a feasible program sketch is found, our algorithm completes the sketch in a bottom-up fashion, using partial evaluation to further increase the power of deduction for rejecting partially-filled program sketches. We apply the proposed synthesis methodology for automating a large class of data preparation tasks that commonly arise in data science. We have evaluated our synthesis algorithm on dozens of data wrangling and consolidation tasks obtained from on-line forums, and we show that our approach can automatically solve a large class of problems encountered by R users.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Jun 14, 2017
- Source ID
- 10.1145/3140587.3062351
Entities
People
- Işıl Dillig
- Jacob Van Geffen
- Ruben Martins
- Swarat Chaudhuri
- Yu Feng
Organizations
- Defense Advanced Research Projects Agency
- National Science Foundation
- Rice University
- University of Texas at Austin