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 deployed in many database applications, even those that do not support set-valued attributes. In this paper, we study the problem of set containment join. Given two collections R and S of records, the set containment join R ⊆S retrieves all record pairs {(r,s)} ∈ R × S such that r ⊆ s . This problem has been extensively studied in the literature and has many important applications in commercial and scientific fields. Recent research focuses on the in set containment join algorithms, In this paper, we propose three novel partitioning algorithms, called the Adaptive Pick-and-Sweep Join (APSJ), the Adaptive Divide-and-Conquer Join (ADCJ), and Divide-and-Conquer Join (DCJ) which allow computing set containment joins efficiently. We present a detailed analysis of the algorithms and study their performance on real and synthetic data using an implemented of this algorithm.

Algorithms, Experimentation, Performance and Implementations

[1] HELMER, S. AND MOERKOTTE, G. 1997. Evaluation of main memory joins algorithms for joins with set comparison join predicates. In VLDB’97, Proceedings of 23rd International Conference on Very Large Data Bases, August 25-29, 1997, Athens, Greece, M. Jarke, M. J. Carey, K. R. Dittrich, F. H. Lochovsky, P. Loucopoulos, and M. A. Jeusfeld, Eds. Morgan Kaufmann, 386–395.
[2] Ramasamy, K., Patel, J. M., Naughton, J. F., and Kaushik, R. 2000. Set containment joins: The good, the bad and the ugly. In VLDB 2000, Proceedings of 26th International Conference on Very Large Data Bases, September 10-14, 2000, Cairo, Egypt, A. E. Abbadi, M. L. Brodie, S. Chakravarthy, U. Dayal, N. Kamel, G. Schlageter, and K.-Y. Whang, Eds. Morgan Kaufmann, 351–362.
[3] C. Faloutsos and S. Christodoulakis. Signature _les: An access method for documents and its analytical performance evaluation. ACM Trans. On office Information Systems (TOIS), 2(4):267-288, 1984.
[4] ISHIKAWA, Y., KITAGAWA, H., AND OHBO, N. 1993. Evaluation of signature files as set access facilities in oodbs. In Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data, Washington, D.C., May 26-28, 1993, P. Buneman and S. Jajodia, Eds. ACM Press, 247–256.
[5] MELNIK, S. AND GARCIA-MOLINA, H. 2002. Divide-and-conquer algorithm for computing set containment joins. In Proceedings of Advances in Database Technology - EDBT 2002, 8th International Conference on Extending Database Technology, Prague, Czech Republic, March 25-27, C. S. Jensen, K. G. Jeffery, J. Pokorn´y, S. Saltenis, E. Bertino, K. Bohm, and M. Jarke,Eds. Lecture Notes in Computer Science, vol. 2287. Springer.
[6] GRAY, J., SUNDARESAN, P., ENGLERT, S., BACLAWSKI, K., AND WEINBERGER, P. J. 1994. Quickly generating billion-record synthetic databases. In Proceedings of the 1994 ACM SIGMOD International Conference on Management of Data, Minneapolis, Minnesota, May 24-27, 1994,R. T. Snodgrass and M. Winslett, Eds. ACM Press, 243–252.
[7] CAI, J.-Y., CHAKARAVARTHY, V. T., KAUSHIK, R., AND NAUGHTON, J. 2001. On the complexity of join predicates. In PODS’01, Proceedings of the 20th ACM SIGACT-SIGMOD-SIGARTSymposium on Principles of Database Systems, May 21-23, 2001, Santa Barbara, California. ACM Press.Faloutsos, C. and Christodoulakis, S. 1984. Signature files: An access method for documents and its analytical performance evaluation.
[8] HELLERSTEIN, J. M., KOUTSOUPIAS, E., AND PAPADIMITRIOU, C. H. 1997. On the analysis of indexing schemes. In PODS’97, Proceedings of the 16th ACM SIGACT-SIGMOD-SIGARTSymposium on Principles of Database Systems, May 12-14, 1997, Tucson, Arizona. ACMPress, 249–256.
[9] Patel, J. M. and DeWitt, D. J. 1996. Partition based spatial-merge join. In Proceedings of the 1996 ACM SIGMOD International Conference on Management of Data, Montreal, Quebec,Canada, June 4-6, 1996, H. V. Jagadish and I. S. Mumick, Eds. ACM Press, 259–270.
[10] BOHM, C. AND KRIEGEL, H.-P. 2000. Dynamically optimizing high-dimensional index structures. In Proceedings of Advances in Database Technology - EDBT 2000, 7th International Conferenceon Extending Database Technology, Konstanz, Germany, March 27-31, 2000, C. Zaniolo, P. C.Lockemann, M. H. Scholl, and T. Grust, Eds. Lecture Notes in Computer Science, vol. 1777.Springer