Login | Register

Extending magic sets techniques to deductive databases with uncertainty


Extending magic sets techniques to deductive databases with uncertainty

Qiong, Huang (2008) Extending magic sets techniques to deductive databases with uncertainty. Masters thesis, Concordia University.

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


With the magic sets techniques having been proposed to improve the efficiency of bottom-up evaluations of Datalog programs by taking advantage of goal structure, we extend these techniques to deductive databases with uncertainty in the context of the parametric framework (PF). In our endeavor, we develop the generalized magic sets and generalized supplementary magic sets techniques, and establish their correctness. We have implemented the proposed techniques and have conducted numerous experiments for the assessment of the evaluation performance. Our experiment results reveal that different programs enjoy different efficiency gain, depending on the potential facts ratio, which measures the capacity to improve efficiency. When this ratio ranges from 1% to 20%, the efficiency observed was approximately 1 to 700 times faster. Our results also indicate that an integration of magic sets techniques and semi-naive evaluation with predicate partitioning yield the best performance.

Divisions:Concordia University > Gina Cody School of Engineering and Computer Science > Computer Science and Software Engineering
Item Type:Thesis (Masters)
Authors:Qiong, Huang
Pagination:ix, 89 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:975919
Deposited By: Concordia University Library
Deposited On:22 Jan 2013 16:17
Last Modified:18 Jan 2018 17:41
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