Browse Prior Art Database

Extended Disjunctive Normal Form for Efficient Processing of Re- Cursive Logic Queries

IP.com Disclosure Number: IPCOM000039517D
Original Publication Date: 1987-Jun-01
Included in the Prior Art Database: 2005-Feb-01
Document File: 5 page(s) / 62K

Publishing Venue

IBM

Related People

Brady, S: AUTHOR [+2]

Abstract

Described in this article is the Extended Disjunctive Normal Form (EDNF) for efficiently processing a large class of logic queries. This class encompasses all the logic queries in function-free Horn-clause logic having recursions involving the Query goal. EDNF minimizes the need to create temporary tables that contain the intermediate results. It also eliminates the arbitrary processing structure imposed by the user-written rules. This makes it possible for the optimizer to search through alternative query processing strategies and choose the best one. Since the EDNF is in a form most amenable to database query optimization, this technique is especially useful in a loosely-coupled environment in which the existing database system takes care of data retrieval.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 30% of the total text.

Page 1 of 5

Extended Disjunctive Normal Form for Efficient Processing of Re- Cursive Logic Queries

Described in this article is the Extended Disjunctive Normal Form (EDNF) for efficiently processing a large class of logic queries. This class encompasses all the logic queries in function-free Horn-clause logic having recursions involving the Query goal. EDNF minimizes the need to create temporary tables that contain the intermediate results. It also eliminates the arbitrary processing structure imposed by the user-written rules. This makes it possible for the optimizer to search through alternative query processing strategies and choose the best one. Since the EDNF is in a form most amenable to database query optimization, this technique is especially useful in a loosely-coupled environment in which the existing database system takes care of data retrieval.

(Image Omitted)

Good performance of inference engines is essential in expert systems that handle large numbers of rules and facts. Function-free Horn- clause logic queries differentiate themselves from conventional database queries in that they allow recursion. Interpretive processing is convenient to handle recursion, but only with sacrifice in performance. Recently, Ullman
[*] proposed a data structure and algorithm to capture the class of logic queries in Function-free Horn-clause logic. However, the proposed method is inherently inefficient because (1) it requires creation of many temporary tables unnecessarily, and (2) the structure of the query representation (data structure) prohibits optimization of the query. The creation of temporary tables not only wastes CPU and storage resources, but also degrades performance because joining the temporary tables in main memory and the tables in the database system is a very expensive operation in a loosely-coupled system. A loosely-coupled system is defined as one in which the inference engine and the database system are two separate systems that communicate with each other. On the other hand, we define a system that integrates inference capability and data retrieval/manipulation capability as a tightly-coupled system. Even in a tightly-coupled system, temporary tables must be created only when it is beneficial to improving the performance. However, this decision has to be made by the query optimizer, rather than dictated by the structure of the query representation. In Ullman's method, the temporary tables are created and the query processed according to the data structure representing the query. This data structure, in turn, is imposed by the structure of the rules that the users write in the system before issuing the query. In the following, the representation of logic queries is transformed into a normal form representation (EDNF). The algorithm to process the query based on the EDNF, as well as the algorithm to obtain the EDNF given a query, is subsequently described. First, the data structure program graph will be defined. The program gra...