One of the key problems in healthcare informatics is the inability to share patient records across enterprises. To address this problem, an important industry initiative called "integrating the healthcare enterprise (IHE)" specified the "cross enterprise document sharing (XDS)" profile. In the IHE XDS, healthcare enterprises that agree to work together form a "clinical affinity domain" and store healthcare documents in an ebXML registry/repository architecture to facilitate their sharing. The affinity domains also agree on a common set of policies such as coding lists to be used to annotate clinical documents in the registry/repository and the common schemes for patient identification. However, since patients expect their records to follow them as they move from one clinical affinity domain to another, there is a need for affinity domains to be federated to enable information exchange. In this paper, we describe how IHE XDS can be enhanced to support federated clinical affinity domains. We demonstrate that federation of affinity domains are facilitated when ontologies, rather than coding term lists, are used to annotate clinical documents. Furthermore, we describe a patient identification protocol that eliminates the need to keep a master patient index file for the federation.