Efficient Algorithms and Performance Results for Multi-User Knowledge Bases
Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence. Knowledge Base Technology. Pages 759-766.
© 1995 International Joint Conferences on Artificial Intelligence
Abstract
The paper describes research efforts to develop efficient implementation techniques for large, shared knowledge bases, focusing on efficient concurrent access of large knowledge bases by multiple users. We present an algorithm , called the Dynamic Directed Graph policy, originally proposed in [Chaudhri et al., 1992], which allows efficient interleaved execution of transactions against a large knowledge base with the intent of optimizing transaction throughput. The implementation of the policy and experimental evaluation results are also presented and discussed . The paper concludes with discussion on lessons learnt from this research.
- [Agrawal and Abbadi, 1990] D. Agrawal and A. El Ab- badi. Locks with Constrained Sharing. In 9TH A CM Symposium on Principles of Database Systems, pages 85-93, April 1990.
- Agrawal et al., 1 987]
- Rakesh Agrawal, Michael J. Carey, and Miron Livny. Concurrency Control Per- formance Modeling: Alternatives and Implications. A CM Transactions on Database Systems, 12( 4) :609- 654, December 1987.
- [Ballou et al., 1988] Nat Ballou, Hong-Tai Chou, Jorge F. Garza, Won Kim, Charles Petrie, David Russinoff, Donald Steiner, and Darrell Woelk. Coupling an Expert System Shell With and Object-Oriented Database System. Journal of Object Oriented Programming, 1(2):12-21, 1988.
- [Bernstein et al., 1987] Philip A. Bernstein, Vassos Hadzilacos, and Nathan Goodman. Concurrency Con- trol and Recovery in Database Systems. Addison- Welssley Publishing Company, 1987.
- [Borgida and Patel-Schneider, 1994] Alex Borgida and Peter F. Patel-Schneider. A Semantics and Com- plete Algorithm for Subsumption in CLASSIC De- scription Logic. Journal of Artificial Intelligence Re- search, 1:277-308, 1994.
- [Carol!, 1988] M. D. Carol!. Data Flow Analysis via Dominator and Attribute Updates. Technical Report LCSR-TR-111, Rutgers University, May 1988.
- [Chaudhri et al., 1992] Vinay K. Chaudhri, Vassos Hadzilacos, and John Mylopoulos. Concurrency Con- trol for Knowledge Bases. In Proceedings of the Third International Conference on Knowledge Representa- tion and Reasoning, pages 762-773, 1992.
- [Chaudhri et al., 1994] Vinay K. Chaudhri, Vassos Hadzilacos, John Mylopoulos, and Ken Sevcik. Quan- titative Evaluation of a Transaction Facility for a Knowledge Base Management System. In Proceed- ings of the Third International Conference on Knowl- edge Management, pages 122-131, Gaithersberg, MD, 1994.
- [Chaudhri, 1995] Vinay K. Chaudhri. Transaction Syn- chronization in Knowledge Bases: Concepts, Realiza- tion and Quantitative Evaluation. PhD thesis, Uni- versity of Toronto, Toronto, January 1995.
- [Eswaran et al., 1976] K. Eswaran, J . Gray, R. Lorie, and I. Traiger. The Notions of Consistency and Pred- icate Locks in Database Systems. Communications of the ACM, 19(9):624-633, 1976.
- [Gray and Reuter, 1993] Jim Gray and Andreas Reuter. Transaction Processing: Concepts and Techniques.
- Guha and Lenat, 1. 994
- R. V. Guha and Douglas B. Lenat. Enabling Agents to Work Together . Commu- nications of the ACM, 37(7) :126-142, 1994.
- [Livny, 1990] Miron Livny. DeNeT User's Guide (Ver- sion 1.5) . Technical report, University of Wisconsin, 1990.
- [Mays et al., 1991] E. Mays, S. Lanka, B. Dionne, and R. Weida. A Persistent Store for Large Shared Knowl- edge Bases. IEEE Transactions on Knowledge and Data Engineering, 3(1):33-41, 1991.
- [Mylopoulos and Brodie, 1990] John Mylopoulos and Michael Brodie. Knowledge Bases and Databases: Current Trends and Future Directions. In Lecture Notes in Computer Science, Vol. 414: Information Systems and Artificial Intelligence: Integration As- pects, New York, 1990.
- [Mylopoulos et al., 1992] J . Mylopoulos, B. Kramer, H. Wang, M. Benjamin, Q. B. Chou, and S. Mensah . Expert System Applications in Process Control. In Proceedings of the International Symposium on Artifi- cial Intelligence in Materials Processing Applications, Edmonton, August 1992.
- [Patil et al., 1992] Ramesh Patil, Richard E. Fikes, Pe- ter F. Patel-Schneider, Don Mackay, Tim Finin, Thomas Gruber, and Robert Neches. The DARPA Knowledge Sharing Effort: Progress Report. In The Third International Conference on Principles of Knowledge Rep_resentation and Reasoning, pages 777- 788, Boston, MA, 1992.
- [Plexousakis, 1993] D. Plexousakis. Integrity Constraint and Rule Maintenance in Temporal Deductive Knowl- edge Bases. In Proceedings of the 19th International Conference on Very Large Databases, pages 146-157, Dublin, IR, August 1993.
- [Salem et al., 1994] Kenneth Salem, Hector Garcia- Molina, and Jeannie Shands. Altruistic Locking. ACM Transactions on Database Systems, 19(1) :117- 164, 1994.
- [Shasha, 1994] Dennis E. Shasha. Database Tuning - A Principled Approach. Prentice Hall, NJ, 1994.
- [Silberschatz and Kedem, 1980] A. Silberschatz and z. M. Kedem. Consistency in Hierarchical Database Systems. Journal of the Association for Computing Machinery, 27(1) :72-80, 1980.
- [Yannakakis, 1982] Mihalis Yannakakis. A Theory of Safe Locking Policies in Database Systems. Journal of the Association for Computing Machinery, 29(3):718- 740, July 1982.
References were extracted automatically from the PDF and may contain errors.
Full text extracted automatically from the PDF; figures, tables and equations may differ. The PDF is the version of record.
1 Problem Statement
Concurrent processing of user requests can lead to large speed ups in user response time as compared to process ing the requests of one user at a time [Gray and Reuter, 1993]. Arbitrary concurrency can, however, lead to in consistent information in the knowledge base and one must make sure that the concurrent executions are seri alizable [Bernstein et al., 1987] : interleaved execution of a set of transactions must be equivalent to some serial execution of the same collection of transactions in the sense that it leaves the knowledge base in the same state and returns the same answers to the users.
Most commercial database systems use locking-based algorithms to ensure serializability. The best known locking algorithm, two-phase locking (2PL) [Eswaran et al., 1976], works along the following lines. Associated with each data item is a distinct "lock" . A transac tion must acquire a lock on a data item before accessing it. While a transaction holds a lock on a data item no other transaction may access it . A transaction cannot acquire any additional locks once it has started releasing locks (hence the name "two-phase" locking). In a simple generalization of this model , the transactions may hold shared and exclusive locks on data items. The instant when a transaction has acquired all the locks that it will ever need is called its locked point.
Transactions in a knowledge base system often access large number of data items, for example, while inferenc ing over long rule chains. Such a transaction may po tentially access all the nodes that are descendants of the goal in the inference graph from which it begins execu tion. Similar long transactions are generated while per forming truth maintenance operations in a knowledge base. In such situations, 2PL implies that a transac tion will have to hold each lock until its locked point thereby locking most of the knowledge base for other users. Hence, concurrency is significantly reduced when running such "global" transactions. For this reason, our research has been directed towards the development of new methods that only hold a small number of locks at any one time, even for global transactions.
Interestingly, knowledge bases generally possess much richer internal structure (e.g., generalization and aggre gation hierarchies, deductive rules, temporal dimensions defined in terms of history or belief time, etc.) than that of traditional databases . Information about this struc ture can be potentially useful in allowing early release of locks . Indeed, a concurrency control algorithm does exist for databases that have a directed acyclic graph structure, and is accordingly called DAG policy [Silber schatz and Kedem, 1980; Yannakakis, 1982). Under the DAG policy, a transaction may begin execution by lock ing any item. Subsequently, it can lock an item if it has locked all the predecessors of that item in the past and is currently holding a lock on at least one of those parents . Moreover, under the DAG policy a transaction may only lock an item once. The DAG policy exploits the assumption that there are no cycles in the under lying structure and the structure does not undergo any change. Unfortunately, such a policy cannot be adopted for knowledge bases without modifications. The struc ture of a knowledge base is likely to contain cycles (e.g., the inference graph generated for a collection of recur sive rules) and will undergo change (e.g. , when rules are added or deleted) .
In summary, neither 2PL nor DAG policy is, by itself, appropriate for knowledge bases. 2PL is too conserva tive, thereby causing reduced concurrency, while DAG policy does not provide sufficient functionality. Accord ingly, we are proposing a new graph-based policy, the Dynamic Directed Graph policy (DDG) that can handle cycles and updates in the knowledge base and also allows release of locks before the locked point of a transaction, thereby promising better performance than 2PL.
2 The Dynamic Directed Graph Policy
The knowledge bases that we have in mind are assumed to support an object-oriented representational frame work with an assertional sub-language used for both deductive rules and constraints. Also, possibly, they might support facilities for representing special kinds of knowledge (for example, temporal knowledge, incom plete knowledge, etc.). A large class of knowledge bases can be represented in terms of such directed graphs, not only the ones based on semantic nets, frames but also description logics or even logics [Plexousakis, 1993; Borgida and Patel-Schneider, 1994). Therefore, for the purposes of concurrency control, a knowledge base is a directed graph G(V, E) , where V is a set of nodes (e.g., Employee), and E is a set of edges which are ordered pairs of nodes (e.g. , (Manager, Employee)).
We first define some properties of directed graphs that are necessary for specifying our algorithm. A root of a directed graph is a node that does not have any prede cessors . A directed graph is rooted if it has a unique root and there is a path from the root to every other node in the graph. A directed graph is connected, if the underly ing undirected graph is connected. A strongly connected component (SCC) G; of a directed graph G is a maximal set of nodes such that for each A, B E G;, there is a path from A to B. An SCC is non-trivial if it has more than one node. An entry point of an SCC, G;, is a node B such that there is an edge (B, A) in G, A isinG;, but B is not in G; . Thus, if a node is an SCC by itself, its entry points are simply its predecessors.
The dominator D of a set of nodes W is a node such that for each node A E W, either every path from the root to A passes through D or D lies on the same strongly connected component as A. Thus, in a rooted graph, the root dominates all the nodes in the graph including itself. All nodes on a strongly connected com ponent dominate each other.
The DDG policy has three types of rules. Prepro cessing rules convert an arbitrary graph to a rooted and connected graph. Locking rules specify how each trans action should acquire locks. Maintenance rules specify additional operations that must be executed by transac tions to keep the structure rooted and connected. The rest of the discussion in this section focuses on locking rules . A detailed description of the DDG algorithm ap pears elsewhere [Chaudhri, 1995).
A transaction may lock a node in shared or exclusive mode [Bernstein et al., 1987). Two transactions may simultaneously lock a node only if both lock it in shared mode. The locking rules are as follows:
Ll. Before a transaction T performs any INSERT, DELETE or WRITE operation on a node A (or an edge (A, B)), T has to lock A (both A and B) in exclusive mode . Before T performs a READ operation on a node A (an edge (A, B)) , it has to lock A (both A and B) in either mode .
L2. A node that is being inserted can be locked at any time.
L3. Each node can be locked by T at most once.
L4. The first lock obtained by T can be on any node. If the first node locked by T belongs to a non-trivial SCC, all nodes on that sec are locked together in the first step.
Subsequently,
L5. All nodes on an SCC are locked together if:
L5a. All entry points of that SCC in the present state of G have been locked by Tin past , and Tis now holding a lock on at least one of them, and
L5b. For every node A on this SCC that is a successor of an entry point, and every path A1 , . . . ,Ap,A,p;::: 1, in the present state of the underlying undirected graph of G, such that T has locked A1 (in any mode), and A2 , . .. , Ap in shared mode, T has not unlocked any of A1, ... , Ap so far.
As an example application of the DDG-SX policy con sider the knowledge base and the transactions shown in Figure 1. (LS and LX respectively denote the acquisition of lock in shared and exclusive mode , U denotes release of lock on a node and (U *) denotes the release of all the locks held by a transaction.) Tt begins by locking node 1 (locking rule 14) in shared mode and then locks node 2 in exclusive mode (locking rule 15) . It locks the nodes 3 and 4 which form a strongly connected compo nent in shared mode in one step (locking rule 15) . It is able to do so because the condition 15b is satisfied for each path from node 2 to node 3 and 4. Tt locks node 5 in exclusive mode and finishes execution. T2 begins by locking both nodes 3 and 4 (locking rule 14) and then locks node 5 and finishes execution. If Tt adds the edge (2, 5) (locking rule 11), then T2 will be unable to lock node 5 because in order to do that it must lock node 2 which is a predecessor of node 5 in the current state of the graph (locking rule 15a) . T2 must abort and start from node 2.
Figure 1: An Example Application of the DDG policy
Theorem: The DDG policy produces only serializable schedules [Chaudhri , 1995].
The DDG policy does not permit concurrency within cycles (see rule 15 above) suggesting that if a knowledge base contains cycles, concurrency will be reduced. We have a version of the DDG policy that permits concur rency within cycles [Chaudhri et al., 1992]. We adopted the above version , because the transactions in knowledge bases tend to access all the nodes on a cycle together , and therefore, the cycles are a natural unit of locking.
For a transaction to be able to satisfy locking rule 15 for all the nodes that it needs to lock, it has to begin by locking the dominator of all the nodes that it is going to access. This is not a contradiction to locking rule 14, which just says that to lock the first node, no other condition needs to be satisfied.
3 Implementation of the DDG Policy
The DDG policy has been implemented in the DeNet [1ivny, 1990] simulation environment . The implementa tion ideas that we present here are independent of any specific system.
There are two main issues in the implementation of the DDG policy. First, to enforce the rules of the lock ing policy, we need to compute and maintain information about several graph properties . Second, we need a mech anism to decide the order in which the locks should be acquired and released.
To enforce the locking rules , we need information on the dominator relationships and the strongly connected components within the knowledge base graph. In our implementation, the dominator tree of the knowledge base is computed at compile time using a bit vector al gorithm [Chaudhri, 1995]. Using this information, the dominator of the set of nodes in the transaction can be computed in time linear in the length of a transaction. The dominator information is maintained using an in cremental algorithm [Caroll , 1988]. The information on strongly connected components is computed at compile time using depth-first search. There was no algorithm available for incrementally maintaining information on strongly connected components as the knowledge base evolves, and therefore, we developed an algorithm for this purpose [Chaudhri , 1995].

