A policy is incorporated into a first set of policies at least in part by generating a second set of policies corresponding to the policy. An index of the first set of policies is generated based at least in part on a policy element of a normal form. Based at least in part on the index, a subset of the first set of policies that is relevant to at least one of a plurality of policy enforcement components is identified and provided to at least one of the plurality of policy enforcement components of a virtual resource provider identified as relevant. A request subject to the policy is received, and the policy is enforced at least in part by evaluating the request with respect to the subset of the first set of policies.