Abstract

Uncertainty reasoning has been identified as an important and challenging issue in the database research presented in the Lowell report [ea05]. Many logic frameworks have been proposed to represent and reason about uncertainty in deductive databases. Based on the way in which uncertainties are associated with the facts and rules in programs, these frameworks have been classified into: "annotation based" (AB) and "implication based" (IB). [Shi05] has investigated the relative expressive powers of AB and IB frameworks and has introduced the notion of certainty constraints, which makes them equivalent in terms of expressive power. Due to this equivalence, we developed transformation algorithms operating between AB and IB frameworks. With presence of certainty constraints in rule bodies in logic programs, query processing and optimizations become more complicated. The bottom-up query evaluation algorithms Naive, Semi-Naive, and Semi-Naive with Partition in parametric framework [SZ04, SZ08] do not consider certainty constraints. We extend these algorithms by incorporating a new checker module and develop extended evaluation algorithms which deal with certainty constraints. We have developed the proposed techniques and conducted many experiments to measure efficiency. Our results and benchmarks indicate that the proposed techniques and strategies yield a useful and efficient evaluation engine for deductive databases with certainty constraints.