CoordinateSpace

[Mark S. Miller <mark>]

Date: Mon, 23 Oct 89 14:48:55 PDT
   From: heh (Hugh Hoover)

   >>semantically justify [store working with multiple values/key]

   >That's the problem, of course...

   I think that MarkM's thoughts on non-unique spaces may have some relevance
   here.  I forget whether non-unique only breaks with backfollow or not.
   The upshot is that for orgl's, there are no non-unique spaces (at least in
   some future rev of febe).  Should this apply to tables too? MarkM?

This was already true of the Alpha-1 rev of Febe.  Backfollow wasn't
the motivating problem.  The problem was: if we have

OrglC (
	1 => OrglA (3 => "w", 4 => "x"),
	1 => OrglB (5 => "y", 6 => "z"))

We can form the following two "subsets" of the original:

OrglC' (
	1 => OrglA' (3 => "w"),
	1 => OrglB' (5 => "y"))

and

OrglC'' (
	1 => OrglA'' (4 => "x"),
	1 => OrglB'' (6 => "z"))

(Ravi points out that these are not in fact subsets according to
mathematics.  He suggests "subordinate".  I'll use that until someone
comes up with a better term.)

Now what happens if we combine these?  Do we get the original, or do
we get:

OrglC''' (
	1 => OrglD (3 => "w", 6 => "z"),
	1 => OrglE (5 => "y", 4 => "x"))

By symmetry, the combine operation sees either answer as exactly as
plausible.  Note that OrglIDs wouldn't help, as orgls derived from
OrglA and OrglB would have new IDs, so that we still couldn't tell who
to recombine with whom.  However, if we represent a multi-valued
mapping from integers with a single valued mapping from integers cross
IDs, then we get


OrglC (
	[1, IDA] => OrglA (3 => "w", 4 => "x"),
	[1, IDB] => OrglB (5 => "y", 6 => "z"))

We can form the following two subordinates of the original:

OrglC' (
	[1, IDA] => OrglA' (3 => "w"),
	[1, IDB] => OrglB' (5 => "y"))

and

OrglC'' (
	[1, IDA] => OrglA'' (4 => "x"),
	[1, IDB] => OrglB'' (6 => "z"))

Obviously, these can only combine to form the original.  The invariant
that we must maintain is that the combination of subordinates of X is
itself a subordinate of X.

Note that this exercise isn't just academic.  I figured this all out
as a result of coming across an important case in the Docs&Links layer
which broke the previous multi-valued orgl semantics.  We want a Link
End to be able to be attatch to multiple disjoint parts of a document.
This means that the context path tree has to be a subordinate of the
original document, and contain discontiguous pieces.  The best
protocol I could think of to do this was to create the individual
context path trees for each component of the intended context path
tree, and then combine these.  The above invariant ensure that the
result is itself a valid context path tree.

Note that all of this is very specific to multi-orgls.  It just makes
me suspicious of multi-valued tables, and demonstrates that regular
tables can do their job quite nicely.