The algorithm for SUPERJOIN

Here is the algorithm for ‘SUPERJOIN’, which generates the question about ‘how many possible binary operators’:

 

Attribs a3={}
For a1 in r1.attribs
  If L and a1 not in rel2.attribs then a3 += a1
  If C and a1 in rel2.attribs then a3 += a1
For a2 in r2.attribs
  If R and a2 not in rel1.attribs then a3 += a2
Tuple t3(a3)={}
For t1 in r1.tuples
  For t2 in r2.tuples
    If T and t1 not match t2 then t3 += t1
    If M and t1 match t2 then t3 += t1 + t2 // <<-- see note
    If B and t1 not match t2 then t3 += t2
Relation r3(a3,t3)

These are set operations, so duplicate attributes and tuples are discarded. The final result is r3 with heading a3.  The operation ‘+’ is taken to mean a new tuple that is the union of its arguments. It occurs to me that a different operation could be substituted at this point, with different outcomes.

The above generates the results in this table:

L C R LC CR LR LCR
T
M
B
TM
TB
MB
TMB

 

Every tick is a unique outcome. Blanks are either OUTER joins or empty.  The question is: which if any well-known binary (dyadic) algebraic operations on relations cannot be generated by this algorithm?

Leave a Comment

Filed under General

Leave a Reply

Your email address will not be published. Required fields are marked *