A Graph-Oriented Knowledge Representation and Unification Technique for Automatically Selecting and Invoking Software Functions

William Kaemmerer, James LarsonAAAI 1986

Abstract

This paper introduces a system designed to act as a "virtual information system," enabling users to perform declarative queries across heterogeneous databases and software modules. By modeling both data and functions as conceptual graphs, the system employs heuristic search and graph unification to automatically identify and sequence the necessary "server-units" to fulfill complex requests. Experimental results on a parts inventory domain demonstrate that the system can efficiently formulate execution plans in seconds, effectively bridging the gap between high-level user goals and low-level procedural execution.

Introduction: The Formulation Problem

In the mid-1980s, the proliferation of computerized information systems created a significant challenge for end-users. Professionals, such as bank loan officers, were often required to manually navigate multiple disparate sources—ranging from credit records and book value databases to standalone amortization software. This environment forced users to become "procedural experts," requiring them to know exactly where data resided and how to manually pipe information between different programs.

The authors address this "formulation problem" by proposing a framework that bridges the gap between a user’s high-level, declarative request (the "what") and the specific sequence of software invocations (the "how") required to fulfill it across a heterogeneous environment of databases and application programs.

Methodology

Unified Knowledge Representation

The core of the proposed system is the treatment of every data source and software function as a "server-unit." A critical observation made by the authors is that an invokable function can be viewed as a "virtual relation" between its inputs and outputs. By adopting conceptual graphs (inspired by John Sowa’s work), the entire capability space of a system can be represented uniformly, whether the underlying resource is a static database table or a dynamic procedural function.

When a user submits a request, it is encoded as a graph. The system then attempts to "cover" this request graph by unifying it with various server-unit graphs. This unification process involves substituting variables and merging nodes to find a valid match.

To manage the computational complexity of searching the power set of all available server-units, the authors implemented a two-step heuristic approach:

  1. Pruning: The system immediately eliminates server-units that share no predicates with the request.
  2. Best-First Search: A heuristic function ($H$) is employed to balance the number of server-units used against the number of request nodes left uncovered.
  3. Dataflow Validation: Once a candidate set is identified, the system ensures the units form a valid, acyclic dataflow graph where all mandatory inputs are satisfied by known variables or previous outputs.

Experimental Evaluation

The prototype was evaluated using a custom-built domain model for parts inventory and equipment maintenance. The capability space consisted of 17 server-units representing three separate databases and three application programs. The system was implemented in Zetalisp on a Symbolics 3600 Lisp machine, which communicated with personal computers hosting the actual databases.

Key Results

The prototype demonstrated that the approach was computationally tractable for real-world use cases. For typical requests, the pruning step removed more than 50% of the search space immediately. As shown in the performance data, formulating a plan for complex queries—such as determining the day of the week a part was replaced—typically took between 1 and 3 seconds.

Performance metrics for various information requests in the sample domain.

The system successfully generated sequences for queries requiring multiple joins and function calls, such as linking a parts database to a date-conversion utility, effectively discovering "hidden database joins" that the user did not explicitly mention.

Discussion and Future Work

The "functions as data" paradigm allows the system to use standard logic-based retrieval techniques to handle procedural code. By transforming a static description of a goal into a sequenced execution plan, the system performs a form of automatic programming.

However, several limitations remain. The current implementation is restricted to "select/project/join" type requests (conjunctions) and does not yet handle disjunctions, aggregations, or recursion. Furthermore, the algorithm focuses on finding a valid sequence rather than the most computationally efficient one. Future work will focus on optimizing these execution plans and developing a more user-friendly, natural-language interface for non-technical users.

Summary updated

BibTeX
@inproceedings{kaemmerer1986graph,
  author = {William Kaemmerer and James Larson},
  title = {{A Graph-Oriented Knowledge Representation and Unification Technique for Automatically Selecting and Invoking Software Functions}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1986},
}
Figure