Quantitative evaluation of a transaction facility for knowledge base management system

ABSTRACT

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. In this paper, we examine a novel concurrency control policy called Dynamic Directed Graph (or DDG) policy that effectively exploits the rich semantic structure of a knowledge base.Our analysis is carried out in the context of a real knowledge based system application from which knowledge base structure and workload parameters are computed. These serve as a basis for studying the implementation alternatives that arise as a result of knowledge base characteristics. The implementation alternatives that we consider include selection of portions of the knowledge base structure to be exploited for concurrency control, and also the dependence of concurrency on the traversal strategy used to search through the knowledge base. We analyze the effects of various workload parameters and conclude that the DDG policy improves substantially the response time for short transactions when there is heavy data contention.

REFERENCES

• 1: Divyakant Agrawal , Amr El Abbadi, Locks with constrained sharing (extended abstract), Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.85-93, April 02-04, 1990, Nashville, Tennessee, United States [doi>10.1145/298514.298545]
• 2: Rakesh Agrawal , Michael J. Carey , Miron Livny, Concurrency control performance modeling: alternatives and implications, ACM Transactions on Database Systems (TODS), v.12 n.4, p.609-654, Dec. 1987 [doi>10.1145/32204.32220]
• 3: Howard W. Beck , Sunit K. Gala , Shamkant B. Navathe, Classification as a Query Processing Technique in the CANDIDE Semantic Data Model, Proceedings of the Fifth International Conference on Data Engineering, p.572-581, February 06-10, 1989
• 4: Philip A. Bernstein , Vassco Hadzilacos , Nathan Goodman, Concurrency control and recovery in database systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1987
• 5: Alexander Borgida , Ronald J. Brachman , Deborah L. McGuinness , Lori Alperin Resnick, CLASSIC: a structural data model for objects, Proceedings of the 1989 ACM SIGMOD international conference on Management of data, p.58-67, June 1989, Portland, Oregon, United States
• 6: Vinay K. Chaudhri, Transaction synchronization in knowledge bases: concepts, realization and quantitative evaluation, University of Toronto, Toronto, Ont., Canada, 1996
• 7: V. K. Chaudhri, V. Hadzilacos, and J. Mylopoulos. Concurrency Control for Knowledge Bases. In Proceedings of the Third International Conference on Knowledge Representation and Reasoning, pages 762-773, 1992.
• 8: Fernando de Ferreira Rezende , Theo Härder, A lock method for KBMSs using abstraction relationships' semantics, Proceedings of the third international conference on Information and knowledge management, p.112-121, November 29-December 02, 1994, Gaithersburg, Maryland, United States [doi>10.1145/191246.191267]
• 9: K. P. Eswaran , J. N. Gray , R. A. Lorie , I. L. Traiger, The notions of consistency and predicate locks in a database system, Communications of the ACM, v.19 n.11, p.624-633, Nov. 1976 [doi>10.1145/360363.360369]
• 10: Jim Gray , Andreas Reuter, Transaction Processing: Concepts and Techniques, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1992
• 11: J. N. Gray, R. A. Lorie, G. R. Putzolu, and I. L. Traiger. Granularity of Locks and Degrees of Consistency iin a Shared Database. In G. M. Nijssen, editor, Modeling in Database Management Systems, pages 365-394. North Holland Publishing Company, 1976.
• 12: Theodore Johnson , Dennis Sasha, The performance of current B-tree algorithms, ACM Transactions on Database Systems (TODS), v.18 n.1, p.51-101, March 1993 [doi>10.1145/151284.151286]
• 13: Averill M. Law , W. David Kelton, Simulation Modeling and Analysis, McGraw-Hill Higher Education, 1997
• 14: Edward D. Lazowska , John Zahorjan , G. Scott Graham , Kenneth C. Sevcik, Quantitative system performance: computer system analysis using queueing network models, Prentice-Hall, Inc., Upper Saddle River, NJ, 1984
• 15: M. Livny. DeNeT User's Guide (Version 1.5). Technical report, University of Wisconsin, 1990.
• 16: C. Mohan, ARIES/KVL: a key-value locking method for concurrency control of multiaction transactions operating on B-tree indexes, Proceedings of the sixteenth international conference on Very large databases, p.392-405, September 1990, Brisbane, Australia
• 17: John Mylopoulos , Alex Borgida , Matthias Jarke , Manolis Koubarakis, Telos: representing knowledge about information systems, ACM Transactions on Information Systems (TOIS), v.8 n.4, p.325-362, Oct. 1990 [doi>10.1145/102675.102676]
• 18: 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 A rtificial Intelligence in Materials Processing Applications, Edmonton, August 1992.
• 19: Christos Papadimitriou, The theory of database concurrency control, Computer Science Press, Inc., New York, NY, 1986
• 20: Dimitris Plexousakis, Integrity Constraint and Rule Maintenance in Temporal Deductive Knowledge Bases, Proceedings of the 19th International Conference on Very Large Data Bases, p.146-157, August 24-27, 1993
• 21: In Kyung Ryu , Alexander Thomasian, Analysis of database performance with dynamic locking, Journal of the ACM (JACM), v.37 n.3, p.491-523, July 1990 [doi>10.1145/79147.79152]
• 22: Kenneth Salem , Héctor García-Molina , Jeannie Shands, Altruistic locking, ACM Transactions on Database Systems (TODS), v.19 n.1, p.117-165, March 1994 [doi>10.1145/174638.174639]
• 23: Abraham Silberschatz , Zvi Kedem, Consistency in Hierarchical Database Systems, Journal of the ACM (JACM), v.27 n.1, p.72-80, Jan. 1980 [doi>10.1145/322169.322176]
• 24: V. Srinivasan , Michael J. Carey, Performance of B⁺ tree concurrency control algorithms, The VLDB Journal — The International Journal on Very Large Data Bases, v.2 n.4, p.361-406, October 1993 [doi>10.1007/BF01263046]
• 25: Y. C. Tay, Locking performance in centralized databases, Academic Press Professional, Inc., San Diego, CA, 1988
• 26: Jeffrey D. Ullman, Principles of Database and Knowledge-Base Systems: Volume II: The New Technologies, W. H. Freeman & Co., New York, NY, 1990
• 27: H. Wang. Personal Communication, 1993.
• 28: Gerhard Weikum , Christof Hasse, Multi-level transaction management for complex objects: implementation, performance, parallelism, The VLDB Journal — The International Journal on Very Large Data Bases, v.2 n.4, p.407-454, October 1993 [doi>10.1007/BF01263047]
• 29: Mihalis Yannakakis, A Theory of Safe Locking Policies in Database Systems, Journal of the ACM (JACM), v.29 n.3, p.718-740, July 1982 [doi>10.1145/322326.322333]
• 30: Philip S. Yu , Daniel M. Dias , Stephen S. Lavenberg, On the analytical modeling of database concurrency control, Journal of the ACM (JACM), v.40 n.4, p.831-872, Sept. 1993 [doi>10.1145/153724.153733]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Concurrency

General Terms:
Measurement, Performance, Theory