TL;DR
This paper tackles the scalability problem of frame-based knowledge representation systems (FRS) by integrating them with a database management system (DBMS). They demonstrate that this approach allows FRSs to handle large knowledge bases (KBs) and support concurrent multi-user access, overcoming limitations of traditional in-memory systems.
What Problem Does This Paper Address?
Artificial Intelligence (AI) has long used frame-based knowledge representation systems (FRS) to model information. These systems offer powerful features like inference, classification, and inheritance, which are superior to conventional database systems in many ways. However, despite decades of research and numerous implementations, FRSs have seen limited adoption in general computing practice. The authors hypothesize that this is primarily due to engineering limitations: FRSs struggle to scale to large knowledge bases (KBs) due to slow storage and retrieval, and they lack support for concurrent multi-user access to shared KBs. This prevents FRSs from being practical for anything beyond small-scale applications.
Methods
The core innovation is a storage subsystem that "submerges" a DBMS within an FRS. This subsystem is designed to be transparent to the FRS user. Key aspects of their approach include:
- Incremental Loading: Frames are loaded from the DBMS into the FRS on demand, similar to how operating systems handle page faults. This avoids loading the entire KB into memory at once.
- Incremental Saving: Only updated frames are saved back to the DBMS, reducing the overhead of save operations.
- Generic Schema: The authors designed a generic DBMS schema that can accommodate any FRS information without requiring users to understand or design a specific DBMS schema for each new KB.
- EXODUS Storage Manager: Initially, they experimented with the EXODUS extensible storage management system, a flexible, low-level system. Later, they opted for a commercial relational DBMS (RDBMS) due to its ease of use and the minimal performance difference observed.
- Frame Faulting and Stub Management: When a frame is not in memory (a "frame fault"), the system retrieves it from the DBMS. To handle inter-frame references efficiently, they employ "stub objects" as placeholders for frames not yet loaded, which are later replaced when the actual frame is faulted in.
- Prefetching: To further improve performance, they developed a prefetching mechanism that anticipates future frame needs based on relationships like subconcepts and slot-fillers. This involves a multi-process architecture (DR and FD processes) to parallelize data retrieval and frame definition.
Datasets
The experiments used synthetically generated knowledge bases (KBs) with varying numbers of instances (500 to 5000). These KBs were designed to mimic the characteristics of the SOCAP (transportation-planning) KB, which was driving their work. They also used a random KB for some experiments.
Key Insights and Ideas
- Engineering is Key: The paper strongly argues that the lack of robust engineering (scalability, concurrency) has been a major bottleneck for FRS adoption, more so than theoretical limitations.
- DBMS as an Enabler: Integrating a DBMS as a transparent storage layer is a viable and effective strategy for overcoming FRS scalability issues, combining the strengths of both worlds.
- Demand-Driven Loading is Efficient: Loading frames only when needed (demand faulting) significantly improves performance for large KBs, especially when users access only a fraction of the KB.
- Prefetching Offers Potential: While not fully evaluated, prefetching shows promise for further performance gains, particularly by leveraging idle system time and reducing query overhead.
- RDBMS vs. EXODUS: While EXODUS offered flexibility, the practical advantages of a commercial RDBMS (ease of use, SQL interface) made it the preferred choice for future work, despite minimal performance differences in their initial tests.
Key Results
- Linear Scalability: The storage subsystem achieves linear time complexity with respect to the number of frames referenced for loading and the number of frames updated for saving.
- Performance Comparison:
- For THEO, loading N instances from the DBMS was 5-8 times slower than loading from flat files.
- For LOOM (which involves classification), loading was 3-4 times slower than flat files.
- The DBMS approach is competitive with flat files when users access up to 15% of frames in THEO or 30% in LOOM (this threshold improved to 70% with later RDBMS optimizations).
- Saving Performance: Saving updated frames to the EXODUS storage manager was about 7 times slower than saving to flat files, but the DBMS approach was faster for saving when less than 15% of the KB was changed.
- Prefetching Benefits: Fetching frames in batches (10-40 frames) reduced the time per frame by half compared to individual fetches. Prefetching is beneficial if more than half of the prefetched frames are actually referenced.
Limitations and Future Work
- Concurrency Control: The current system provides uncoordinated multi-user access. Future work will focus on developing mechanisms to control multi-user access to shared KBs.
- Virtual Memory Limitation: The current system assumes KBs can fit in virtual memory. Future work aims to remove this restriction.
- Prefetching Evaluation: The evaluation of the prefetching mechanism is ongoing and not yet complete.
- Slot-Based Schema for Queries: While the frame-based schema is good for faulting, a slot-based schema is needed for efficient querying. The authors suggest a hybrid approach where only queried slots are stored in a slot-based schema for better query performance.
- DBMS Choice: While EXODUS was used for experiments, the authors decided to use an RDBMS for future work due to its ease of use, despite minimal performance differences in their initial tests. They also note that recent RDBMS optimizations have significantly improved its performance.
Summary updated