26th ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering (ESEC/FSE 2018), November 4–9, 2018, Lake Buena Vista, FL, USA

Desktop Layout

Repair and Synthesis
Research Papers
Syntax-Guided Synthesis of Datalog Programs
Xujie Si, Woosuk Lee, Richard Zhang, Aws Albarghouthi, Paraschos Koutris, and Mayur Naik
(University of Pennsylvania, USA; Hanyang University, South Korea; University of Wisconsin-Madison, USA)
Artifacts Available Artifacts Functional
Publisher's Version
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.


Time stamp: 2019-03-19T15:58:27+01:00