Join indices

ABSTRACT

In new application areas of relational database systems, such as artificial intelligence, the join operator is used more extensively than in conventional applications. In this paper, we propose a simple data structure, called a join index, for improving the performance of joins in the context of complex queries. For most of the joins, updates to join indices incur very little overhead. Some properties of a join index are (i) its efficient use of memory and adaptiveness to parallel execution, (ii) its compatibility with other operations (including select and union), (iii) its support for abstract data type join predicates, (iv) its support for multirelation clustering, and (v) its use in representing directed graphs and in evaluating recursive queries. Finally, the analysis of the join algorithm using join indices shows its excellent performance.

REFERENCES

• 1: BAYER, R., AND MCCREIGHT, E. Organization and maintenance of large ordered indexes. Acts inf. 1, 3, 1972.
• 2: Dina Bitton , Haran Boral , David J. DeWitt , W. Kevin Wilkinson, Parallel algorithms for the execution of relational database operations, ACM Transactions on Database Systems (TODS), v.8 n.3, p.324-353, Sept. 1983 [doi>10.1145/319989.319991]
• 3: Dina Bitton , David J. DeWitt , Carolyn Turbyfill, Benchmarking Database Systems A Systematic Approach, Proceedings of the 9th International Conference on Very Large Data Bases, p.8-19, October 31-November 02, 1983
• 4: BLASGEN, S. W., AND ESWARAN, Z.P. Storage and access in relational databases. IBM Syst. J. 16, 4, (1977).
• 5: Kjell Bratbergsengen, Hashing Methods and Relational Algebra Operations, Proceedings of the 10th International Conference on Very Large Data Bases, p.323-333, August 27-31, 1984
• 6: E. F. Codd, Extending the database relational model to capture more meaning, ACM Transactions on Database Systems (TODS), v.4 n.4, p.397-434, Dec. 1979 [doi>10.1145/320107.320109]
• 7: Douglas Comer, Ubiquitous B-Tree, ACM Computing Surveys (CSUR), v.11 n.2, p.121-137, June 1979 [doi>10.1145/356770.356776]
• 8: George P. Copeland , Setrag N. Khoshafian, A decomposition storage model, Proceedings of the 1985 ACM SIGMOD international conference on Management of data, p.268-279, May 1985, Austin, Texas, United States
• 9: S. Misbah Deen, An Implementation of Impure Surrogates, Proceedings of the 8th International Conference on Very Large Data Bases, p.245-256, September 08-10, 1982
• 10: David J DeWitt , Randy H Katz , Frank Olken , Leonard D Shapiro , Michael R Stonebraker , David Wood, Implementation techniques for main memory database systems, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• 11: Leo R. Gotlieb, Computing joins of relations, Proceedings of the 1975 ACM SIGMOD international conference on Management of data, May 14-16, 1975, San Jose, California [doi>10.1145/500080.500089]
• 12: John Guttag, Abstract data types and the development of data structures, Communications of the ACM, v.20 n.6, p.396-404, June 1977 [doi>10.1145/359605.359618]
• 13: Theo Haerder, Implementing a generalized access path structure for a relational database system, ACM Transactions on Database Systems (TODS), v.3 n.3, p.285-298, Sept. 1978 [doi>10.1145/320263.320284]
• 14: HALL, P., OWLETT, J., AND TODD, S. J.P. Relations and entities. In Modelling in DBMS, G. Nijssen, Ed. North-Holland, Amsterdam, 1976, pp. 201-220.
• 15: Matthias Jarke , Joachim W. Schmidt, Query processing strategies in the PASCAL/R relational database management system, Proceedings of the 1982 ACM SIGMOD international conference on Management of data, June 02-04, 1982, Orlando, Florida [doi>10.1145/582353.582402]
• 16: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 17: M. Missikoff, A domain based internal schema for relational database machines, Proceedings of the 1982 ACM SIGMOD international conference on Management of data, June 02-04, 1982, Orlando, Florida [doi>10.1145/582353.582395]
• 18: Nicholas Roussopoulos, View indexing in relational databases, ACM Transactions on Database Systems (TODS), v.7 n.2, p.258-290, June 1982 [doi>10.1145/319702.319729]
• 19: Eric Simon , Patrick Valduriez, Design and implementation of an extendible integrity subsystem, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• 20: D. Tsichritzis, LSL: a Link and Selector Language, Proceedings of the 1976 ACM SIGMOD international conference on Management of data, June 02-04, 1976, Washington, D.C.
• 21: Patrick Valduriez , Georges Gardarin, Join and Semijoin Algorithms for a Multiprocessor Database Machine, ACM Transactions on Database Systems (TODS), v.9 n.1, p.133-161, March 1984 [doi>10.1145/348.318590]
• 22: VALDURIEZ, P., AND BORAL, H. Evaluation of recursive queries using join indices. In Proceedings o{ the 1st International Con{erence on Expert Database Systems (Charleston, S.C., Apr. 1986), Benjamin/Cummings, Menlo Park, Calif., 1986, pp. 197-208.
• 23: Patrick Valduriez , Setrag Khoshafian , George P. Copeland, Implementation Techniques of Complex Objects, Proceedings of the 12th International Conference on Very Large Data Bases, p.101-110, August 25-28, 1986
• 24: S. B. Yao, Approximating block accesses in database organizations, Communications of the ACM, v.20 n.4, p.260-261, April 1977 [doi>10.1145/359461.359475]

INDEX TERMS

Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Trees
  E.5 FILES
      Subjects: Organization/structure

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Data models
      H.2.2 Physical Design
          Subjects: Access methods
      H.2.4 Systems
          Subjects: Query processing
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing
          Subjects: Indexing methods

General Terms:
Algorithms, Design, Performance