Synthesis of data completion scripts using finite tree automata
Synthesis of data completion scripts using finite tree automata
复制标题
使用有限树自动机合成数据完成脚本
DOI：
10.1145/3133886
复制
发表时间：
2017
影响因子：
--
通讯作者：
Rishabh Singh
中科院分区：
文献类型：
--
作者：
Xinyu Wang;Işıl Dillig;Rishabh Singh
在以表格格式存储数据的应用域中，一个常见的任务是使用存储在其他单元格中的值填充某些单元格的值。例如，此类数据完成任务是在数据科学中缺少价值插入以及电子表格和关系数据库中衍生的数据计算的上下文中出现的。不幸的是，最终用户和数据科学家通常会在许多需要非平凡的编程专业知识的数据完成任务中挣扎。本文介绍了一种使用示例编程（PBE）自动化数据完成任务的合成技术和一种非常轻巧的草图方法。给定一个公式草图（例如，AVG（？1，？2））和每个孔的一些输入输出示例，我们的技术合成了一个程序以自动化所需的数据完成任务。为了实现这一目标，我们提出了一种特定领域的语言（DSL），该语言在表格数据上结合了空间和关系推理以及一种可以生成与输入输出示例一致的DSL程序的新型合成算法。我们方法的关键技术新颖性是基于有限树自动机（FTA）的新版本太空学习算法。在学习算法中使用FTA会导致更紧凑的表示形式，该表示允许在程序之间进行更多与示例一致的共享。我们已经在名为DACE的工具中实施了建议的方法，并根据从在线帮助论坛中获得的84个基准进行了评估。我们还通过将我们的技术与两个现有合成器（即散文和草图）进行比较来说明我们方法的优势。
In application domains that store data in a tabular format, a common task is to fill the values of some cells using values stored in other cells. For instance, such data completion tasks arise in the context of missing value imputation in data science and derived data computation in spreadsheets and relational databases. Unfortunately, end-users and data scientists typically struggle with many data completion tasks that require non-trivial programming expertise. This paper presents a synthesis technique for automating data completion tasks using programming-by-example (PBE) and a very lightweight sketching approach. Given a formula sketch (e.g., AVG(?1, ?2)) and a few input-output examples for each hole, our technique synthesizes a program to automate the desired data completion task. Towards this goal, we propose a domain-specific language (DSL) that combines spatial and relational reasoning over tabular data and a novel synthesis algorithm that can generate DSL programs that are consistent with the input-output examples. The key technical novelty of our approach is a new version space learning algorithm that is based on finite tree automata (FTA). The use of FTAs in the learning algorithm leads to a more compact representation that allows more sharing between programs that are consistent with the examples. We have implemented the proposed approach in a tool called DACE and evaluate it on 84 benchmarks taken from online help forums. We also illustrate the advantages of our approach by comparing our technique against two existing synthesizers, namely Prose and Sketch.