Whereas self-tuning physical database design has received a lot of attention recently, self-tuning logical database design seems to be under-studied.

Roughly speaking, database administrators (DBA) have to maintain on a daily basis "efficient databases", i.e. databases for which SQL queries have to perform effi- ciently for end-users, while keeping "coherent" databases, i.e. databases without update problems. Moreover, the huge number of null values occurring in practice may incur a significant overhead on his daily work, either to optimize the memory layout or to maintain (or design new) SQL queries.

In order to reach a trade-off between the desire to maintain efficient databases and coherent databases, we propose a framework in which a database should be able to self-tuning its logical database schema with respect to SQL workloads and the data themselves.

We discuss the main points of this framework, its feasibility and its relationships with some data mining problems.