一句话：提出 Mobius，从数据中全自动合成含递归与发明谓词的关系查询，并用数据溯源加速搜索。
从数据中合成关系查询在存在递归和发明谓词时十分困难。本文提出全自动两阶段方法：先合成与给定数据一致的非递归查询，再识别其中的递归模式，通过迭代谓词统一泛化到任意数据；该过程利用数据溯源构造额外约束，加速收敛。每轮由约束求解器提出候选查询，查询求值器检查一致性，失败查询的溯源用于精化搜索。作者实现工具 Mobius，在 21 个具挑战性的递归查询合成任务上，其运行时间和准确率均优于 Gensynth、ILASP 和 Popper 三个基线，并证明合成查询对未见数据泛化良好。
Synthesizing relational queries from data is challenging in the presence of recursion and invented predicates. We propose a fully automated approach to synthesize such queries. Our approach comprises of two steps: it first synthesizes a non-recursive query consistent with the given data, and then identifies recursion schemes in it and thereby generalizes to arbitrary data. This generalization is achieved by an iterative predicate unification procedure which exploits the notion of data provenance to accelerate convergence. In each iteration of the procedure, a constraint solver proposes a candidate query, and a query evaluator checks if the proposed program is consistent with the given data. The data provenance for a failed query allows us to construct additional constraints for the constraint solver and refine the search. We have implemented our approach in a tool named Mobius. On a suite of 21 challenging recursive query synthesis tasks, Mobius outperforms three state-of-the-art baselines Gensynth, ILASP, and Popper, both in terms of runtime and accuracy. We also demonstrate that the synthesized queries generalize well to unseen data.
@article{paperbot1834,
title = {Mobius: Synthesizing Relational Queries with Recursive and Invented Predicates},
author = {Aalok Thakkar and Nathaniel Sands and George Petrou and Rajeev Alur and Mayur Naik and Mukund Raghothaman},
journal = {Proceedings of the ACM on Programming Languages},
volume = {7},
number = {OOPSLA2},
year = {2023},
doi = {10.1145/3622847}
}