Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Recently developed inferential database systems face some common problems: a very fast growth of search space and difficulties in recognizing inference termination (especially for recursive axioms). These shortcomings stem mainly from the fact that the inference process is usually separated from database operations. A problem-oriented inferential system i8 described which refers to the database prior to query (or subquery) processing, so that the inference from the very beginning is directed by data relevant to the query. A multiprocessor implementation of the system is presented based on a computer network conforming to database relations and axioms. The system provides an efficient indication of query termination, and is complete in the sense that it produces all correct answers to a query in a finite time.

REFERENCES

• 1: Dennis de Champeaux, Bidirectional Heuristic Search Again, Journal of the ACM (JACM), v.30 n.1, p.22-32, Jan. 1983 [doi>10.1145/322358.322360]
• 2: Chin-Liang Chang , Richard C. Lee , Richard Char-Tung Lee, Symbolic Logic and Mechanical Theorem Proving, Academic Press, Inc., Orlando, FL, 1997
• 3: CHANG, C.-L. DEDUCE--a deductive query language for relational data bases. In Artificial Intelligence and Pattern Recognition, C. G. Chen, Ed., Academic Press, New York, 1976, 108-134.
• 4: CHANa, C.-L. DEDUCE 2: Further investigations of deduction in relational data bases. In Logic and Data Bases, H. Gatlaire and J. Minker, Eds., Plenum Press, New York, 1978, 201-236.
• 5: CHANG, C.-L. On evaluation of queries containing derived relations in a relational data base. In Advances in Data Base Theory, vol. 1, H. Gallaire, J. Minker, and J.-M. Nicolas, Eds., 1981, 235-260.
• 6: CLARK, K.L. Negation as failure. In Logic and Data Bases, H. Gallaire and J. Minker, Eds., Plenum Press, New York, 1978, 77-106.
• 7: E. F. Codd, A relational model of data for large shared data banks, Communications of the ACM, v.13 n.6, p.377-387, June 1970 [doi>10.1145/362384.362685]
• 8: Yasunori Dohi , Akira Suzuki , Noriyuki Matsui, Hardware sorter and its application to data base machine, Proceedings of the 9th annual symposium on Computer Architecture, p.218-225, April 26-29, 1982, Austin, Texas, United States
• 9: FISt}MAN, D. H. A problem-oriented search procedure for theorem proving. IEEE Trans. Comput. C-25, 8 {Aug. 1976), 807-815.
• 10: GALLAIRE, H., MINKER, J., AND NICOLAS, J.M. An overview and introduction to logic and data bases. In Logic and Data Bases, H. Gallaire and J. Minker, Eds., Plenum Press, New York, 1978, 3-32.
• 11: Roger L. Haskin , Lee A. Hollaar, Operational characteristics of a harware-based pattern matcher, ACM Transactions on Database Systems (TODS), v.8 n.1, p.15-40, March 1983 [doi>10.1145/319830.319832]
• 12: HENSCHEN, L. J., AND NAQVI, S.A. On compiling queries in recursive first-order databases. In Proceedings of the Workshop on Logical Bases for Data Bases (Toulouse, 1982), J.-M. Nicolas, Ed.
• 13: Lawrence J. Henschen , Shamim A. Naqvi, On compiling queries in recursive first-order databases, Journal of the ACM (JACM), v.31 n.1, p.47-85, Jan. 1984 [doi>10.1145/2422.2423]
• 14: C. A. R. Hoare, Communicating sequential processes, Communications of the ACM, v.21 n.8, p.666-677, Aug. 1978 [doi>10.1145/359576.359585]
• 15: HORN, A. On sentences which are true of direct unions of algebras. J. Symb. Logic I6 (1951), 14-21.
• 16: HSlAO, D. K. Data base computers. In Advances in Computers I9, M. C. Yovits, Ed., 1980, 1-64.
• 17: KELLOGG, C., KLAHR, P., AND TRAVIS, L. Deductive planning and pathfinding for relational data bases. In Logic and Data Bases, H. Gallaire and J. Minker, Eds., Plenum Press, New York, 1978, 179-200.
• 18: KLAHR, P. Planning techniques for rule selection in deductive question-answering. In Pattern- Directed Inference Systems, D. A. Waterman and F. Hayes-Roth, Eds., Academic Press, New York, 1978, 223-240.
• 19: KOWALSKI, R. And-or graphs, theorem-proving graphs and bi-directional search. In Machine Intelligence 7, B. Meltzer and D. Michie, Eds., Edinburgh University Press, 1973, 167-194.
• 20: Robert Kowalski, A Proof Procedure Using Connection Graphs, Journal of the ACM (JACM), v.22 n.4, p.572-595, Oct. 1975 [doi>10.1145/321906.321919]
• 21: KOWALSK~, R. Logic for data description. In Logic and Data Bases, H. Gallaire and J. Minker, Eds., Plenum Press, New York, 1978, 77-106.
• 22: McKAv, D. P., AND SHAPmO, S.C. Using active connection graphs for reasoning with recursive rules. In Proceedings of the 7th International Joint Conference on Artificial Intelligence (Vancouver, 1981), 368-374.
• 23: Jack Minker, Performing inferences over relation data bases, Proceedings of the 1975 ACM SIGMOD international conference on Management of data, May 14-16, 1975, San Jose, California [doi>10.1145/500080.500092]
• 24: Jack Minker, Search strategy and selection function for an inferential relational system, ACM Transactions on Database Systems (TODS), v.3 n.1, p.1-31, March 1978 [doi>10.1145/320241.320242]
• 25: MtNKER, J. An experimental relational data base system based on logic. In Logic and Data Bases, H. Gallaire and J. Minker, Eds., Plenum Press, New York, 1978, 107-148.
• 26: MINKER, J., AND NICOLAS, J.-M. On recursive axioms in deductive databases. In/. Syst. 8, 1 (1983), 1-13.
• 27: NAQvI, S. A., AND HENSCHEN, L.J. Performing inferences over recursive databases. In Proceedings 1st Annual National Conference on Artificial Intelligence (Stanford, 1980), 263-265.
• 28: NICOLAS, J.-M., AND GALLAIRE, H. Data base: Theory vs. interpretation. In Log& and Data Bases, H. Gallaire and J. Minker, Eds., Plenum Press, New York, 1978, 33-54.
• 29: NICOLAS, J.-M., AND YAZDANIAN, K. Integrity checking in deductive data bases. In Log/c and Data Bases, H. Gallaire and J. Minker, Eds., Plenum Press, New York, 1978, 325-346.
• 30: Nils J. Nilsson, Problem-Solving Methods in Artificial Intelligence, McGraw-Hill Pub. Co., 1971
• 31: POHL, I. Bi-directional search. In Machine Intelligence 6, B. Meltzer and D. Michie, Eds., Edinburgh University Press, 1971, 127-140.
• 32: PRAMANIK, S. B. Highly parallel associative search and its application to cellular database machine design. In Proceedings AFIPS National Computer Conference (1981), vol. 50, 521-528.
• 33: RELIER, R. On structuring a first-order data base. In Proceedings 2nd National Conference of the Canadian Society on Computational Studies of Intelligence (Toronto, 1978), R. Perrault, Ed., 90-99.
• 34: REITER, R. On closed-world data bases. In Logic and Data Bases, H. Gallaire and J. Minker, Eds., Plenum Press, New York, 1978, 55-76.
• 35: REITER, R. Deductive question-answering on relational data bases. In Logic and Data Bases, H. Gallaire and J. Minker, Eds., Plenum Press, New York, 1978, 149-177.
• 36: SHAPIRO, S. C., AND McKAY, D.P. Inference with recursive rules. In Proceedings 1st Annual National Conference on Artificial Intelligence (Stanford, i980), 151-153.
• 37: John C. Shepherdson, Negation as failure: a comparison of Clark's completed data base and Reiter's closed world assumption, Journal of Logic Programming, v.1 n.1, p.51-79, June 1984 [doi>10.1016/0743-1066(84)90023-2]
• 38: Jeffrey D. Ullman, Principles of Database Systems, W. H. Freeman & Co., New York, NY, 1983
• 39: Jeffrey D. Ullman, Implementation of logical query languages for databases, ACM Transactions on Database Systems (TODS), v.10 n.3, p.289-321, Sept. 1985 [doi>10.1145/3979.3980]
• 40: Gordon J. VanderBrug , Jack Minker, State-space problem-reduction, and theorem proving—some relationships, Communications of the ACM, v.18 n.2, p.107-119, Feb. 1975 [doi>10.1145/360666.360672]

INDEX TERMS

Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.3 Other Architecture Styles
          Subjects: Data-flow architectures

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.3 Deduction and Theorem Proving
          Subjects: Deduction (e.g., natural, rule-based)

General Terms:
Algorithms, Design, Performance, Theory, Verification