Text size
  • Small
  • Medium
  • Large
  • Standard
  • Blue text on blue
  • High contrast (Yellow text on black)
  • Blue text on beige

    Speeding up the Counting Method by Computing Heritage Functions in Topological Order

    Advances in Databases and Information Systems '97

    St Petersburg, 2nd - 5th September 1997


    Y. Chen


    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.


    PDF filePDF Version of this Paper (244kb)