  We consider the problem of private information retrieval (PIR) of a single
message out of $K$ messages from $N$ non-colluding and non-replicated
databases. Different from the majority of the existing literature, which
considers the case of replicated databases where all databases store the same
content in the form of all $K$ messages, here, we consider the case of
non-replicated databases under a special non-replication structure where each
database stores $M$ out of $K$ messages and each message is stored across $R$
different databases. This generates an $R$-regular graph structure for the
storage system where the vertices of the graph are the messages and the edges
are the databases. We derive a general upper bound for $M=2$ that depends on
the graph structure. We then specialize the problem to storage systems
described by two special types of graph structures: cyclic graphs and
\emph{fully-connected graphs}. We prove that the PIR capacity for the case of
cyclic graphs is $\frac{2}{K+1}$, and the PIR capacity for the case of
fully-connected graphs is $\min\{\frac{2}{K},\frac{1}{2}\}$. To that end, we
propose novel achievable schemes for both graph structures that are
capacity-achieving. The central insight in both schemes is to introduce
dependency in the queries submitted to databases that do not contain the
desired message, such that the requests can be compressed. In both cases, the
results show severe degradation in PIR capacity due to non-replication.
