A Data-Driven Model for a Subset of Logic Programming

Abstract

There is a direct correspondence between semantic networks and a subset of logic programs, restricted only to binary predicates. The advantage of the latter is that it can describe not only the nodes and arcs comprising a semantic net, but also the data-retrieval operations applied to such nets. The main objective of this paper is to present a data-driven model of computation that permits this subset of logic programs to be executed on a highly parallel computer architecture. We demonstrate how logic programs may be converted into collections of data-flow graphs in which resolution is viewed as a process of finding matches between certain graph templates and portions of the data-flow graphs. This graph fitting process is carried out by messages propagating asynchronously through the data-flow graph; thus computation is entirely data driven, without the need for any centralized control and centralized memory. This permits a potentially large number of independent processing elements to cooperate in solving a given query.