The Use of a Semantic Network in a Deductive Question-Answering System

1. Introduction

Semantic Networks have been used primarily in natural language applications to help disam­ biguate sentences and to understand natural language text. In this paper we consider the use of a semantic network to aid in the deductive search process of a Question-Answering (QA) Sys­ tem. The semantic network is based on an adapta­ tion of the predicate calculus and is described only briefly in this paper and more extensively by M:Skimin and Minker (M::Skimin [1976], and M::Skimin and Minker [1977]) . Terminology from the predicate calculus will be used throughout the paper.

Three ways will be discussed in which semantic information may be applied to help restrict deductive searches. These are:

1. To apply semantic information during the pattern-matching process (unification algorithm). t.bst ctrrrent pattern-matching systerns are based solely on syntactic tests. Using the semantic network, semantic constraints may be applied during the patternmatching process to inhibit data base assertions and general axioms that are semantically irrelevant to the search from entering into the deductive search space.
2. To apply semantic well-formedness tests to query and data base assertions input to the system so as to reject queries that have no answer because they violate semantic rest ric-

Jack Minker

Department of Computer Science University of Maryland College Park, Maryland 20742

tions. Thus, it should be possible to deter­ mine that a query such as ''Who is the pe:son who is both father and the mother of a g1ven individual?" is not answerable.

1. To identify those queries which have a ~wn maximum number of solutions so as to teTIDl.- nate searches for additional answers once the known fixed number is found.

The semantic net\\Urk discussed in this paper is described briefly in Section 2. In Section 3, we describe how the semantic network may be used to solve some of the problems associated with the above items. An example which illustrate~ the use of the semantic network is presented 1n Section 4. A surunary of the work and future directions is given in Section 5.

2. Semantic Network

Although the term 'semantic network' ~as been used extensively in the literattrre, there 1s no universal agreement as to what constitutes such a net\\Urk. Hence, we shall define the term in the context of this paper.

The semantic network to be described arose out of the need to provide meaning to objects in a domain and to statements made about these.obj ects so as to make deductive searches more ef­ ficient. Although the semantic network developed is used in deductive searches, it nevertheless bears considerable relationship to those developed through the need to unde~stand natural language by computers. The semantl.c network developed by Schubert [1976], for e~ple, bears many similarities to the one used here.

The semantic network described here is an adaptation of the predicate calc':llus and is able to express quantification, functl.<;>ns, . terms and logical connectives. The adaptatl.~n l.S b~ed upon the notation of Fishman and Minker (Fl.~~ [l973], Fishman and Minker [197~]), who mod1f1ed predicate calculus clause notat1on to handle sets of objects that have the same template structtrre.

The article by Schubert [1976] discusses many semantic network representations used for natural language processing, and surveys the literattrre so that we neither refer to nor compare our work on semantic networks with that achieved by others.

In order to implement the techniques described in the introduction, domain-dependent information nrust be stored in the computer in a form convenient for use. Consequently, a major part of this research has concerned the identifi­ cation of the types of semantic information to be stored, aro the development of structures in which to store the information. To this end, a collec­ tion of structures termed the "semantic netiDrk" has been developed which contains all information available to the question-answering-5ystem.

The semantic network consists of four com­ ponents: (1) the semantic ~aph which specifies the set-theoretic relation ~tween named subsets of the domain; (2) the data base of assertions and inference rules; (3) the semantic form saace which defines the semantic constraints place on arguments of relational n-tuples; and (4) the dictionary which defines the set membership for eaCh element of the domain. All four components of the semantic network are used by the techniques described above for making the QA process more efficient. Illustrations of how this information is used will be given in the next section.

(a) The Semantic Graph

The major emphasis of this effort is the investigation of techniques by which user-supplied semantic information may be stored in a computer and used to make the deductive inference process more efficient. The approach taken is to define explicitly the' contents of the domain of discourse D as well as the relationships in which various subsets of the domain may occur.

