Appendix B

Proofs of Theorems, Lemmas and Corollaries

Theorem 5.1

*Given a linear* DDG *with data sets* {*d*_{1}, *d*_{2}, *…*, *d*_{n}}, *the length of P*_{min}*<d*_{s}, *d*_{e}*> of its CTT is the minimum cost rate for storing the data sets in the* DDG, *and the corresponding storage strategy is to store the data sets that P*_{min}*<d*_{s}, *d*_{e}*> traverses.*

**Proof of Theorem 5.1**: First, there is a one-to-one mapping between the storage strategies of the DDG and the paths from *d*_{s} to *d*_{e} in the CTT. Given any storage strategy of the DDG, we can find an order of these stored data sets, since the DDG is linear. Then, we can find the exact path in the CTT that has traversed all these stored data sets. Similarly, given any path from *d*_{s} to *d*_{e} in the CTT, we can find the data sets it has traversed, ...