Speeding up the Counting Method by Computing Heritage Functions in Topological Order
Yangjun Chen · Electronic workshops in computing · 1997
In this paper, an optimal method for evaluating linear recursive datalog queries is proposed. The method is based on the concepts of so-called heritage appearance function and heritage selection function. By computing such functions in topological order, a counting-like strategy can be implemented, which requires only linear time for non-cyclic data.