From wand@ccs.neu.edu Fri Nov 17 12:32:50 2000 Date: Fri, 17 Nov 2000 12:32:16 -0500 (EST) To: Karl Lieberherr Here is a revised and cleaned-up version of the presentations I gave at BBN and at the seminar last week. The stuff about paths through strategy graphs is new since Wednesday. --Mitch **************************************************************** Strategies for finding paths in object graphs. 1. Notation: We will write R(a,b), aRb, and (a,b) \in R interchangebly. We denote composition of relations by "." eg x (R.S) z iff there exists a y st xRy and ySz. We also write x R y S z. Sometimes we'll even omit the ".", and write RS. And of course we get to take the reflexive transitive closure of a relation, denoted R*, as usual. If B is a set, we will occasionally write R.B for {a | exists b in B s.t. aRb}. We often think of directed graphs as relations (and vice versa), so we write C(c1,c2) or c1 C c2 when there is an edge from c1 to c2 in C. 2. Definitions Def. A class graph consists of a set of classes, a relation C on classes ("has as part"), and a partial order <= on classes ("is subclass of") We write => for the inverse of <= . Def. If C is a class graph, then an object graph of C is a directed graph O equipped with a map class : O -> C, such that: if O(o1,o2), then class(o1) <=.C.=> class(o2) {all edges are images of ones in C}. May sometimes wish for an additional condition: if class(o1) <= c1 and C(c1,c2), then there exists an o2 st O(o1,o2) and class(o2) <= c2 {there are enough edges}, but this may not happen in practice, because fields may be null. We sometimes say o is of *type* c iff class(o) <= c. This model doesn't have labels on the edges. However, if class(o) = c, then for every edge out of o (to o') there exists a c' such that c <=.C c' => o'. c' is the "declared type" of the edge, and we use this "declared type" in place of the label. It is a small matter of engineering to add label management. The issue is: we are at an object of class c, and we wish to find all reachable objects of class <= c'. Which edges must we explore in order to find them. That is, we need to find POSS(c,c') = { c'' | there exists an object graph O of C and objects o, o', and o'' such that (1) class(o) = c (2) class(o') <= c' (3) class(o'') <= c'' (4) c <=.C c'' (5) o O o'' O* o' } This set is defined by quantification over all object graphs, but of course we need to find it statically. 3. Navigation algorithms We can use these sets to find not just reachable objects of a given type, but paths that pass through objects of a given type. Def. Let R = (c1,..,cK) be a non-empty sequence of classes. Let p = (o1,..,oN) be a path in O. Then p is an R-path iff there is a subsequence o_{j_1} ,..,o_{j_K} of p such that for each i, o_{j_i} has type c_i, and j_K = N (ie the last element of the path must be part of the subsequence). We say an R-path is minimal iff it has no initial segment that is also an R-path. Given an object o, we can visit all the endpoints of minimal R-paths starting at o as follows: Procedure search(o,R): Let R = (c1,..,cn). 1. If o does not have type c1, then for each e in POSS(class(o),c1), search(o.e, R). {We are not yet on a path}. 2. If o has type c1, and R = (c1), then visit(o). 3. If o has type c1, and R = (c1, c2,..,cn), then search(o,(c2,..,cn)) . We could find all R-paths, by modifying step 2 to say: visit(o). Then for each e in POSS(class(o),cn), search(o.e, (c1)). Lieberherr et al [ ] introduce a more complex set of paths, defined by a "strategy graph": Def. A strategy graph is given by a set of states Q, a relation S on states, a map class : Q -> C, a set QI \subset Q of initial states, and a set QF \subset Q of final states. We denote such a strategy graph by S. Def. A path p = (o1,..,oN) in O is an S-path iff there is a subsequence o_{j_1} ,..,o_{j_K} of p and a path (q_1,...,q_K) in S such that for each i, o_{j_i} has type class(q_i), and j_K = N, and q_K \in QF. As before, we say an S-path is minimal iff it has no initial segment that is also an S-path. Given an object o, we can visit all the endpoints of minimal S-paths starting at o as follows: Let Q' be a subset of Q. Initialize Q' to QI Procedure search(o,Q'): 1. If o does not have type class(q) for any q in Q', then for each q in Q', and each e in POSS(class(o),class(q)), search(o.e, Q'). {We are not at a point on the subsequence} 2. If o has type class(q) for some q in Q' \intersect QF, then visit(o). 3. Otherwise let Q'' = {q in Q' | o does not have type class(q)} u {q'| exists q in Q' s.t. o has type class(q) and S(q,q')}. Then search(o,Q''). We typically start with a inique start state and an object o that matches that state. 4. Calculating POSS We develop a static description of POSS using a sequence of lemmas. We start with a fixed class graph C. Lemma 1. There exists an object graph O of C and objects o1, o2 such that O(o1,o2) iff class(o1) <=.C.=> class(o2) Proof. The forward direction is immediate from the definition of an object graph of C. For the reverse direction, construct an object graph with two objects o1 and o2 and the specified link. Lemma 2. There exists an object graph O of C and objects o1, o2 such that O*(o1,o2) iff class(o1) (<=.C.=>)* class(o2) . Proof. Again, the forward direction is immediate. For the reverse, induct on the definition of (-)*, using the preceding lemma. Lemma 3. Let c1 and c2 be classes. Then there exists an object graph O of C and objects o1, o2 such that class(o1) <= c1 and class(o2) <= c2 and O*(o1,o2) iff c1 => class(o1) (<=.C.=>)* class(o2) <= c2. Theorem. POSS(c,c') = {c'' | c <=.C c'' and c'' =>.(<=.C.=>)*.<= c'} Proof: We must show that there exists an object graph O of C and objects o, o', and o'' such that (1) class(o) = c (2) class(o') <= c' (3) class(o'') <= c'' (4) c <=.C c'' , and (5) o O o'' O* o' iff c <=.C c'' and c'' =>.(<=.C.=>)*.<= c' . The forward direction is immediate from the definition of an object graph of C. For the reverse definition, consider a sequence of classes c <=.C c'' => c1 (<=C=>) c2 (<=C=>) ... (<=C=>) cN <= c' Then construct an object graph with N+2 objects, of classes c, c1,...,cN, c'. Let o be the first object in this sequence, o'' be the second, and o' be the last. This object graph satisfies the requirements. QED. ****************************************************************