The methods for computing joins discussed in Section 10.5 all deal with equi-joins. Discuss their applicability to the problem of computing inequality joins, such as r daA

Suppose we use sort-merge join to compute inequality joins, such as r daA


```
Input: relation r sorted on attribute A;
relation s sorted on attribute B
Output: rA
Result := { } // initialize Result
tr := getFirst(r) // get ?rst tuple
ts := getFirst(s)

while !eof(r) && !eof(s) do {
while !eof(s) && tr.A >= ts.B do
ts := getNext(s);
if tr.A = c < ts.B then {
Result := (?A=c(r) × ?B>c(s)) ? Result;
tr := the next tuple t ? r where t[A]>c
}
}
return Result;
```

As to other methods, hash join is not useful for equality conditions. Nested loops and block-nested loops work with little change. Index-nested loops join also works is minor changes, if the index on B in s is B+ tree. If the B+ tree is unclustered, then index nested loops join is going to be expensive, but the algorithm still works.
If the index is a hash index, then Index-nested loops join is not useful for computing inequality joins.

Computer Science & Information Technology

You might also like to view...

A(n) __________ entity contains both data and procedures.

a. object b. instance c. event d. array

Computer Science & Information Technology

The control unit is one component of the ________

A) front side bus B) clock C) CPU D) cache

Computer Science & Information Technology

____ allow the physical data to reside at separate and independent locations that are electronically networked together.

A. Discrete databases B. Singleton databases C. Distributed databases D. Normalized databases

Computer Science & Information Technology

__________ is the mortal enemy of a PC.

dirt dust heat grime

Computer Science & Information Technology