One of the main applications of description logics (DLs) is ontology-based data
access: a conceptual model of a domain is formalized using a DL TBox, and this
formalization is exploited to obtain complete answers when querying data stored
in an ABox. The current availability of professional and comprehensive ontologies
for the bio-medical domain such as SNOMED CT, NCI, and Galen allows an easy
and inexpensive adoption of this approach in bio-medical applications such as
querying electronic medical records [
The aim of this paper is (i) to propose a notion of ABox relevance of a symbol that describes when a symbol S is relevant for ABoxes formulated in a given signature , with a given background TBox T in place; and (ii) to study the computational complexity of deciding ABox relevance. This decision problem is of interest for a variety of reasons. First, knowing which symbols are relevant for ABox querying is useful for the construction of meaningful queries because non-relevant symbols can be discarded. When working with TBoxes that have more than 400.000 concept names such as SNOMED CT, support of this type is clearly indispensable. Second, the set of relevant symbols can be used to guide module extraction [2{4]. Recall that module extraction is the problem of extracting a subset M from a TBox T so that M can be used instead of T in a particular application. In most cases, the extraction of M is guided by a signature that is of interest for the application and about which the module should \say the same" as the original TBox. If the targeted application is query answering, it is natural to use as the signature the set of symbols that are relevant for ABoxes formulated in the desired ABox signature. With the right notion of `module' at hand, the extracted module can then be used instead of the original TBox for query answering. Note that our notion of relevance is based on an ABox signature instead of on a concrete ABox. The rationale behind this is that, in typical applications, the ABox changes frequently which makes it unrealistic to assume that the set of relevant symbols is re-computed after every ABox modi cation, not to speak of the rather costly module extraction.
The notion of ABox relevance depends on the query language used. In this
paper, we study instance queries as the simplest kind of query commonly used,
and conjunctive queries due to their recent popularity in the DL community [5{
13]. After introducing preliminaries in Section 2, we present our notion of ABox
relevance along with some basic observations in Section 3. We then analyze the
complexity of deciding relevance in the E L family of DLs in Section 4, showing
that it ranges from polynomial to ExpTime-complete. Results on the ALC
family of DLs are given in Section 5, showing in particular that ABox relevance is
decidable in ALC and ALCI, but relevance regarding instance queries is
undecidable in ALCF and relevance regarding conjunctive queries is undecidable in
ALCF I. Some proofs are deferred to the full version [
We consider various DLs throughout the paper and use standard notation for
syntax, semantics, and DL names, see [
We study two query languages: (i) the set IQ of instance queries, which take the form A(v); and (ii) the set CQ of conjunctive queries (CQs), which take the form 9v:'(v; u) where ' is a conjunction of atoms of the form A(t) and r(t; t0) with t; t0 terms, i.e., variables or individual names. Note that we disallow composite concepts in instance queries and conjunctive queries, which is a realistic assumption for many applications. Also note that instance queries can only be used to query concept names, but not role names. This is the traditional de nition, which is due to the fact that role assertions in an ABox can only be implied by an ABox if they are explicitly contained in it (and thus querying is trivial). Given a TBox T , an ABox A, and a (conjunctive or instance) query q with k answer variables v1; : : : ; vk, we write T ; A j= q[a1; : : : ; ak] if the tuple (a1; : : : ; ak) of individual names is a certain answer to q w.r.t. A and T (de ned in the usual way). We use certT ;A(q) to denote the set of all certain answers to q w.r.t. A and T .
We use the term symbol to refer to a concept name or role name, signature to refer to a set of symbols, and sig(q) to denote the set of symbols used in the query q. Given a signature , a -ABox (resp. -concept ) is an ABox (resp. concept) using symbols from only. 3
bTeheusfeodll oinwianqgudeerynpitoisoend daegsacirnisbteAstBhoexesestthoaftsyamrebfoolrsmuTlLattehdaitnctahne msiegannaitnugrfeully, with the TBox T in the background.
language. A symbol S is L-relevant for given T if there exists a -ABox and L-query q such that A is consistent w.r.t. T , S 2 sig(q), and certT ;A(q) 6= ;.
L := T [ fS 2 NC [ NR j S is L-relevant for T and g: For example, the concept name A is both IQ- and CQ-relevant for = frg given T = f9r:> v Ag, as witnessed by the query q = A(v) and -ABox fr(a; b)g rsoinlecencaemrteTs; Aca(nq)no=t ofaccgu.rNionteanthiantstanTIcQe qcaunerny.evWere ianrceluindteeraensyterdolien ndaemciedsinsginLcerelevance for L 2 fIQ; CQg: given a TBox T , a signature and a symbol S, sdFFieoogcrrniIdaettthxesueahrwmoefohuprellmdteTLh,en.eirfro, tTiStb=se2usfuArcpTeLvsr.istC9ionrlg:enBaotrgthleyaa,ttn,htdhiantisgcpee=nrrtoeTfbrAa;lAelg,m(,Bwte(hcvaen)nn)eeB=bde2n;=uofstoeTrIhdQaavt,lolebucot-TIAmBQBp=ou2xteesTTCCtAhQQe... For the latter, note that certT ;A(9v:B(v)) = f()g when A = fA(a)g (and where () is the empty tuple representing a positive answer to the Boolean query). The following lemma, which is independent of the DL in which TBoxes are formulated, shows that we can always concentrate on CQs of such a simple form. It is an easy consequence of the fact that, since composite concepts are disallowed, CQs are purely positive, existential, and conjunctive.
Lemma 1 allows us to consider only queries of the form 9v:A(v) and 9v; v0:r(v; v0) when dealing with CQ-relevance. From now on, we do this without further notice.
Answering conjunctive queries is typically more di cult than answering
instance queries, both regarding the computational complexity and the required
algorithms [
Proof (sketch). Let T be a TBox, a signature, B a concept name that does not occur in T and , and s a role name that does not occur in T and . Then 1. A is CQ-relevant for given T i B is IQ-relevant for [fsg given the TBox
T 0 = T [ TB [ fA v Bg, where TB = f9r:B v B j r = s or r occurs in T g; 2. r is CQ-relevant for given T i B is IQ-relevant for [ fsg given the
TBox T 0 = T [ TB [ f9r:> v Bg, where TB is as above.
The proofs of Points 1 and 2 are similar and we concentrate on Point 1. First suppose that A is CQ-relevant for given T . Then there is a -ABox A such that T ; A j= 9v:A(v). Choose an a0 2 Ind(A) and set A0 := A[fs(a0; b) j b 2 Ind(A)g. Using the fact that T ; A j= 9v:A(v) and the de nition of A0 and T 0, it can be shown that T 0; A0 j= B(a0). For the converse direction, suppose that B is IQrelevant for [ fsg given T 0. Then there is a [ fsg-ABox A0 such that T 0; A0 j= B(a) for some a 2 Ind(A0). Let A be obtained from A0 by removing all assertions s(a; b). Using the fact that T 0; A0 j= B(a) and the de nition of A0 and T 0, it can be shown that T ; A j= 9v:A(v). tu In some proofs, it will be convenient to drop the UNA. The following lemma states that this can be done w.l.o.g. in ALCI (and all its fragments such as EL and ALC) because the certain answers and thus also the notion of L-relevance does not change. The lemma is easily proved using the fact that, in ALCI, we can easily convert a model I for an ABox and a TBox that violates the UNA into a model I0 that satis es the UNA by \duplicating points" and such that I and I0 are bisimilar.
is identical with and without UNA.
An analogous statement fails, e.g., for ALCF . To see this, take T = f> v ( 1 r) t Ag and = frg. Then A is IQ- and CQ-relevant with UNA due to the ABox fr(a; b); r(a; b0)g, but it is not relevant without UNA. 4
The E L Family
We study ABox relevance in the EL family of lightweight DLs [
Throughout this section, we assume that the UNA is not imposed. This can be done w.l.o.g. due to Lemma 2. Since DLs of the EL family do not o er negation, it may be deemed unnatural to de ne ABox relevance based on literal ABoxes, which admit negation. However, as the following lemma demonstrates, there is actually no di erence between de ning ABox relevance based on literal ABoxes and positive ABoxes, in which all concept assertions are of the form A(a) with A a concept name. This holds for both IQ- and CQ-relevance. The proof is via canonical models.
conjunctive query q, we have certT ;A(q) = certT ;A (q), where A is the restriction of A to assertions of the form A(a) and r(a; b).
We now state the announced converse of Theorem 1. The proof proceeds by showing that A is IQ-relevant for given T i B is CQ-relevant for [ fXg given the TBox T 0 = T [ fA u X v Bg, where B and X are concept names that do not occur in T .
vance.
Theorem 2 allow us to choose freely between IQ and CQ when proving lower and upper bounds for relevance in the E L family of DLs. Note that, by the example given in Section 2, these two notions do not coincide even in E L.
Proof. We consider IQ-relevance. Let T be an E L-TBox and a signature. De ne the total -ABox as A := fA(a ) j A 2 g [ fr(a ; a ) j r 2 g. Claim. For all concept names A, A is IQ-relevant for A(a ); given T i
T ; A
j=
Since the instance problem can be solved in polynomial time in E L [
The \if" direction of the above claim is trivial. For the \only if" direction,
let A be IQ-relevant for given T . By Lemma 3, there is a positive -ABox A
such that T ; A j= A(a0) for some a0 2 Ind(A). Let I be a model of T and A .
We have to show that a0I 2 AI . Modify I by setting bI := aI for all individual
names b. It is easy to verify that I is a model of the positive ABox A and of T .
Since T ; A j= A(a0), we have a0I 2 AI as required. tu
Note that we need very little for the proof of Theorem 3 to go through: it su ces
that A is consistent with every TBox and that the DL in question is monotone.
It follows that for all DLs of this sort, deciding IQ- and CQ-relevance has the
same complexity as subsumption/instance checking (whose complexity coincides
for almost every DL). The upper bound is obtained as in the proof of Theorem 3,
based on instance checking. For the lower bound, note that C is subsumed by
D w.r.t. T i B is IQ-/CQ-relevant for T [ fA v C; D v Bg and the signature
fAg, where A; B 2= sig(C; D; T ). We thus obtain the following result for the DL
E LI, in which subsumption and instance checking are ExpTime-complete [
The simplest extension of E L in which the total ABox A is not consistent w.r.t.
every TBox is E L?. Here, deciding relevance is signi cantly harder than deciding
subsumption/instance checking (which can be decided in polynomial time). We
start by proving an NP lower bound for a very simple fragment of E L?: let L
be the DL that admits only CIs of the form A u A0 v B and A u B v ?, with A,
A0, and B concept names. This is a fragment of E L?, but also of those variants
of DL-Lite that admit conjunction on the left-hand side of CIs [
Proof. Reduction from SAT. Let ' be a propositional formula in NNF using variables v0; : : : ; vn and sub(') the set of subformulas of '. De ne a TBox T as the union of the following: tu tu { Avi u A:vi v ? for all i n; { A# u A v A for all = # ^ { A# v A ; A v A for all
2 sub('); = # _ 2 sub(').
Let = fAvi ; A:vi j i given T i ' is satis able.
ng. It can be veri ed that A' is IQ-relevant for For full E L?, Theorem 5 can be improved to an ExpTime lower bound. The idea is to make use of an existing ExpTime lower bound for deciding conservative extensions in E L/E L? established in [18]. To implement this, we rst establish a technical proposition. Its proof is similar to Lemma 22 (i) in [18] and given in the full paper.
We now prove the lower bound.
Proof. We consider IQ-relevance. The following result can be established by carefully analyzing the reduction underlying Theorem 36 in [18]: given an E L?TBox T , a signature , and a concept name B, it is ExpTime-hard to decide if there exist a -concept C such that C is satis able w.r.t. T and T j= C v B. Thus it su ces to show that the following conditions are equivalent, for any E L?-TBox T , signature , and concept name B: 1. there exists a -concept C such that C is satis able w.r.t. T and T j= C v
B; 2. there exists a -ABox A such that (T ; A) is consistent and (T ; A) j= B(a) for some a 2 Ind(A).
The implication from Point 1 to Point 2 is trivial and the reverse direction is established by Proposition 1.
To prove a matching upper bound for Theorem 6, we rst establish a proposition that constrains the shape of ABoxes to be considered when deciding relevance in E L?. Here and in what follows, an ABox A is tree-shaped if 1. the directed graph (Ind(A); f(a; b) j r(a; b) 2 A for some r 2 NRg) is a tree and 2. for all a; b 2 Ind(A), there is at most one role name r such that r(a; b) 2 A. The following is a simple consequence of Proposition 1.
For the upper bound, we use non-deterministic bottom-up automata on nite, ranked trees. Such an automaton is a tuple A = (Q; F ; Qf ; ), where Q is a nite set of states, F is a ranked alphabet, Qf Q is a set of nal states, and is a set of transition rules of the form f (q1; : : : ; qn) ! q, where n 0, f 2 F is of rank n, and q1; : : : ; qn; q 2 Q. Note that transition rules for symbols of rank 0 replace initial states.
Automata work on nite, node-labeled, ordered trees T = (V; E; `), where V is a nite set of nodes, E V V is a set of edges, and ` is a node-labeling function the maps each node v 2 V with i successors to a symbol `(v) 2 F of rank i. We assume an implicit total order on the successors of each node. A run of the automaton A on T is a map : V ! Q such that { (") 2 Qf , with " 2 V the root of T ; { for all v 2 V with `(v) = f and where v has (ordered) successors v1; : : : ; vn, n 0, we have that f ( (v1); : : : ; (vn)) ! (v) is a rule in .
An automaton A accepts a tree T if there is a run of A on T . We use L(A) to denote the set of all trees accepted by A. It can be computed in polynomial time whether L(A) = ;.
Proof. Let T be an E L?-TBox, a signature, and A0 a concept name such that it is to be decided whether A0 is IQ-relevant for given T . W.l.o.g., we may assume that A0 occurs in T . We use sub(T ) to denote the set of all subconcepts of concepts occurring in T and set := [ sub(T ). A -type is a nite set t of concept names that occur in and such that u t is satis able w.r.t. T . A -type is a subset t of such that u t is satis able w.r.t. T . Given a -type t, we use clT (t) to denote the set fC 2 j T j= u t v Cg. We use ex(T ) to denote the number of concepts of the form 9r:C that occur in T (possibly as a subconcept). De ne an automaton A = (Q; F ; Qf ; ) as follows: { F = fht; r1; : : : ; rni j t a { Q is the set of -types;
-type, i < ex(T )g with ht; r1; : : : ; rni of rank n; { Qf = fq 2 Q j A0 2 qg; { consists of all rules f (q1; : : : ; qn) ! q with f = ht; r1; : : : ; rni such that q = clT (t [ f9r:C 2 sub(T ) j r = ri and C 2 qi for some i with 1 i ng: In the full version of this paper, we show that L(A) 6= ; i A0 is IQ-relevant for given T . Since A is single-exponentially large in jT j and the emptiness problem can be decided in polynomial time in the size of the automaton, we obtain a single-exponential-time procedure for deciding relevance in E L?. tu
We establish some rst results for ABox relevance in ALC and its extensions. For ALCI, we prove decidability of IQ- (and thus also CQ-) relevance, and a NExpTimeNP upper bound; for ALCF , we prove undecidability of IQ-relevance. 5.1
ABox Relevance in ALC and ALCI The NExpTimeNP upper bound is based on the following theorem, which places an upper bound on the size of ABoxes that we need to consider.
propositional ABoxes, then there is a literal -ABox A such that A is consistent w.r.t. T , T ; A j= A(a) for some a 2 Ind(A), and jInd(A)j 2jT j+j j. Proof. We do not make the UNA. We consider only the case A 2 NC, as the case r 2 NR is analogous. Assume that A is IQ-relevant for given T . Then there is a literal -ABox A such that A is consistent w.r.t. T and T ; A j= A(a0) for some a0 2 Ind(A). Let I be a model of A and T , and let J be the ltration of I w.r.t. = cl(T ) [ fA; :A j A 2 g, i.e., de ne an equivalence relation
I I by setting d e i and set Clearly, j J j an ABox fC j C 2 ^ d 2 CI g = fC j C 2
^ e 2 CI g
J := f[d] j d 2 I g AJ := f[d] j d 2 AI g rJ := f([d]; [e]) j 9d0 2 [d]; e0 2 [e] : (d0; e0) 2 rI g aJ := [aI ] 2jT j+j j. It is routine to prove that J is a model of T . De ne
AJ = fA(a[d]) j A 2 f:A(a[d]) j A 2 fr(a[d]; a[e]) j r 2 ^ [d] 2 AJ g [ ^ [d] 2 (:A)J g [ ^ ([d]; [e]) 2 rJ g: Clearly, J is a model of AJ . Thus, AJ is consistent w.r.t. T . It remains to show that T ; AJ j= A(a[a0I]). Let J 0 be a model of AJ and T . De ne a model I0 from J 0 by setting aI0 = (a[aI])J 0 for all a 2 Ind(A). It is readily checked that I0 is a model of A and T , and thus a0 2 AI0 , implying a[Ja0I0] 2 AJ 0 as required. tu It is interesting to note that the bound from Theorem 8 is tight. To see this, let T := f
A v :P0 u
u :Pn 1 9r:(P0 u 9r:((:P0 t 9r:((:P0 t 9r:(P0 u
u Pi) v :Pi u Pi 1 u :Pi) v Pi t :Pi 1) u Pi) v Pi t :Pi 1) u :Pi) v :Pi and = fA; rg. Then X is relevant for T and , but the smallest witness ABox is an r-chain of length 2n whose last element is an instance of A. Note that an ABox that has the form of a cycle of length < 2n is inconsistent w.r.t. T . We now use Theorem 8 to prove membership in NExpTimeNP.
Theorem 9. In ALCI, IQ-relevance and CQ-relevance are in NExpTimeNP. Proof. We show the result for IQ-relevance; the upper bound for CQ-relevance follows by Theorem 2. Consider the following nondeterministic algorithm: Step 1: Guess a -ABox A such that jInd(A)j = 2jT j+j j.
Step 2: Use an oracle to verify that A is consistent with T . Reject if not. Step 3: For each a 2 Ind(A), use an oracle to check whether A [ f:A(a)g is consistent with T . Accept if for some a 2 Ind(A) the ABox A [ f:A(a)g is inconsistent with T . Otherwise reject.
If the algorithm accepts, then we have found a -ABox A consistent with T which implies some assertion A(a), i.e. A is IQ-relevant for given T . Conversely, if A is IQ-relevant, then by Theorem 8, there must be some -ABox A with at most 2jT j+j j individuals which is consistent with T and such that T ; A j= A(a) for some a 2 Ind(A). We create a new -ABox from A as follows: A0 = A [ f>(bi) j 1 i 2jT j+j j jInd(A)jg. By construction, A0 has precisely 2jT j+j j individuals, is consistent with T , and is such that A0; T j= A(a). If A0 is guessed in Step 1, the algorithm accepts.
We remark that in Steps 2 and 3 of the algorithm, we test the consistency of literal ABoxes that are exponentially larger than the TBox T . Because of this, the standard precompletion approach to deciding ABox consistency w.r.t. a TBox requires only nondeterministic polynomial time (rather than the usual deterministic single-exponential time). This means that we can use an NP-oracle in Steps 2 and 3, yielding membership in NExpTimeNP. tu We conjecture that IQ- and CQ-relevance are actually NExpTimeNP-complete, but leave the lower bound open for now. We show that the simple addition of functional roles to ALC leads to undecidability of IQ-relevance, and that the further addition of inverse roles leads to undecidability of CQ-relevance. Both proofs are by reduction of the tiling problem of nite (but unbounded) rectangles. An instance of this problem is given by a triple (T; H; V ) with T a non-empty, nite set of tile types including an initial tile Tinit to be placed on the lower left corner and a nal tile T nal to be placed on the upper right corner, H T T a horizontal matching relation, and V T T a vertical matching relation. A tiling for (T; H; V ) is a map f : f0; : : : ; ng f0; : : : ; mg ! T such that n; m 0, f (0; 0) = Tinit, f (n; m) = T nal, (f (i; j); f (i + 1; j)) 2 H for all i < n, and (f (i; j); f (i; j + 1)) 2 v for all i < m. It is undecidable whether a tiling problem has a tiling.
For the reduction to IQ-relevance in ALCF , let (T; H; V ) be an instance of the tiling problem with T = fT1; : : : ; Tpg. We construct a signature and a TBox T such that (T; H; V ) has a solution i a selected concept name A is IQ-relevant for given T . More precisely, the ABox A witnessing IQ-relevance has the form of an n m-rectangle together with a tiling for (T; H; V ). W.l.o.g., we concentrate on solutions where T nal occurs nowhere else than in the upper right corner. The ABox signature is
= fT1; : : : ; Tp; x; yg where T1; : : : ; Tp are used as concept names and x and y are functional role names representing horizontal and vertical adjacency of points in the rectangle. In T , we additionally use the concept names U; R; A; Y; Z; C, where U and R mark the upper and right border of the rectangle, A is the concept name used in the instance query, and Y , Z, and C are used for technical purposes explained below. More precisely, T is de ned as the union of the following CIs, for all (Ti; Tj ) 2 H and (Ti; T`) 2 V :
T nal v Y u U u R 9x:(Tj u Y u U ) u Ti v U u Y 9y:(T` u Y u R) u Ti v R u Y (9x:9y:Z u 9y:9x:Z) t (9x:9y::Z u 9y:9x::Z) v C 9x:(Tj u Y u 9y:Y ) u 9y:(T` u Y u 9x:Y ) u C u Ti v Y Y u Tinit v A
U v 8y:?
R v 8x:? 9y::R v :R 9x::U v :U 1 s<t p Ts u Tt v ? t Observe that the concept name A used in the instance query occurs only once in the TBox, on the right-hand side of a CI. Taken together, the upper part of T ensures the existence of a tiled n m-rectangle in a witness ABox. The concept name Y is entailed at every individual name in such an ABox that is part of the rectangle. Observe that the CIs for Y enforce the horizontal and vertical matching conditions. The CI for C enforces con uence, i.e., C is entailed at an individual name a if there is an individual b that is both an x-y-successor and a y-x-successor of a. This is so because, intuitively, Z is universally quanti ed: if con uence fails, we can interpret C in a way such that neither of the two disjuncts in the pre-condition of the CI for C is satis ed. The following lemma is proved in the full paper.
consistent with T and such that T ; A j= A(a) for some a. Undecidability of IQ-relevance now follows directly from Lemma 4.
The reduction to CQ-relevance in ALCF I is very similar to the previous one. We now assume that the roles x and y are functional and inverse functional. The signature is as in the previous proof, and also the TBox T is identical except that we replace the CI with C on the right-hand side with the following one, where B ranges over all Boolean combinations of the concept names Z1; Z2, i.e., over all concepts L1 u L2 where Li is a literal over Zi, for i 2 f1; 2g: 9x:9y:B u 9y:9x:B v C The following lemma is proved in the full paper.
consistent with T and such that T ; A j= 9v:A(v). We thus get the desired result.
6
Several notions of relevance have been previously proposed in the philosophy and arti cial intelligence literatures, but they are rather di erent in nature from the notion of relevance we study in this paper. For example, in the area of relevant logic [19], it is an inference, rather than a symbol, which is said to be relevant, and in the work of Levy et al. [20] it is a premise of a proof which may or may not be relevant to the deduction of a given formula. Relevance of a signature (hence symbol) can be found in Lakemeyer's study of relevance [21], in which he de nes relevance of a signature to a formula given a theory as well as relevance of two signatures to each other given a theory. However, Lakemeyer's notions of relevance are de ned only for propositional logic, and even in the case of propositional theories, do not appear to bear any relationship to ABox relevance as studied in this paper. 7
We have introduced a new notion of relevance that describes when a symbol can be used meaningfully in queries that are posed to ABoxes formulated in a given signature, with a given background TBox in place. We have established a relatively complete picture regarding the complexity of deciding IQ- and CQrelevance in the E L family of lightweight DLs, and some rst results for DLs of the ALC family. Some important open questions have been pointed out in the paper, most notably the exact complexity of relevance in ALC and ALCI, and the decidability of CQ-relevance in ALCF . Another open issue is the formulation of a notion of relevance for queries that may contain composite concepts. This is not trivial due to the possibility of using tautological concepts in the query. Finally, we are currently investigating whether the set of relevant symbols as de ned in this paper can be used to obtain more e cient algorithms for module extraction. 18. Lutz, C., Wolter, F.: Deciding inseparability and conservative extensions in the description logic EL. To appear in Journal of Symbolic Computation (2009) 19. Mares, E., Meyer, R.: Relevant Logic. In: The Blackwell Guide to Philosophical
Logic. Blackwell (2001) 20. Levy, A.Y., Fikes, R., Sagiv, Y.: Speeding up inferences using relevance reasoning:
A formalism and algorithms. Arti cial Intelligence 97(1-2) (1997) 83{136 21. Lakemeyer, G.: Relevance from an epistemic perspective. Arti cial Intelligence 97(1-2) (1997) 137{167