Title :
New transitive closure algorithm for recursive query processing in deductive databases
Author :
Toroslu, I.H. ; Qadah, G.Z.
Author_Institution :
Dept. of Electron. Eng. & Comput. Sci., Northwestern Univ., Evanston, IL, USA
Abstract :
An algorithm suitable for the full transitive closure problem, which is used to solve uninstantiated recursive queries in deductive databases, is presented. In this algorithm there are two phases. In the first phase a general graph is condensed into an acyclic graph and at the same time a special sparse matrix is formed from the acyclic graph. The second phase is the main one, where all of the page I/O operations are minimized. Simulation is used to study the performance of this algorithm and compare it with that of previous algorithms
Keywords :
database theory; deductive databases; query processing; acyclic graph; deductive databases; page I/O operations; recursive query processing; sparse matrix; transitive closure algorithm; uninstantiated recursive queries; Database systems; Deductive databases; Intelligent systems; Iterative algorithms; Logic; Postal services; Query processing; Sparse matrices; Tree graphs;
Conference_Titel :
Tools with Artificial Intelligence, 1992. TAI '92, Proceedings., Fourth International Conference on
Conference_Location :
Arlington, VA
Print_ISBN :
0-8186-2905-3
DOI :
10.1109/TAI.1992.246414
