Login | Register

Query processing and optimization in deductive databasses with certainty constraints


Query processing and optimization in deductive databasses with certainty constraints

Lai, Jinzan (2009) Query processing and optimization in deductive databasses with certainty constraints. Masters thesis, Concordia University.

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


Uncertainty reasoning has been identified as an important and challenging issue in the database research presented in the Lowell report [ea05]. Many logic frameworks have been proposed to represent and reason about uncertainty in deductive databases. Based on the way in which uncertainties are associated with the facts and rules in programs, these frameworks have been classified into: "annotation based" (AB) and "implication based" (IB). [Shi05] has investigated the relative expressive powers of AB and IB frameworks and has introduced the notion of certainty constraints, which makes them equivalent in terms of expressive power. Due to this equivalence, we developed transformation algorithms operating between AB and IB frameworks. With presence of certainty constraints in rule bodies in logic programs, query processing and optimizations become more complicated. The bottom-up query evaluation algorithms Naive, Semi-Naive, and Semi-Naive with Partition in parametric framework [SZ04, SZ08] do not consider certainty constraints. We extend these algorithms by incorporating a new checker module and develop extended evaluation algorithms which deal with certainty constraints. We have developed the proposed techniques and conducted many experiments to measure efficiency. Our results and benchmarks indicate that the proposed techniques and strategies yield a useful and efficient evaluation engine for deductive databases with certainty constraints.

Divisions:Concordia University > Gina Cody School of Engineering and Computer Science > Computer Science and Software Engineering
Item Type:Thesis (Masters)
Authors:Lai, Jinzan
Pagination:xi, 108 leaves : ill. ; 29 cm.
Institution:Concordia University
Degree Name:M. Comp. Sc.
Program:Computer Science and Software Engineering
Thesis Supervisor(s):Shiri, Nematollaah
ID Code:976317
Deposited By: Concordia University Library
Deposited On:22 Jan 2013 16:23
Last Modified:18 Jan 2018 17:42
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