A systematic, efficient compilation method for query evaluation of DeductiveDatabases (DeDB) is proposed in this paper. In order to eliminate redundancyand to minimize the potentially relevant facts, which are two key...A systematic, efficient compilation method for query evaluation of DeductiveDatabases (DeDB) is proposed in this paper. In order to eliminate redundancyand to minimize the potentially relevant facts, which are two key issues to theefficiency of a DeDB, the compilation process is decomposed into two phases.The first is the pre-compilation phase, which is responsible for the minimiza-tion of the potentially relevant facts. The second, which we refer to as thegeneral compilation phase, is responsible for the elimination of redundancy.The rule/goal graph devised by J. D. Ullman is appropriately extended andused as a uniform formalism. Two general algorithms corresponding to the twophases respectively are described intuitively and formally展开更多
The left-linear transformation presented by Ullman, Naughton el al. is a rule-rewriting algorithm, which is similar to the magic sets transformation. Since left-linear recursions are among the most common recursions i...The left-linear transformation presented by Ullman, Naughton el al. is a rule-rewriting algorithm, which is similar to the magic sets transformation. Since left-linear recursions are among the most common recursions in practice and the transformed rules can be evaluated bottom-up efficiently, the left-linear transformation has been chosen as one of the best strategies for recursive query processing by the NALL! system at Stanford and the LDL system at MCC. However, there are two strick restraints for the left-linear展开更多
文摘A systematic, efficient compilation method for query evaluation of DeductiveDatabases (DeDB) is proposed in this paper. In order to eliminate redundancyand to minimize the potentially relevant facts, which are two key issues to theefficiency of a DeDB, the compilation process is decomposed into two phases.The first is the pre-compilation phase, which is responsible for the minimiza-tion of the potentially relevant facts. The second, which we refer to as thegeneral compilation phase, is responsible for the elimination of redundancy.The rule/goal graph devised by J. D. Ullman is appropriately extended andused as a uniform formalism. Two general algorithms corresponding to the twophases respectively are described intuitively and formally
基金Project supported in part by the Grant 91028 from the Natural Science Foundation of Henan Province, China.
文摘The left-linear transformation presented by Ullman, Naughton el al. is a rule-rewriting algorithm, which is similar to the magic sets transformation. Since left-linear recursions are among the most common recursions in practice and the transformed rules can be evaluated bottom-up efficiently, the left-linear transformation has been chosen as one of the best strategies for recursive query processing by the NALL! system at Stanford and the LDL system at MCC. However, there are two strick restraints for the left-linear
