A Factorizing Optimization Algorithm Of Magic Transformation

In field of deductive database, magic transformation is an evaluation strategy that combines top-down with bottom-up. It restricts the computation of logic program to tuples that are related to the query. However, in search of the relevant data, the cost of generating additional tuples produced by logic program to which magic transformation is applied increases with the arity of IDB(Intensional DataBase) predicates increasing. Therefore, trying to reduce the arity of IDB .. predicates is significative to improving the efficiency of query. The central work of this paper is as follow:(1) A new factorizing optimization algorithm which reduce the arity of IDB predicates by factorizing the logic program is presented Magic transformation is applied to subprogram. Moreover the decomposed subprogram can be implemented in parallel. Therefore, it improves the efficiency of magic transformation. The result of experiment shows that the algorithm is effective too.(2) In order to validate the efficiency of algorithm, this paper design and implement a testing , platform rule processor based on SQL SERVER. The main function of the processor is to translate the first order logic rule into embedded-SQL programs, which make SQL SERVER DBMS possess the capability in expressing recursive query with logic language. We have implemented a series of algorithm, which includes rule adornment, logic program adornment and factorization, magic transformation, factorizing magic transformation. The platform is characteristic of transplant, expansion.(3)The left-linear and right-linear recursive transformation and traditional magic transformation are contrasted with the factorizing magic transformation. Afterward, the cost of tuple ID is analyzed in factorizing magic transformation. Based on the analysis two further optimization methods were put forward. Finally, the result of experiment was offered.The algorithm of this paper is applicable to two-dimension factorizing program, which includes one IDB predicate. Because the factorization attribute of logic program possess the property of uncertainty, exploring the fargoing factorizing algorithm need further study.