Mobius: Synthesizing Relational Queries with Recursive and Invented Predicates
summary
Mobius presents a concrete pipeline: seed a non‑recursive synthesizer, normalize the result, and perform iterative predicate unification guided by data provenance to recover recursive definitions and schema‑invented predicates (example: monochromatic path). The implementation uses Souffle and Z3 for evaluation and constraint solving, runs on 21 benchmarks, and reports higher accuracy and much lower runtime than Gensynth, ILASP, and Popper while generalizing to unseen graphs.
AI-written summary · about
chapters (7)
- 0:00Mobius and relational queries
- 3:27Synthesizing recursive predicates
- 8:07Non-recursive predicate invention
- 10:18Extrapolating recursive programs
- 13:27Evaluation versus state-of-the-art
- 15:34Mobius take-home message
- 16:18Q&A: Multiple solutions
related talks
26mProgram Synthesis Using Example Propagation
20mAutomating Pruning in Top-Down Enumeration for Program Synthesis Problems with(…)
14mRelational Synthesis for Pattern Matching
31mDesign Datalog Templates for Synthesizing Bidirectional Programs from Tabular E...
25mRecursive Program Synthesis using Paramorphisms
20mSemantic Reification: A New Paradigm for Random Program Generation
13mInductive Synthesis of Inductive Heap Predicates
19mSome Novel miniKanren Synthesis Tasks