To this end, much of the work has involved the investigation of how one might subdivide the domain D into a finite mnnber of named subsets Si such that all elements of each Si have some set of properties in coJIIIDn. These sets are expressed as Boolean Category Expressions (BCE) . Examples are: senatorn malen--liberal, state, judge n laWyer. The names "senator", "state" and "judge" are examples of what are defined to be the sim­ plest type of BCE possible aro are called semantic categories. A BCE is any arbitrary combination of categories using the set operations of union (U), intersection (n) and complement (-). It is necessary to subdivide the domain D into subsets since certain relational statements may only be made about specified subsets of D, and one would like to make these subsets e~licit rather than implicit. This subdivision IS specified by a semantic graph Gs which defines how each category Cis subdivided into subsets Cl,Cz, .·. ,Cn and how each of the Ci is similarly defined. Figure 1 shows an example of such a graph. N::>te that both animate and living are the superset of animal; however animate is the superset of robot which is disjoint from l.iving, and living is the superset of plant which is disjoint from animate. Thus, animate and living overlap.

Subdividing D in this manner and defining where in the hierarchy each domain element lives (the function of the dictionary), has several ad­ vantages over expressing set memberships by unary relations. In particular, it should be computa­ tionally more efficient to perform trivial set membership inference using such a structure rather than by using unary relations. Thus, Sirica E judge might be stored in the dictionary rather than storing the unit clause JUDGE(Sirica) in the data base. The rationale for this choice is given in McSkimin [1976].

(b) Data Base

Assertions are facts, whereas general axioms are used to infer assertions about domain elements that are otherwise stored implicitly in the data base. Both types are stored m a ''Parallel clause" notation, termed 11-o notation, an extension of the IT-representation of Fishman and Minker. An exam­ ple of an assertion in n-o notation is: ((a,x,y), {{ [PARENr]/a, [Ruth,Herb]/x, [Anne,Carol,Jim]/y}}). The assertion states that Ruth and Herb are the parents of Anne, Carol and Jim. An example of a general axioin is: ( <v(a,x, y) v (S,x, y), { { [RESIDE]/ a , congressperson/x, state/y, [REPRESENf]/S}}). The axiom states that for all a, S, x, and y, if the object x is in the set con§lessperson, and the ob­ ject a is the predicate RES DE, and x resides in the set given by the state y, then the object x represents the state ~e first form represents 6 clauses in first-order predicate calculus. The second clause restricts the variable x to the set congressperson, while y is restricted to the set state.

