Exploiting Irrelevance Reasoning to Guide Problem Solving

1 Introduction

Control of reasoning is a major issue in scaling up prob­ lem solvers that use declarative representations, since inference is slowed down significantly as the size of the knowledge base (KB) is increased. A key facto· for the slow down is the search of the inference engine through parts of the KB that are irrelevant to the query at hand. Moreover, since a KB is designed for a variety of tasks, it is often at a level of detail that is too refined for a spe­ cific query. Often , we have additional knowledge about the domain or about the KB that can be used to cut down drastically the space that the inference engine has to search. One important type of such knowledge con­ sists of irrelevance claims stating that certain formulas are redundant with respect to, or will not be part of any derivation of a given class of queries, and consequently, those formulas can be removed. Such irrelevance claims can be either given by the user or derived automatically by the system.

*Supported by a fellowship from Shell Oil Company.

Yehoshua Sagiv

Dept. of Computer Science Hebrew University Jerusalem, Israel ( sagiv@cs.huji.ac.il)

Effective use of irrelevance reasoning requires a formal understanding of the issues involved in such reasoning, as has been done in the context of probabilistic reason­ ing [Pearl, 1988]. The work of [Subramanian, 1989] pre­ sented a framework for stating irrelevance claims , and raised several issues concerning irrelevance reasoning. However, two issues remain largely open. The first is to find efficient methods for automatically deriving ir­ relevance claims. The second issue is to determine the utility of removing irrelevant knowledge, since removing irrelevant parts of a KB does not always improve effi­ ciency. For example, redundant formulas (which may be considered irrelevant) can often speedup problem solvers.

To address these issues, we first present a space of defi­ nitions of irrelevance, based on a proof-theoretic analysis of the notion. This space enables us to make finer dis­ tinctions than those possible in the framework of [Subra­ manian, 1989]. The main distinction we make is between weak-irrelevance claims and strong-irrelevance claims. Roughly, a formula is strongly irrelevant to a query if it cannot appear in any of its derivations, whereas it is weakly irrelevant if it does not appear in some of its derivations. Strong-irrelevance claims turn out to have some desirable properties. For example, in many cases it is possible to find efficiently formulas in the KB that are strongly irrelevant to a given query. In some cases it is even possible to find all strongly-irrelevant formulas. Furthermore, unlike weak irrelevance, remov­ ing strongly-irrelevant formulas from a KB may only improve the performance (and sometimes the improve­ ment is by orders-of-magnitude, as we will show) . We investigate strong irrelevance in detail for Horn-rule KBs and describe novel algorithms for efficiently deriving new strong-irrelevance claims from those given by the user .

