Towards Relational Contextual Equality Saturation
summary
Claims a method to bring contextual equality saturation into the egglog relational model by treating contexts and equivalence relations as lattices and mapping between them, representing per-context e-classes as quotient sets backed by a union-find hierarchy, and materializing only needed quotients on demand. Provides a formal meet/join approach to merge context-aware rewrites, identifies canonicalization of quotient sets as unresolved, and reports ongoing implementation work to add smart materialization algorithms rather than a finished system.
AI-written summary · about
chapters (11)
- 0:00Introduction
- 1:26Contextual equalities in optimization
- 3:52Context pushdown in equality saturation
- 5:15Colored equality saturation
- 6:20Egglog relational model challenges
- 7:23Equivalence relations lattice
- 9:27Lattice-based rewriting advantages
- 10:52Equivalence sets in egglog
- 12:14Quotient set canonicalization challenges
- 13:39Proposed approach summary
- 14:22Question and answer session
related talks
20mEquality Saturation and Joins
17mBetter Together: Unifying Datalog and Equality Saturation
30megg: Fast and Extensible Equality Saturation
19meqsat: An Equality Saturation Dialect for Non-destructive Rewriting
18mAssociativity and Commutativity in Equality Saturation
26mEquality Saturation Guided by Large Language Models
29mObserving Definitional Equality
21mHashing Modulo Context-Sensitive Alpha-Equivalence