Optimization of Nonrecursive Queries

Abstract

State-of-the-art optimization approaches for relational database systems, e.g., those used in systems such as OBE, SQL/DS, and commercial INGRES. when used for queries in non-traditional database applications, suffer from two problems. First, the time complexity of their optimization algorithms, being combinatoric, is exponential in the number of relations to be joined in the query. Their cost is therefore prohibitive in situa-tions such as deductive databases and logic oriented languages for knowledge bases, where hundreds of joins may be required. The second problem with the traditional approaches is that, al-beit effective in their specific domain, it is not clear whether they can be generalized to different scenarios (e.g. parallel evalua-tion) since they lack a formal model to define the assumptions and critical factors on which their valiclity depends. This paper