A Cycle-Detection Algorithm for Deductive Databases Containing Cyclic and Asynchronous Data and an Application for Recursive Query Compilation

A new algorithm for detecting all cycles in a directed cyclic graph has been developed. It takes as input either a binary relation, or an n-ary relation projected to two attributes. It produces a list of cycle information, including a sequence of data values in each cycle, and the cycle length. The algorithm can be used as a preprocessor to general database functions, including Level-Cycle Merge, an algorithm for linear recursive query compilation. ;