The subject disclosure pertains to logical schema tuning for databases. Mechanisms are provided for automatically recommending one or more logical schema transformations to improve database performance with respect to workload and data characteristics. Furthermore, several potential schema transformations including desirable properties are presented including mapping tables, vertical partitioning, frequent value elimination and type and attribute conversion. Still further yet, disclosed is a mechanism for rewriting database operations (e.g. queries, updates . . . ) for an optimized schema to ensure correct evaluation.