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