Normalization of linear recursions in deductive databases

A graph-matrix expansion-based compilation technique is introduced, which transforms complex linear recursions into highly regular linear normal forms (LNFs). A variable connection graph-matrix, the V-matrix, is constructed to simulate the expansions of a linear recursion and discover its expansion regularity. Based on the expansion regularity, a linear recursion can be normalized into LNF. The normalization of linear recursions not only captures the bindings which are difficult to be captured otherwise but also facilitates the development of powerful query analysis and evaluation techniques for complex linear recursions in deductive databases.