A Net Structure Based Relational Question Answerer: Description and Examples

Stuart C. Shapiro, George H. Woodmansee

Published in 1969, this paper introduces SAMENLAQ II, an early and influential question-answering system that represents a significant step toward what we now call Knowledge Graphs. Developed at the University of Wisconsin, the system explores how complex reasoning can emerge from a simple, generalized memory structure based on binary relations.

The Problem: Domain-Specific Brittleness

In the late 1960s, most "intelligent" systems were brittle and domain-specific. If a system needed to understand geography, researchers wrote geography-specific code; if it needed to handle logic, they wrote logic code. Stuart Shapiro and George Woodmansee sought to build a general-purpose system. Their core hypothesis was that "intelligence" should reside in the organization of the data (the memory structure) rather than in the complexity of the processing routines (the executive). They aimed to create a system where domain-specific instructions could be entered into memory as data, allowing the system to "learn" how to reason about new topics on the fly.

Methods: The Net Structure

SAMENLAQ II (written in SNOBOL3) uses a Net Structure—a directed graph—to represent knowledge. The system's executive logic, illustrated in Figure 1, categorizes input into statements, questions, or requests to determine the appropriate processing path.

Flowchart of the SAMENLAQ II executive program

Key components of this architecture include:

  • Binary Relations: All input follows the form $x R y$ (e.g., BOSTON EAST.OF WORCESTER).
  • Relations as Nodes: Crucially, the labels on the edges (the relations) are also nodes in the net. This allows the system to store information about relations, such as whether they are transitive or symmetric.
  • Converse Storage: Every statement $x R y$ is automatically stored as $y R(CNV) x$, ensuring all information about an entity is reachable regardless of its position in a sentence.
  • The IMPLBY (Implied By) Operator: This is the system’s primary engine for inference. Users can define a relation using others (e.g., SOUTH.OF IMPLBY NORTH.OF(CNV)). The system uses these as substitution rules during its search process.
  • Complex Relations: The system supports "relative products" (path-following) and "node restrictions" (filtering results based on properties). Figure 2 shows the syntax for such a complex relational expression, demonstrating how the system can navigate sophisticated queries.
Example of a complex relational expression in SAMENLAQ II

Datasets and Evaluation

The authors evaluated the system using several hand-crafted "micro-worlds":

  • Geography: Facts about cities in New York and Massachusetts.
  • SIR Subdialogues: Replicating the logic of Raphael’s Semantic Information Retriever (handling subsets, ownership, and part-whole relations).
  • Census & Flight Data: A database of cities, populations, and airline flight connections.
  • Logic & Set Theory: Axioms for Modus Ponens and set membership.
  • The Missionary-Cannibal Problem: Representing the puzzle as a state-transition graph.

Key Insights and Results

By treating relations as nodes, the authors blurred the line between data and logic. A rule like "transitivity" isn't a hard-coded function; it's just another path in the graph that the search routine can follow. This allowed for recursive reasoning, such as defining arithmetic properties recursively.

The system demonstrated qualitative success across diverse tasks:

  • Deduction: It inferred that a "nostril" is part of a "professor" by traversing the chain: nostril → nose → person → teacher → professor.
  • Problem Solving: It solved the Missionary-Cannibal puzzle by finding a path from the initial state node to the goal state node.
  • Concept Formation: The system could "induce" complex definitions for new concepts based on shared properties in the graph.

Limitations and Future Work

Despite its versatility, SAMENLAQ II faced the "threat of exponential growth" due to its exhaustive search method. The authors suggested that future systems would require heuristic search techniques. Additionally, the system was limited to binary relations ($x R y$) and lacked explicit variables for universal quantification. These limitations led to the development of a successor system, MENS, designed to handle n-ary relations and treat entire statements as nodes.

Summary updated

BibTeX
@inproceedings{shapiro1969net,
  author = {Stuart C. Shapiro and George H. Woodmansee},
  title = {{A Net Structure Based Relational Question Answerer: Description and Examples}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1969},
}
Figure