Multi-way counting method

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)219-229
Number of pages11
JournalInformation Systems
Issue number3
StatePublished - 1989
Externally publishedYes

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Hardware and Architecture

Cite this