Datalog and Equality Saturation
summary
Claims that equality saturation can be encoded as Datalog while keeping the congruence closure algorithm work in practice lead to a concrete system and benchmarks: an implementation called egglog combines Datalog rules with a runtime union‑find canonicalization and worst‑case‑optimal joins, delivers million× faster e‑matching on pathological multipatterns, gives natural incrementality and multipattern support, and reproduces e‑graph extraction. Drawbacks are loss of per‑term identity (only canonical families exist), dependence on a single equivalence relation, and unresolved algebraic questions about the merge semantics.
AI-written summary · about
chapters (10)
- 0:00Introduction to E-graphs
- 1:41Equality saturation basics
- 6:29E-graph structure and use
- 13:41Extraction and optimization
- 19:44The e-matching mechanism
- 26:24E-class analysis
- 28:27Encoding EGS in Datalog
- 37:02Overcoming performance issues
- 45:14Egg log and future directions
- 58:32Concluding Q&A
related talks
17mBetter Together: Unifying Datalog and Equality Saturation
01h 08mAlgebraic Structures in Logic and Query Evaluation 4
41mOptimizing Relational Programs I
36mOptimizing Relational Programs II
01h 02mAlgebraic Structures in Logic and Query Evaluation 3
26mRelational E-matching
13mAccelerating Program Analyses in Datalog by Merging Library Facts
17mBring Your Own Data Structures to Datalog