The author presents an algorithm for matching queries against a database stored as a semantic network (concepts represented as nodes, joined by relationships represented as arcs). The query is also a net, some of whose nodes are or may be variables. Its processing requires solving the subgraph isomorphism problem, some varieties of which are NP-complete. To speed up the matching, the author transforms the query to an Eulerian graph and then to a linear template that traces an Eulerian path through the transformed query. Each node of the network to be searched becomes an active process that can receive some suffix of the template. When a node receives a template, it can do one of three things: (1) signal “failure” to the sender if it does not match the first node or has no adjacent arc matching the first arc; (2) signal “success” if it matches and is the last node in the template; or (3) remove the first node and arc from the template and send copies of the rest along its adjacent arcs that match the first arc in the template, notifying the sender of the success or failure of each of these efforts.

The algorithm is a straightforward and promising way to expedite one application of semantic networks by implementing them as dataflow machines. Two questions that are not addressed in the brief presentation will be of interest to potential users of the algorithm:

• (1) How can a dataflow architecture enhance operations other than query retrieval on semantic networks? These networks are frequently used for tasks such as concept classification (in the KL-ONE tradition) or reasoning by association (as in Quillian’s pioneering work [1]), as well as for information retrieval. The feasibility of building such nets as dataflow structures depends on the ability of the implementation to support a broad repertoire of techniques, not just retrieval.

• (2) What are the complexity characteristics of the algorithm? Query processing in network databases is notorious for its combinatorial problems. This approach appears to relieve these problems. Once the query becomes a linear template, processing time on a machine that allocates a single processor to each node in the database will be linear in the number of nodes in the transformed query. The dependence of the search time on the connectivity of the network being searched is more involved, though, as is the complexity of the algorithm for transforming a query into a linear template. Superficially, both appear to be tractable, but a detailed exposition would be helpful