An Efficient Algorithm for the Generalized Partially Instantiated Same Generation Query in Deductive

An Efficient Algorithm for the Generalized Partially Instantiated Same Generation Query in Deductive Databases

Nabil Arman

Palestine Polytechnic University, Palestine

 Abstract: The expressive power and intelligence of traditional database systems can be improved by recursion. Using recursion, relational database systems are extended into knowledge-base systems (deductive database systems). Linear recursion is the most frequently found type of recursion in deductive databases. In this paper, an algorithm to solve the generalized partially instantiated form of the same generation query in deductive databases is presented. The algorithm uses special data structures, namely, a special matrix that stores paths from roots of the graph representing a two-attribute normalized database relation to all nodes reachable from these roots, and a reverse matrix that stores paths from any node to all roots related to that node. Using simulation, this paper also studies the performance of the algorithm and compares that with the standard depth-first search based algorithms. 

Keywords: Deductive databases, linear recursive rules, same generation query. 

Received April 28, 2003; accepted July 22, 2003

Full Text

                                          

Read 8736 times Last modified on Thursday, 23 June 2011 04:29
Share
Top
We use cookies to improve our website. By continuing to use this website, you are giving consent to cookies being used. More details…