Let us describe the order in which a transaction ac quires and releases locks . A transaction always begins by locking the dominator of all the nodes that it might access. The dominator is computed on the assumption that a transaction may access all the descendants of the first node on which it requests a lock. Subsequently, every time a lock is requested, the locking conditions are checked, and if not enough predecessors are locked (rule L5a), lock requests for them are issued recursively. Before a node A can be unlocked by a transaction T, following conditions must be satisfied:
Ul. A is no longer needed by T, and
U2. Releasing the lock on node A does not prevent the locking of any of its successors at a later stage in the execution ofT (as required by rule L5a) , and
U3. For every path A, At , .. . , Ap , B in the present state of the underlying undirected graph, such that A is locked (in any mode) , At , .. . , Ap are locked in shared mode, T intends to lock B in future, T must not unlock any of A, At , ... , Ap (by locking rule L5b) .
To implement U1, we require T to send a message to the lock manager when it has finished processing a node.
To implement U2 , we have to know how many of the descendants might be later locked by T . Moreover , of all the predecessors of a node A, only one has to be kept locked until T locks A. Therefore, we distinguish one of the predecessors that needs to be locked until all the successors have been locked, and associate with it the number of successors that are yet to be locked. Once the number of successors yet to be locked for a node becomes zero, U2 is satisfied.
To implement U3, we check all the undirected paths from A to all the nodes that T may lock in future . U3 needs to be checked only when T acquires an exclusive lock or when T locks a node none of whose descendants will be locked by it in future . The check can be made more efficient by observing that if U3 is not satisfied for a node A, it is also not satisfied for descendants of A, and therefore, the paths passing through them need not be checked.

