EFFICIENT TOP-DOWN COMPUTATION OF QUERIES UNDER THE WELL-FOUNDED SEMANTICS

The well-founded model provides a natural and robust semantics for log ic programs with negative literals in rule bodies. Although various pr ocedural semantics have been proposed for query evaluation under the w ell-founded semantics, the practical issues of implementation for effe ctive and efficient computation of queries have been rarely discussed. This paper investigates two major implementation issues of query eval uation under the well-founded semantics, namely, (a) to ensure that ne gative literals be resolved only after their positive counterparts hav e been completely evaluated, and (b) to detect and handle potential ne gative loops. We present efficient incremental algorithms for maintain ing positive and negative dependencies among subgoals in a top-down ev aluation. Both completely evaluated subgoals and potential negative lo ops are detected by inspecting the dependency information of a single subgoal. Our implementation can be viewed as an effective successor to SLDNF resolution, extending Prolog computation in a natural and smoot h way.