A heuristic multiprocessor approach in computing the fully restricted transitive closure of a database relation

Author

Toptsis, Anestis A.

Author_Institution

Dept. of Comput. Sci. & Math., York Univ., Toronto, Ont., Canada

fYear

1993

fDate

1-5 Mar 1993

Firstpage

10

Lastpage

17

Abstract

Transitive closure is one of the most important operations in deductive database systems. The author presents the algorithm 2-PBFRTC which computes the fully restricted transitive closure of a database relation with the help of heuristics. In the performance evaluation of 2-PBFRTC it is established that the incorporation of heuristics produces drastic improvement over the use of no heuristics. The algorithm N-PBFRTC is outlined as a generalization of 2-PBFRTC. Like 2-PBFRTC, N-PBFRTC uses a heuristic function to achieve quick path establishment. Unlike 2-PBFRTC, N-PBFRTC is fully scalable, in the sense that it is capable of employing any number of processors to compute the closure

Keywords

database theory; deductive databases; multiprocessing systems; relational databases; software performance evaluation; 2-PBFRTC; N-PBFRTC; database relation; deductive database systems; fully restricted transitive closure; fully scalable; generalization; heuristic multiprocessor approach; heuristics; performance evaluation; quick path establishment; Artificial intelligence; Computer science; Concurrent computing; Deductive databases; Educational institutions; Employment; Mathematics; Parallel processing; Prototypes; Relational databases;

fLanguage

English

Publisher

ieee

Conference_Titel

Artificial Intelligence for Applications, 1993. Proceedings., Ninth Conference on

Conference_Location

Orlando, FL

Print_ISBN

0-8186-3840-0

Type

conf

DOI

10.1109/CAIA.1993.366667

Filename

366667