Constraints are an important aspect of role-based models. Several types of constraints, such as separation of duty constraints, cardinality constraints and temporal constraints have been identified in the literature. Although the speci-fication of constraints has received significant research in-terest, there has been little work on the development of an efficient constraint enforcement model. In particular there does not exist a model for the data structures that are refer-enced and maintained by the constraint enforcement mech-anism. In this paper, we define a formal model for such data structures that record salient information to be used by the constraint enforcement mechanism. We introduce the con-cept of a constraint evaluation structure that is used by the constraint enforcement mechanism to determine whether granting a request would violate a constraint. Two partic-ular constraint evaluation structures form part of the run-time model we introduce in order to enforce dynamic con-straints.