Syntax-guided synthesis of Datalog programs

Xujie Si, Woosuk Lee, Richard Zhang, Aws Albarghouthi, Paraschos Koutris, Mayur Naik

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.

BibTeX

@inproceedings{Si-al:FSE18,
  author    = {Xujie Si and
               Woosuk Lee and
               Richard Zhang and
               Aws Albarghouthi and
               Paraschos Koutris and
               Mayur Naik},
  title     = {Syntax-guided synthesis of Datalog programs},
  booktitle = {{ESEC/SIGSOFT} {FSE}},
  pages     = {515--527},
  publisher = {{ACM}},
  year      = {2018},
}

Syntax-guided synthesis of Datalog programs

Abstract

Related papers