Our algorithms consider, in addition to the rules of the KB, only constraints on the ground facts that may possi­ bly appear (e.g., order constrc: 'nts, sorts) , as opposed to looking at the ground facts t' .emselves. Consequently, if the ground facts change, the irrelevance claims still hold and, therefore, the cost of irrelevance reasoning is amortized over many queries. The main difficulty in ir­ relevance reasoning is finding properties satisfied by all possible derivations of a given query. To do so, we use a powerful tool, the query tree, first introduced in [Levy and Sagiv, 1992] . The query tree encodes finitely all possible derivations of the query (even when rules are recursive). The query tree facilitates automatic derivation of irrelevance claims that follow from an examination of the KB and irrelevance claims supplied by the user.

2 Formalizing Irrelevance

2.1 Preliminaries

We consider a knowledge base (KB) of closed formulas ~ in first-order predicate calculus. We assume that the inference mechanism of the KB employs a set of inference rules S. A derivation D of a closed formula 1/J from ~ is a sequence of formulas, a 1 , . .. , an, such that an = 1/J and for each i (1 ~ i ~ n), either a; E ~.a; is a logical axiom, or a; is the result of applying a rule in S to some elements a; 1 , ··· , a; 1 that appear prior to a;. The formulas a; 1 , ··· , a; 1 are said to be immediate subgoals of a;. The set of formulas in D that do not have any subgoal is called the base of the derivation, denoted by Base(D) . The set Base(D) represents a "support set" for 1/J. We consider only derivations in which every a; is a subgoal of 1/J (not necessarily an immediate subgoal).

A query is represented by a formula 1/J. If 1/J is a closed formula (i.e., has no free variables), then the answer is true if the the inference mechanism can find some derivation of 1/J from~. and talse otherwise. 1 If 1/J con­ tains free variables, the answer is the set of assignments for the free variables, such that the resulting closed for­ mulas are derivable from ~; 2 in this case, a derivation is a set containing a single derivation for each answer. A query may have several derivations from a given knowl­ edge base, and we denote the set of those derivations by 'D t:. ( 1/J) (note that if 1/J has free variables, then 1J t:. ( 1/J) is a set of sets of derivations).

2.2 Definitions of Irrelevance

Our goal is to express and reason with irrelevance claims of the form "X is irrelevant to 1/J with respect to the theory ~." and so, we need to give such claims a formal defini­ tion. X is called the subject of the irrelevance claim. In this paper, we discuss the case in which X is a formula or set of formulas. Other irrelevance subjects such as objects, predicates and distinctions between predicates are discussed in [Levy, 1993] .

In order for a definition of irrelevance to be useful, it should give us information that could be used effectively. For example, we would like to know whether irrelevance claims can be derived, how the claims change when the KB changes, and what is the utility of removing irrele­ vant facts. Unfortunately, there is no single best defini­ tion of irrelevance that both matches our intuition and enables us to establish such properties. For example, we can define a formula <P to be irrelevant to 1/J if there is some derivation of 1/J that does not contain </J, or alter­ natively, we can require that no derivation of 1/J contains </J. To make the needed distinctions, we present a space of definitions of irrelevance and investigate the different properties of various definitions within this space.

1 We can return unknown if neither ¢ nor -.¢ are derivable. However that does not affect our discussion.

2 An alternative definition often considered is finding one variable binding that satisfies the query formula. However, this distinction does not affect our discussion.

It should be noted that our analysis is not an attempt to formalize the common sense notion of irrelevance or argue for properties of such a notion (as done, for ex­ ample, by [Gardenfors, 1978]) . Our goal is to utilize the notion of irrelevance to speed inference and, there­ fore, we analyze the ways in which it can arise in in­ ference. Specifically, we analyze irrelevance in a proof­ theoretic setting by considering the possible derivations (or more generally, paths) that an inference mechanism can pursue in answering a query. In contrast, the analy­ sis of [Subramanian, 1989] is meta-theoretic, i.e., it con­ siders only the formulas in the KB, not the possible derivations of the query. Consequently, we are able to make finer distinctions than those made in Subrama­ nian's framework .

Definitions in the space vary along two axes. The first considers different ways of defining irrelevance of a sub­ ject <P with respect to a single derivation D of the query 1/J. We capture this by a definition of derivation irrel­ evance, denoted by DI(<P , D) . The following are a few examples of how DI can be defined:

• D/1(</J, D) iff <P ft Base(D).
• D/2(</J, D) iff </J ft D.
• DI3(4J, D) iff Base( D) ~ </J.
• D/4 (</J, D) iff Base( D) ~ </J, -,<jJ ,

' Definition D/1 requires <P not to be in the support set of D . Definition Dh is stronger and requires <P not to ap­ pear in D. Definition D/3 is even stronger and requires that <P not be a logical consequence of the formulas in D, while D/4 requires the same also for -,<jJ . Note that <P is not necessarily a formula in the KB.

Requiring that DI holds for all possible derivations of the query may be too restrictive. Therefore, in the second axis we examine different restrictions on the set of derivations we consider. For example, we can require DI to hold for the set of minimal derivations 3 of the query, or for the set all derivations bounded by some resource constraint. Alternatively, we can require DI to hold for some derivation in the chosen set. For example, we can require that DI hold for some minimal derivation of the query. 4 Given a predicate DI and a set of derivations, a definition of irrelevance in our space is as follows:

Definition 2.1: Let ~be a KB, <P be a closed formula, 1/J be a query, and 7J0 be a subset of the set 'D t:. ( 1/J) of all possible derivations of 1/J . Let DI( r, D) be a condition specifying when a formula r is irrelevant with respect to a derivation D.

The formula <Pis said to be weakly irrelevant to 1/J with re­ spect toLl, DI and 7J0 , denoted by W 1(</J, 1/J, ~ . DI , 'Do) , if DI( </J, D) holds for some D E 1Jo.

3 Given some criteria of minimality for derivations. See Section 3 for a definition of minimality in the case of Horn­

rule KBs.

4 We can also consider other ways of quantifying over a set of derivations, such as requiring that DI holds for some per­ cent of the derivations. In this paper, however, we consider only universal and existential quantifications.

The formula 4> is said to be strongly irrelevant to '1/J with respect to ~. DI and 1J0, denoted by SI(¢, '1/J, ~. DI , 1J0 ), if DI(¢, D) holds for every DE 1J0 . If'DA(t/J) is empty (i.e., '1/J is not derivable from~), then 4> is both weakly and strongly irrelevant to t/J. I

