Expressive Power of Logic Frameworks with Certainty Constraints

All Papers

Uncertainty reasoning has been a challenging issue in AI and database research. During the last two decades, numerous frameworks have been proposed by extending the standard logic programming and deductive database systems. These frameworks vary in different ways including the way in which uncertainties are associated with the facts and rules in programs. On the basis of this, we have classified the approaches of these frameworks into "annotation based" (AB) and "implication based" (IB). In the AB approach, uncertainties are associated with the atoms whereas in the IB approach they are associated with implications. Except for some particular cases, the exact relationship between the two approaches has not been studied previously, in that, the two are treated as somewhat orthogonal and unrelated. In this paper, we investigate this issue and introduce the notion of certainty constraint. The purposes are two fold. First, this notion supports the operations of selection and join by certainty, which are often useful in query formulation and processing in the context of uncertainty. Second and more importantly, this notion "relates" the expressive power of the two approaches. To be precise, we propose a transformation technique which establishes that the AB and IB approaches are equally expressive when the rule bodies are extended with certainty constraints. A consequence of this result is that, using the transformation technique, we can adopt and use successful developments in either approach.