Towards a generalized theory of deductive databases with uncertainty

摘要

Uncertainty management is identified as a challenging issue in databases [SSU91]. Logic database programming, with its declarative advantage and its powerful top-down and bottom-up query processing techniques has attracted the attention of researchers, and numerous logic frameworks with uncertainty have been proposed over the last decade. On the basis in which uncertainty is associated with the facts and rules in a program, we classify the approaches taken to uncertainty in these frameworks into the annotation based (AB) and implication based (IB). In the AB approach, certainties are associated with the atoms in the rules and facts, while in the IB approach, they are associated with the implications in the programs.;In this thesis, we attempt to address the aforementioned challenging issue. To this end, we take an axiomatic approach and study the relevant issues: (1) the language aspects, (2) query optimization, (3) the termination behaviors and data complexity of the bottom-up evaluations of logic programs with uncertainty, (4) the expressive power, and (5) the ease and efficiency of implementing such languages. Each of these issues is discussed in a chapter of this thesis, in that order. Although our focus in this study is on the IB approach, the insights provided and the lessons learned are useful in a more general context of deduction with uncertainty.;In order to study these issues in a framework independent manner, we first identify a number of "reasonable" properties which are normally satisfied by combination functions in programs with uncertainty. We will then propose a language, called the parametric framework, where the parameters are the combination functions defined on the underlying certainty lattice. The proposed framework uses multisets as the basis of the structure of the semantics, as opposed to using sets, which are often used.;This is the key point to the expressive power of our framework, which unifies and generalizes the IB approach to uncertainty. With this framework as a basis, we study the other relevant issues mentioned and establish various results. A main advantage of our axiomatic approach in studying the various issues in the thesis is that it makes the results applicable to a wide range of (IB) frameworks. Our top-down and bottom-up implementations of the parametric framework show that the ideas in the thesis are practical which lend themselves to an-easy-to-use and efficient "environment" for deduction with uncertainty at large.