We often refer to irrelevance of a set of formulas or to irrelevance of formulas with respect to a set of KBs. To define irrelevance of a set of formulas, we extend the defi­ nition of DI as follows . If~ is a set of formulas, we define DI(~, D) to hold if DI(¢i, D) holds for every ¢i E ~- To define irrelevance for a set of knowledge bases E, we de­ fine WI(¢, t/J, E, DI, 'Do) to hold if WI(¢, t/J, ~. DI, 'Do) holds for every ~ E E, and similarly for SI. 5 The fol­ lowing example illustrates the various definitions.

Example 2.2: Let '1/J = CanT A( Fred, 101) be the query and ~o be the following knowledge base:

r1 : AttendClass(x, y) => Pass(x, y) .

r 2 : PassExam(x, y) => Pass(x, y) .

T3 : Pass(x, y) 1\ TookGradCourse(x) => CanTA(x, y).

T4 : Pass(x, y) 1\ (y ~ 200) => TookGradCourse(x).

91 : AttendClass(Fred, 101) . 92 : PassExam(Fred, 101) .

93 : PassExam(Fred, 202) .

94 : PassExam(Fred, 161).

Note that WI(g2, 1/J,~o,Dh'DA('I/J)) holds (i.e., Y2 is weakly irrelevant to '1/J), because only one of g1 and Y2 is needed to prove t/J. Atom g4 is strongly irrelevant to '1/J (i.e., SI(g4, '1/J, ~o , Dh 'DA(t/J)) holds), since it is not used in any derivation of t/J. CanT A( Fred, 202) is strongly irrelevant to '1/J if DI2 is used for DI (i .e., SI(CanTA(Fred, 202), '1/J, ~o, Dh 1JA(tP)) holds), but not if DI3 is used instead of DI2. I

