Abstract

Uncertainty management has been identified as an important challenge in AI and database research. Many frameworks of logic programming have been proposed to manage uncertain information in deductive databases and expert systems. These proposals address fundamental issues of modeling, semantics, query processing and optimization. However, there have been fewer reports on efficient implementation of such frameworks. In this research, we study this issue in the context of a fragment of the parametric framework [19] over the certainty domain of [0, 1]. It has been shown that the standard Semi-Naive fixpoint evaluation method does not have a counterpart when uncertainty is present [32]. We have refined a Semi-Naive method, originally proposed in [32], and developed a Semi-Naive evaluation engine that takes into account the multiplicity of derivations of the same atom. We also introduced a refinement of this evaluation, called Semi-Naive with Partition, which further improves the efficiency of the Semi-Naive method with uncertainty. Finally, we adopt "stratification" from Datalog, which is shown to make a significance efficiency for certain input programs with uncertainty. We have conducted numerous experiments to assess the benefits of the collection of optimizations proposed in this research. Our experiments and benchmarks indicate that the proposed techniques and tricks yield a useful, efficient evaluation engine for deductive databases with uncertainty.