Automating the physical design process in database systems is an important research topic that has received considerable attention in the last decade, leading to the development of prototypes for database management systems such as Microsoft SQL Server, Oracle, and DB2. Usually, only a storage constraint is considered for physical design tuning, but the authors of this paper argue that this is not enough for real-world situations. Thus, they advocate an interactive physical design tuning where multiple and complex constraints can be specified.

The constraint language proposed is simple but expressive. It accepts simple constraints, generators (application of a template constraint to each element in a collection), filters, aggregations, nested constraints, annotations to guide the search process, and both hard and soft constraints (strict versus desirable goals). Besides, it can be extended, thanks to the use of C++ as an intermediate language to represent the constraints. A prototype implementation is also described and an experimental evaluation of the proposed search framework is presented.

This is a very relevant and complete work, which builds upon previous works accepted by top-level conferences on databases. It could be interesting not only for researchers working on related topics, but also for students in advanced courses on databases. The current proposal focuses on the use of indexes in the physical design process, and could be extended to consider other physical design techniques as well. Of particular relevance is the study of ways to assist the database administrator in the specification of relevant constraints and appropriate annotations.