A method, system, and computer program product for optimizing database queries in a data processing system. A query optimization (QO) utility maximizes the query coverage of Materialized Query Tables (MQTs) in order to efficiently process various types of incoming queries to a database engine. In particular, the QO utility enables MQT technology for nullable foreign key columns in a number of table joins involving fact tables and dimension tables, in which the fact tables and dimension tables have column data which are not null. The QO utility also enables MQT query matching for a relational database engine for non-additive measures, and improves the performance of existing query-matching capabilities for a relational database engine for additive measures. The QO utility specifies a number of functionally dependent relationships between the columns of a table in order to enhance the query matching abilities of the database engine.