Representing Databases in Frames

Ey-Chih ChowAAAI 1987

Introduction

In the late 1980s, the development of expert systems highlighted a significant architectural challenge: the "impedance mismatch" between structured relational databases and frame-based AI toolkits. While relational databases link data through symbolic keys (e.g., a Dealer ID), frame-based systems represent concepts as objects with "slots" that often use direct memory pointers for relationships. This paper, published by Hewlett-Packard Laboratories in 1987, investigates the performance trade-offs of different data representation strategies when importing relational data into an AI environment.

Methodology

The study evaluates three distinct representation "schemata" within the HP-RL (Hewlett-Packard Representation Language) toolkit:

  1. Schema #1 (Pointers Only): Relationships are modeled as direct memory links between frames, the native approach for AI reasoning.
  2. Schema #2 (Keys Only): Relationships use symbolic names or IDs, mimicking the structure of a standard relational database.
  3. Schema #3 (Redundant): A hybrid approach using both pointers and keys.

These models were tested using the Fasttrack benchmark, which simulates a sales-record system. The dataset consists of 500 dealers, 100 products, 1,500 orders, 1,000 outlets, and 4,500 competitors.

The Fasttrack benchmark schema (Fig. 2a) and its relational mappings (Fig. 2b).

The performance of these frame-based approaches was also compared against Iris, a contemporary relational/object-oriented database system, to identify the strengths and weaknesses of specialized database engines versus general-purpose AI toolkits.

Performance Analysis

The results revealed a stark contrast in query performance based on the representation method. Representing relationships as pointers (Schema #1) significantly accelerated "join" operations because the system could follow memory addresses rather than searching for matching keys.

Query execution times (in seconds) for HP-RL schemata versus the Iris database across various benchmark queries.

As shown in the data, Schema #1 was significantly faster than Schema #2 for complex queries, with some specific joins showing up to a 60-fold improvement. However, this speed comes with a "memory tax"; pointer-based databases were approximately 20% larger than those using keys alone. Furthermore, the frame-based system excelled at simple, in-memory lookups (e.g., 0.08s for HP-RL vs. 3.8s for Iris), demonstrating the efficiency of direct pointer dereferencing.

Challenges in Frame-Based Systems

Despite the pointer advantage, frame systems faced several bottlenecks:

  • Loading Overhead: Schema #2 (keys) was faster to load because it avoided the creation of "partial frames"—placeholders created when a frame points to another that hasn't been loaded yet.
  • Garbage Collection: Complex joins in HP-RL generated numerous temporary frames, triggering frequent garbage collection cycles. This often resulted in the second execution of a query being slower than the first due to memory management overhead.
  • Scalability: For massive joins with high data redundancy, the Iris database outperformed the frame system (e.g., 57s vs. ~600s for query q5) due to its superior buffer management and optimized execution engine.

Conclusion

The study concludes that neither system is a universal solution. Instead, it proposes a hybrid architecture. In this model, a robust relational database like Iris serves as the primary store for large-scale data and complex joins. Specific subsets of data are then transformed and "cached" into a frame-based system using pointers for high-speed, in-memory reasoning during expert system sessions. Future research is needed to address data consistency and update propagation between these two layers.

Summary updated

BibTeX
@inproceedings{chow1987representing,
  author = {Ey-Chih Chow},
  title = {{Representing Databases in Frames}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1987},
}
Figure