4 Evaluation of the DDG Policy
Our performance model is similar to an earlier model [Agrawal et al., 1987] and has four components: a source, which generates transactions, a transaction manager, which models the execution of transactions, a concur rency control manager, which implements the details of a particular algorithm; and a resource manager, which models the CPU and I/0 resources of the database.
Performance of the DDG policy was studied on a knowledge base under development for industrial pro cess control [Mylopoulos et al., 1992]. The application is called Advanced Process Analysis and Control Sys tem (APACS) . The objects represented in the knowl edge base (boilers, valves, preheaters, alarms, etc.) are organized into a collection of classes, each with its own subclasses, instances and semantic relationships to other classes. There are several semantic relationships in this knowledge base. The isA relationship captures the class subclass relationship, the instanceD! relationship rep resents the instances of a class, and the linkedTo rela tionship stores how the components are linked to each other in the power plant.
For our experiments, we view this knowledge base as a directed graph. Each class and each instance is repre sented by a node. There are 2821 nodes in this graph. There is an edge between two nodes if they have some se mantic relationship. For example, there is an edge from node A to node B , if the object represented by A is a part of the object represented by node B.
The knowledge base receives two classes of transac tions. Class 1 transactions are long and traverse the knowledge base along one of its structural relationships. Class 2 transactions are short and look-up or update an attribute value and occasionally change the structural relationships in the knowledge base. The proportion of the transactions in Class. 1 was determined to be 27% with the remaining 73% being in Class 2.
Since there are several semantic relationships in the knowledge base, we can selectively use one or more of these as the graph to be used for concurrency control. Making a semantic relationship known to concurrency control gives it information on the entities to be accessed by transactions that traverse that relationship, but on the other hand, for transactions that do not traverse this relationship, it may mean locking more nodes than they actually require. We analyzed this tradeoff [Chaudhri, 1995] and concluded that for the APACS workload, using the graph defined by the union of isA and instanceOt relationships leads to the best performance, and there fore, used it as the graph with respect to which the lock ing rules of the DDG policy were applied.
In the APACS application, Class 1 transactions do not specify the traversal strategy that should be used, and therefore, one can choose a strategy that leads to bet ter performance. We considered two traversal strategies: depth-first traversal (DFT) and breadth-first traversal (BFT). In general, transactions using a DFT hold a lesser number of locks on average as compared to the average number of locks held while using a BFT. To quantify the difference, we show, in Figure 2, the per centage improvement in the Class 2 response times as obtained when Class 1 transactions use DFT as com pared to BFT. We do not show the improvement in Class 1 response t ime as it was found to be insignificant . The improvement is shown as a function of Multiprogram ming level of Class 1 transactions and the write prob ability. Multiprogramming level (MPL) is the number of transactions that are concurrently executing at any given time and can be controlled by the system admin istrator. Permitting too few active transactions (or a low MPL) may not exploit full benefits of concurrency and permitting too many active transactions (or a high MPL) may lead to excessive contention and degrada tion in user response time. Write probability is the pro portion of accesses performed by a transaction that are updates. If R(j)BFT and R(i)DFT are the mean re sponse times of transactions in the Class j then the per centage improvement of DFT over BFT is computed as (R(j)BFT- R(j)DFT )/ R(i)BFT * 100. We can see that, even at high write probabilities, by using DFT, Class 2 response times showed consistent improvement . This result shows that in a multi-user knowledge base envi ronment, while using the DDG policy, DFT is a more desirable traversal strategy than BFT.

