Copyright © 1998 T. H. Merrett COMP 612 Principles of Database ProgramminG Week 7 Relational Recursion Views 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. >> Recursion 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.>> pr!!ANC 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.