Date Added: Jun 2011
In this paper, the authors conceptualize the database layout problem as a state space search problem. A state is a given assignment of tables to computer servers. They begin with a database and collect, for use as a workload input, a sequence of queries that were executed during normal usage of the database. The operators in the search are to fully replicate, horizontally partition, vertically partition, and de-normalize a table. They do a time intensive search over different table layouts, and at each iteration, physically create the configurations, and evaluate the total throughput of the system.