Constrained Physical Database Design - Automated Physical Database Design and Tuning - page 215

is painted white. We can clearly see that the configuration satisfying S70 is
always under the baseline (as expected). The figure also helps understand the
trade-offs in cost for queries when the S70 constraint is additionally enforced.
As with the previous example, the S70 constraint is worse than the storage-
only constraint overall (901 vs. 1,058 units) because the search space is more
restricted. However, some queries in the “no- S70 ” configuration fail to enforce
the 70% bound that is required.

11.4 Summary

• As DBMS applications become increasingly complex and varied, the

constrained physical design problem is an important addition to the
tool set of advanced DBAs.

• A simple constraint language can express several real-world constraints

easily.

• Extensions to traditional top-down solutions are able to handle multiple,

possibly conflicting constraints.

11.5 Additional Reading
The field of constrained optimization has been extensively studied in the past,
and the approaches vary depending on the nature of both the constraints
and the optimization function. More specifically, combinatorial optimization is
concerned with problems where the set of feasible solutions is discrete. A clear
and rigorous topic by Papadimitriou and Steiglitz describes several combina-
torial optimization techniques in detail. 2 In the context of physical database
design, Bruno and Chaudhuri present additional implementation details and
an experimental evaluation of the approach described in this chapter. 1

References
1. Nicolas Bruno and Surajit Chaudhuri. Constrained physical design tun-
ing. In Proceedings of the VLDB Journal , 19, 1, 2010.
2. Christos Papadimitriou and Kenneth Steiglitz. Combinatorial Optimiza-
tion: Algorithms and Complexity . Prentice-Hall, 1998.