Zheng, Zhi Hong (2004) On efficient fixpoint computation of deductive databases with uncertainty. Masters thesis, Concordia University.
- 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  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 . We have refined a Semi-Naive method, originally proposed in , 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.|
|Degree Name:||M. Comp. Sc.|
|Thesis Supervisor(s):||Shiri, N|
|Deposited By:||Concordia University Libraries|
|Deposited On:||18 Aug 2011 18:15|
|Last Modified:||18 Aug 2011 18:15|
Repository Staff Only: item control page
Downloads per month over past year