Building Knowledge Base Management Systems.

John Mylopoulos, Vinay K. Chaudhri, Dimitris Plexousakis, Adel Shrufi, Thodoros Topaloglou: Building Knowledge Base Management Systems. VLDB J. 5(4): 238-263(1996)
  author    = {John Mylopoulos and
               Vinay K. Chaudhri and
               Dimitris Plexousakis and
               Adel Shrufi and
               Thodoros Topaloglou},
  title     = {Building Knowledge Base Management Systems},
  journal   = {VLDB J.},
  volume    = {5},
  number    = {4},
  year      = {1996},
  pages     = {238-263},
  ee        = {db/journals/vldb/MylopoulosCPST96.html},
  bibsource = {DBLP,}


Advanced applications in fields such as CAD, software engineering, real-time process control, corporate repositories and digital libraries require the construction, efficient access and management of large, shared knowledge bases. Such knowledge bases cannot be built using existing tools such as expert system shells, because these do not scale up, nor can they be built in terms of existing database technology, because such technology does not support the rich representational structure and inference mechanisms required for knowledge-based systems. This paper proposes a generic architecture for a knowledge base management system intended for such applications. The architecture assumes an object-oriented knowledge representation language with an assertional sublanguage used to express constraints and rules. It also provides for general-purpose deductive inference and special-purpose temporal reasoning. Results reported in the paper address several knowledge base management issues. For storage management, a new method is proposed for generating a logical schema for a given knowledge base. Query processing algorithms are offered for semantic and physical query optimization, along with an enhanced cost model for query cost estimation. On concurrency control, the paper describes a novel concurrency control policy which takes advantage of knowledge base structure and is shown to outperform two-phase locking for highly structured knowledge bases and update-intensive transactions. Finally, algorithms for compilation and efficient processing of constraints and rules during knowledge base operations are described. The paper describes original results, including novel data structures and algorithms, as well as preliminary performance evaluation data. Based on these results, we conclude that knowledge base management systems which can accommodate large knowledge bases are feasible.

Key Words

Knowledge base management systems, Storage management, Concurrency control, Constraint enforcement, Rule management

Copyright © 1996 by Springer, Berlin, Heidelberg. Permission to make digital or hard copies of the abstract is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice along with the full citation.

Online Edition (Springer)

Citation Page

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 4 Issue 1, Books, VLDB-j, TODS, ..." and ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ... BibTeX


