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 intelligent algorithm to
solve the generalized fully 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
techniques.
