Efficient query processing in deductive databases: the logicbase approach
Ling Liu · Summit (Simon Fraser University) · 1996
The thesis investigates the design and implementation of a deductive database system prototype, LogicBase, and several query processing and optimization techniques in deductive database systems.LogicBase adopts the compilation-based query processing method, where logic programs are compiled into highly regular forms.A query is evaluated on the compiled form by performing iterative relational operations.LogicBase facilitates a detailed query analysis to select an appropriate query evaluation strategy and t o generate an efficient query processing plan, thus to achieve declarativeness and efficiency.An important feature of LogicBase is its ability to handle constraints, which are manipulated to determine the safety of an evaluation plan and to reduce search space in some expensive query processing.Constraints and monotonicity are investigated to benefit constraint pushing and derivation.Moreover, interaction of constraints with different programs is studied.A set of query processing strategies are proposed for efficient evaluation of programs with multiple linear recursions, which extends the method of handling single linear recursions by accessing the union of separate relations.Furthermore, an ext ension of counting method to deal with cyclic data path is devised, which transforms the counting method into the propagations of relative distances over cyclic paths in a directed acyclic graph constructed from strongly connected components of the original data graph.of support, encouragement and pleasant cooperation.I would like to thank Dr. Tiko Kameda and Dr. Laks V.S. Lakshmanan who spent extra effort to help me generate a better thesis.