Breadcrumb

 
 

On efficient fixpoint computation of deductive databases with uncertainty

Title:

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.

[img]
Preview
PDF - Accepted Version
4Mb

Abstract

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 > Faculty 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
Date:2004
Thesis Supervisor(s):Shiri, N
ID Code:8114
Deposited By:Concordia University Libraries
Deposited On:18 Aug 2011 14:15
Last Modified:18 Aug 2011 14:15
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

Document Downloads

More statistics for this item...

Concordia University - Footer