Search
1989 Volume 4
Article Contents
RESEARCH ARTICLE   Open Access    

Computer architectures for logic-oriented data/knowledge bases1

More Information
  • Abstract: Knowledge base management systems (KBMS) are designed to efficiently retrieve and manipulate large shared knowledge bases. A significant subclass of KBMS consisting of a combination of logic programming and database is often called a logic oriented knowledge base system (LOKBS). These systems must possess considerable processing and I/O capabilities so many approaches have been taken to the improvement of their performance. In this paper we review the current performance enhancing hardware approaches for LOKBS. We include parallelism, both in processing and I/O, algorithms, caching, and physical data organizations.
  • 加载中
  • Abe S, Bandoh T, Yamaguchi S, Kurosawa K and Kiriyama K, 1987. “High performance Integrated Prolog Processor IPP” In: Proceedings of the 14th Annual Symposium on Computer Architecture, pp 100–107.

    Google Scholar

    Aho AV and Ullman JD, 1979. “Universality of data retrieval languages” In: ACM Symposium on Principles of Programming Languages, pp 110–117

    Google Scholar

    Berra PB, Chung SM and Hachem N, 1987. “Computer architecture for a surrogate file to a very large data/knowledge base”, IEEE Computer20(3) pp 25–32

    Google Scholar

    Berra PB and Oliver E, 1979. “The role of associative array processors in database machine architecture”, IEEE Computer12(3) pp 53–61

    Google Scholar

    Boral H and DeWitt DJ, 1983. “Database machines: An idea whose time has passed? A critique of the future of database machines” In: Proceedings of 3rd International Workshop on Database Machines, pp 166–187

    Google Scholar

    Boral H and Redfield S, 1985. “Database machine morphology” In: Proceedings of 11th International Conference on VLDB, pp 59–71

    Google Scholar

    Comer D, 1979. “The ubiquitous B-tree”, ACM Computing Surveys11(2) pp 121–137

    Google Scholar

    Conery JS, 1987. Parallel Execution of Logic Programs, Kluwer Academic Publishers: Boston, Massachusetts

    Google Scholar

    Dadam P, 1986. “A DBMS prototype to support extended NF2 relations: an integrated view on flat tables and hierarchies” In: Proceedings of SIGMOD '86, pp 356–367

    Google Scholar

    DeWitt DJ and Gerber R, 1985. “Multiprocessor hash-based join algorithms” In: Proceedings of the 11th International Conference on Very Large Data Bases, pp 151–164

    Google Scholar

    Dorby T, 1987. “A coprocessor for AI; LISP, Prolog and data bases” In: COMPCON Spring '87, pp 396–402

    Google Scholar

    Dorby TP, Despain AM and Patt YN, 1985. “Performance studies of a Prolog machine architecture” In: Proceedings of the 12th Symposium on Computer Architectures, pp 180–190

    Google Scholar

    Dorby TP, Patt YN and Despain AM, 1984. “Design decisions influencing the microarchitecture for a Prolog machine” In: Micro 17 Proceedings, pp 217–231

    Google Scholar

    Dwork C, Kanellakis P and Mitchell J, 1984. “On the sequential nature of unification” Journal of Logic Programming1 pp 35–50

    Google Scholar

    Fagin BS and Despain AM, 1987. “Performance studies of a parallel Prolog architecture” In: Proceedings of the 14th Annual Symposium on Computer Architecture, pp 108–116

    Google Scholar

    Fuchi K and Furukawa K, 1986. “The role of logic programming in the fifth generation computer project” In: Proceedings of the Third International Conference on Logic Programming, pp 1–24

    Google Scholar

    Gonzalez-Rubio R, Rohmer J, Bradier A and Bergsten B, 1987. “DDC: a deductive database machine” In: Proceedings of the Fifth International Workshop on Database Machines, pp 116–129

    Google Scholar

    Hahne K, Pilgram P, Schuett D, Schweppe H and Wolf G, 1985. “Associative processing in standard and deductive databases” In: DeWitt DJ and Boral H, eds, Database Machines—Fourth International Workshop, New York: Springer-Verlag, pp 1–12

    Google Scholar

    Harland J and Jaffar J, 1987. “On parallel unification for Prolog” New Generation Computing5 pp 259–279

    Google Scholar

    Hillyer BK and Shaw DE, 1986. “Execution of OPS5 production systems on a massively parallel machine” Journal of Parallel and Distributed Computing3 pp 236–268

    Google Scholar

    Hwang K, Ghosh J and Chowkwanyun R, 1987. “Computer architectures for artificial intelligence processing” IEEE Computer20(1) pp 19–27

    Google Scholar

    Itoh H, 1988. “Knowledge base system in logic programming paradigm” In: Proceedings of the 1988 International Conference on Fifth Generation Computer Systems

    Google Scholar

    Kellog C, 1986. “From data management to knowledge management” IEEE Computer19(1) pp 75–84

    Google Scholar

    Kim MY, 1986. “Synchronized disk interleaving” IEEE Transactions on Computers C-35(11) pp 978–988

    Google Scholar

    Li D, 1984Prolog Database System, London: Research Studies Press

    Google Scholar

    Li G and Wah BW, 1985. “MANIP-2: a multicomputer architecture for evaluating logic programs” In: Proceedings of the International Conference on Parallel Processing, pp 123–130

    Google Scholar

    Lipovski GJ, 1978. “Semantic paging on intelligent disks” In: Proceedings of the Fourth Workshop on Computer Architecture for Non-Numeric Processing, pp 30–34

    Google Scholar

    Lipovski GJ and Hermenegildo MV, 1985. “B-LOG: a branch and bound methodology for the parallel execution of logic programs” In: Proceedings of International Conference on Parallel Processing,, pp 123–130

    Google Scholar

    Nakazaki R, 1985. “Design of a high-speed Prolog machine (HPM)” In: Proceedings of the 12th International Symposium on Computer Architectures, pp 191–197

    Google Scholar

    Nievergelt J, Hinterberger H and Sevcik KC, 1984. “The grid file: an adaptable, symmetric multikey file structure” ACM Transactions on Database Systems9(1) pp 38–71

    Google Scholar

    Noye J and Syre J-C, 1987. “ICM3: design and evaluation of an inference crunching machine” In: Proceedings of the 5th International Workshop on Database Machines, pp 1–14

    Google Scholar

    Ozkarahan EA and Bozsahin CH, 1988. “Join strategies using data space partitioning” New Generation Computing6 pp 19–39

    Google Scholar

    Qadah GZ, 1985. “Database machines: a survey” In: National Computer Conference, pp 212–223

    Google Scholar

    Ramamohanarao K and Shepherd J, 1986. “A superimposed codeword indexing scheme for very large Prolog databases” In: Proceedings of the 3rd International Conference on Logic Programming, pp 569–576

    Google Scholar

    Ribler RL, 1987. “The integration of the Xenologic X-l artificial intelligence coprocessor with general purpose computers” In: COMPCON Spring '87, pp 403–407

    Google Scholar

    Robinson P, 1985. “The SUM: an AI coprocessor” Byte10(6) pp 169–180

    Google Scholar

    Roth MA, Korth HF and Batory DS, 1987. “SQL/NF: a query language for ⌝1NF relational databases” Information Systems132(1) pp 99–114

    Google Scholar

    Sabbatel GB and Dang W, “Search strategy for Prolog data bases” In: Proceedings of the 5th International Workshop on Database Machines, pp 654–667

    Google Scholar

    Sakai H, 1986. “Development of Delta as a first step to a knowledge base machine” In: Sood AK and Qureshi AH, eds, Database MachinesNew York: Springer-Verlag, pp 159–181

    Google Scholar

    Schneider H-A and Dilger W, 1986. “Information processing with associative processors” In: Proceedings of the Conference on Algorithms and Hardware for Parallel Processing, pp 222–229

    Google Scholar

    Shaw D, 1985. “Relational query processing on the Non-Von supercomputer” In: Kim W, Reiner DS and Batory DS, eds, Query Processing in Database Systems, New York: Springer-Verlag, pp 248–258

    Google Scholar

    Shin D and Berra PB, 1989. “Surrogate file approach to managing first order terms in secondary storage” In: Proceedings of the SPIE Conference on Applications of AI VII, pp 1051–1062

    Google Scholar

    Shobatake Y and Aiso H, 1986. “A unification processor based on a uniformly structured cellular hardware” In: Proceedings of the 13th International Symposium on Computer Architectures, pp 140–148

    Google Scholar

    Stolfo SJ, 1987. “Initial performance of the DADO 2 prototype” IEEE Computer20(1) pp 75–83

    Google Scholar

    Stone HS, 1987. “Parallel querying of large databases: a case study” IEEE Computer20(10) pp 11–21

    Google Scholar

    Stormon CD, 1986. An Associative Processor and Its Application to Logic Programming Computation Technical Report 8611, Syracuse University-CASE Center

    Google Scholar

    Su SYW, 1988. Database Computers—Principles, Architectures, and Techniques, New York: McGraw-Hill

    Google Scholar

    Su SYW and Emam A, 1978. “CASDAL: CASSM's DAta Language” ACM Transations on Database Systems3(1) pp 57–91

    Google Scholar

    Su SYW, Nguyen LH, Emam A and Lipovski GJ, 1979. “The architectural features and implementation techniques of the multiceli CASSM” IEEE Transactions on Computers C–28(6) pp 430–445

    Google Scholar

    Tanabe M and Aiso H, 1987. “The unification processor by pipeline method” In: Proceedings of the 5th International Workshop on Database Machines, pp 668–680

    Google Scholar

    Tanaka Y, 1986. “Massive parallel database computer MPDC and its control schemes for massively parallel processing” In: Sood AK and Qureshi AH, eds, Database Machines, New York: Springer-Verlag, pp 127–158

    Google Scholar

    Tanaka Y, 1984. “A multiport page-memory architecture and a multiport disk-cache system” New Generation Computing2 pp 241–260

    Google Scholar

    Taylor S, 1984. “Logic programming using parallel associative operations” In: Proceedings of the 1984 International Symposium on Logic Programming, pp 58–68

    Google Scholar

    Taylor S, Maio C, Stolfo SJ and Shaw DE, 1983. Prolog on the DADO Machine: A Parallel System for High-Speed Logic Programming Technical Report CUCS-46–83, Columbia University

    Google Scholar

    Thinking Machines Technical Report HA87–4, 1987. Connection Machine Model CM-2 Technical Summary Thinking Machines Co

    Google Scholar

    Treleaven PC and Refenes AN, 1986. “Computer architecture for artificial intelligence” In: Proceedings of the Advance Courses on Future Parallel Computers, pp 416–492

    Google Scholar

    Vitter JS and Simons RA, 1986. “New classes for parallel complexity: a study of unification and other complete problems for P” IEEE Transactions on Computers C–35(5) pp 403–418

    Google Scholar

    Wada M, Morita Y, Yamazaki H, Yamashita S, Miyazaki N and Itoh H, 1987. ‘A superimposed code scheme for deductive databases” In: Proceedings of the 5th International Workshop on Database Machines, pp 569–582

    Google Scholar

    Wah BW, Li G and Yu CF, 1989. “The status of MANIP—a multicomputer architecture for solving combinatorial extremum-search problems” In: Proceedings of the 11th Annual Symposium on Computer Architecture, pp 56–63

    Google Scholar

    Warren DHD, 1983. An Abstract Prolog Instruction Set Technical Report 306, SRI International

    Google Scholar

    Woo NS, 1985a. “The architecture of the hardware unification unit and an implementation” In: Micro 18 Proceedings, pp 89–98

    Google Scholar

    Woo NS, 1985b. “A hardware unification unit: design and analysis” In: Proceedings of the 12th International Symposium on Computer Architectures, pp 198–205

    Google Scholar

    Yasuura H, 1989. “On parallel computational complexity of unification” In: Proceedings of the International Conference on Fifth Generation Computer Systems, pp 235–243

    Google Scholar

    Yokota H and Itoh H, 1986. “A model and an architecture for a relational knowledge base” In: Proceedings of the 13th International Symposium on Computer Architectures, pp 2–9

    Google Scholar

    Yu CF and Wah BW, 1983.“Virtual memory support for branch-and-bound algorithms” In: COMPSAC, pp 618–626

    Google Scholar

    Zaniolo C, 1985. “The representation and deductive retrieval of complex objects” In: Proceedings of the llth International Conference on VLDB, pp 21–23

    Google Scholar

  • Cite this article

    Donghoon Shin, P. Bruce Berra. 1989. Computer architectures for logic-oriented data/knowledge bases1. The Knowledge Engineering Review. 4: doi: 10.1017/S0269888900004720
    Donghoon Shin, P. Bruce Berra. 1989. Computer architectures for logic-oriented data/knowledge bases1. The Knowledge Engineering Review. 4: doi: 10.1017/S0269888900004720

