UW’s PL group has been focusing lately on this notion of E-Graphs and a technique called Equality Saturation. An E-Graph is a structure that efficiently represe

UW’s PL group has been focusing lately on this notion of E-Graphs and a technique called Equality Saturation. An E-Graph is a structure that efficiently represents equivalent rewrites of a program (exponentially many rewrites in polynomial space iiuc). Equality saturation is the process of generating an e-graph that represents all possible rewrites by inserting rewrites until the e-graph doesn’t change (is saturated). After the graph is created, you can use some heuristic to pick a good rewrite. This paper applies E-graphs to augment Datalog's reasoning/constraint solving.