Challenges in Fixpoint Computation with Multisets

Uncertainty management has been a challenging issue in AI and database research. Logic database programming with its declarative advantage and its top-down and bottom-up query processing techniques has been an attractive formalism for representing and manipulating uncertain information, and numerous frameworks with uncertainty has been proposed. These proposals address fundamental issues of modeling, semantics, query processing and optimization, however, one important issue which remains unaddressed is efficient implementation of such frameworks. In this paper, we illustrate that the standard semi-naive evaluation method does not have a counterpart in general in these frameworks. We then propose a desired semi-naive algorithm, which extends the corresponding standard method, and establish its equivalence with the naive method with uncertainty. We implemented the algorithm and conducted numerous tests. Our experimental results indicate that the proposed technique is practical and supports efficient fixpoint computation with uncertainty. We believe that the method is also useful in a more general context of fixpoint computation with aggregations.