Article Metrics

Article views(25) PDF downloads(272)

Other Articles By Authors

RESEARCH ARTICLE   Open Access    

Computer architectures for logic-oriented data/knowledge bases1

The Knowledge Engineering Review  4 Article number: 10.1017/S0269888900004720  (1989)  |  Cite this article

Abstract: Abstract: Knowledge base management systems (KBMS) are designed to efficiently retrieve and manipulate large shared knowledge bases. A significant subclass of KBMS consisting of a combination of logic programming and database is often called a logic oriented knowledge base system (LOKBS). These systems must possess considerable processing and I/O capabilities so many approaches have been taken to the improvement of their performance. In this paper we review the current performance enhancing hardware approaches for LOKBS. We include parallelism, both in processing and I/O, algorithms, caching, and physical data organizations.

    • Copyright © Cambridge University Press 19891989Cambridge University Press
References (66)
  • About this article
    Cite this article
    Donghoon Shin, P. Bruce Berra. 1989. Computer architectures for logic-oriented data/knowledge bases1. The Knowledge Engineering Review. 4: doi: 10.1017/S0269888900004720
    Donghoon Shin, P. Bruce Berra. 1989. Computer architectures for logic-oriented data/knowledge bases1. The Knowledge Engineering Review. 4: doi: 10.1017/S0269888900004720
  • Catalog

      /

      DownLoad:  Full-Size Img  PowerPoint
      Return
      Return