Recursive functions in a data base language for complex objects

摘要

The work presented in this paper demonstrates a new method for recursive queries in a complex object data base system. The method is called functional recursion. Most previous approaches express recursive queries by set oriented recursion, i.e. they allow us to define a set M recursively by an equation M = ƒ(M). In contrast to set oriented recursion, functional recursion as defined in this paper allows the user to define a function ƒ recursively by an equation ƒ = F(ƒ). As opposed to recursive functions written in a conventional programming language, the termination criterion which sometimes is rather complex does not have to be programmed by the user but is given implicitly. By providing appropriate parameters to a function, the user can integrate a selection into the recursion in a convenient and natural way. This is not the case for set oriented recursion. When using set recursion, the user is forced to formulate a query which computes more than really needed. It is the task of the optimizer then to push the subsequent selection into the recursion. This means that the user cannot write the query in a natural way and the system then has to figure out what the user wanted. All these problems are avoided when using recursive functions as defined in this paper. Moreover, a solution based on key oriented duplicate elimination is presented which solves the problem of lists and arithmetics in the context of recursive functions. The method is illustrated by bill-of-materials examples and by a railroad example.