Efficient Algorithms and Performance Results for Multi-User Knowledge Bases

IJCAI 1995

TL;DR

This paper introduces the Dynamic Directed Graph (DDG) policy, a novel concurrency control mechanism designed to improve transaction throughput in large, shared knowledge bases. By leveraging the semantic structure of knowledge bases, DDG allows for more efficient lock release compared to traditional database methods like Two-Phase Locking (2PL), leading to significant performance gains, especially for long transactions.

What Problem Does This Paper Address?

As knowledge bases grow to contain millions of facts, managing concurrent access by multiple users becomes a critical challenge. Traditional database concurrency control mechanisms, like Two-Phase Locking (2PL), are often too conservative for the complex, long-running transactions common in knowledge bases (e.g., inference or truth maintenance). These long transactions can lock large portions of the knowledge base, severely limiting concurrency and throughput. While some graph-based concurrency control methods exist (like the DAG policy), they typically assume acyclic structures and static schemas, which don't hold for knowledge bases. This paper addresses the need for a concurrency control mechanism that can handle the dynamic, cyclic nature of knowledge bases while still optimizing transaction throughput.

Methods

The core contribution is the Dynamic Directed Graph (DDG) policy. Unlike 2PL, which holds locks until a transaction's "locked point," DDG allows for earlier lock release by exploiting the semantic structure of the knowledge base, represented as a directed graph. Key aspects of the DDG policy include:

  • Graph Representation: Knowledge bases are modeled as directed graphs where nodes represent objects and edges represent semantic relationships.
  • Locking Rules: Transactions acquire locks (shared or exclusive) on nodes. Crucially, DDG defines rules (L1-L5) that allow transactions to lock nodes within strongly connected components (SCCs) together and to release locks earlier than in 2PL, provided certain conditions related to predecessors and successors are met.
  • Dominator and SCC Awareness: The policy relies on identifying dominators (nodes that lie on all paths from the root to a set of nodes) and strongly connected components (SCCs) within the knowledge base graph. This information helps determine when locks can be released.
  • Implementation: The DDG policy was implemented within the DeNet simulation environment. This involved developing algorithms for computing and incrementally maintaining dominator trees and SCCs, which are crucial for enforcing the locking rules.
  • Adaptive Scheme: The authors also propose an adaptive scheme that can switch between 2PL and DDG based on workload characteristics (specifically, the write probability of transactions) to achieve consistently better performance.

Datasets

The evaluation of the DDG policy was performed using a simulated knowledge base derived from the Advanced Process Analysis and Control System (APACS) application. This application involves objects like boilers, valves, and alarms, organized into classes and subclasses with various semantic relationships. The knowledge base was represented as a directed graph with 2821 nodes. The authors also considered two other knowledge bases: Wines (a description logic knowledge base) and Tove (a knowledge base developed at the University of Toronto).

Key Insights and Ideas

  • Semantic Structure is Key: The paper strongly advocates for leveraging the rich semantic structure of knowledge bases to improve concurrency control, moving beyond generic database techniques.
  • Long Transactions are the Bottleneck: The primary motivation is to address the performance issues caused by long transactions, which are inherent in knowledge base operations like inference.
  • Early Lock Release is Achievable: DDG demonstrates that it's possible to allow transactions to release locks before their "locked point" without sacrificing serializability, by carefully considering the graph structure.
  • Cycles and Updates are Handled: Unlike simpler DAG policies, DDG is designed to handle cycles in the knowledge base graph and dynamic updates.
  • Traversal Strategy Matters: The choice of traversal strategy (e.g., Depth-First vs. Breadth-First) significantly impacts performance in conjunction with the concurrency control policy. DFT was found to be more desirable with DDG.
  • Knowledge Base Structure Influences Performance: Metrics like fanin, fanout, and depth factor of the knowledge base graph can predict how well DDG will perform compared to 2PL. Highly structured graphs (tree-like, low fanin/fanout) are more amenable to DDG's benefits.

Key Results

  • Significant Improvement for Long Transactions: The DDG policy showed considerable improvement in response time for Class 2 transactions (short, lookup/update) when Class 1 transactions (long, traversal) performed updates. This improvement could be as high as 50%.
  • DFT Outperforms BFT: For Class 1 transactions using the DDG policy, Depth-First Traversal (DFT) consistently yielded better response times for Class 2 transactions compared to Breadth-First Traversal (BFT).
  • DDG vs. 2PL: When Class 1 transactions were read-only, DDG's performance was comparable to 2PL. However, when Class 1 transactions performed updates, DDG significantly outperformed 2PL, especially at lower multiprogramming levels.
  • Adaptive Scheme Benefits: An adaptive scheme that switches between 2PL and DDG based on workload consistently performed better than using 2PL alone.
  • Implementation Complexity: While DDG is more complex to implement than 2PL (requiring more lines of code), the performance gains were shown to outweigh the added overhead in their simulations.

Limitations and Future Work

  • Implementation Complexity: The authors acknowledge that DDG is more complex to implement than 2PL, requiring a greater implementation effort. The trade-off between complexity and performance needs to be evaluated by implementors.
  • Knowledge Base Structure Dependency: The performance benefits of DDG are sensitive to the structure of the knowledge base graph. Highly structured graphs are more advantageous. The paper suggests that pre-computing all subsumption relationships might reduce the benefits of DDG by creating large fanin/fanout.
  • Future Work: The authors mention that their current work addresses the issue of fault-tolerance for the DDG policy. They also emphasize the importance of research at the intersection of knowledge bases and database systems for future cooperative information systems.

Summary updated

BibTeX
@inproceedings{1995efficient,
  title = {{Efficient Algorithms and Performance Results for Multi-User Knowledge Bases}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1995},
}

Loading related content...

Figure