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. Deductive databases queries are
computationally intensive and lend themselves naturally
to parallelization to speed up the solution of such
queries. In this paper, a parallel 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 source nodes of
the graph representing a two-attribute normalized
database relation to all nodes reachable from these
source nodes, and a reverse matrix that stores paths
from any node to all source nodes related to that node.
