Search strategy and selection function for an inferential relational system

ABSTRACT

An inferential relational system is one in which data in the system consists of both explicit facts and general axioms (or “views”). The general axioms are used together with the explicit facts to derive the facts that are implicit (virtual relations) within the system. A top-down algorithm, as used in artificial intelligence work, is described to develop inferences within the system. The top-down approach starts with the query, a conjunction of relations, to be answered. Either a relational fact solves a given relation in a conjunct, or the relation is replaced by a conjunct of relations which must be solved to solve the given relation. The approach requires that one and only one relation in a conjunction be replaced (or expanded) by the given facts and general axioms. The decision to expand only a single relation is termed a selection function. It is shown for relational systems that such a restriction still guarantees that a solution to the problem will be found if one exists. The algorithm provides for heuristic direction in the search process. Experimental results are presented which illustrate the techniques. A bookkeeping mechanism is described which permits one to know when subproblems are solved. It further facilitates the outputting of reasons for the deductively found answer in a coherent fashion.

REFERENCES

• 1: CHANG, C. Deduce--a deductive query language for relational databases. In Artificial Intelligence and Pattern Recognition, C.G. Chen, Ed., Academic Press, New York, 1976, pp. 108--134.
• 2: CHANG, C.L., AND SLAGLE, J.R. An admissible and optimal algorithm for searching AND/ OR graphs. Artif. Intel. ~ (1971), 117-128.
• 3: Daniel Herbert Fishman, Experiments with a resolution-based deductive question-answering system and a proposed clause representation for parallel search., 1973
• 4: FISnMAS, D.H. Experiments with a deductive question-answering system. Tech. P~ep. 74C-10, Comptr. and Inform. Sci. Dept., U. of Massachusetts, Amherst, Mass., 1974.
• 5: FISHMAN, D.H. A problem oriented search procedure for theorem proving. IEEE Trans. Complrs. C-25, 8 (Aug. 1976), 807-815.
• 6: HART, P., NILSSON, N., AND RAPHAEL, B. A formal basis for the heuristic determination of minimum cost graphs. IEEE Trans. Syst. Sci. Cybernet. SSC-$, 2 (July 1968), 100-107.
• 7: HEWITT, C. Procedural embedding of knowledge in PLANNER. Proc. IJCAI, British Comptr. Soc., London, 1971, pp. 167-182.
• 8: HILL, }~. LUSH resolution and its completeness. DCL Memo No. 78, School of Artif. Intel., U. of Edinburgh, Edinburgh, Scotland, Aug. 1974, p. 30.
• 9: K~EBURTZ, R.B., AND LUCKItAM, D. Compatibility and complexity of refinements of the resolution principle. SIAMJ. Comput. I, 4 (Dec. 1972), 313-332.
• 10: KOW,~LSKI, R. Search strategies for theorem proving. In Machine Intelligence 5, B. Meltzer and D. Miehie, Eds., American Elsevier, New York, 1970, pp. 181-200.
• 11: KOWALSXI, R. Predicate logic as programming language. Information Processing 74, North-Holland Pub. Co., Amsterdam, 1974, pp. 569-574.
• 12: ~OWALSKI, R., AND KUEHNER, D. Linear resolution with selection function. Artif. Intel. 2, 3/4 (1971), 221-260.
• 13: KUEHNER, D. Strategies for improving the e~ciency of automatic theorem proving. Ph.D. Th., DCL Memo No. 72, School of Artif. Intel., U. of Edinburgh, Edinburgh, Scotland, May 1971.
• 14: LUCKHAM, }:)., AND NILSSON, N.J. Extracting information from resolution proof trees. Arlif. Intel. 2 1 (Spring 1971), 198-213.
• 15: 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]
• 16: MIN~ER, g. Set operations and inferences over relational databases. Proc. Fourth Tex. Conf. on Comptng. Syst., Nov. 1975, pp. 5A-l.l-5A-l.10.
• 17: MINKER, J. Binary relations, matrices and inference developments. Tech. Rep. TR-466, Dept. of Comptr. Sci., U. of Maryland, College Park, Md., July 1976, p. 40.
• 18: MINKER, J., ~-~ISHMAN, D.H., AND McSKIMIN, 5.R. The Q* algorithm--a search strategy for a deductive question-answering system. Artif. Intel. 4 (1973), 225-243.
• 19: MINKEII, J., McSKIMIN, J.R., AND FISHMAN, D.H. MRPPS--an interactive refutation proof procedure system for question-answering. Int. J. Comptr. and Inform. Sci. 8, 2 (June 1974), 105-122.
• 20: MINKER, J., AND WII, SON, G.A. A note on answer-extraction in resolution-based theorem proving. Tech. Note TR 447, Comptr. Sci. Dept., U. of Maryland, College Park, Md., March 1976. To appear in Int. J. Comptrs. and Inform. Sci.
• 21: Nils J. Nilsson, Problem-Solving Methods in Artificial Intelligence, McGraw-Hill Pub. Co., 1971
• 22: POWELL, P. Answer--reason extraction in a parallel relational database. M.S. Th. (draft copy), Dept. Comptr. Sci., College Park, Md., 1976.
• 23: REHERT, M. A bookkeeping strategy for implementing the arbitrary selection functions in MRPPS 3.0. Scholarly M.S. Paper, Dept. Comptr. Sci., U. of Maryland, College Park, Md., 1976.
• 24: J. A. Robinson, A Machine-Oriented Logic Based on the Resolution Principle, Journal of the ACM (JACM), v.12 n.1, p.23-41, Jan. 1965 [doi>10.1145/321250.321253]
• 25: Michael Stonebraker, Implementation of integrity constraints and views by query modification, Proceedings of the 1975 ACM SIGMOD international conference on Management of data, May 14-16, 1975, San Jose, California [doi>10.1145/500080.500091]
• 26: SUSSMAN, G.J., AND McDEaMOTT, D.V. From PLANNER to CONNIVER--a genetic approach. Proc. AFIPS 1972 FJCC, AFIPS Press, Montvale, N.J., pp. 1171-1179.
• 27: YANwRBRuG, G.J. A geometric analysis of heuristic search. Proc. AFIPS 1976 NCC, AFIPS Press, Montvale, N.J., pp. 979--986.
• 28: 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

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Relational databases

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Search process

General Terms:
Design

Keywords:
answer and reason extraction, heuristics, inference mechanism, logic, predicate calculus, relational databases, search strategy, selection function, top-down search, virtual relations