Better Together: Unifying Datalog and Equality Saturation
Authors:
- Yihong ZhangYZYihong Zhang
- Yisu Remy WangYWYisu Remy Wang
- Oliver FlattOFOliver Flatt
- David CaoDCDavid Cao
- Philip ZuckerPZPhilip Zucker
- Eli RosenthalEREli Rosenthal
- Zachary TatlockZTZachary Tatlock
- Max WillseyMWMax Willsey
Preprint
Abstract
We present egglog, a fixpoint reasoning system that unifies Datalog and equality saturation (EqSat). Like Datalog, it supports efficient incremental execution, cooperating analyses, and lattice-based reasoning. Like EqSat, it supports term rewriting, efficient congruence closure, and extraction of optimized terms. We identify two recent applications--a unification-based pointer analysis in Datalog and an EqSat-based floating-point term rewriter--that have been hampered by features missing from Datalog but found in EqSat or vice-versa. We evaluate egglog by reimplementing those projects in egglog. The resulting systems in egglog are faster, simpler, and fix bugs found in the original systems.Keywords
All Related Versions
This publication has 45 references indexed in Scilit:
- The Choice Construct in the Soufflé Language2021
- Structure-Sensitive Points-To Analysis for C and C++2016
- Using Datalog for Fast and Easy Program Analysis2011
- Using Datalog with Binary Decision Diagrams for Program Analysis2005
- Proof-Producing Congruence Closure2005
- Theory and practice of constraint handling rulesThe Journal of Logic Programming, 1998
- Fixpoint iteration with subsumption in deductive databasesJournal of Intelligent Information Systems, 1995
- On the relationship of congruence closureand unificationJournal of Symbolic Computation, 1989
- A generalization of the differential approach to recursive query evaluationThe Journal of Logic Programming, 1987
- A theory of type polymorphism in programmingJournal of Computer and System Sciences, 1978