Join indices
Patrick Valduriez · ACM Transactions on Database Systems · 1987
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.
Cited by 504 works. doi:10.1145/22952.22955 Open-access PDF
Authors
References
- The Art of Computer Programming: Volume 3: Sorting and Searching
- Organization and maintenance of large ordered indexes
- Ubiquitous B-Tree
- Extending the database relational model to capture more meaning
- Implementation techniques for main memory database systems
- Benchmarking Database Systems A Systematic Approach
- Extending the data base relational model to capture more meaning
- Abstract data types and the development of data structures
- Approximating block accesses in database organizations
- Storage and access in relational data bases