Hi Mira:

the papers below on path constraints might provide a more general
answer to your backward edge idea.

But the visitor/adjuster model is probably more urgent.

-- Karl
=================

The database group at the University of Pennsylvania 
http://www.cis.upenn.edu/~db/
has several papers on path constraints for structured and semi-structured data.
http://www.cis.upenn.edu/~db/langs/

Consider 

Student = StudentName
  <taking> Set(Course).
Course = CourseName
  <enrolled> Set(Student).

School = 
  <students> Set(Student)
  <courses> Set(Course).

This does not give the full information about the intended structure.
We also want:

for all s in aSchool.students 
  for all c in s.taking
    c in aSchool.courses

more formally (taking edge labels as binary predicates)

For all c 
  Exists s 
    students(aSchool,s) and taking(s,c) => courses(aSchool,c)))

The paper talks about path constraints. Seems useful to generate
code for such constraints to check them or define derived edges:

students(aSchool,s) and
taking(s,c) =>
courses(aSchool,c)

Such a constraint is called a word constraint in Abiteboul/Vianu,
PODS 1997: Regular path queries with constraints.
http://www-cse.ucsd.edu/users/vianu/
A summary of this paper:

"Path queries are of the form: Find all objects reachable by 
paths whose labels form a word in r, where r is a regular expression 
over an alphabet of labels"