  Differential privacy (DP) is a widely applied paradigm for releasing data
while maintaining user privacy. Its success is to a large part due to its
composition property that guarantees privacy even in the case of multiple data
releases. Consequently, composition has received a lot of attention from the
research community: there exist several composition theorems for adversaries
with different amounts of flexibility in their choice of mechanisms. But apart
from mechanisms, the adversary can also choose the databases on which these
mechanisms are invoked. The classic tool for analyzing the composition of DP
mechanisms, the so-called composition experiment, neither allows for
incorporating constraints on databases nor for different assumptions on the
adversary's prior knowledge about database membership. We therefore propose a
generalized composition experiment (GCE), which has this flexibility. We show
that composition theorems that hold with respect to the classic composition
experiment also hold with respect to the worst case of the GCE. This implies
that existing composition theorems give a privacy guarantee for more cases than
are explicitly covered by the classic composition experiment. Beyond these
theoretical insights, we demonstrate two practical applications of the GCE: the
first application is to give better privacy bounds in the presence of
restrictions on the choice of databases; the second application is to reason
about how the adversary's prior knowledge influences the privacy leakage. In
this context, we show a connection between adversaries with an uninformative
prior and subsampling, an important primitive in DP. To the best of our
knowledge, this paper is the first to analyze the interplay between the
databases in DP composition, and thereby gives both a better understanding of
composition and practical tools for obtaining better composition bounds.