[Agrawal et al. 1987]
Rakesh Agrawal, Michael J. Carey, Miron Livny: Concurrency Control Performance Modeling: Alternatives and Implications. ACM Trans. Database Syst. 12(4): 609-654(1987) BibTeX
[Aho et al. 1987]
Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman: Data Structures and Algorithms. Addison-Wesley 1983, ISBN 0-201-00023-7
[Allen 1983]
James F. Allen: Maintaining Knowledge about Temporal Intervals. Commun. ACM 26(11): 832-843(1983) BibTeX
[Attardi and Simi 1981]
[Bernstein et al. 1987]
Philip A. Bernstein, Vassos Hadzilacos, Nathan Goodman: Concurrency Control and Recovery in Database Systems. Addison-Wesley 1987, ISBN 0-201-10715-5
Contents BibTeX
[Bertino and Kim 1989]
Elisa Bertino, Won Kim: Indexing Techniques for Queries on Nested Objects. IEEE Trans. Knowl. Data Eng. 1(2): 196-214(1989) BibTeX
[Biliris 1992]
Alexandros Biliris: The Performance of Three Database Storage Structures for Managing Large Objects. SIGMOD Conference 1992: 276-285 BibTeX
[Bocca 1986]
Jorge B. Bocca: On the Evaluation Strategy of EDUCE. SIGMOD Conference 1986: 368-378 BibTeX
[Brodie et al. 1984]
Michael L. Brodie, John Mylopoulos, Joachim W. Schmidt (Eds.): On Conceptual Modelling, Perspectives from Artificial Intelligence, Databases, and Programming Languages, Book resulting from the Intervale Workshop 1982. Topics in Information Systems Springer 1984, ISBN 3-540-90842-0
Contents BibTeX
[ Bry et al. 1988]
François Bry, Hendrik Decker, Rainer Manthey: A Uniform Approach to Constraint Satisfaction and Constraint Satisfiability in Deductive Databases. EDBT 1988: 488-505 BibTeX
[Buchanan and Wilkins 1993]
[Carey et al. 1986]
Michael J. Carey, David J. DeWitt, Joel E. Richardson, Eugene J. Shekita: Object and File Management in the EXODUS Extensible Database System. VLDB 1986: 91-100 BibTeX
[Carroll 1988]
[Ceri and Widom 1990]
Stefano Ceri, Jennifer Widom: Deriving Production Rules for Constraint Maintainance. VLDB 1990: 566-577 BibTeX
[Chakravarthy et al. 1988]
Upen S. Chakravarthy, John Grant, Jack Minker: Foundations of Semantic Query Optimization for Deductive Databases. Foundations of Deductive Databases and Logic Programming. 1988: 243-273 BibTeX
[Chaudhri 1995]
[Chaudhri and Hadzilacos 1995]
Vinay K. Chaudhri, Vassos Hadzilacos: Safe Locking Policies for Dynamic Databases. PODS 1995: 233-244 BibTeX
[Chaudhri et al. 1992]
Vinay K. Chaudhri, Vassos Hadzilacos, John Mylopoulos: Concurrency Control for Knowledge Bases. KR 1992: 762-773 BibTeX
[Chaudhri et al. 1994]
Vinay K. Chaudhri, Vassos Hadzilacos, John Mylopoulos, Kenneth C. Sevcik: Quantitative Evaluation of a Transaction Facility for a Knowledge Base Management System. CIKM 1994: 122-131 BibTeX
[Chaudhri and Mylopoulos 1995]
Vinay K. Chaudhri, John Mylopoulos: Efficient Algorithms and Performance Results for Multi-User Knowledge Bases. IJCAI (1) 1995: 759-767 BibTeX
[Chomicki 1992]
Jan Chomicki: History-less Checking of Dynamic Integrity Constraints. ICDE 1992: 557-564 BibTeX
[Copeland and Khoshafian 1985]
George P. Copeland, Setrag Khoshafian: A Decomposition Storage Model. SIGMOD Conference 1985: 268-279 BibTeX
[Dechter et al. 1989]
Rina Dechter, Itay Meiri, Judea Pearl: Temporal Constraint Networks. KR 1989: 83-93 BibTeX
[Decker 1986]
Hendrik Decker: Integrity Enforcement on Deductive Databases. Expert Database Conf. 1986: 381-395 BibTeX
[Eswaran et al. 1976]
Kapali P. Eswaran, Jim Gray, Raymond A. Lorie, Irving L. Traiger: The Notions of Consistency and Predicate Locks in a Database System. Commun. ACM 19(11): 624-633(1976) BibTeX
[Findler 1979]
[Finkelstein et al. 1988]
Sheldon J. Finkelstein, Mario Schkolnick, Paolo Tiberio: Physical Database Design for Relational Databases. ACM Trans. Database Syst. 13(1): 91-128(1988) BibTeX
[Frank et al. 1992]
Martin R. Frank, Edward Omiecinski, Shamkant B. Navathe: Adaptive and Automated Index Selection in RDBMS. EDBT 1992: 277-292 BibTeX
[Frenkel 1991]
Karen A. Frenkel: The Human Genome Project and Informatics. Commun. ACM 34(11): 40-51(1991) BibTeX
[Gupta et al. 1994]
Ashish Gupta, Yehoshua Sagiv, Jeffrey D. Ullman, Jennifer Widom: Constraint Checking with Partial Information. PODS 1994: 45-55 BibTeX
[Guttman 1984]
Antonin Guttman: R-Trees: A Dynamic Index Structure for Spatial Searching. SIGMOD Conference 1984: 47-57 BibTeX
[Hull and King 1987]
Richard Hull, Roger King: Semantic Database Modeling: Survey, Applications, and Research Issues. ACM Comput. Surv. 19(3): 201-260(1987) BibTeX
[Hulsmann and Saake 1990]
Klaus Hülsmann, Gunter Saake: Representation of the Historical Information Necessary for Temporal Integrity Monitoring. EDBT 1990: 378-392 BibTeX
[Ibaraki and Katoh 1983]
Toshihide Ibaraki, Naoki Katoh: On-Line Computation of Transitive Closures of Graphs. Inf. Process. Lett. 16(2): 95-97(1983) BibTeX
[Ioannidis et al. 1993]
Yannis E. Ioannidis, Raghu Ramakrishnan, Linda Winger: Transitive Closure Algorithms Based on Graph Traversal. ACM Trans. Database Syst. 18(3): 512-576(1993) BibTeX
[Ioannidis and Kang 1991]
Yannis E. Ioannidis, Younkyung Cha Kang: Left-Deep vs. Bushy Trees: An Analysis of Strategy Spaces and its Implications for Query Optimization. SIGMOD Conference 1991: 168-177 BibTeX
[Ishikawa et al. 1993]
Hiroshi Ishikawa, Fumio Suzuki, Fumihiko Kozakura, Akifumi Makinouchi, Mika Miyagishima, Yoshio Izumida, Masaaki Aoshima, Yasuo Yamane: The Model, Language, and Implementation of an Object-Oriented Multimedia Knowledge Base Management System. ACM Trans. Database Syst. 18(1): 1-50(1993) BibTeX
[Italiano 1988]
Giuseppe F. Italiano: Finding Paths and Deleting Edges in Directed Acyclic Graphs. Inf. Process. Lett. 28(1): 5-11(1988) BibTeX
[Jarke and Koch 1984]
Matthias Jarke, Jürgen Koch: Query Optimization in Database Systems. ACM Comput. Surv. 16(2): 111-152(1984) BibTeX
[Jarke and Koubarakis 1989]
[Jeusfeld and Jarke 1991]
Manfred A. Jeusfeld, Matthias Jarke: From Relational to Object-Oriented Integrity Simplification. DOOD 1991: 460-477 BibTeX
[Khshafian and Copeland 1986]
Setrag Khoshafian, George P. Copeland: Object Identity. OOPSLA 1986: 406-416 BibTeX
[Kim et al. 1989]
Won Kim, Kyung-Chang Kim, Alfred G. Dale: Indexing Techniques for Object-Oriented Databases. Object-Oriented Concepts, Databases, and Applications 1989: 371-394 BibTeX
[Kramer et al. 1996]
Bryan M. Kramer, John Mylopoulos, Michael E. Benjamin, Q. B. Chou, Peter Ahn, John Opala: Developing an Expert System Technology for Industrial Process Control: An Experience Report. Canadian Conference on AI 1996: 172-186 BibTeX
[Kuchenhoff 1991]
Volker Küchenhoff: On the Efficient Computation of the Difference Between Concecutive Database States. DOOD 1991: 478-502 BibTeX
[Law and Kelton 1991]
[Lengauer and Tarjan 1979]
Thomas Lengauer, Robert Endre Tarjan: A Fast Algorithm for Finding Dominators in a Flowgraph. ACM Trans. Program. Lang. Syst. 1(1): 121-141(1979) BibTeX
[Ling and Lee 1992]
[Lipeck 1990]
Udo W. Lipeck: Transformation of Dynamic Integrity Constraints into Transaction Specifications. Theor. Comput. Sci. 76(1): 115-142(1990) BibTeX
[Livny 1986]
[Lockemann et al. 1991]
Peter C. Lockemann, Hans-Hellmut Nagel, Ingrid M. Walter: Databases for knowledge bases: empirical study of a knowledge base management system for a semantic network. Data Knowl. Eng. 7: 115-154(1991) BibTeX
[Mylopoulos et al. 1990]
John Mylopoulos, Alexander Borgida, Matthias Jarke, Manolis Koubarakis: Telos: Representing Knowledge About Information Systems. ACM Trans. Inf. Syst. 8(4): 325-362(1990) BibTeX
[Neches et al. 1991]
[Nicolas 1982]
Jean-Marie Nicolas: Logic for Improving Integrity Checking in Relational Data Bases. Acta Inf. 18: 227-253(1982) BibTeX
[Paul et al. 1987]
H.-Bernhard Paul, Hans-Jörg Schek, Marc H. Scholl, Gerhard Weikum, Uwe Deppisch: Architecture and Implementation of the Darmstadt Database Kernel System. SIGMOD Conference 1987: 196-207 BibTeX
[Plexousakis 1993a]
Dimitris Plexousakis: Integrity Constraint and Rule Maintenance in Temporal Deductive Knowledge Bases. VLDB 1993: 146-157 BibTeX
[Plexousakis 1993b]
[Plexousakis 1996a]
[Plexousakis and Mylopoulos 1996]
Dimitris Plexousakis, John Mylopoulos: Accomodating Integrity Constraints During Database Design. EDBT 1996: 497-513 BibTeX
[Qaddah et al. 1991]
Ghassan Z. Qadah, Lawrence J. Henschen, Jung J. Kim: Efficient Algorithms for the Instantiated Transitive Closure Queries. IEEE Trans. Software Eng. 17(3): 296-309(1991) BibTeX
[Schieber and Vishkin 1988]
Baruch Schieber, Uzi Vishkin: On Finding Lowest Common Ancestors: Simplification and Parallelization. SIAM J. Comput. 17(6): 1253-1262(1988) BibTeX
[Selinger et al. 1979]
Patricia G. Selinger, Morton M. Astrahan, Donald D. Chamberlin, Raymond A. Lorie, Thomas G. Price: Access Path Selection in a Relational Database Management System. SIGMOD Conference 1979: 23-34 BibTeX
[Shrufi 1994]
Adel Shrufi: Performance of Clustering Policies in Object Bases. CIKM 1994: 80-87 BibTeX
[Silberschatz and Kedem 1980]
Abraham Silberschatz, Zvi M. Kedem: Consistency in Hierarchical Database Systems. J. ACM 27(1): 72-80(1980) BibTeX
[Snodgrass 1987]
Richard T. Snodgrass: The Temporal Query Language TQuel. ACM Trans. Database Syst. 12(2): 247-298(1987) BibTeX
[Stanley 1986]
[Steinbrunn et al. 1993]
[Stickel 1985]
Mark E. Stickel: Automated Deduction by Theory Resolution. IJCAI 1985: 1181-1186 BibTeX
[Stonebraker 1975]
Michael Stonebraker: Implementation of Integrity Constraints and Views by Query Modification. SIGMOD Conference 1975: 65-78 BibTeX
[Stonebraker and Dozier 1991]
[Tay 1987]
[Topaloglou 1993]
Thodoros Topaloglou: Storage Management for Knowledge Bases. CIKM 1993: 95-104 BibTeX
[Topaloglou et al. 1992]
Thodoros Topaloglou, Arantza Illarramendi, Licia Sbattella: Query Optimization for KBMSs: Temporal, Syntactic and Semantic Transformantions. ICDE 1992: 310-319 BibTeX
[Ullman 1988]
Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume I. Computer Science Press 1988, ISBN 0-7167-8158-1
Contents BibTeX
[Valduriez 1987]
Patrick Valduriez: Join Indices. ACM Trans. Database Syst. 12(2): 218-246(1987) BibTeX
[Valduriez et al. 1986]
Patrick Valduriez, Setrag Khoshafian, George P. Copeland: Implementation Techniques of Complex Objects. VLDB 1986: 101-110 BibTeX
[Vilain et al. 1989]
Marc B. Vilain, Henry A. Kautz: Constraint Propagation Algorithms for Temporal Reasoning. AAAI 1986: 377-382 BibTeX
[Wallace 1991]
Mark Wallace: Compiling Integrity Checking into Update Procedures. IJCAI 1991: 903-910 BibTeX
[Yannakakis 1982]
Mihalis Yannakakis: A Theory of Safe Locking Policies in Database Systems. J. ACM 29(3): 718-740(1982) BibTeX
[Yao 1977]
S. Bing Yao: Approximating the Number of Accesses in Database Organizations. Commun. ACM 20(4): 260-261(1977) BibTeX
[Zdonik and Maier 1989]
Stanley B. Zdonik, David Maier (Eds.): Readings in Object-Oriented Database Systems. Morgan Kaufmann 1990, ISBN 1-55860-000-0

Referenced by

  1. Thodoros Topaloglou, John Mylopoulos: Representing Partial Spatial Information in Databases. ER 1996: 325-340
  2. Dimitris Plexousakis, John Mylopoulos: Accomodating Integrity Constraints During Database Design. EDBT 1996: 497-513
  3. Adel Shrufi, Thodoros Topaloglou: Query Processing for Knowledge Bases Using Join Indices. CIKM 1995: 158-166
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
VLDB Journal: 1992-1995 Copyright © by VLDB Endowment / 1996-... Copyright © by Springer Verlag,
ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Sun May 17 00:31:28 2009