Copyright © 1998 T. H. Merrett

COMP 612              Principles of Database ProgramminG                  Week 7

                               Relational Recursion

Aldat (and relix) permits _views_ to be defined using the word  is  in place of
the assignment arrow,  <- .
                   <identifier> is <relational expression>
Any relational expression whatever is permitted, and virtual attributes (defined
by the domain algebra) are allowed in it.

The effect of the view is to define a deferred operation. Think of it as a
parameterless function: in this respect it is similar to the domain algebra
construct,  let .. be . A view will be computed when used in a regular
assignment statement or in a print command. For example, in relix,
    R is S ijoin T;    << R is a view. The join is not executed at this point.>>
    Q <- [A, B] in R;  << Now the join is executed, and A, B are projected    >>
                       << from the result. >>
    pr R;             << The join is executed again, and the result printed. >>

Any view may be _recursive_, that is, the relation name to the left of  is  may
appear in the relational expression. The semantics of this is, essentially, that
when the view definition is executed, it may be thought of as being converted to
an assignment statement and placed in a loop. Initially the relation defined by
the view is empty, and the loop iterates until this relation stops changing.

The simplest example of this is _transitive closure_.
    relation T(START, END);              << Declaration needed to help relix. >>
    T is G ujoin G [END:icomp:START] T;  << G is a given graph, G(START, END) >>
    TRANS <- T;                          << Compute transitive closure of G   >>
An application is to derive all ancestors given parents.
    relation ANC(SR, JR);
    ANC is PAR ujoin PAR [SR:icomp:JR] ANC;
  <<An ancestor is a parent or the parent of an ancestor.>>

The domain algebra may also be used, as in the explosion of a bill-of-materials.
    let A' be A; let S' be S; let Q' be Q;
    let Q'' be equiv + of Q*Q' by A, S';
    let Q''' be Q*Q''; let Q be Q'''; << This is OK if we project Q carefully >>
    relation EXPLO(A, S, Q);
    EXPLO is [A,S,Q] in [A,S,Q'''] in << Here is the careful projection       >>
             (PARTOF [A,S:ujoin:A,S'] << PARTOF(A, S, Q) is the given bom     >>
                     ([A,S',Q''] in EXPLO [S:ijoin:A'] (A',S',Q' in PARTOF)
             )       );

Mutual recursion is also allowed.
    R is S ujoin T;
    S is [A, B] in R;
is a trivial example which probably does nothing interesting.

Of course, we can always write recursive views that never terminate, or produce
nonsense. But there are some significant applications, apart from transitive
closures and path computations such as bom explosions. An inference engine for
if-then rule-based expert systems is one.
The implementation in relix reflects the semantics given above. This is "naive"
and could be more efficient for special cases such as transitive closure and
path computations. But it is fully general, and one can usually rewrite the
simple code for, say, transitive closure, above, into sophisticated versions
of three or four mutually recursive views which run much faster.