2020/03/21 by Shi Li, Li, Shi, Sai Vikneshwar Mani Jayaraman +3
Computer Science · Decision Sciences · #Advanced Database Systems and Queries #Data Management and Algorithms #Data Quality and Management #Databases (cs.DB) #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.2003.09537
openalex publication_date 2020/03/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 (Ri)i ∈ [m]. Let JQ = \Joini=1m Ri denote the join output of Q. In addition to Q, we are given a parameter Δ: 1≤ Δ≤ n and our goal is to compute the smallest subset TQ, Δ ⊆ JQ such that every tuple in JQ is within Hamming distance Δ- 1 from some tuple in TQ, Δ. The join covering problem captures both computing the natural join from database theory and constructing a covering code with covering radius Δ- 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 |TQ, Δ| in terms of the structure of Q and value of Δ. One obvious approach to upper bound |TQ, Δ| 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 |TQ, Δ| for the arity two case. We prove lower bounds for |TQ, Δ| 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.