Monthly Archives: October 2014

16/10/2014 · 9:18 pm

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

08/10/2014 · 9:14 pm

What does a type system need?

I’d like to ask what TTM really needs of a type system. My opinion:

A ‘type’:

  • Is a named set of values and operations on those values.
  • The set of values is fixed, but the set of operations may be extensible.
  • An attribute of a tuple belongs to a type, and every value it can take on is a value of that type. (No NULLs unless NULL happens to be a value of that type).
  • Values are associated with an underlying implementation-defined bit pattern, and every value has a unique bit pattern. Not every bit pattern is a value.

A ‘type system’:

  • Is an interoperable set of types, of sufficient scope for its intended purpose.
  • A minimalistic abstract type system consists of Number, Character, Binary, Tuple and Relation. All of these are ‘infinite’.
  • A practical concrete type system includes members consistent or compatible with common programming language and SQL types, such as Boolean, Integer, Float, Decimal, Time, etc. All of these are ‘finite’.
  • An open type system is extensible by some means to add members that are valuable in a particular problem domain. Otherwise it is closed.
  • Provides conversions from one type to another, which may be ‘implicit’ (preserves all values) or ‘explicit’ (some values lost or altered).

Note that all tuples are of Tuple type and all relations of Relation type. The header is not part of the type, so it must be part of the value.

An ‘expression’:

  • Is a composition of literal values, variable values, attribute values and operations, which can be evaluated to return a single value (closed), multiple values (open) or a (possibly ordered) collection of values (array).
  • Provides support for the chosen Relational Algebra, in particular for creating, extending and filtering tuples and relations (NEW, EXTEND, WHERE).
  • Provides support for an external programming language to evaluate expressions and retrieve values and arrays of values.

That’s a summary of where I’m up to. I don’t see a need for type inheritance, given implicit conversions. I don’t see a need for building the extension capabilities into a new language. The above looks complete, consistent and implementable.

I’m happy with the Rel approach using Java to extend the type system. In that case the type system comprises the built in types, type definitions in Tutorial D code and the jar file that extends the type system.

Leave a Comment

Filed under Rationale