練習：データベースのテーブル結合アルゴリズムのモデル実装。 inner loop/sort merge/semi join

dbjoin.py

job = set([
    # id name
    (1, 'animator'),
    (2, 'blacksmith'),
    (3, 'cook'),
    (4, 'doctor'),
    (5, 'engineer'),
    (6, 'founder'),
    (7, 'guitarist'),
])

import random
import string
person = set([
    # id, name age job_id
    (i
    , ''.join(
        random.choice(string.lowercase)
            for j in range(random.randint(4, 8))
        )
    , random.randint(1, 30)
    , random.randint(1, 7)
    ) for i in xrange(100)
    #) for i in xrange(2) # test for semijon
])


def key(row, cols, side):
    return tuple(row[c0 if side == 0 else c1] for c0,c1 in cols)
    
def keypair(row0, row1, cols):
    return [(row0[c0], row1[c1]) for c0,c1 in cols]
    
def compare(r, s, cols):
    for a,b in keypair(r, s, cols):
        x = cmp(a, b)
        if x != 0:
            return x
    return 0

# innered loop join algorithm
# ref: http://dev.mysql.com/doc/refman/5.1/en/nested-loop-joins.html
def inneredloop(t, u, cols):
    result = set()
    for outer in t:
        for inner in u:
            if compare(outer, inner, cols) == 0:
                result.add(outer + inner)
    return result

# sort-merge join algorithm
def sortmerge(t, u, cols):
    result = set()
    st = sorted(t, key=lambda row: key(row, cols, 0))
    su = sorted(u, key=lambda row: key(row, cols, 1))
    pt = 0
    ps = 0
    while not (len(t) == pt or len(u) == ps):
        c = compare(st[pt], su[ps], cols)
        if c < 0:
            pt += 1
        elif c > 0:
            ps += 1
        else:
            result.add(st[pt] + su[ps])
            pt += 1 
    return result


def semijoin(t, u, cols):
    result = set()
    # site x
    xkey = set(key(row, cols, 0) for row in t)
    # site y
    partial = set()
    partial_cols = [(i, cols[i][1]) for i in range(len(cols))]
    for row in u:
        for k in xkey:
            if compare(k, row, partial_cols) == 0:
                partial.add(row)
    # site x
    return inneredloop(t, partial, cols)
    

def projection(tbl, cols):
    return [tuple(row[col] for col in cols) for row in tbl]
def order(tbl, cols, asc=True):
    fn = lambda row: [row[col] for col in cols]
    return sorted(tbl, key=fn, reverse=not asc)
def select(tbl, fn):
    return [row for row in tbl if fn(row)]
    
    

fn = inneredloop
fn = sortmerge
fn = semijoin

for n in fn(person, job, [(3, 0)]):
#for n in projection(fn(person, job, [(3, 0)]), [0,1,5]):
#for n in order(projection(fn(person, job, [(3, 0)]), [5,1,0]), [0]):
#for n in select(order(projection(fn(person, job, [(3, 0)]), [5,1,0]), [0]), lambda row: row[2] > 20):
    print n