K

Consider the following extension to Homework problem 8:

A strategy D is (// A B) | (join D1 D2)

To define a well-formedness predicate for strategies, we introduce Source and Target predicates:

well-formed(// A B) = true
well-formed(join D1 D2)
   iff well-formed(D1) and well-formed(D2) and Source(D2) = Target(D1)
Source(// A B) = A
Target(// A B) = B
Source(join D1 D2) = Source(D1)
Target(join D1 D2) = Target(D2)

An object path p satisfies strategy D = (join D1 D2) iff p is either a path from an A-node to B-node or p1 is the fusion of two paths p1 and p2 where p1 satisfies D1 and p2 satisfies D2.

The fusion of two paths p1 = (x1, ...  xn) and p2 = (y1, ...  ym), where xn = y1, is

the path (x1, ... xn-1 y1, ... yn). (The join point of the two paths appears only once.)

Consider a class graph G and the following graph construction:

PG[G](// A B) = Graph(Paths[G](A B))
PG[G](join D1 D2) = PG[G](D1) union PG[G](D2)

Graph(Paths[G](A,B)) is the smallest graph that consists of all paths from A to B in G. A path from A to B must satisfy the relation (C.=>)* where C is a field relation (or has-a relation)

from an AlternativeName to a TypeName. TypeName => AlternativeName is the reverse is-a

relation. Both has-a and is-a relations are introduced by the DD and Alternative rules in hw 8.

PG[G](D) is the propagation graph that we consult during object traversal to decide which edges in the object graph to follow, as we did in homework 8. We define the propagation graph traversal of an object graph as follows: When we are at a node iAlternativeName1 with outgo-

ing edge (iAlternativeName1,x,iAlternativeName2) we traverse field x iff the propagation
graph has an edge (AlternativeName1,x,type(AlternativeName2) where AlternativeName

is the constructor of iAlternativeName and type is defined by the is-a relation.

s

Theorem S: Given a class graph G and a well-formed strategy D, the propagation graph traversal of an object graph belonging to Objects(G) produces only object paths that satisfy D.

Question 1: Show a counter example to this theorem by showing a class graph G and a strategy D where the propagation graph traversal produces object paths that don’t satisfy D.

Question 2: Can you think of a constraint C we could impose on G and D so that if C(G,D) holds then Theorem S holds.