A new way to speed up recursion in relational databases

Composite object represented as a directed graph is an important data structure which requires efficient sup-port in CAD/CAM, CASE, office systems, software man-agement, web databases and document databases. It is cumbersome to handle such an object in relational database systems when it involves recursion relationships. In this pa-per we present a new encoding method to support the effi-cient computation of recursion. In addition, we devise a linear time algorithm to identify the sequence of spanning trees (forests) w.r.t. a directed acyclic graph (DAG), which covers all the edges of the graph. Together with the new en-coding method this algorithm enable us to compute recur-sion w.r.t. a DAG in time O(e), where e represent the number of the edges of the DAG. More importantly, this,method is especially suitable for a relational environment.