1. A method for tuning a database to recommend a set of physical design structures for the database that optimize database performance for a given workload, wherein the workload comprises queries that have been executed on the database, and wherein a total time bound that defines a maximum amount of time that can be spent tuning is given, the method comprising the steps of: maintaining a cumulative set of recommended structures; and updating the cumulative set of recommended structures by tuning the database by examining a predetermined portion of the workload during a time slice that is a fraction of the total time bound such that at the end of the time slice, a set of recommended structures has been enumerated that is based on the workload portions that have been examined; and repeating the updating step until all queries in the workload have been examined or until the time bound is reached.