Transaction synchronization in knowledge bases: concepts, realization and quantitative evaluation
Vinay K. Chaudhri, John Mylopoulos, Vassos Madzilacos · 1995
Large knowledge bases that are intended for applications such as CAD, corporate repositories or process control will have to be shared by multiple users. For these systems to scale up, to give acceptable performance and to exhibit consistent behavior, it is mandatory to synchronize user transactions using a concurrency control algorithm. The transactions in knowledge bases often access a large number of entities and perform complex inferences that may last for a long period of time. In such a situation, using conventional concurrency control methods, which require a transaction to hold its locks until it has acquired all the locks it will ever need, do not lead to good performance. This thesis examines the problem of concurrency control for such long transactions in a knowledge base setting. Using a directed graph as a general model of a knowledge base, we develop an algo-rithm, called the Dynamic Directed Graph (DDG) policy, that allows release of locks by a transaction before it has acquired all the locks that it will ever need. Furthermore, it deals with a knowledge base whose graph may contain cycles and may receive insertions and deletions of nodes and edges. We develop a theory of correctness for schedules in such