The space encompasses several definitions of irrele­ vance and related notions discussed in the past. The def­ initions of [Subramanian, 1989] are instances of weak ir­ relevance; in particular, although her definitions are not in terms of derivations, the main definition of [Subrama­ nian, 1989] is equivalent to WI(¢,'1/J,~,DI3 ,1JA('I/J)). 6 The definition of update independence in (Elkan, 1990] is equivalent to WI(¢,'1/J,~ , Dllo'DA(tP)) (see [Levy and Sagiv, 1993]). The definition of irrelevance given in [Srivastava and Ramakrishnan, 1992] is equivalent to SI(¢, '1/J, ~. Dh, 1JA(t/J)) . In [Levy and Sagiv, 1992], we discuss strong irrelevance with respect to the set 'Do of minimal derivations.

Several properties can be shown for classes of defini­ tions in the space, mostly distinguishing between weak and strong irrelevance. Here, we mention only two of them. For full details , see [Levy, 1993].

Observation 2.3: Closure under union. When a system needs to determine whether it can use all the ir­ relevance claims it has, or whether using certain ones will falsify others, it needs to know whether they are closed under union of their subjects. Weak-irrelevance claims do not add up in general, but for strong-irrelevance claims we have a sufficient condition for adding up that depends on DI. Specifically, if the following holds for any derivation D and sets ~1, ~2 (as, for example, in the case of Dh -DI4),

5 Note that for every f::l. E E, the set Vo is actually dif­ ferent. We assume that Vo is a characterization of a set of derivations that can be instantiated for any given f::l. (e.g., all minimal derivations).

6 Assuming the inference engine is complete. A variant of this definition, which is given in [Subramanian and Gene­ sereth, 1987], is obtained by using D I4 ·

then for any choice of 'Do and E, S/(~1, tf;, E, DI, 'Do) 1\ S/(~2, tf;, E, DI , 'Do) => SI( { ~1, ~2}, '1/J, E, DI, 'Do).

Observation 2.4: Problem-solving payoff. The utility of removing irrelevant formulas is an important question. For weak irrelevance, this is a subtle is­ sue. In fact, explanation-based learning systems do ex­ actly the opposite by adding redundant rules, which are weakly irrelevant. In Example 2.2, adding the rule AttendClass(x, y) 1\ (y ;:::: 200) => CanTA(x, y) may speed the solving of some queries . The utility of adding such rules is a subject of ongoing research (e.g. , [Minton , 1988]). For strong irrelevance, savings are guaranteed for many cases. For example, when considering all derivations of the query (i .e. , 1J0 = 1JA(t/J)) , deriving '1/J from~-~ costs no more than deriving it from ~ if SI(~, '1/J, ~. Dh 'DA(t/J)) holds. This property also holds if we consider a set of derivations 1J0 , such that the in­ ference engine is always guaranteed to find one of the derivations in 1J0 before it finds others. In the next sec­ tion, we will illustrate that removing strongly-irrelevant formulas can result in significant time savings and not only in space savings.

3 Deriving Irrelevance Claims

A key issue in relevance reasoning is the ability to decide which formulas are irrelevant to a given query. Specifi­ cally, two questions are of interest. First, given a knowl­ edge base and a query, which formulas in the knowledge base are irrelevant to the query? Second, if we are given an irrelevance claim by a user, can we derive other irrele­ vance claims that logically follow. This section considers these questions for the case of KBs consisting of a set P of Horn rules and a set G of ground atomic facts .

We consider atomic queries that are either ground or contain free variables. A derivation of a query uses a single rule of inference: Given an instance of a rule from the KB, the consequent of the rule can be inferred if the antecedents were inferred previously. A derivation D is conveniently viewed as a tree, as shown in Figure 1. A derivation tree (and the corresponding derivation) is minimal if there is no pair of identical goal-nodes, n1 and n2, such that n1 is an ancestor of n2 . A formula 4> is said to be irrelevant to a derivation D if 4> does not appear in D (i .e., we use DI2 from the previous section). We distinguish two sets of predicates in the KB, the extensional predicates (EDB) that appear in G and the intensional predicates that appear in the consequents of the rules. As a syntactic convenience, we assume that base predicates do not appear in the consequents of any of the rules.

Deriving irrelevance claims requires that we establish properties of all possible derivations of a query, and that entails examining the whole KB. This is, of course, impractical and defeats the original goal of relevance rea­ soning. Therefore, we would like to derive irrelevance claims that depend only on a small and stable part of the KB and are independent of changes to other parts of the KB. In many applications, the bulk of the KB con­ sists of ground facts that are updated frequently, while the rules of the KB form a small and stable part. There­ fore, we are not going to examine the ground facts of KB directly. Instead, we will use a set C of high-level con­ straints describing the ground facts that may possibly appear in the KB (e.g., Age(z, y)::} y ~ 150) .

