1. A system for optimizing queries against a database, comprising: a memo structure that encodes a plurality of query expressions; and a signature mechanism that enables an assignment of the query expressions into equivalence classes.