Assume there is an index on attribute Ra Describe how this i

Assume there is an index on attribute R.a. Describe how this index could be used to improve the execution of the following operations. Under what circumstances would be index-based algorithm be more efficient than sort- or hash-based algorithms ? R U_s S (assume that R and Shave no duplicates, although they may have tuples in common ? R _s S (again with R and S sets ? Delta (R) ?

Solution

Our option is to first copy all the tuples of R to the output. Then, for each tuple t of S, retrieve the tuples of R for which R.a matches the a-value of t. Check whether t appears among them, and output t if not.This method can be efficient if S is small and V(R,a) is large