Constraints may also appear in rules, in the form of interpreted predicates (such as the order predicates=, -:p, ~and < , or sort predicates). Many interactions between rules can be detected by analyzing the semantics of these interpreted predicates. Furthermore, interpreted predi­ cates play an important role in many applications, and often, reasoning with them can be done efficiently. Note that in particular, the variable patterns in the rules can be viewed as constraints (using equality) .

We would like our relevance reasoning to incorporate both the semantics of the interpreted predicates appear­ ing in rules and the semantics of the constraints imposed on the possible ground facts. Formally, it means that we have to consider the following problem. Given a set P of rules, a set C of constraints on the ground facts, and a query q, find (some or all) rules and ground facts that are irrelevant to q in every KB of :E(P, C), where :E(P, C) denotes the set of all KBs consisting of P and a set G of ground facts, such that G satisfy the constraints of C.

The distinctions made in our space of definitions also correspond to different answers to the above problem. First, we observe that determining weak irrelevance is undecidable, even in very restricted cases:

Proposition 3.1: Determining whether a formula ljJ is weakly irrelevant to a query q, with respect to DI2 and the set of all derivations 'D A. ( q), is undecidable even if the rules of P contain no function symbols, C is empty and there are no interpreted predicates in rules.

This result is proved by a reduction from the rule­ redundancy problem [Shmueli, 1987]. Algorithms that find some weakly-irrelevant formulas, but may fail to identify all of them, are described by [Sagiv and Yan­ nakakis, 1981] and [Sagiv, 1988] .

For strong irrelevance, the situation is much better. In [Levy and Sagiv, 1992], we have shown that strong irrelevance is decidable for function-free Horn rules and interpreted predicates. The result shows that strong ir­ relevance is decidable when considering either the set of all derivations 'D 6 ( q) or only the set of all minimal derivations. 7 The algorithms cover a wide range of in­ terpreted predicates, e.g., order and sort constraints 8

When function symbols are introduced, determining strong irrelevance is undecidable for KB's with recursion . However, the algorithms described remain sound, i.e., if they deem a formula irrelevant, then it is irrelevant.

Example 3.2 : Let step, bigStep, badPoint and goodPoint be the EDB predicates, where the rules are:

r1: badPoint(x) 1\path(x, y) 1\goodPoint(y) => goodPath(x , y).

r2 : link(x, y) => path(x, y).

r3 : link(x, z) 1\ path(z , y) => path(x , y).

r, : step(x , y)::} link(x , y).

r5 : bigStep(x, y) ::} link(x, y).

The following constraints are known about the ground facts: badPoint(x) => 100 < x < 200, step(x, y) => x < y. goodPoint( x) ::} 150 < x < 170. bigStep(x, y) ::} x < 100 1\ y > 200.

Figure 2 shows that Rule rs is strongly irrelevant to the query goodPath(z , y) , since the constraints on bigStep contradict those of the nodes that might be unified with the consequent of r 5 . Moreover, we can also deem many ground facts strongly irrelevant , such as all badPoi?:t(z), where z;::: 170, all step(x,y), where z > 170 or y < 100, and all the facts for bigStep. I

In the next section, we will describe an algorithm for deriving logical conclusions from irrelevance claims given by the user. The algorithm uses a powerful tool, called the query tree, first introduced in [Levy and Sagiv, 1992]. Below, we briefly describe some aspects of query trees .

3.1 The Query Tree

There are several difficulties in deriving irrelevance claims. First, we need to establish properties of the set of all derivations of the query without enumerating them. Second, we are given the rules of the KB, but have only a partial knowledge about the ground facts in the KB. Finally, we want to enforce the semantics of the inter­ preted predicates. The query tree provides a compact representation of precisely the set of all derivations of the query that satisfy the semantics of the interpreted predicates.

