A method, apparatus, and article of manufacture for optimizing a query being performed by a computer system to retrieve data from a database stored on the computer system. The query is analyzed to identify any joins therein that are lossless and to identify any tables of the identified joins that are eligible for removal. This analysis includes partitioning the joins into lossless and lossy joins, and partitioning the tables of the joins according to their associated quantifiers, wherein each of the quantifiers has a quantifier state indicating whether the table participates in a join that is lossless. The query is then rewritten to eliminate the identified tables that are eligible for removal.