  Private information retrieval (PIR) allows a user to retrieve a desired
message out of $K$ possible messages from $N$ databases without revealing the
identity of the desired message. Majority of existing works on PIR assume the
presence of replicated databases, each storing all the $K$ messages. In this
work, we consider the problem of PIR from storage constrained databases. Each
database has a storage capacity of $\mu KL$ bits, where $K$ is the number of
messages, $L$ is the size of each message in bits, and $\mu \in [1/N, 1]$ is
the normalized storage. In the storage constrained PIR problem, there are two
key design questions: a) how to store content across each database under
storage constraints; and b) construction of schemes that allow efficient PIR
through storage constrained databases. The main contribution of this work is a
general achievable scheme for PIR from storage constrained databases for any
value of storage. In particular, for any $(N,K)$, with normalized storage $\mu=
t/N$, where the parameter $t$ can take integer values $t \in \{1, 2, \ldots,
N\}$, we show that our proposed PIR scheme achieves a download cost of
$\left(1+ \frac{1}{t}+ \frac{1}{t^{2}}+ \cdots + \frac{1}{t^{K-1}}\right)$. The
extreme case when $\mu=1$ (i.e., $t=N$) corresponds to the setting of
replicated databases with full storage. For this extremal setting, our scheme
recovers the information-theoretically optimal download cost characterized by
Sun and Jafar as $\left(1+ \frac{1}{N}+ \cdots + \frac{1}{N^{K-1}}\right)$. For
the other extreme, when $\mu= 1/N$ (i.e., $t=1$), the proposed scheme achieves
a download cost of $K$. The interesting aspect of the result is that for
intermediate values of storage, i.e., $1/N < \mu <1$, the proposed scheme can
strictly outperform memory-sharing between extreme values of storage.