The query tree is a symbolic AND-OR tree consisting of goal nodes and rule nodes (see Figure 2). The root of the tree is a goal node labeled with the query. A goal­ node g has a child for every rule whose consequent unifies with g, and the actual child is the rule resulting from the unification with g. A rule node has a goal-node child for

7 The algorithms for these two cases differ in their complexity

8 Formally, we require that the constraint language C sat­ isfy several properties. We must be able to determine when two sentences in the constraint language are equivalent. Fur­ thermore, there must be a finite number of non-equivalent sentences when the number of variables is fixed. For full de­ tails, see [Levy and Sagiv, 1992].

every conjunct in its antecedent. If a KB has recursive rules, such a simple minded construction of the tree will not terminate. In order to get a finite representation of all possible derivations, we attach a label to each node in the tree. The label of a node contains the tightest con­ straint that needs to be satisfied by tuples generated in that node. The label is inferred by the constraint literals appearing in the rules and the constraints known about the possible ground facts that may appear in the KB. A goal node will be further expanded only if there is no other expanded node in the tree that has an isomorphic label. Note that computing the labels of the nodes may require several phases of propagation through the nodes in the tree.

A query-tree T encodes a set of symbolic derivations. A symbolic derivation is like a derivation except that some constants are replaced by variables, and it repre­ sents the set of derivations that can be obtained by as­ signing constants to those variables. A symbolic deriva­ tion is encoded by the query tree if it can be constructed as follows. Start from the root and choose one rule-node child and its subgoal nodes. Inductively, let t be the tree created so far. If n is a leaf oft for an IDB predicate, let n' be the goal node in T that has a label isomorphic to n and was expanded (n' may be n itself). Expand n with one of the children of n'.

When the KB contains no function symbols, the query tree encodes precisely the set of derivations of the query that use formulas that satisfy the constraints. Specifi­ cally:

• For any derivation d' E 'Do that uses only ground facts that satisfy the constraints of C, there exists a symbolic derivation d and an assignment u, such that u( d) = d' and d is encoded by the query tree.
• For every symbolic derivation d encoded by the tree, there is a variable assignment u , such that u( d) E 1)0 and the leaves of u( d) satisfy C.

Consequently, the query tree provides a sound and complete inference mechanism for strong irrelevance (with respect to 'Dt.(q)). Specifically, a rule is strongly irrelevant to q if and only if an instance of it does not ap­ pear in the tree. A ground fact p(a1 , ... , an) is strongly irrelevant if and only if a1, ... , an does not satisfy the la­ bel of any goal node of pin the query tree. When the KB contains function symbols.( and recursion) the query tree encodes a superset of 'Dt.(q), and therefore, it provides only a sound inference mechanism for strong irrelevance.

By refining the labels of nodes in the tree, the query tree can also be made to encode precisely the set of mini­ mal derivations of the query (see [Levy and Sagiv, 1992]) and the set of all derivations when some of the EDB lit­ erals appear negated (see [Levy et al., 1993]) .

The complexity of building the tree (and therefore of deriving SI) is linear in the number of rules in P. It may be exponential in the arity of predicates. However, arities of predicates tend to be very small (e.g., frame systems usually employ mostly binary predicates) . Fur­ thermore, we believe that exponential running time is not likely to occur in practice (since finding examples with exponential running time requires careful crafting of the rules), 9 and so, building the query tree is not an expensive operation.

3.2 Irrelevance Facts from an External Source

Often a user may be able to supply the system with ad­ ditional irrelevance claims based on his knowledge about the ground facts in the KB (or those that may appear in the KB). Specifically, the user may know that a set of formulas <II is strongly irrelevant to the query q in the current state of the KB. This knowledge may not be expressible as explicit constraints on ground facts. 10 Clearly, if we are told that a formula ¢ is strongly ir­ relevant to q, we can remove¢ from the KB. However , we may also be able to conclude that other formulas are irrelevant as well. This section describes an algorithm for deriving such conclusions using the query-tree.

9 Specifically, it requires rules that create in their conse­ quents permutations of the variables from their antecedents

1 °For example, this knowledge may be based on the fact that the join of two relations is empty.

Suppose that P is a set of rules and C is a set of con­ straints on the EDB predicates. Let I be an irrelevance claim stating that a set of formulas ~ is strongly irrele­ vant to a query q; more precisely, I states that the set of possible KBs is some subset E' ~ E(P,C), such that SI(~,q,E',Dh'Da(q)) holds. We assume that~ is ei­ ther a set of rules or a set of ground facts specified as {p(x) I C(.i)}, where pis some predicate and C(.i) is a formula with only interpreted predicates.

To derive logical conclusions from I, our strategy is to create a set of rules P1, such that when formulas from ~ are excluded, P 1 and P produce the same derivations of the query q for every set of ground facts G satisfying C. We then create a query tree for P1 and find all formulas that are strongly irrelevant to q. Clearly, if a formula¢ is strongly irrelevant with respect to P 1 , then it is also strongly irrelevant with respect to P whenever I holds.

Formally, P1 is created as follows:

1. If~ is a set of rules, then P1 = P- ~-
2. If~= {p(.i) I C(.i)}, then let the negation of C(.i) be d1 V ... V dm, where each d; is a conjunction of lit­ erals of interpreted predicates. The set P 1 consists of all the rules of P whose consequent is not p and all rules of the form q1(xl)/\ .. . ql(x!)/\d;(x) =} p(.i) (1 :::; i:::; m), where q1(x1) 1\ .. . q1(i1) =} p(x) is a rule of P.

