A multilevel database is intended to provide the security needed for database systems that contain data at a variety of classifications and serve a set of users having different clearances. A formal security model for such a system is described. The model is formulated in two layers, one corresponding to a reference monitor that enforces mandatory security, and the second an extension of the standard relational model defining multilevel relations and formalizing policies for labeling new and derived data, data consistency, and discretionary security. The model also defines application-independent properties for entity integrity, referential integrity, and polyinstantiation integrity.<>