On the existence property over a predicate

We prove that in a countable theory T fully stable over a predicate P, any complete set A has the existence property. This means that A can be extended to a model of T without changing the P-part. In particular, T has the Gaifman property: any model of P occurs as the P-part of some model of T. This generalizes results of Lachlan (on stable theories), Hodges (on relatively categorical abelian groups), and Afshordel (on difference fields of characteristic 0).