Example 3.3: Suppose that in Example 3.2 we are told that {path(x, y) I x < 1101\ y > 160} are strongly irrel­ evant. The rules for the predicate path in P 1 would therefore be:

link(x, y) 1\ x ~ 110 =} path(x, y).

link(x, z) 1\ x ~ 1101\ path(z, y) =} path(x, y).

link(x, y) 1\ y:::; 160 =} path(x, y).

link(x, z) 1\ path(z, y) 1\ y :::; 160 =} path(x, y) .

The query tree for P 1 shows that {badPoint(x) I x < 110} and {goodPoint(x) I x > 160} are strongly irrele­ vant to goodPath(x, y) . I

Theorem 3.4: Suppose that ¢ is strongly irrelevant to q with respect to E(P1 , C), or more precisely, sup­ pose that SI(¢, q, E(P1,C), Dh Va(q)) is true. Then SI(¢, q, E', DI2, Va(q)) holds, where E' is the set of pos­ sible KBs, as implied by I .

Proof sketch: The theorem follows from the observa­ tion that P 1 produces the same derivations as P, except for the ones that use formulas in ~. If~ is a set of rules, the observation follows trivially. If ~ includes ground facts, the added literals in the rules of P 1 guarantee that formulas in ~ will not be used in derivations of P1. I

In general; as the theorem below shows, even if there are no function symbols, finding all the logical conse­ quences of a strong-irrelevance claim is not possible.

Theorem 3.5: Suppose that I states that the set of possible KBs is some subset E' ~ E(P, C), such that SI(~, q, E', Dh Va(q)) holds. Determining whether SI(¢, q, E', Dh Va(q)) holds is undecidable.

The theorem is proved by a reduction from the rule­ redundancy problem [Shmueli, 1987].

3.3 The Utility of Relevance Reasoning

Removing strongly-irrelevant formulas (i.e., rules and ground facts) effectively prunes many useless paths that a problem solver (such as a backward chainer) has to pur­ sue. Removing a large number of ground facts can par­ ticularly impact the performance, since much of the cost of a problem solver is in doing database lookups . The savings will be especially significant when the lookup involves uninstantiated variables. For instance, in Ex­ ample 3.2 we need to perform many lookups of the form step(x, y), where y is uninstantiated. Removing all the ground facts for which y ~ 170 will drastically reduce the search.

Identifying irrelevant facts also yield savings when up­ dates are done. For example, if the KB is updated with a fact that is known to be irrelevant, then we need not recompute the answer to the query. Finally, identifying which facts are irrelevant to a query leads to space sav­ ings in storing the KB. This is especially significant when deciding which parts of a large KB should be brought into main memory.

We tested the impact of removing irrelevant facts for over 20 sets of queries taken from four domains . Space limitations preclude the presentation of the complete results. Table 1 presents a set of representative re­ sults. More detailed results can be found in [Levy, 1993] . Rows 1 & 2 use the rules given in Example 3.2. Rows 36 are taken from a travel KB (using real airline data) . Row 7 uses a KB describing compatibilities between wines and dishes (gleaning some knowledge from [Rom­ bauer and Rombauer-Becker, 1975]), while the last row uses a KB describing relationships between students , ad­ visors and institutions (using a database of Ph.D. grad­ uates in computer science).

In the table, Filtering Time is the time taken to build the query tree and to remove the irrelevant facts . Per­ cent irrelevant is the percent of facts that were removed from the KB. BC1 is the time taken to find all solu­ tions to the query using the original KB, and BC2 is the corresponding time using the filtered KB. 11 There­ sults show significant speedups, usually in excess of 3, ranging up to 31 (mean: 10.8, median: 4.4), while the time taken to build the query tree and filter the KB are usually insignificant. The speedups grew significantly as the percent of irrelevant facts grew. For example, using the same query as in Row 3, the speedup was a factor of 280 when 90% of the ground facts were removed. Fur­ thermore, the speedups grew as the size of the KB grew, even when the percent of irrelevant facts remained the same. Similar speedups were recorded when the number of nodes visited in the search was the performance mea­ sure (instead of the execution time) and when measuring the time taken to find just the first solution to the query. The experiments were performed on a TI Explorer II .

11 The performance of our backward chainer compared fa­ vorably with that of Epikit (a commercial implementation of MRS [Russell, 1985]).

4 Discussion

Relevance reasoning is a powerful method to control in­ ference. We presented a general framework for stating knowledge about irrelevance and reasoning with it . We concentrated on the class of strong-irrelevance claims that has several desirable properties, such as existence of efficient algorithms for detecting irrelevant facts. Re­ moving strongly-irrelevant formulas may only improve the performance, and our experiments have shown that these savings are significant . Furthermore, relevance rea­ soning is done with only partial knowledge about the contents of the KB and does not need to be repeated when certain changes occur in the KB. Consequently, our methods are especially effective for KBs that con­ tain many ground facts.

Our analysis of irrelevance can be viewed as a refine­ ment of the analysis in [Subramanian, 1989]. The spe­ cific definitions considered by Subramanian fall under weak irrelevance in our framework. Subramanian de­ fined the class of computational-irrelevance claims to be claims that lead to computational savings. Our class of strong irrelevance is a prime example of computational irrelevance. It should be noted that [Subramanian and Genesereth, 1987] discusses a definition of strong irrel­ evance, but it is a variation on weak irrelevance and is not an instance of computational irrelevance.

The query tree encodes the space of possible deriva­ tio~s of the query. Recently, the question of finding optimal methods to search that space has received a lot of attention [Smith, 1986, Greiner, 1991]; a related issue is analyzing the utility of techniques in explana­ tion based learning [Etzioni , 1990, Greiner and Jurisica, 1992] . Much of this work requires a graph-like repre­ sentation of the search space under consideration. The query tree is such a representation that handles recursive theories in a principled manner and fully incorporates the interpreted constraints appearing in rules.

5 Acknowledgements

The authors would like to thank Richard Fikes Nir Friedman, Karen Myers, Pandu Nayak and Jeff' Van Baalen for valuable discussions and comments on ear­ lier drafts of this paper.