Development and Application of
Knowledge Base Management Systems

Abstract

Knowledge based systems are now routinely used in thousands of real world applications. Most such applications involve relatively small knowledge bases, containing hundreds rather than thousands of units (objects, rules, frames, cases). Developing the next generation of knowledge based systems with knowledge bases containing hundreds of thousands or even millions of units will require a technology for building, accessing and managing these large knowledge bases. Such a technology will be founded on extensions of current techniques for knowledge bases and databases and address issues of physical storage management (how to minimize disk I/Os during the evaluation of a query), query optimization (transforming a query to an equivalent but simpler expression), concurrency control (interleaving the execution of knowledge base operations to optimize the use of computer resources), constraint enforcement and others. Apart from such traditionally database-oriented techniques, knowledge base management requires new techniques, specific to knowledge bases, including efficient implementations of inference mechanisms (terminological subsumption, deduction, induction and abduction). Moreover, knowledge base management demands new tools for knowledge acquisition, knowledge base validation, verification and maintenance, as well as new architectures that accommodate a multi-user, distributed environment.

The tutorial aims at providing a comprehensive review on the state-of-the-art in knowledge base management techniques and commercial tools, as well as recent research results and on-going projects. All these will be presented from the application point of view and the actual development process of knowledge based applications will be stressed.

Topic Outline

Part I: Introduction

What are knowledge bases and how do they differ from databases? What is knowledge base management? How does it relate to knowledge engineering? Background technologies such as expert system shells, database management systems, deductive, object-oriented and active database systems. Assumed operating environment for knowledge based systems.

Part II: Knowledge Representation and Reasoning

Basic approaches to knowledge representation. Knowledge representation vs. conceptual models. Formal vs. informal representations. General purpose reasoning methods - deductive, abductive, inductive, terminological and analogical reasoning. Specialized reasoning methods such as case-based reasoning.

Part III: The State-of-the-Art

Commercial tools for knowledge base management. Commercial expert system shells. Case-based reasoning tools and systems. Communication tools. Object-oriented DBMSs. Selection criteria and architectural considerations. Experiences from industrial projects.

Part IV: Implementation of Large Knowledge Bases

Query processing in relational databases. Query optimization: syntactic and semantic transformations. Access planning. Query processing in object-oriented database and knowledge base systems (research prototypes). Query processing in Telos, including the treatment of temporal knowledge and temporal queries. Access planning and optimization using explanation-based learning. Knowledge visualization - implicit and explicit contexts, context-based similarity, flexible similarity-based retrieval mechanisms. Concurrency control policies for graph structured databases. The DAG policy and its extensions to knowledge bases. Performance analysis tools, methodologies and results.

Part V: Knowledge Base Management Tools

Tools for knowledge acquisition, verification and validation; knowledge sharing. Knowledge mining. Applications of machine learning techniques on improving the performance of KBMSs.

Part VI: A case study: A Real World Application

APACS is a knowledge-based cooperative environment for building real-time intelligent applications in a particular domain. It supports the real-time monitoring and diagnosis of plant malfunctions and prediction of plant behavior. The case study contains architecture design, tool selection, implementation and integration for the APACS.

Part VII: Summary

Conclusions and future trends.

The KBMS Project

The KBMS project undertaken by the research group of prof. John Mylopoulos at the Department of Computer Science, University of Toronto, is a five-year research effort in functionality and performance issues for knowledge base management, involving a large number of researchers. The material of the present tutorial has been put together by J. Mylopoulos (principal investigator), V. Chaudhri, D. Plexousakis, A. Shrufi, T. Topaloglou, and the presenters. The material has already been presented to the Toronto-area computer industry community as a full day tutorial organized by the Information Technology Research Center of Ontario in 1993 and an updated tutorial was accepted for presentation at IJCAI-95. The research results from the KBMS project have been published at several major conferences. Following is a list of papers (co-)authored by one or more members of the group (many of which are available in a postscript form):

