Let \(C : \Sigma ^n \to \Sigma ^N\) be a code that maps \(x_1, \dots , x_n\) to \(c_1, \dots , c_N\). The code \(C\) is a \(k\)-batch code if, for every multiset of indices \(\{ i_1, \dots , i_k\} \subset [n]\), there exist \(k\) mutually disjoint sets \(R_1, \dots , R_k \subseteq [N]\) and functions \(g_1, \dots , g_k\) such that, for all information symbols \(x_1, \dots , x_n \in \Sigma \) and codewords \((c_1, \dots , c_N) = C(x_1, \dots , x_n) \in \Sigma ^N\), and for all \(j \in [k]\), we have \(g_j(c|_{R_j}) = x_{i_j}\). Here \(c|_{R_j}\) denotes the restriction of the codeword \(c\) to the coordinates indexed by \(R_j\).

We say \(C\) is a linear batch code if \(\Sigma = \mathbb {F}\) is a finite field, the functions \(g_i\) are all linear, and \(C\) is a linear map. We say \(C\) has a systematic encoding if \(c_i = x_i\) for \(i = 1, \dots , n\).

The redundancy of \(C\) is \(N - n\). (For a linear code with a systematic encoding, \(\dim C = n\), so the redundancy equals \(N - \dim C\).)

Definition 1 is the primitive multiset special case of the general notion of batch code of Ishai–Kushilevitz–Ostrovsky–Sahai. In the general definition, \(n\) symbols are encoded into “buckets” of symbols whose total size is \(N\), and each batch of \(k\) symbols can be decoded by reading at most one symbol from each bucket. A batch code is a multiset batch code if (a) the \(k\) requested symbols may form a multiset and (b) the \(k\) symbols can be decoded by querying \(k\) pairwise disjoint sets of buckets. When each bucket stores a single symbol the batch code is called primitive. Throughout this blueprint “batch code” means the primitive multiset notion of Definition 1.