Login | Register

On efficient fixpoint computation of deductive databases with uncertainty


On efficient fixpoint computation of deductive databases with uncertainty

Zheng, Zhi Hong (2004) On efficient fixpoint computation of deductive databases with uncertainty. Masters thesis, Concordia University.

Text (application/pdf)
MQ94763.pdf - Accepted Version


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.

Divisions:Concordia University > Gina Cody School of Engineering and Computer Science > Computer Science and Software Engineering
Item Type:Thesis (Masters)
Authors:Zheng, Zhi Hong
Pagination:x, 132 leaves : ill. ; 29 cm.
Institution:Concordia University
Degree Name:M. Comp. Sc.
Program:Computer Science
Thesis Supervisor(s):Shiri, N
ID Code:8114
Deposited By: Concordia University Library
Deposited On:18 Aug 2011 18:15
Last Modified:18 Jan 2018 17:32
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

Back to top Back to top