ALPS Framework

Syntax-Guided Synthesis of Datalog Programs

Abstract

Datalog has witnessed promising applications in a variety of domains. We propose a programming-by-example system, ALPS, to synthesize Datalog programs from input-output examples. Scaling synthesis to realistic programs in this manner is challenging due to the rich expressivity of Datalog. We present a syntax-guided synthesis approach that prunes the search space by exploiting the observation that in practice Datalog programs comprise rules that have similar latent syntactic structure. We evaluate alps on a suite of 34 benchmarks from three domains—knowledge discovery, program analysis, and database queries. The evaluation shows that alps can synthesize 33 of these benchmarks, and outperforms the state-of-the-art tools Metagol and Zaatar, which can synthesize only up to 10 of the benchmarks.

Publication
In The ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering.
Date