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

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.