Chapter 15, Problem 21E

Explanation of Solution

Extending the hash-join algorithm:

• The hash-join is used to compute the natural join of two relations.
• The hash-join algorithm can be extended to compute the natural left outer join by,
  • Padding the tuple t_r in the probe relation with nulls, if no matching tuple is found in the build relation’s hash partition.
  • Include this null padded tuple in the result as well.
• The hash-join algorithm can be extended to compute the natural right outer join by,
  • Keeping a Boolean flag with each tuple in the current build relation partition which resides in memory.
  • Set it whenever any probe relation tuple matches the above tuple.
  • Finally, Pad with null those tuples which do not have their flags set and include them in the result.
• The hash-join algorithm can be extended to compute the natural full outer join by performing natural left outer join and natural right outer join together.

Example:

Consider the customer and depositor relations given below:

customer_name	customer_address	customer_city
Adam	Park Street	Brooklyn
Eve	Main Road	Rye
John	Bell Cross	Harrison
Jane	Sand Hill	Woodside
Tom	Walnut	Pittsfield
Jerry	Alma	Alabama