This research investigates query processing and optimization in a deductive database system. The most important computational challenges that arise in such a system are due to the presence of recursively defined relations, i.e., those defined by recursive Horn clauses. We will extend known algebraic models and use them to study recursion. We will implement several processing algorithms for recursion and compare their performance while varying the values of several important database parameters. We will also develop query optimization algorithms that take into account the important processing algorithms and, using realistic estimates for intermediate result sizes, suggest the most effective access plan for the query concerned. Our implementation effort will be supported by the investigation of several theoretical issues that arise regarding recursion in database systems, such as maintaining materialized relations that are defined recursively, characterizing uniformly bounded recursion, and characterizing equivalence of nonlinear and linear Horn clauses. The importance of this research is that it leads to improvements in database management systems, allowing them to answer more complicated kinds of inquiries automatically. These enhanced database management systems are needed to effectively support new application areas, such as Computer Assisted Design/Manufacturing and knowledge based reasoning systems in artificial intelligence.
