The present Chapter introduces Semantic Gossiping [ACMH03b]; a novel technique that selectively forwards queries from one peer database to the others in a PDMS network. This Chapter mainly reports on a tradeoff between the precision and recall of the set of answers to a query. Another contribution is the description of various methods that can be applied in order to estimate the quality of local query reformulations in large-scale, uncertain PDMS networks. The details of each of these methods are elaborated for a simple data model that is expressive enough to cover many practical cases (Sect. 4.2). The introduced methods consist of:
(1) A syntactic analysis of search queries after the application of reformulations in order to determine the potential information loss incurred through a reformulation. We analyze to which degree query constituents are preserved during reformulation (Sect. 4.4).