COMPILATION AND EVALUATION OF NESTED LINEAR RECURSIONS: A DEDUCTIVE DATABASE APPROACH
Tong Lü · 1993
A deductive database system is an extension of a relational database system by supporting a rulebased, more expressive database language while preserving the set-oriented and declarative style of a relational database query language. This thesis studies the implementation and extension of the chain-based compilation and evaluation method, an interesting method for deductive query evaluation. Our'work makes the following two contributions : (1) a query-independent compilation method is developed in C using LexlYacc, which automatically generates compiled chain-forms for linear recursions; and (2) the applicable domain of the chain-based compilation and evaluation method is extended to functional nested linear recursions. The query-independent compilation method is based on the expansion regularity of a graph matrix, the V-matrix, which represents the variable connection pattern of a recursive rule. A complex linear recursion can be compiled into a highly regular chain-form and linear normal form, which facilitates efficient query analysis and processing. The study on the extension of the applicable domain of the chain-based compilation and evaluation method to fbnctional nested linear recursions leads to the systematic analysis of a typical logic program, the n-queens program. Our analysis shows that nested linear recursions can be implemented systematically and efficiently using the chain-based query evaluation method.