Efficient processing of joins on set-valued attributes

ABSTRACT

Object-oriented and object-relational DBMS support set valued attributes, which are a natural and concise way to model complex information. However, there has been limited research to-date on the evaluation of query operators that apply on sets. In this paper we study the join of two relations on their set-valued attributes. Various join types are considered, namely the set containment, set equality, and set overlap joins. We show that the inverted file, a powerful index for selection queries, can also facilitate the efficient evaluation of most join predicates. We propose join algorithms that utilize inverted files and compare them with signature-based methods for several set-comparison predicates.

REFERENCES

• 1: Antonio Corral , Yannis Manolopoulos , Yannis Theodoridis , Michael Vassilakopoulos, Closest pair queries in spatial databases, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.189-200, May 15-18, 2000, Dallas, Texas, United States
• 2: Uwe Deppisch, S-tree: a dynamic balanced signature index for office retrieval, Proceedings of the 9th annual international ACM SIGIR conference on Research and development in information retrieval, p.77-87, September 1986, Palazzo dei Congressi, Pisa, Italy [doi>10.1145/253168.253189]
• 3: Christos Faloutsos, Signature files, Information retrieval: data structures and algorithms, Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
• 4: S. W. Golomb. Run length encodings. IEEE Transactions on Information Theory, 12(3):399--401, 1966.
• 5: Ralf Hartmut Güting, An introduction to spatial database systems, The VLDB Journal — The International Journal on Very Large Data Bases, v.3 n.4, October 1994
• 6: Antonin Guttman, R-trees: a dynamic index structure for spatial searching, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• 7: Sven Helmer , Guido Moerkotte, Evaluation of Main Memory Join Algorithms for Joins with Set Comparison Join Predicates, Proceedings of the 23rd International Conference on Very Large Data Bases, p.386-395, August 25-29, 1997
• 8: S. Helmer and G. Moerkotte. A study of four index structures for set-valued attributes of low cardinality. In Technical Report, University of Mannheim, number 2/99. University of Mannheim, 1999.
• 9: Yoshiharu Ishikawa , Hiroyuki Kitagawa , Nobuo Ohbo, Evaluation of signature files as set access facilities in OODBs, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.247-256, May 25-28, 1993, Washington, D.C., United States
• 10: N. Mamoulis, D. W. Cheung, and W. Lian. Similarity search in sets and categorical data using the signature tree. In Proc. of Int'l Conf. on Data Engineering (ICDE), 2003.
• 11: Weiyi Meng , Clement Yu , Wei Wang , Naphtali Rishe, Performance Analysis of Three Text-Join Algorithms, IEEE Transactions on Knowledge and Data Engineering, v.10 n.3, p.477-492, May 1998 [doi>10.1109/69.687979]
• 12: Alistair Moffat , Timothy A. H. Bell, In situ generation of compressed inverted files, Journal of the American Society for Information Science, v.46 n.7, p.537-550, Aug. 1995 [doi>10.1002/(SICI)1097-4571(199508)46:7<537::AID-ASI7>3.0.CO;2-P]
• 13: Karthikeyan Ramasamy , Jignesh M. Patel , Jeffrey F. Naughton , Raghav Kaushik, Set Containment Joins: The Good, The Bad and The Ugly, Proceedings of the 26th International Conference on Very Large Data Bases, p.351-362, September 10-14, 2000
• 14: Michael Stonebraker , Dorothy Moore, Object Relational DBMSs: The Next Great Wave, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1995
• 15: Justin Zobel , Alistair Moffat , Kotagiri Ramamohanarao, Inverted files versus signature files for text indexing, ACM Transactions on Database Systems (TODS), v.23 n.4, p.453-490, Dec. 1998 [doi>10.1145/296854.277632]
• 16: Justin Zobel , Alistair Moffat , Ron Sacks-Davis, An Efficient Indexing Technique for Full Text Databases, Proceedings of the 18th International Conference on Very Large Data Bases, p.352-362, August 23-27, 1992
• 17: Justin Zobel , Alistair Moffat , Ron Sacks-Davis, Searching Large Lexicons for Partially Specified Terms using Compressed Inverted Files, Proceedings of the 19th International Conference on Very Large Data Bases, p.290-301, August 24-27, 1993

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Set theory

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Object-oriented databases; Relational databases

General Terms:
Algorithms, Experimentation, Performance