A IT-a clause, in more specific terms, is an ordered pa1r, [ = (T,~) where T is a template which is like a first order predicate calculus clause, where T contains terms which are free of constants and predicates. Literals of the tem­ plate T are (n+l) ary tuples where the first tuple entry denotes the predicate name. ~ is a finite set of extended IT-substitution sets, ~ = {~1 , ... ,~}, where ~ e ~is the form~= {S1/vl, ... ,Sm/vm}, and where a IT-substitution compQnent S/v is an expression of the form S/v = ( [i>E,DX], DI/v). nE is a possibly empty finite set of con­ stants explicitly included in S; nX is a possibly empty finite set of constants explicitly excluded from S; DI is a possibly empty set of constants represented as a BCE and implicitly included in S; vis termed a placeholder (or a vp.riable). The following conditions hold: (1) nc n DI = ~; (2) nX s: DI.

A IT -substitution component indicates that v is universally quantified over the set nE U (DIn -DX). A IT-a literal is an ordered pair, (L,~), where Lis a literal template (i.e .· free of constants and predicates), and ~ is represented as an (n+l) ary tuple.

(c) Dictionary

For each predicate, constant and function name in the system, the dictionary lists the semantic category, of which it is a member. In addition, it defines the set of categories that are subsets of each category in the semantic graph Gs.

(d) Semantic Form Space

The semantic form space defines semantic con­ straints that are to be imposed on each argument of a predicate. Each semantic form defines what predicates, constants, or functions are legal to substitute into arguments of some subset Si of the possible set of n-tuples in the system. Not only are possible argument types stored, but so are possible combinations of types. An example of a semantic form is: ((a,x,y), {{[REPRESENT]/a , senator/x,state/y}, {[REPRESENT]/a,representa­ tive/x,state/y}}). That is, senators and repre­ sentatives can represent a state - no other BCE combinations are permitted. Additional informa­ tion is retained with a semantic form to count solutions possible for a given predicate. This is described in Section 3.3.1. The above constitutes the semantic network.

3. Use of the Semantic Network in Deductive QA Searches

The development of the semantic network is in­ tended to restrict the searCh for solutions to questions when a deductive search is required. There are three ways in which the search can be restricted. These are: (a) to semantically unify clauses; (b) to perform semantic well-formedness tests; and (c) to detect fully solved problems

(i.e., problems which, because of the knowledge of the domain of application, have a known maxiim..un number of solutions). Each of these three topics is discussed below.

3.1 Semantic Unification

Insisting that variables be restricted to specific domains, limits the domain of a variable more than is normally possible in the predicate calculus. In the first-order predicate calculus, all variables are universally quantified; because no restriction on the variables is possible, in order to unify two clauses, one must therefore assume that when one variable is to be substituted for another, that they belong to consistent do­ mains. However, if variables could be restricted e~licitly to disjoint domains, then no possible s stitution of one variable for the other can be made, and unification must therefore fail because of semantic considerations.

The details of a IT-a semantic unification are too cumbersome to describe in this paper; they are described by M::Skimin. We shall provide a brief summary of the tests needed to effect IT-a semantic unification. Two TI-a literals must unify syntactically to be considered for semantic unifi­ cation. When two variables are to be substituted for one another, an algorithm, called the CONFLICT algorithm, determines if the BCEs of the two variables overlap. If they do, a new variable whose BCE is the intersection of the two BCEs re­ places each variable. If the two BCEs are dis­ joint then the two variables are semantically in­ consistent since there exists no domain element that can be substituted for both. If a constant is to replace a variable with BCE B1, the constant must belong to some semantic category B2 such that B2s:B1. If a function is to be substituted for a variable, the BCE of the range of the function must be a subset of the BCE of the variable. In all of these areas the semantic graph is used to determine the relation between the two BCEs.

For example, consider the following IT- a clauses:

(1) (-v(a,x,y),{{[Jack]/x, [P]/a,human/y}})

(2) (-v( f3 l,ul>vl) v (a l,ul,vl),{{male/ul>h]jn/vl>

• ' TFJ!B1, [P a1}}) (3) (-v (f32,u2, v2) v (a2,u2, v2), { {female/u2,human/v2, l.MJTr32, [P] Ta2TI)

where male, female, and human are semantic cate­ gories, Jack E male, and rrru..e_ fl~ = ~ . In a first-order predicate calculus system, there is only one universal semantic category. Thus, human, female, and male do not appear and the variables are universally quantified over the en­ tire domain. In this case, two resolvents would result when resolving clause (1), with clause (2) and clause (3). However, with IT-a semantic unifi­ cation, there is only one resolvent that is ob­ tained from clause (1) and clause (2) . The IT-a literal, in clause (3), ((a2,u2,v2),{{[P]/a2 , female/u2,human/v2}}) cannot unify with ((a,x,y), Tf[PJla, [JaCK]lx,human/y} }) . This is so since a conflict exists as Jack E female. The CONFLICT routine would find that Jack E male by accessing the dictionary entry for Jack. ~e semantic graph would denote that male n female is empty, and the t\'.Q n-o literals would be prevented from unifying. Thus, clause (3) \'.Quld never be entered into the search space, so that it \'.QUld not lead to a deductive search path, thereby decreasing the time and space used over that of a purely syntac · tic pattern match.

Semantic unification is applied during the deductive search process. It is also applied when one is entering new facts or general rules into the system, and when a query is entered. These are described in the following sections.

3.2 Semantic Well-Formedness of n-o Clauses

One way in which the rr-o unification algorithm may be used is to perform semantic well-formedness tests on rr -o clauses input to a question-answering system. TI-o clauses are used in two different ways: both as assertions and general axioms to be stored in the data base, and as questions posed to the system. As noted previously, the data base comprises one part of the semantic net\'.Qrk. The data base stores facts about members of the do­ main (i.e., assertions) and provides general axioms that are used to deduce implicit assertions from those already known. Both of these are stored as n-o clauses.

The semantic form space defines how domain elements may interact; that is, in what corrtJina­ tions they may co-occur in rr-o clauses of the sys­ tem. In particular, semantic forms define the subsets of the domain UNIV from which arguments of relations must be chosen. It is necessary that all data base clauses conform to these rules. If data base clauses were stored that did not con­ form with these rules, incorrect deductions could be generated.

In addition, when a query is posed to a ~ system, it is useful to know if it is potentially unanswerable. A query may be unanswerable for several reasons. If a query makes reference to domain elements that are unknown to the system, then it is very unlikely that the questions about that object could be answered.

A query could also be unanswerable because it violates the constraints specified by the semantic form space. Thus, if one asked whether President Carter voted for a certain congressional bill, the system should answer that the question was not well-formed since only members of Congress may vote for bills and Carter is not a member of Con­ gress. Naturally, doing so requires the availa­ bility of a complete semantic net\'.Qrk including dictionary, semantic graph, and semantic form space. By rejecting such a query, it is possible to avoid a futile search for an answer which, as­ suming the data base is consistent, will never be found.

The purpose of the rr-o unification algorithm is to detect such discrepancies in both data base clauses and queries. This is done by unifying each rr-o literal L of an input clause against all semantic ·forms (which are stored in rr-o clause representation themselves). If some instance of the rr-o literal L fails to unify with any rr-o semmtic form in the semantic space, then that instance of the rr -o literal L does not conform with semantics because at least one of its argu­ ments conflicts with the corresponding argument of all semantic forms for that n-tuple size.

Although some instances of the n-o literal L might fail to unify with any semantic form, others may succeed. What is desirable therefore, is to transform a rr -o clause input to the system into one (or perhaps several) clauses that are entirely well-formed. These clauses may then be entered into the data base or input to the deductive mechanism as appropriate. Those instances failing to unify should be isolated and the user informed of the error. The semantic well-formedness al­ gorithm which does all of these things is given by McSkimin.

An important part of the well-formedness al­ gorithm is the unification of input literals against the semantic form space. Each semantic form F = (T,~) consists of a template T of the form: (v0 ,v1 , ··· ,vu) v Sand a rr-o set ~. The tuple (v0 , ··· ,vn) 1s called the distin~shed lit­ eral of F, and the literals in S are c led the semantic literals of F.

Unifying substitutions are also applied to the semantic literals which are carried along dur­ ing the process, appended to the query, during the deductive search to perform further semantic checks on a literal by retrieving or inferring in­ formation from the data base (rather than the semantic space) .

The tuple V = (v0,v1, ··· ,vn) along with the substitutions for the placeholder variables vi oc­ curring in ~ determine what elements of the domain may co-occur in arguments of an (n+l) tuple. If a portion of an input literal L unifies with some semantic form F on literal V, then that combina­ tion of predicate and domain elements is consider­ ed well-formed. If a literal L does not unify with any semantic form, then it is not well-formed since it conflicts with all possible ways that domain elements may be combined.

An example of semantic well-formedness, and how the semantic form S is used will now be given.

Example: Let F = ((a,x,y) v (13,x,y) { { [M]/a,. female/ x, animal / y,[EQUAL]/ 13 }}) be a semant1c form that determines the well-formedness of the ''roother" predicate. (a,x,y) is the dist~ished literal in the semantic form. The semant1c liter­ al (13,x,y) is used to indicate that if x arid y are equal then a semantic conflict has been de­ tected. For example, the following query, asking if Mary is her own mother, when resolved with the semantic form F, yields the new clause, ((13,x,y), {{ [M]/a, [Mary]/x, [Mary]/y, [EQUAL]/ 13}}).

The inferred n-o literal ((13,x,y),{{[EQUAL]/13, [Mary]/x, [Mary]/y}}), is not unified against the semantic forms since it descended from a semantic literal. Thus, all literals that came from the query have been successfully unified against the semantic form. The literal that remains is then appended to the query to form the new query: -v(a,x,y) v (13,x,y) { { [M]/a, [Mary]/x, [Mary]/y, [EQUAL]/13}}.

Before the proof mechanism starts to answer the query, a test is made to determine if there are any literals eligible for predicate evaluation. If there are, then they are evaluated. Thus, in this case, the proof mechanism evaluates the liter­ al (S,x,y) to true and the entire clause is there­ fore removed from the search space, which indi­ cates that the question is unanswerable. If the literals appended to the query are not eligible for predicate evaluation, they are treated as any other literal and must be resolved away in order for the query to be answered.

In this section it has been shown how seman­ tic constraints may be used to reject semantically inconsistent queries and data base assertions. The third use of the semantic network is given in the following section.

3.3 Semantic Actions in the Search Space

A major problem facing any problem solving system is the growth of the search space. When the problem to be solved is complicated, the search space grows and usually, when a solution is not found, one runs out of machine work-space rather than time. One can use knowledge about the problem domain to help decrease the workspace needed.

3.3.1 Representing Counting Restrictions

A natural candidate for decreasing the work­ space is to have knowledge concerning predicates. In particular, one might refer to counting predi­ cates as ones in which there can be either a fixed or-all upper bound to the number of solutions to the problem. For example, when referring to the U.S. Senate, there are two senators who represent one state. Thus, if one is searching for an an­ swer to a subproblem which concerns senators who represent Maryland, only a maximum of two may be found in the system.

To take advantage of counting predicates, counting information must be represented in the semantic network, and a bookkeeping mechanism must exist during the search process to keep track of when a solution has been found, and when all pos­ sible solutions have been found. We sketch how this is accomplished below. (See McSkimin for details.)

To motivate the discussion, consider the following query, 'Who represents the states of New York or New Jersey?". The query, in IT-a notation may be given in negated form as: c~ca,x,y), {{[REPRESENT]/a, [NY,NJ]/y}}). Information of a general nature concerning the predicate REPRESENT is contained in the semantic form space. Thus, it is desired to denote that two senators represent every state, and that there are 15 re­ presentatives for NJ and 39 from NY, and that each senator or congressman can represent at most one state.

The above semantic information can be re­ presented in the semantic form space as,

By the notation B #m/v, is meant, that each element of a Boolean Category Expression (BCE), B, can occur in at most m distinct n-tuples which unify with that particular substitution set.

The query, when tested against a semantic form during a well-formedness test is modified to reflect the above possibilities. Thus, Q becomes

For every substitution set ~i of a predicate there is associated a semantic set count (SSC), which represents the number of poss1ble solutions that can be found relative to the predicate. Let the substitution set ~be given by, ~ = {S0#1/v 0 , Sl#ml/vl,····Sn#ffinlvn}. Then it is easy to see that n

where Card(Si) is the cardinality of the setS., and mi is the element semantic count. Thus, fBr ~ = { [REPRESENT]/a,senator#l/x, [NY,NJ]#Z/y}, SSC= min(l00·1,2·2)=4, where Card(senator)=lOO. That is, there are only 4 possible solut1ons - the two senators from each state for the particular sub­ stitution set. If one sums the sse over all sub­ stitution sets relative to the subproblem (liter­ al), one obtains the total possible solutions. If all solutions are found for all substitution sets, the literal is said to be full~ solved. For the single subproblem associated w1th the sample query there are 4+15+39=58 possible semantic solutions.

The ~tactic count (SC) for a substitution set is simply the number of possible entries in the relation, and is given by

This number is always greater than or equal to the semantic set count, and generally is considerably larger. In particular SC=ZOO for the above ex­ ample.

Given an IT - a literal in the search space, a target SYgtactic count (TSC)is specified for each s~bSt1tut1on set ~i for each literal, and is de­ f1ned as TSCi = (SCi-SSCi)· When a IT-a literal is to be solved, it is removed from the clause and placed in a special list. The literal on the list is initially given the count equal to se. As unique solutions are found for the literal, they are subtracted out of the substitution set, and the count of the literal initially set to SC is decremented by the number of unique solutions found. When the count for the literal on the list equals TSC, then the literal is fully solved.

To take advantage of counting predicates, it is necessary to know, when, during the search pro­ cess, a literal has been solved, and if so, wheth­ er the literal has been fully solved. In the en­ vironment of Question-Answering Systems, Fishman [1973,1974] has experimental evidence which indi­ cates that linear resolution with selection func­ tion (SL resolution), developed by Kowalski and Kuehner [1971], and independently by Loveland [1969,1970] (who termed it model elimination), or

a variant thereof, will be used for the inference mechanism. SL resolution is very convenient to use since one lmows exactly when a literal has been solved. This occurs when truncation takes place. The bookkeeping associated with SL resolu­ tion permits one to backup to the clause where one first started to search for a solution to the l i t­ eral. It is at the clause where one first starts to search for a solution to the literal that one wants to initiate semantic actions.

Three types of semantic actions may be taken when fully solved substitution sets of a search space literal L =(L, ~) are found. Starting at the clause in which the fully solved substitution set appears, one must remove from the search space each substitution set that has been fully solved. This will inhibit any further clauses from being resolved against the clause. If, all resolvents from the IT-a literal have been found, some of the resolvents may not yet have been entered into the workspace. In this case, a pointer to the resol­ vent set 'I'.Ould exist, and could be deleted. The reason for inhibiting any additional clauses from entering the search space is because all solutions have already been found, and no other solutions are possible. By bringing in additional clauses, one is merely trying to find another solution via a different path. The best that can result is that a duplicate solution will be found.

If all substitution sets ~ · become fully solved, then the entire subprobfem L=(L, ~ ) is fully solved, all further resolvents or potential resolvents of L should be deleted. Thus all fur­ ther interactions between L and the data base are avoided. The semantic action of rerroving fully · solved sets and subproblems can thus potentially save a great deal in search effort.

Unfortunately, the interactions (i.e., reso­ lution operations) between literal L and data base clauses are seldom serial in nature. Rather, it is often the case that several interactions may proceed at the same time as cooperating processes (or coroutines) controlled by the search strategy. As a consequence, even though some literal L be­ comes fully solved, there may be deductions in progress for L that, if continued may duplicate solutions already found. Therefore, ideally, these processes should be terminated. Thus, the second type of semantic action taken is to prune possible redundant derivation trees from the search space. A convenient data structure to fa­ cilitate pruning is one in which the immediate resolvents of a clause are linked together in a list, where each clause in the list points to its parent clause, and the parent clause points to the first and last entries in the list (i.e., it is a binary tree). Pruning in such a search space data structure is straightforward, and is not discussed further here.

The third type of semantic action concerns the literals of generated clauses in redundant derivation trees. As each clause ~ is generated by resolution or factoring, the search strategy may seleet a literal from ~ to be resolved against the data b~se. The literal might be on a list of literals waiting to be resolved (for example, see Minker et al,[l973]), or in the process of being resolved. Leaving such a· literal there will per­ mit it to interact with the data base, thus pro­ ducing rrore unnecessary deductions. Therefore if such a list exists, the selected literals from' all clauses of a redundant derivation must be removed from the list and resolvents in process or that have been found must be terminated or deleted as the case may be.

The following section illustrates how the above techniques may be used together in answering a query.

4. An Example of the Use of Semantics in a QA System

The data base used in this example consists of assertions and general rules that might be use­ ful in a political context. Asswne there are many assertions that state where a member of Congress legally resides; i.e.,

A 1 : (ex,x,y), { { [RESIDE]/ex , [Beall,Mathias,Holt, ... , Hogan,Gude]/x, [Mi]/y},

A 2 :

{[RESIDE/ex, [Buckley,Javits,Chisholm, ... ,Abzug]/x, [NY]/y} }

These assertions may be used to derive the state a member of Congress represents by the following general rule:

R 1 : (-v(ex,x,y) V (13 ,x,y), {{ [RESIDE]/ex, congressjx, stately, [REPRESENT/13}}).

In addition, there might be several axioms that are used to deduce whether a member of Con­ gress supports a special interest group (such as organized labor) by referencing numerical ratings established by different lobbying groups (e.g., COPE, the Committee on Political Education of the AFLCIO). For instance if a senator or represen­ tative has a COPE rating of 67-100 (on a 0-100 scale) then one may conclude that he (she) sup­ ports organized labor. Many of these rules may be stored as well as other general rules that deduce whether one supports some state, country, or interest group. These rules are given below.l

R 2 : (-v (ex,x,y) V (13,x,y), { { [COPE]/ ex ,congress/x, R67100/y, [SUPPORT]/13, labor/ z,}

R3:

{ [NSC]/ ex ,congress/x, R67100/y,[SUPPORT]/13, defensejz},

R4: (-v (a, x, y) V (13,x, y), { { [REPRESENT]/ ex, congress/ X, stately, [SUPPORT]/13}} ).

The last rule states that if a member of Congress represents a state, then he or she 'I'.Ould be ex­ pected to support that state.

To derive whether one would support a spe­ cial-interest group, the ratings of each senator and representative could be stored as assertions:

A 3 :((a,x,y),{{[NSC]/a, [Mathias,Cranston, ... , Mitchell]/x, [11]/y},

1 Note: NSC = Nat. Security Council, a defense lobby; NFU = Nat. Farm Union: and LCV = League of Conservation Voters; R671UO = A category con­ taining all integers from 67 to 100.

{{[NSC/a,[Javits,Schweiker, ... , Podell]/x,[33]/y}}).

Besides the data base, semantic forms are al­ so needed. The fOllowing semantic forms might be used:

F 1 :(a,x,y){{[REPRESENT]/a,senator#l/X,state#2jy, {[REPRESENT]/a,rep#1/x,[MD]#8/y}, { [REPRESENT]/a,rep#l/x, [NY] #39/y}},

F 2 : (a,x,y) {[RESIDE]/a,human#l/x,state#v/y}

F 3 :(a,x,y) {[SUPPORT]/a,congress#v/x,(state U country U interest)#v/y}.

The element semantic counts that apply to each form is provided.

It is assumed that dictionary entries for all predicates, constants, and BCEs have been created; because of their large number, these will not be shown, nor will the semantic graph be shown.

Suppose that the following query is asked: C ~ (a,x,y),{{[SUPPORT]/a,[Sirica]/x,QMininginterest/y}}), i.e., Does Sirica sup­ port mining interests?" This query fails to unify against any of the semantic forms; in particular, it fails to match F3 since Sirica E judge and judge is disjoint from congress. The query is re­ jected as meaningless.

Now suppose another query is entered: (~(a,x,y) v (f3,x, z), { {[SUPPORT]/ a, [REPRESENT]/13, senator/X,defensejy, [Md,NY]/z}});

i.e., "Are there any senators from New York or Maryland who support defense interests?" Each literal is resolved against the semantic form to test its well-formedness. The literal (f3,x,y) unifies with form F1 and the literal (a,x,y) uni­ fies with the form F3. These unifications are successful because senator ~ congress and defense ~ defense, as MJuld be found in the semantic graph. The query is thus well-formed.

A scenario for the proof, shown in Figure 2, using SL resolution as the inference system of the above query, follows:

1) A heuristic function f is used to select which literal of the query to solve first. As discussed in McSkimin [1976], Minker et al. [1973], and Min­ ker [1976], the number of potential solutions of literals is a good indication of the a!IK)unt of work required to solve them. In this case, the element set counts of the semantic form relevant to each literal are referenced and the semantic set counts computed. Since at most tMJ senators can represent a state, the literal with the REPRE­ SENT predicate has 4 solutions as shown in Sec­ tion 3.3.1.

No bounds can be placed on the SUPPORT liter­ al since it is not a counting predicate as is REPRESENT. SolVIng the SUPPORT literal first could cause numerous inferences to be generated, assuming that there are many senators listed who support some defense interest. Thus, the REPRE­ SENT literal is chosen to be solved first.

1. The target syntactic count for the REPRESENT literal, which equals the syntactic count minus

the semantic set count is calculated. In this case, there are SC=l00·2=200 syntactic solutions and SSC=4 semantic solutions. Thus, the value TSC =SC-SSC=200-4=196, is stored with the REPRESENT literal L and referenced whenever new solutions are found. L is then ITDdified to remove those so­ lutions found so far. When the syntactic count of L equals TSC=l96, L will be fully solved. This process is illustrated by the proof tree of Figure 2 using SL resolution.

1. The general rule Rl is resolved with ~cs,x,z) since no direct match 1s possible. Since senator ~ congress and [Md,NY] ~ state, resolvent 2 is formed.
2. The RESIDE literal L is now the right-most (and only) literal in the SL resolvent, and is thus solved next. The element set counts from se­ mantic form F2 are read, and the number of solu­ tions for L is calculated as, SSC=min(l00·1,2·v) = 100, where ''v" means an unknown number of solutions are possible. The target syntactic count is cal­ culated as TSC=(l00·2)-100=100, and stored with the RESIDE literal. Thus, 100 solutions must be found before the literal is considered fully solved. Since it is semantically impossible for 100 sena­ tors to reside in two states, this situation will never occur. Fortunately, the RESIDE literal will become indirectly fully solved because its ancestor the REPRESENT literal ~cs,x,z) will be fully solved. This process is described below.
3. Many RESIDE assertions are stored in the data base; only those instances are allowed to enter the search space that involve senators from Mi or NY - all representatives from Md and NY and any resident of some other state is excluded. Since {Beall, Mathias, Buckley, Javits} ~ senator they are the only ones that pass through the II -a unification algorithm.
4. Since the A-literal [~(y,x,z)] appears as the right-most literal of clause 3, it implies that a subproblem has been solved. Up-links are followed until ~(y,x,z) appears without brackets in clause 2 (denoting the point at which the current deduc­ tive chain began as indicated by the dotted lines of Figure 5). The solutions found are:

~(y,x~z){{[RESIDE]/y, [Beall,Mathias]/x,[Mi]/z}, {[RESIDE]/y,[Buckley,Javits]/x,[NY]/z}}.

By the procedure described in McSkimin, these so­ lutions are reiTDved from clause 2 (whose syntactic count is 200) leav1ng a new clause whose syntactic count equals 196. Since this does not equal the target syntactic count of 100, no semantic actions can be taken.

1. The A-literal [~(y,x,z)] is thus truncated from Clause 3, yielding clause 4.
2. Another subproblem has been solved. since [~Cs,x,z)] is the right-most literal of clause 4. U~-links are followed until ~cs,x,z) first appears w1thout brackets (clause 1). Since four solutions have been found for the literal, its syntactic count becomes 196. Since this equals the target syntactic count, ~cs,x,z) is therefore reiTDved from the search space to prevent other inference rules from attempting to deduce the senators from Md or

NY. In addition, the literal ~(y,x,z) from clause 2 is removed also since all residents of Md and NY of interest have been found. Thus, even though this literal had 96 solutions left to find, it could be pruned since it was a descendant of a literal which was fully solved. These are examples of semantic actions.

1. The A-literal [~(s,x,z)] is next truncated from clause 4 yielding clause 5, which is next solved in a similar fashion.

This example has illustrated how user-sup­ plied semantic information may be incorporated within the framework of predicate calculus so as to make the deductive inference process more ef­ ficient. Three methods were shown to be effec­ tive in reducing the amount of effort involved in answering a query: semantic well-formedness tests, semantic operator selection, and semantic actions. Naturally, these are not beneficial for all data bases; conditions under which each is expected to prove most beneficial are given by ~Skimin.

5. Summary

We have described three basic uses of a seman­ tic network: (1) To semantically unify two liter­ als. (2) To perform semantic well-formedness tests. (3) To perform semantic actions. Semantic unification serves to decrease the number of de­ ductions that one may have over syntactic metmds Semantic well-formedness tests serve to delete data f~om entering the data base if they are not seman­ t1~all~ well-formed relative to the domain of ap­ ~l1cat1on. Semantic well-formedness tests may also 1ntroduce new literals into the search space which must be satisfied for a solution to be found Se­ mantic actions serve to use counting information to determine w~en a literal has been fully solved, and to ~ake actwns based upon this information. These act1ons serve to delimit the search space.

An alternative approach to the one described here would be to build into the system unary predi­ cates rather than set information as represented in the semantic graph. We do not believe that such an approach would be effective since the addition of axioms to the system to represent transitive super­ set relations and disjoint relations would be too cumbersome to deal with in practice and would lead to very long proofs.

Although the approach appears to be viable, we cannot yet provide experience which would demon­ strate its effectiveness. We expect to determine its effectiveness. One factor is the data struc­ ture to be used to perform pattern-directed search for clauses which semantically and syntactically match literals in the data base. A second factor will be the amount of time required to perform the CONFLICT algorithm. This algorithm determines whether or not two boolean category expressions are semantically consistent. If the conflict algorithm is too time consuming, it may defeat the whole approach and make it comparable to a strictly syn­ tactic approach. Further analysis is needed to estimate whether the effort expended in executing the semantic routines will exceed the extra effort incurred if they are not performed at all.

We believe that an advantage will be shown for the techniques described here. We are cur­ rently implementing a system, MRPPS 3.0 which in­ corporates the techniques described here. We ex­ pect to experiment with the system to determine how well it will work on large data bases.

Acknowledgements

The authors wish to express their apprecia­ tion to the National Science Foundation for the support that they have provided for this effort under NSF GJ-43632. They would also like to ex­ press their appreciation to Mr. Guy Zanon for his careful reading of the paper and his many sugges­ tions.