The “left outer join” operation is an extension of the relational join operation
ID: 3574664 • Letter: T
Question
The “left outer join” operation is an extension of the relational join operation. The basic idea is that all tuples in the left relation always appear in the “left outer join” result, irrespective of whether they join with any tuple in the right relation. For example, consider two relations R(A, B), and S(B, C). Assume that R has the following tuples: (1, 10), (1, 20), and S has the following tuples: (10, 75), (10, 85), (30, 95). R LeftOuterJoin S will have the following tuples: (1, 10, 75), (1, 10, 85), (1, 20, null). Note that the first two tuples are the result of a regular join operation between R and S. The third tuple (1, 20, null) is added to the left outer join result because the tuple (1, 20) in R (which is the left relation) does not join with any tuple in S; the S column values are set to null in this case.
Note that the left outer join operation is not symmetric because tuples in the right relation do not appear in the outer join result unless they join with a tuple in the left relation. In our example, the tuple (30, 95) in S (the right relation) does not appear in the left outer join result because it does not join with any tuple in R.
Given the above description of left outer joins, answer the following questions.
How can you adapt the block nested-loops join algorithm to process left outer joins?
How can you adapt the sort-merge join algorithm to process left outer joins?
Explanation / Answer
How can you adapt the block nested-loops join algorithm to process left outer joins?
Answer: Block Nested-Loop(BNL) uses buffering rows in outer loops so that it decreases the looping
again for inner loops.
for each row in table1 match range {
for each row in table2 match reference key {
store used columns from table1, table2 in join buffer
if buffer is full {
for each row in table3 {
for each table1, table2 combination in join buffer {
if row satisfies join conditions,
send to client
}
}
empty buffer
}
}
}
if buffer is not empty {
for each row in table3 {
for each table1, table2 combination in join buffer {
if row satisfies join conditions,
send to client
}
}
}
-------------------------------------------------------------------------------------------------------------------------------------------------------------
How can you adapt the sort-merge join algorithm to process left outer joins?
It merges the attributes and sort it. Here required condition is that atleast one equal predicate must
match in other tuple. The approach of this algorithm is merge two tuples and when values of two join
tuple attributes differnt, it will skip to next row to either left or right hand. It depends on lower values.
If more than one match then backtracking is necessary.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.