  In this paper, we initiate a theoretical study of what we call the join
covering problem. We are given a natural join query instance $Q$ on $n$
attributes and $m$ relations $(R_i)_{i \in [m]}$. Let $J_{Q} = \ \Join_{i=1}^m
R_i$ denote the join output of $Q$. In addition to $Q$, we are given a
parameter $\Delta: 1\le \Delta\le n$ and our goal is to compute the smallest
subset $\mathcal{T}_{Q, \Delta} \subseteq J_{Q}$ such that every tuple in
$J_{Q}$ is within Hamming distance $\Delta - 1$ from some tuple in
$\mathcal{T}_{Q, \Delta}$. The join covering problem captures both computing
the natural join from database theory and constructing a covering code with
covering radius $\Delta - 1$ from coding theory, as special cases.
  We consider the combinatorial version of the join covering problem, where our
goal is to determine the worst-case $|\mathcal{T}_{Q, \Delta}|$ in terms of the
structure of $Q$ and value of $\Delta$. One obvious approach to upper bound
$|\mathcal{T}_{Q, \Delta}|$ is to exploit a distance property (of Hamming
distance) from coding theory and combine it with the worst-case bounds on
output size of natural joins (AGM bound hereon) due to Atserias, Grohe and Marx
[SIAM J. of Computing'13]. Somewhat surprisingly, this approach is not tight
even for the case when the input relations have arity at most two. Instead, we
show that using the polymatroid degree-based bound of Abo Khamis, Ngo and Suciu
[PODS'17] in place of the AGM bound gives us a tight bound (up to constant
factors) on the $|\mathcal{T}_{Q, \Delta}|$ for the arity two case. We prove
lower bounds for $|\mathcal{T}_{Q, \Delta}|$ using well-known classes of
error-correcting codes e.g, Reed-Solomon codes. We can extend our results for
the arity two case to general arity with a polynomial gap between our upper and
lower bounds.
