Divide-and-Conquer Algorithm for Computing Set Containment Joins

A set containment join is a join between set-valued attributes of two relations, whose join condition is specified using the subset (⫅) operator. Set containment joins are used in a variety of database applications. In this paper, we propose a novel partitioning algorithm called Divide-and-Conquer Set Join (DCJ) for computing set containment joins efficiently. We show that the divide-and-conquer approach outperforms previously suggested algorithms over a wide range of data sets. We present a detailed analysis of DCJ and previously known algorithms and describe their behavior in an implemented testbed.