1. J. Mylopoulos and M. Brodie (eds). Readings in Artificial Intelligence and Databases. Morgan Kaufmann, 1988.
2. J. Mylopoulos, A. Borgida, M. Jarke and M. Koubarakis.Telos: a Language for Representing Knowledge about Information Systems, ACM Transactions on Information Systems, Vol. 8, no. 4, pp. 325-362, 1990.}
3. H. Wang.Selecting an Expert System Tool, Technical Note CSRI-54, 1990 University of Toronto
4. T. Topaloglou, A. Illaramendi and L. Sbatella.Query Processing for KBMSs: Temporal, Syntactic and Semantic Transformations, International Conference on Data Engineering, 1992.
5. V. Chaudhri, V. Hadzilacos and J. Mylopoulos.Concurrency Control for Knowledge Bases, Third International Conference on Knowledge Representation and Reasoning, 1992.
6. R. Greiner and I. Jursica. A Statistical Approach to Solving the EBL Utility Problem, AAAI-92, pp. 241-248, 1992.
7. V. Chaudhri and R. Greiner. A Formal Analysis of Solution Caching, Canadian AI Conference, 1992.
8. J. Mylopoulos, V. Chaudhri, D. Plexousakis and T. Topaloglou.A Performance-Oriented Approach to Knowledge Base Management, 1st International Conference on Information and Knowledge Management, 1992. A revised version of the paper appeared as: Adapting Database Implementation Techniques to Manage Very Large Knowledge Bases, In {\em International Workshop on Building and Sharing Very Large Knowledge Bases}, Dec 3-4, 1993, Tokyo, Japan, pp. 215-226.
9. D. Plexousakis.Semantical and Ontological Consideration in Telos: a Language for Knowledge Representation, Computational Intelligence Journal, Vol. 9, no. 1, pp.41-72, 1993.
10. D. Plexousakis.Integrity Constraint and Rule Maintenance in Temporal Deductive Knowledge Bases, VLDB-93.
11. T. Topaloglou.Storage Management for Knowledge Bases, 2nd International Conference on Information and Knowledge Management, 1993.
12. H. Wang, J. Mylopoulos, A. Kushniruk, B. Kramer, and M. Stanley. KNOWBEL: New Tools for Expert System Development, in Knowledge Engineering Shells - Systems and Techniques, World Scientific Co., NJ, 1993.
13. J. Mylopoulos, H. Wang and B. Kramer. KNOWBEL: A Hybrid Expert System Building Tool and Its Applications,IEEE Expert, February 1993.
14. J. Mylopoulos and R. Motschnig-Pitrik. Partitioning information bases with contexts, Proc. of the Third International Conference on Cooperative Information Systems, Vienna, Austria, 1995.
15. V. Chaudhri, V. Hadzilacos, J. Mylopoulos, K. Sevcik, Quantitative Evaluation of a Transaction Facility for a Knowledge Base Management System, CIKM-94.
16. V. Chaudhri and V. Hadzilacos. Safe Locking Policies for Dynamic Databases, PODS-95.
17. D. Plexousakis, The Role of Ramifications in Transaction Specification Specifications and Integrity Checking, submitted for publication, 1994.
18. Dimitris Plexousakis, John Mylopoulos. Accomodating Integrity Constraints During Database Design EDBT-96, 1996.
19. I. Jurisica. How to retrieve relevant information?, In: Proc. of the AAAI Fall Symposium Series on Relevance, 1994.
20. I. Jurisica. A similarity-based retrieval of relevant cases, Technical Report DKBS-TR-94-5, 1994, University of Toronto.
21. I. Jurisica. TA3: Case-Based Intelligent Retrieval and Advisory Tool, ACM Conference on Society and the Future of Computing, Durango, CO, 1995.
22. I. Jurisica. A Similarity-Based Retrieval Tool for Software Repositories, The Third Workshop on AI and Software Engineering: Breaking the Mold. IJCAI-95, Montreal, Quebec, 1995.
23. I. Jurisica and H. Shapiro. Case-Based Reasoning System Applied as an Advisor for IVF Practitioners, The 51st Conference of the American Society for Reproductive Medicine, Seattle, Washington, 1995.
24. I. Jurisica and J. Glasgow. Applying Case-Based Reasoning to Control in Robotics, 3rd Robotics and Knowledge-Based Systems Workshop, St. Hubert, Quebec, 1995.
25. I. Jurisica and J. Glasgow. Context-Based Similarity for Case-Based Reasoning, submitted for publication, 1995.
26. Anthony J. Bonner, Adel Shrufi,Steve Rozen. LabFlow-1: a Database Benchmark for High-Throughput Workflow Management EDBT-96, 1996.

Biographical Notes

Both authors presented tutorials on KBMS and CBR on various occasions, including CAIA-94 conference, TRIO/ITRC tutorial in 1994 and ITRC tutorial in 1993.

Huaiqing Wang

is a University Lecturer in the Department of Information Systems, City University of Hong Kong. He was a research scientist in the Artificial Intelligence Group at University of Toronto from 1988 to 1994. His current research interests include the application of knowledge-based and database systems, intelligent and cooperative information systems, knowledge sharing, and hypermedia systems. Wang received his PhD in artificial intelligence and computer vision from the University of Manchester in 1987, his MS in computer science from Huazhong University in 1982, and his BS in electrical engineering from Jiaotong University in 1967.

iswang@cityu.edu.hk
Department of Information Systems, City University of Hong Kong
Kowloon, Hong Kong
Tel: 852 2788 8491, Fax: 852 2788 8694

Igor Jurisica

is a Ph.D. candidate in the Department of Computer Science at the University of Toronto. He has been a member of the knowledge base management group for three years. Prior to moving to Toronto, he was a member of the AI group of the Slovak Technical University in Bratislava, Slovakia, participating in various projects under the contracts from industry. He obtained his M.Sc. degree in electrical engineering at the Slovak Technical University and the M.Sc. degree in computer science at the University of Toronto in 1991 and 1993 respectively. His thesis work is on the representation and management issues for case-based reasoning systems.

juris@ai.utoronto.ca
Department of Computer Science, University of Toronto
Toronto, Ontario, M5S 1A4 Canada
Tel: (416) 978-7589, Fax: (416) 978-1455