Automating Physical Database . . .

In a high-level query language such as SQL, queries yield the same result no matter how the logical schema is physically implemented. Nevertheless, a query's cost can vary by orders of magnitude among different physical implementations of the same logical schema, even with the most modern query optimizers. Therefore, designing a low-cost physical implementation is an important pragmatic problem. Physical database design involves deciding on primary and secondary indexes, deciding how to vertically partition logical tables, deciding which queries should be materialized views, etc. These decisions require a sophisticated understanding of physical design options and query strategies, and involve estimating query costs, a tedious and error-prone process when done manually. We have devised a simple framework for automating physical design in relational or post-relational DBMSs and in database programming languages. Within this framework, design options are uniformly represented as "features", and designs are represented by "conflict"-free sets of features. Mutually exclusive features (e.g. two primary indexes on the same table) con ict. Using features simplifies the incorporation of a wide variety of design options and supports extensibility � adding a new design option (e.g. a new inde