A technique for efficiently updating a key table during outline restructure of a multi-dimensional database. A command is executed in a computer to perform a database operation on a relational database stored on a data store connected to the computer. It is determined that a multi-dimensional database has been restructured. Then, a key table of the relational database is rebuilt to correspond to the restructured multidimensional database.