Monday, December 19, 2005

Minimum Union

The key operation to provide outer joins that are associative and communitive, as noted in Outer Joins Aren't Primitive, is called "minimum union". Minimum union (I've also seen "outer union") pads with nulls the tuples of two schemas and then unions them (without duplicate removal).

The original thesis "Algebraic Optimization of Outerjoin Queries" gives a variant of relational algebra that allows tuples defined by different sets of attributes (schemes) rather than padding with nulls. This actually removes the requirement for nulls. It also includes presenting the data in a nested relational form, where instead of having one tuple in a parent-child relationship, children are a set to a parent. This is just like the way Kowari presents its results (Figure 3.2 in the paper).

No comments: