MCDB is a prototype database management system for managing uncertain data models in relational fashion. We discuss the challenges associated with translating and optimizing SQL queries that make use of uncertain data tables and propose a cost-based optimizer that "learns" its cost estimation functions from previously executed query plans. Advanced optimization strategies that materialize intermediate query results and stochastic tables for future queries are described.