Proceedings

Efficient Algorithms and Performance Results for Multi-User Knowledge Bases

Download BibTeX Cite

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.

  1. [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.
  2. Agrawal et al., 1 987]
  3. 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.
  4. [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.
  5. [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.
  6. [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.
  7. [Carol!, 1988] M. D. Carol!. Data Flow Analysis via Dominator and Attribute Updates. Technical Report LCSR-TR-111, Rutgers University, May 1988.
  8. [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.
  9. [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.
  10. [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.
  11. [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.
  12. [Gray and Reuter, 1993] Jim Gray and Andreas Reuter. Transaction Processing: Concepts and Techniques.
  13. Guha and Lenat, 1. 994
  14. R. V. Guha and Douglas B. Lenat. Enabling Agents to Work Together . Commu- nications of the ACM, 37(7) :126-142, 1994.
  15. [Livny, 1990] Miron Livny. DeNeT User's Guide (Ver- sion 1.5) . Technical report, University of Wisconsin, 1990.
  16. [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.
  17. [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.
  18. [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.
  19. [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.
  20. [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.
  21. [Salem et al., 1994] Kenneth Salem, Hector Garcia- Molina, and Jeannie Shands. Altruistic Locking. ACM Transactions on Database Systems, 19(1) :117- 164, 1994.
  22. [Shasha, 1994] Dennis E. Shasha. Database Tuning - A Principled Approach. Prentice Hall, NJ, 1994.
  23. [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.
  24. [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.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards