Counting and Topological Order

The counting method is a simple and efficient method for processing linear recursive datalog queries. Its time complexity is bounded by O(n.e), where n and e denote the numbers of nodes and edges, respectively, in the graph representing the input relations. In this paper, the concepts of heritage appearance function and heritage selection function are introduced, and an evaluation algorithm based on the computation of such functions in topological order is developed. This new algorithm requires only linear …