Semantic integrity constraints represent knowledge about data with which a relational database must be consistent. To enforce semantic integrity we must ensure that transactions which alter the database will preserve database consistency by accompanying each transaction with integrity tests. In this paper we address two problems. Firstly, how can we choose integrity tests that are correct and efficient? Secondly, how do we schedule and control the execution of integrity tests in the context of a parallel database machine? We use a theorem-proving method for deriving integrity tests to prove the integrity of the database which takes into account knowledge about the transaction, the partitioning strategy, and the truth of all constraints in the initial database state. Our method can derive, at schema compilation time, a range of possible sufficient or necessary tests as well as complete tests for transaction safety with respect to a constraint, and can generate separate sub-tests to independently verify changes to a section of the database. When a transaction is to be executed, tests or sub-tests are selected (from the range of alternatives generated at compile time) in order to maximise parallelism, minimise the amount of data accessed in integrity enforcement activity, and allow testing to commence as soon as possible.