  Federations of RDF data sources provide great potential when queried for
answers and insights that cannot be obtained from one data source alone. A
challenge for planning the execution of queries over such a federation is that
the federation may be heterogeneous in terms of the types of data access
interfaces provided by the federation members. This challenge has not received
much attention in the literature. This paper provides a solid formal foundation
for future approaches that aim to address this challenge. Our main conceptual
contribution is a formal language for representing query execution plans;
additionally, we identify a fragment of this language that can be used to
capture the result of selecting relevant data sources for different parts of a
given query. As technical contributions, we show that this fragment is more
expressive than what is supported by existing source selection approaches,
which effectively highlights an inherent limitation of these approaches.
Moreover, we show that the source selection problem is NP-hard and in
$\Sigma_2^\mathrm{P}$, and we provide a comprehensive set of rewriting rules
that can be used as a basis for query optimization.
