In this chapter, we introduce the basic ideas that stand behind join processing in conventional relational database systems. Understanding the principles, techniques and experiences of traditional join processing is a precondition for understanding (a) the different efficiency considerations that are imposed by temporal joins, and (b) the decisions that we take when designing efficient temporal join techniques in the oncoming chapters.
Section 3.1 formally defines the join operation. In section 3.2, the role of the join operation in the relational data model is elaborated. This should make the reader aware of the significance and the importance of the join and efficient join processing. In section 3.3, we introduce some types of joins. Traditionally, both the vendors and the research community have mainly focused on one type of join, namely the equi-join, because it is by far the most frequent one in typical database installations. Nevertheless, it is stressed that there is a rising need for specific types of joins, such as temporal or spatial joins. Section 3.4 presents a wide range of sequential join algorithms. Although the emphasis is put on equi-joins we also discuss issues regarding nonequi-joins. Similarly, section 3.5 presents techniques for processing joins in parallel. Finally, a classification schema for join algorithms is given in section 3.6.