Better Together: Unifying Datalog and Equality Saturation
Open Access
- 6 June 2023
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 7 (PLDI) , 468-492
Abstract
We present egglog, a fixpoint reasoning system that unifies Datalog and equality saturation (EqSat). Like Datalog, egglog supports efficient incremental execution, cooperating analyses, and lattice-based reasoning. Like EqSat, egglog 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 our system 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
Funding Information
- National Science Foundation (1749570)
- U.S. Department of Energy (DE-SC0022081)
- Defense Advanced Research Projects Agency (FA8650-20-2-7008)
This publication has 47 references indexed in Scilit:
- Simplify: a theorem prover for program checkingJournal of the ACM, 2005
- Using Datalog with Binary Decision Diagrams for Program Analysis2005
- Proof-Producing Congruence Closure2005
- DenaliACM SIGPLAN Notices, 2002
- 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
- Variations on the Common Subexpression ProblemJournal of the ACM, 1980
- Efficiency of a Good But Not Linear Set Union AlgorithmJournal of the ACM, 1975