An Extended Disjunctive Normal Form Approach for Optimizing Recursive Logic Queries in Loosely Coupled Environments
Kyu-Young Whang, Shamkant B. Navathe · Very Large Data Bases · 1987
We present an approach to processing logic queries in loosely coupled environments. We emphasize the importance of the loose coupling technique as a practkal solution to provide deductive capabiities to existing DBMS+especially when an efficient access to a very large database is required in the. process of inferencing. We propose the Extended Disjunctive Normal Form (EDNF) as the basis of our approach. The EDNF is an extension of the disjunctive normal form of relational algebra expressions so as to include recursion. The EDNF is well suited for a loosely coupled environment, where an existing DBMS and optimiition can be fully exploited. It also serves as a clear, graphical characterixation of various recursions that can occur in logic queries. We first present the basic form of the EDNF and then use it as a building block to process a more general class of queries. We extend valid usage of Clark% negation-as-failure evaluation technique to incorporate negation for most practical situations. We also propose new criteria for safety and termination in the presence of negation. To the extent of the authors’ knowledge, optimixation in loosely coupled environments has not been seriously addressed in previous research. We believe our technique provides significant progress in this dhection.