Login | Register

Towards a generalized theory of deductive databases with uncertainty


Towards a generalized theory of deductive databases with uncertainty

Shiri-Varnaamkhaasti, Nematollaah (1997) Towards a generalized theory of deductive databases with uncertainty. PhD thesis, Concordia University.

[thumbnail of NQ39795.pdf]
Text (application/pdf)


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

Divisions:Concordia University > Gina Cody School of Engineering and Computer Science > Computer Science and Software Engineering
Item Type:Thesis (PhD)
Authors:Shiri-Varnaamkhaasti, Nematollaah
Pagination:xi, 135 leaves ; 29 cm.
Institution:Concordia University
Degree Name:Ph. D.
Program:Computer Science and Software Engineering
Thesis Supervisor(s):Lakshmanan, V. S
Identification Number:QA 76.9 D3S522 1997
ID Code:389
Deposited By: Concordia University Library
Deposited On:27 Aug 2009 17:11
Last Modified:13 Jul 2020 19:46
Related URLs:
All items in Spectrum are protected by copyright, with all rights reserved. The use of items is governed by Spectrum's terms of access.

Repository Staff Only: item control page

Downloads per month over past year

Research related to the current document (at the CORE website)
- Research related to the current document (at the CORE website)
Back to top Back to top