dblp.uni-trier.de www.dagstuhl.de www.uni-trier.de

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)
@article{DBLP:journals/vldb/MylopoulosCPST96,
  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, http://dblp.uni-trier.de}
}

Abstract

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 ...

References

[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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Allen 1983]
James F. Allen: Maintaining Knowledge about Temporal Intervals. Commun. ACM 26(11): 832-843(1983) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Biliris 1992]
Alexandros Biliris: The Performance of Three Database Storage Structures for Managing Large Objects. SIGMOD Conference 1992: 276-285 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Bocca 1986]
Jorge B. Bocca: On the Evaluation Strategy of EDUCE. SIGMOD Conference 1986: 368-378 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[ 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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Carroll 1988]
...
[Ceri and Widom 1990]
Stefano Ceri, Jennifer Widom: Deriving Production Rules for Constraint Maintainance. VLDB 1990: 566-577 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Chaudhri 1995]
...
[Chaudhri and Hadzilacos 1995]
Vinay K. Chaudhri, Vassos Hadzilacos: Safe Locking Policies for Dynamic Databases. PODS 1995: 233-244 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Chaudhri et al. 1992]
Vinay K. Chaudhri, Vassos Hadzilacos, John Mylopoulos: Concurrency Control for Knowledge Bases. KR 1992: 762-773 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Chaudhri and Mylopoulos 1995]
Vinay K. Chaudhri, John Mylopoulos: Efficient Algorithms and Performance Results for Multi-User Knowledge Bases. IJCAI (1) 1995: 759-767 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Chomicki 1992]
Jan Chomicki: History-less Checking of Dynamic Integrity Constraints. ICDE 1992: 557-564 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Copeland and Khoshafian 1985]
George P. Copeland, Setrag Khoshafian: A Decomposition Storage Model. SIGMOD Conference 1985: 268-279 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Dechter et al. 1989]
Rina Dechter, Itay Meiri, Judea Pearl: Temporal Constraint Networks. KR 1989: 83-93 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Decker 1986]
Hendrik Decker: Integrity Enforcement on Deductive Databases. Expert Database Conf. 1986: 381-395 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Frank et al. 1992]
Martin R. Frank, Edward Omiecinski, Shamkant B. Navathe: Adaptive and Automated Index Selection in RDBMS. EDBT 1992: 277-292 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Frenkel 1991]
Karen A. Frenkel: The Human Genome Project and Informatics. Commun. ACM 34(11): 40-51(1991) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Gupta et al. 1994]
Ashish Gupta, Yehoshua Sagiv, Jeffrey D. Ullman, Jennifer Widom: Constraint Checking with Partial Information. PODS 1994: 45-55 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Guttman 1984]
Antonin Guttman: R-Trees: A Dynamic Index Structure for Spatial Searching. SIGMOD Conference 1984: 47-57 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Hull and King 1987]
Richard Hull, Roger King: Semantic Database Modeling: Survey, Applications, and Research Issues. ACM Comput. Surv. 19(3): 201-260(1987) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Hulsmann and Saake 1990]
Klaus Hülsmann, Gunter Saake: Representation of the Historical Information Necessary for Temporal Integrity Monitoring. EDBT 1990: 378-392 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Ibaraki and Katoh 1983]
Toshihide Ibaraki, Naoki Katoh: On-Line Computation of Transitive Closures of Graphs. Inf. Process. Lett. 16(2): 95-97(1983) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Italiano 1988]
Giuseppe F. Italiano: Finding Paths and Deleting Edges in Directed Acyclic Graphs. Inf. Process. Lett. 28(1): 5-11(1988) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Jarke and Koch 1984]
Matthias Jarke, Jürgen Koch: Query Optimization in Database Systems. ACM Comput. Surv. 16(2): 111-152(1984) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Jarke and Koubarakis 1989]
...
[Jeusfeld and Jarke 1991]
Manfred A. Jeusfeld, Matthias Jarke: From Relational to Object-Oriented Integrity Simplification. DOOD 1991: 460-477 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Khshafian and Copeland 1986]
Setrag Khoshafian, George P. Copeland: Object Identity. OOPSLA 1986: 406-416 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Kuchenhoff 1991]
Volker Küchenhoff: On the Efficient Computation of the Difference Between Concecutive Database States. DOOD 1991: 478-502 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Neches et al. 1991]
...
[Nicolas 1982]
Jean-Marie Nicolas: Logic for Improving Integrity Checking in Relational Data Bases. Acta Inf. 18: 227-253(1982) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Plexousakis 1993a]
Dimitris Plexousakis: Integrity Constraint and Rule Maintenance in Temporal Deductive Knowledge Bases. VLDB 1993: 146-157 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Plexousakis 1993b]
...
[Plexousakis 1996a]
...
[Plexousakis and Mylopoulos 1996]
Dimitris Plexousakis, John Mylopoulos: Accomodating Integrity Constraints During Database Design. EDBT 1996: 497-513 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Schieber and Vishkin 1988]
Baruch Schieber, Uzi Vishkin: On Finding Lowest Common Ancestors: Simplification and Parallelization. SIAM J. Comput. 17(6): 1253-1262(1988) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Shrufi 1994]
Adel Shrufi: Performance of Clustering Policies in Object Bases. CIKM 1994: 80-87 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Silberschatz and Kedem 1980]
Abraham Silberschatz, Zvi M. Kedem: Consistency in Hierarchical Database Systems. J. ACM 27(1): 72-80(1980) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Snodgrass 1987]
Richard T. Snodgrass: The Temporal Query Language TQuel. ACM Trans. Database Syst. 12(2): 247-298(1987) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Stanley 1986]
...
[Steinbrunn et al. 1993]
...
[Stickel 1985]
Mark E. Stickel: Automated Deduction by Theory Resolution. IJCAI 1985: 1181-1186 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Stonebraker 1975]
Michael Stonebraker: Implementation of Integrity Constraints and Views by Query Modification. SIGMOD Conference 1975: 65-78 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Stonebraker and Dozier 1991]
...
[Tay 1987]
...
[Topaloglou 1993]
Thodoros Topaloglou: Storage Management for Knowledge Bases. CIKM 1993: 95-104 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Topaloglou et al. 1992]
Thodoros Topaloglou, Arantza Illarramendi, Licia Sbattella: Query Optimization for KBMSs: Temporal, Syntactic and Semantic Transformantions. ICDE 1992: 310-319 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Ullman 1988]
Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume I. Computer Science Press 1988, ISBN 0-7167-8158-1
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Valduriez 1987]
Patrick Valduriez: Join Indices. ACM Trans. Database Syst. 12(2): 218-246(1987) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Valduriez et al. 1986]
Patrick Valduriez, Setrag Khoshafian, George P. Copeland: Implementation Techniques of Complex Objects. VLDB 1986: 101-110 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Vilain et al. 1989]
Marc B. Vilain, Henry A. Kautz: Constraint Propagation Algorithms for Temporal Reasoning. AAAI 1986: 377-382 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Wallace 1991]
Mark Wallace: Compiling Integrity Checking into Update Procedures. IJCAI 1991: 903-910 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Yannakakis 1982]
Mihalis Yannakakis: A Theory of Safe Locking Policies in Database Systems. J. ACM 29(3): 718-740(1982) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Yao 1977]
S. Bing Yao: Approximating the Number of Accesses in Database Organizations. Commun. ACM 20(4): 260-261(1977) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Zdonik and Maier 1989]
Stanley B. Zdonik, David Maier (Eds.): Readings in Object-Oriented Database Systems. Morgan Kaufmann 1990, ISBN 1-55860-000-0
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Last update Fri Sep 14 18:29:11 2012 CET by the DBLP TeamThis material is Open Data Data released under the ODC-BY 1.0 license — See also our legal information page