Jack Minker
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.
- 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.Google Scholar
- 2 CHANG, C.L., AND SLAGLE, J.R. An admissible and optimal algorithm for searching AND/ OR graphs. Artif. Intel. ~ (1971), 117-128.Google Scholar
- 3 FISHMAN, D.H. Experiments with a resolution-based deductive question-answering system and a proposed clause representation for parallel search. Ph.D. Th., Tech. Rep. TR-280, Dept. of Comptr. Sci., U. of Maryland, College Park, Md., 1973. Google ScholarDigital Library
- 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.Google Scholar
- 5 FISHMAN, D.H. A problem oriented search procedure for theorem proving. IEEE Trans. Complrs. C-25, 8 (Aug. 1976), 807-815.Google ScholarDigital Library
- 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.Google ScholarCross Ref
- 7 HEWITT, C. Procedural embedding of knowledge in PLANNER. Proc. IJCAI, British Comptr. Soc., London, 1971, pp. 167-182.Google Scholar
- 8 HILL, }~. LUSH resolution and its completeness. DCL Memo No. 78, School of Artif. Intel., U. of Edinburgh, Edinburgh, Scotland, Aug. 1974, p. 30.Google Scholar
- 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.Google ScholarCross Ref
- 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.Google Scholar
- 11 KOWALSXI, R. Predicate logic as programming language. Information Processing 74, North-Holland Pub. Co., Amsterdam, 1974, pp. 569-574.Google Scholar
- 12 ~OWALSKI, R., AND KUEHNER, D. Linear resolution with selection function. Artif. Intel. 2, 3/4 (1971), 221-260.Google Scholar
- 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.Google Scholar
- 14 LUCKHAM, }:)., AND NILSSON, N.J. Extracting information from resolution proof trees. Arlif. Intel. 2 1 (Spring 1971), 198-213.Google Scholar
- 15 MISxER, J. Performing inferences over relational d~tab~ses. ACM SIGMOD Int. Conf. on Management of Data, May 1975, San Jose, Calif., pp. 79-91. Google ScholarDigital Library
- 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.Google Scholar
- 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.Google Scholar
- 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.Google ScholarCross Ref
- 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.Google Scholar
- 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.Google Scholar
- 21 NILSSON, N.J. Problem Solving Methods in Artificial Intelligence. McGraw-Hill, New York, 1971. Google ScholarDigital Library
- 22 POWELL, P. Answer--reason extraction in a parallel relational database. M.S. Th. (draft copy), Dept. Comptr. Sci., College Park, Md., 1976.Google Scholar
- 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.Google Scholar
- 24 ROBINSON, J.A. A machine oriented logic based on the resolution principle. J. ACM 12, 1 (Jan. 1965), 23-41. Google ScholarDigital Library
- 25 STONEBRAKER, M. Implementation of integrity constraints and views by query modification. Proc. ACM SIGMOD Int. Conf. on Management of Data, San Jose, Calif., May 1975, 65--78. Google ScholarDigital Library
- 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.Google Scholar
- 27 YANwRBRuG, G.J. A geometric analysis of heuristic search. Proc. AFIPS 1976 NCC, AFIPS Press, Montvale, N.J., pp. 979--986.Google Scholar
- 28 VANDERBRUG~ G., AND MINKER, J. State-space, problem-reduction, and theorem provingsome relationships. Comm. ACM 18, 2 (Feb. 1975), 107-115. Google ScholarDigital Library
Index Terms
- Search strategy and selection function for an inferential relational system
Recommendations
Inductive Database Relations
The concept of an inductive relation is introduced, as a natural development of other forms of intentional information, such as views and relations defined deductively. A class of top-down methods for computing such inductive relations is analyzed. ...
Inductive Learning in Deductive Databases
Most current applications of inductive learning in databases take place in the context of a single extensional relation. The authors place inductive learning in the context of a set of relations defined either extensionally or intentionally in the ...
Comments