In Figure 3, we plot the percentage improvement in response time of Class 2 transactions obtained by us ing the DDG policy as compared to 2PL. If R(j)zp£ and R(i)DDG are the mean response times of transac tions in class j, then the percentage improvement of the DDG policy over 2PL is computed as 100 x (R(j)zp£ - R(j)DDG )/ R(j)zp£ 0
The results for Class 2 transactions indicate that when Class 1 transactions are read only, the performance of the DDG policy is comparable to 2PL. When Class 1 transactions also perform some updates, the DDG pol icy can improve considerably (of the order of 50%) the response time of Class 2 transactions that are running concurrently. The results for Class 1 transactions are not shown here. We found that at low update probabilities there was slight degradation (about 10%) in Class 1 re sponse time by using the DDG policy and at high update probabilities there was no significant difference between the two algorithms. These results make sense, because when there are only shared locks in a transaction, the DDG policy cannot allow any release of locks before its locked point, but incurs extra overhead, and therefore, leads to a slight degradation in response time. On the other hand, if the Class 1 transactions are update intensive, they release locks before their locked point, and the extra overhead is more than offset by the increased concurrency obtained due to lock pre-release leading to a net improvement in Class 2 response time.
In Figure 3, we can observe that the improvements are smaller at high multiprogramming levels. At low multiprogramming levels (for example, at MPL=l), any release of locks by a transaction before its locked point contributes to the improvement in response time of con currently executing Class 2 transactions. At higher mul tiprogramming levels, this may not be necessarily true, because the lock released by a Class 1 transaction could be acquired by another Class 1 transaction giving no benefit to Class 2 transactions. As a result, we see greater improvements in the Class 2 response time at low multiprogramming levels of Class 1 as compared to improvements at high multiprogramming levels.
The overall system response time can be computed as the weighted sum of the individual class response times where class throughputs are used as weights. In the APACS workload the throughput of Class 2 (25 trans actions/second) is much higher than the throughput of Class 1 (approximately 0.4 transactions/second), and therefore, the behavior of Class 2 transactions dominates the overall response time. On computing the improve ments in the overall response time, we found that im provements were very close to the corresponding values for Class 2 response time as shown in Figure 3.
In view of the relative behavior of the two algorithms, we designed an adaptive scheme which can switch be tween 2PL and the DDG policy depending on the load conditions. Such a scheme uses 2PL at low write prob abilities and the DDG policy at high write probabili ties, thus giving the best of the two algorithms. Since simultaneously using the two algorithms may lead to non-serializable schedules the adaptive scheme uses a transition phase while switching from one algorithm to the other. While switching from 2PL to the DDG pol icy, transactions locked according to the DDG policy are forced to behave as two-phase locked transaction by delaying the release of lock until locked point. While switching from the DDG to 2PL, the adaptive scheme waits until all active transactions running under the DDG policy finish execution. This results in an algo rithm which is a hybrid of 2PL and the DDG policy and performs consistently better than a concurrency control algorithm that only uses 2PL.
Of course, an important consideration in the choice between the two algorithms is the relative complexity of the two algorithms. The DDG policy is more complex than 2PL, and therefore, its implementation requires a greater effort. For example, in our simulation, 2PL re quired approximately 1000 lines of code and the DDG policy required 3000 lines of code. Our simulations in corporate the cost of extra complexity by measurements of runtime overhead of the two algorithms and show that there is a net improvements in response times. Thus, the final choice between the DDG policy and 2PL has to be made by the implementor who has to evaluate whether the improvements showed above are worth the added complexity of the DDG policy.
5 Desired KB Graphs for Better Performance
Since the DDG policy exploits the semantic structure of a knowledge base, its performance is sensitive to the properties of the knowledge base graph. To understand this, consider the directed graphs shown in Figure 4, which have the same number of nodes. Suppose, that a transaction T performs traversal along each graph and locks all entities in exclusive mode. In case of G1 , once a node (1, 2 or 3) has been processed by T, lock on it has to be held until we have locked its only successor. In case of G2, lock on node 1 has to be held until we have locked all three successors (provided the transac tion needs to access all three of them) . Thus, in case of G1 , lock holding time on node 1 is likely to be lower as compared to lock holding time in case of G2. This effect can be captured by measuring the fanout of the graph. Furthermore, in G1 and G2, to lock a node which is not the first node locked by T, we need to lock only one other node, whereas in G3 , to lock node 4, we need to lock both nodes 2 and 3. In this respect, the structure of graph Ga is less desirable than G1 or G2. This effect can be captured by measuring the fanin and analyzing the dominator tree of the knowledge base.
We formalized above intuitions by defining fanin fac tor, fanout factor and depth factor . Fanin (fanout) factor is the ratio of the maximum fanin (fanout) to the knowl edge base size. Smaller the value of the fanin (fanout) ratio, greater are the benefits of using the DDG policy as compared to 2PL. (We had first defined fanin factor as the ratio of average fanin to the knowledge base size, but it was not as effective in discriminating between the knowledge base structures as compared to the definition proposed above.) Thus, a desirable ·graph for the DDG policy would be the one with fanin and fanout equal to 1 and an undesirable graph would be with fanin (or fanout) equal to n - 1 where n is the number of nodes in the graph. Depth factor measures the closeness of the knowledge base graph to a tree. Before we define depth factor, we need following definitions. The dominator tree of a graph G = (V, E) is a tree T = (V, E') such that (A, B) E E' if and only if A dominates B in G and no proper descendant of A in G satisfies this property. Let d(A, G) denote the length of the shortest path from the root of G to A. Then the depth factor of a knowledge base can be defined as follows:

If the knowledge base is a tree, the numerator is equal to zero, giving a depth factor equal to 1. A depth factor value of 1 is most desirable because then transactions lock exactly the same number of entities that they need. Closer the value of depth factor to 1, higher is the po tential for obtaining improvement in performance using the DDG policy.
As an example application of the above ideas, we considered two other knowledge bases in addition to APACS. The first of these, called Wines, is a description logic knowledge base developed at AT&T Bell Labs. The second knowledge base, called Tove, is a knowfedge base developed at University of Toronto by the Enterprise Integration group. For the APACS, Tove and Wines knowledge bases the values of fanout factor are respec tively, 0.09, 0.103 and 0.24, values offanin factors are re spectively, 0.0003, 0.0004 and 0.001 and values of depth factors are respectively 1.0, 0.975 and 0.887. Based on these metrics one would predict that the improvement in performance would be the highest for APACS, fol lowed by Tove and Wines. Interestingly, our experiments showed that for a workload which was similar in every respect, the improvement in performance was the high est for the APACS knowledge base, followed by Tove knowledge base, and finally, the Wines knowledge base.
The results presented in this section are empirical and should not be taken to imply that they will work for every knowledge base application. Using fanin, fanout and depth factors, we were able to intuitively and exper imentally explain the differences in relative performance on three knowledge bases that were considered. For any other application, these metrics can be a useful starting point in judging the suitability of the DDG policy.
6 Related Work
The present paper summarizes and enhances the results published earlier which focused on details of correct~ess [Chaudhri et al., 1992) and performance [Chaudhn et al., 1994) issues. A detailed description of the results can be found in the first author's doctoral dissertation [Chaudhri , 1995).
Knowledge base implementations that have tried to address the issue of concurrent access to a shared knowl edge base include CYCL [Guha and Lenat , 1994), K REP (Mays et al. , 1991) and PROTEUS (Ballou et al. , 1988) . In CYCL, a copy of the whole knowledge base is made and given to each of its users. Users indepen dently make changes to the database and submit it to a central server that tries to detect inconsistencies. If it finds any inconsistencies, it passes them along to the persons who made the changes. Otherwise, it propag~t~s the changes to all users . The K-REP system uses simi lar ideas and allows users to work on different versions of the knowledge base and provides facilities for merging the versions. The basic assumption in the CYCL and K REP approach is that the cost of detecting and repairing inconsistency is much smaller as compared to the cost of preventing it by ensuring serializability. The CYCL and K-REP approach is feasible for a small knowledge base but it is unclear if it will scale up to more realistic knowl edge base sizes. PROTEUS system uses the concurrency control facilities of an underlying object-oriented system ORION. The concurrency control mechanism in ORION is 2PL with locking granularities based on aggregation and generalization hierarchies.
To deal with long transactions, there have been other proposals [Agrawal and Abbadi, 1990; Salem et al. , 1994] that permit more concurrency than 2PL, but they do not exploit the semantic structure of the database .
7 Lessons Learnt
An interesting aspect of our results is the integration of knowledge model features with low level implementation issues . The integration is reflected in the design of the DDG policy that abstracts the knowledge model into a directed graph, and in performance evaluation which is done as a function of data model features .
For example, the presence of cycles in a knowledge base influences the design of the locking policy and the amount of concurrency permitted by it . This indicates that if there are large cycles in the knowledge base that are repeatedly accessed by a transaction then concur rency will be limited. Similarly, we found that a depth first traversal strategy led to a better response time as compared to a breadth-first strategy. Traditionally, traversal strategy has been under the control of a query processor and the designs of transaction manager and query processor have been considered in isolation. Our result on the influence of traversal strategy on concur rency control performance shows that the interaction be tween query processor and concurrency control can play an important role in the overall performance.
To get better advantage of the semantic structure, the knowledge base should be highly structured: it should be almost like a tree (high depth factor) and should not have large fanin and fanout (low fanin and fanout fac tors) . This has an interesting implication for knowledge base implementations that pre-compute all subsumption relationships. Pre-computation of all subsumption re lationships is equivalent to creating a large fanin and fanout in the subsumption hierarchy and in such a sit uation the advantages of using the semantic structure using the DDG policy will be reduced.
Our research illustrates a general framework for in corporating database functionality into knowledge bases . The solution space to achieve this includes [Mylopou los and Brodie, 1990) : coupling an AI system with a database system (loose or tight coupling) or devising an inteO'rated solution (in an evolutionary or a revolution ary 0 way) . We adopt and recommend an evolutionary approach, because it is pragmatic and consistent with software reusability.
An evolutionary approach to design an integrated AI DB solution should be a two step process. In the first step, one should view the problem as a database tuning problem [Shasha, 1 994), and if necessary, one should take the second step and solve a database kernel design prob lem. By solving a kernel design problem we mean ad dressing a core database concern such as storage design or query optimization. Let us illustrate this approach by considering the problem of concurrent access addressed in the present paper . To support concurrent access to a knowledge base, one would start with a database solution which in this case is 2PL. To tune 2PL for long transac tions one would chop the long transactions into smaller trans'actions [Shasha, 1 994) or impose a correctness cri terion which is weaker than serializability. If the long transaction problem still persists one would change the database kernel and augment 2PL with the DDG policy and use an adaptive algorithm that consistently gives a better performance than 2PL. These two steps taken to gether would give a comprehensive integrated solution for concurrent access in a knowledge base environment.
In summary, we feel that to develop a technology for constructing knowledge bases, we need to address the core database issues for knowledge models. A subset of these concerns may be addressed by tuning existing database products but a long term solution would require an integrated approach that makes fundamental changes in the database kernel.
8 Summary and Conclusions
In this paper, we considered the problem of support ing concurrent access to large knowledge bases . We arO'ued that knowledge base operations such as infer en~e over long rule chains and truth maintenance lead to the problem of long transactions which cannot be efficiently solved by existing database techniques. We argued that we can use the rich semantic structure of knowledge bases to devise a more viable solution for long transactions. We showed this by presenting the design , implementation and evaluation of an algorithm called Dynamic Directed Graph (DDG) policy that gives bet ter response time than 2PL at high update rates. We showed that 2PL can be augmented with the DDG policy to give a hybrid algorithm that consistently performs better than a system that uses only 2PL. We also dis cussed the impact of our results on the knowledge base design and presented a refinement of the evolutionary paradigm for constructing knowledge base management systems. In our current work, we are addressing the is sues of fault-tolerance for the DDG policy.
In conclusion, we would like to note that the re sults presented in this paper are at the intersection of knowledge base and database systems. Research com bining techniques from these two fields will be of prime importance in future. One of the major technologi cal innovations in the coming years would be devel opment of cooperative information systems involving a large number of intelligent agents distributed over com puter/communication networks. Developing such sys tems presents a unique opportunity in which techniques from both knowledge bases and databases will play a crucial role. The results presented in this paper make a modest contribution towards this goal.
@inproceedings{ijcai1995p99,
title = {Efficient Algorithms and Performance Results for Multi-User Knowledge Bases},
author = {Chaudhri, Vinay K. and Mylopoulos, John},
booktitle = {Proceedings of the Fourteenth International Joint Conference on
Artificial Intelligence, {IJCAI-95}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Chris S. Mellish},
pages = {759--766},
year = {1995},
note = {Knowledge Base Technology},
url = {https://ijcai.org/proceedings/1995/99},
}
TY - CPAPER TI - Efficient Algorithms and Performance Results for Multi-User Knowledge Bases AU - Chaudhri, Vinay K. AU - Mylopoulos, John T2 - Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence, IJCAI-95 PB - International Joint Conferences on Artificial Intelligence PY - 1995 SP - 759 EP - 766 UR - https://ijcai.org/proceedings/1995/99 ER -Copied
Machine-readable versions of this paper, for tools and AI agents: