  We propose a new model of asynchronous batch codes that allow for parallel
recovery of information symbols from a coded database in an asynchronous
manner, i.e. when queries arrive at random times and they take varying time to
process. We show that the graph-based batch codes studied by et al. are
asynchronous. Further, we demonstrate that hypergraphs of Berge girth larger or
equal to 4, respectively larger or equal to 3, yield graph-based asynchronous
batch codes, respectively private information retrieval (PIR) codes. We prove
the hypergraph-theoretic proposition that the maximum number of hyperedges in a
hypergraph of a fixed Berge girth equals the quantity in a certain
generalization of the hypergraph-theoretic (6,3)-problem, first posed by Brown,
Erd\H{o}s and S\'{o}s. We then apply the constructions and bounds by Erd\H{o}s,
Frankl and R\"{o}dl about this generalization of the (6,3)-problem, known as
the (3$\varrho$-3,$\varrho$)-problem, to obtain batch code constructions and
bounds on the redundancy of the graph-based asynchronous batch and PIR codes.
We derive bounds on the optimal redundancy of several families of asynchronous
batch codes with the query size $t=2$. In particular, we show that the optimal
redundancy $\rho(k)$ of graph-based asynchronous batch codes of dimension $k$
for $t=2$ is $2\sqrt{k}$. Moreover, for graph-based asynchronous batch codes
with $t \ge 3$, $\rho(k) = O\left({k}^{1/(2-\epsilon)}\right)$ for any small
$\epsilon>0$.
