Example-guided synthesis of relational queries
Example-guided synthesis of relational queries
复制标题
DOI：
10.1145/3453483.3454098
复制
发表时间：
2021-06
期刊：
影响因子：
--
通讯作者：
Aalok Thakkar;Aaditya Naik;Nathaniel Sands;R. Alur;M. Naik;Mukund Raghothaman
中科院分区：
文献类型：
--
作者：
Aalok Thakkar;Aaditya Naik;Nathaniel Sands;R. Alur;M. Naik;Mukund Raghothaman
程序合成任务通常是通过输入输出示例指定的。现有的此类任务的枚举技术主要以程序语法为指导，仅在示例中间接使用。我们确定了针对逐示例编程的一类合成算法，我们称之为示例引导的合成（EGS），该算法在生成候选程序的同时，在提供的示例中利用潜在结构。我们提出了一个EGS的实例，用于综合关系查询，并对来自三个应用程序域的86个任务进行评估：知识发现，程序分析和数据库查询。我们的评估表明，基于列举搜索，约束解决和混合技术的合成时间，合成程序的质量以及证明不实现的能力，EGS优于最先进的合成器。
Program synthesis tasks are commonly specified via input-output examples. Existing enumerative techniques for such tasks are primarily guided by program syntax and only make indirect use of the examples. We identify a class of synthesis algorithms for programming-by-examples, which we call Example-Guided Synthesis (EGS), that exploits latent structure in the provided examples while generating candidate programs. We present an instance of EGS for the synthesis of relational queries and evaluate it on 86 tasks from three application domains: knowledge discovery, program analysis, and database querying. Our evaluation shows that EGS outperforms state-of-the-art synthesizers based on enumerative search, constraint solving, and hybrid techniques in terms of synthesis time, quality of synthesized programs, and ability to prove unrealizability.