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.
|
Year | DOI | Venue |
---|---|---|
2018 | 10.1145/3236024.3236034 | ESEC/SIGSOFT FSE |
Keywords | Field | DocType |
Syntax-guided synthesis,Datalog,Active learning,Template augmentation,Program analysis | Active learning,Suite,Computer science,Theoretical computer science,Program analysis,Datalog,Syntax,Syntactic structure,Expressivity | Conference |
ISBN | Citations | PageRank |
978-1-4503-5573-5 | 2 | 0.36 |
References | Authors | |
35 | 6 |
Name | Order | Citations | PageRank |
---|---|---|---|
Xujie Si | 1 | 35 | 6.28 |
Woosuk Lee | 2 | 11 | 0.84 |
Richard Zhang | 3 | 2 | 0.36 |
Aws Albarghouthi | 4 | 250 | 22.87 |
Paraschos Koutris | 5 | 347 | 26.63 |
Mayur Naik | 6 | 12 | 3.87 |