Rosetta Code

Hash join: Difference between revisions

Page Discussion

Hash join (view source)

Revision as of 22:42, 30 November 2013

214 bytes added ,  10 years ago
tidy up task description
mNo edit summary
(tidy up task description)
Line 1:
{{draft task}}
{{task}}[[wp:Hash Join|Hash Join]]
The classic [[wp:Hash Join|hash join]] algorithm for an inner join of two relations has the following steps:
<ul>
<li>Hash phase : Creating a hash table for one of the two relations by applying a hash
Line 10:
 
The algorithm is as follows:
 
<pre>
'''for each''' tuple ''s'' '''in''' ''S'' '''do'''
{ '''let''' ''h'' = hash on join attributes ''s''(b)
'''place''' tuples''s'' '''in''' hash table based''S<sub>h</sub>'' on'''in''' bucket '''keyed by''' hash values};value ''h''
'''for each''' tuple ''r'' '''in''' ''R'' '''do'''
{ '''let''' ''h'' = hash on join attributes ''r''(a)
if r hashes'''if''' in''h'' indicates a nonempty bucket (''B'') of hash table for ''S<sub>h</sub>''
'''if''' ''h'' matches any ''s'' in ''B''
then
{if r hash key matches any s in bucket '''concatenate''' ''r'' and ''s''
'''place''' relation in ''Q}};</pre>''
 
Implement the Hash Join algorithm in your programming language (optionally providing a test case as well).
Anonymous user
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/236666"