  Private information retrieval (PIR) allows a user to retrieve a desired
message from a set of databases without revealing the identity of the desired
message. The replicated databases scenario was considered by Sun and Jafar,
2016, where $N$ databases can store the same $K$ messages completely. A PIR
scheme was developed to achieve the optimal download cost given by $\left(1+
\frac{1}{N}+ \frac{1}{N^{2}}+ \cdots + \frac{1}{N^{K-1}}\right)$. In this work,
we consider the problem of PIR from storage constrained databases. Each
database has a storage capacity of $\mu KL$ bits, where $L$ is the size of each
message in bits, and $\mu \in [1/N, 1]$ is the normalized storage. On one
extreme, $\mu=1$ is the replicated databases case. On the other hand, when
$\mu= 1/N$, then in order to retrieve a message privately, the user has to
download all the messages from the databases achieving a download cost of
$1/K$. We aim to characterize the optimal download cost versus storage
trade-off for any storage capacity in the range $\mu \in [1/N, 1]$. For any
$(N,K)$, we show that the optimal trade-off between storage, $\mu$, and the
download cost, $D(\mu)$, is given by the lower convex hull of the $N$ pairs
$\left(\mu= \frac{t}{N},D(\mu) = \left(1+ \frac{1}{t}+ \frac{1}{t^{2}}+ \cdots
+ \frac{1}{t^{K-1}}\right)\right)$ for $t=1,2,\ldots, N$. To prove this result,
we first present the storage constrained PIR scheme for any $(N,K)$. We next
obtain a general lower bound on the download cost for PIR, which is valid for
the following storage scenarios: replicated or storage constrained, coded or
uncoded, and fixed or optimized. We then specialize this bound using the
uncoded storage assumption to obtain lower bounds matching the achievable
download cost of the storage constrained PIR scheme for any value of the
available storage.
