Efficient Retrieval of Subsumed Subgoals in Tabled Logic Programs

Flávio Cruz and Ricardo Rocha

September 2010


Tabling based systems use call similarity to decide when a tabled subgoal should produce or consume answers. Most tabling engines do that by using variant checks. A more refined method, named call subsumption, considers that a subgoal A will consume answers from a subgoal B if A is subsumed by B, thus allowing greater answer reuse. Recently, we have developed an extension, called Retroactive Call Subsumption, that improves upon call subsumption by supporting bidirectional sharing of answers between subsumed/subsuming subgoals. In this paper, we present an algorithm to efficiently retrieve the set of currently evaluating subgoals that are subsumed by a more general subgoal.


  author =    {F. Cruz and R. Rocha},
  title =     {{Efficient Retrieval of Subsumed Subgoals in Tabled Logic Programs}},
  booktitle = {Proceedings of the 4th International Conference on Compilers, Programming Languages,
               Related Technologies and Applications (CoRTA 2010) - Part of INForum 2010},
  pages =     {201--204},
  editor =    {L. S. Barbosa and M. P. Correia},
  month =     {September},
  year =      {2010},
  address =   {Braga, Portugal},

Download Paper

PDF file

Download Slides

PDF file