Multi-way counting method

摘要

Multi-way counting method represents a group of counting algorithms which generalize the counting method to: (1) complex linear recursions; and (2) versatile recursive queries. Since the counting method has been recognized as one of the best performing algorithms in the processing of “simple” recursive queries on “simple” linear recursions, its generalizations to versatile queries on complex linear recursions may have great potential to outperform other algorithms. In this study, the generalization to complex linear recursions is performed by compilation. Many complex linear recursions can be compiled to multi-chain recursions to which counting algorithms are applicable. The generalization to versatile queries is performed by a quad-state variable binding analysis method. Based on the information provided by queries, compiled recursions and EDB statistics, query analysis determines the application of certain counting algorithms in different direction combinations, hence the name, multi-way counting. A comparison of our method with other previously studied processing methods is also discussed in the paper.