Re: About Replicating Graphs and Trees - (Reponse Part II)

Tech-Archive recommends: Repair Windows Errors & Optimize Windows Performance

From: Sky (forums_at_xact-solutions.removethis.com)
Date: 04/14/04 

Date: Wed, 14 Apr 2004 20:28:00 +0200

You wouldn't have some of that scotch to share??
Ok. So I gather that Synching trees is not a walk in the park. And that
Newton, Einstein, Pinky and the Brain, all failed at solving it...

Considering that I'm more on the level of Pinky, not the Brain, I've got
about a snowballs chance in hell in solving it.

But ...there's 'impossible' ...and 'good enough to hold through the day'...
At this point, I guess what I'm going to have to settle for is "Things we
can do", and "things that we can't do".

Btw: I'm continuing not because I just dont get a hint when I've been given
a strong one... and certainly not that I think I am smart enough to figure
this out.
It's just that...I really really needed to use it... or my ass is grass at
this current job. So... I'm going to continue sketching lines and arcs until
I go blind.

What can we do with the various techniques at our disposal:
Using AdjacentList theories rather than Celko's or MaterializedLists, one
can deal with the following problems you brought up.
> 1. Someone adding a child node to a parent which someone else has moved
> which very may well render the business decision to add that child node
> irrelevant.
True -- but duplication such as this can be 'cleaned' up by the user who
added it after he realizes that it is redundant, when he gets back to the
office?
Not great -- but "possible".

> 2. Two different people adding the same node to the tree. I'm not
referring
> to the hidden, technical ID thing which end users have no clue what it is.
> I'm talking about adding the same data value to the tree. This is mostly
> resolvable, but you are going to require the use of very sophisticated
data
> mining algorithms to determine that the information that two different
This is not my problem. Atleast today. As far as I can see, in the real
world, people duplicate a ton of things anyway...then realize that was done
by someone else, and throw the paper away (re-delete the node).
And the fact that we are talking about tasks, if we end up with two people
putting in the same task, it's pretty obvious to the receiver that they are
the same thing, and igore or delete one...?
Again, Not great -- but "possible".

> 3. Two people adding different nodes at the same initersection point in
the
> tree. Is it allowed? Does one addition cause the other to become
obsolete.

Intersection point? I don't know that term. Are we talking about the same
Materialized Path?
If so, then yes - it's up to the synch device to renumber them/reorder them.
As you pointed out, the end user doesn't care what their numbering/guid/path
is -- just as long as it Looks like it is in the right location.
This is especially moot in the case of Adjacent Lists since there is no
Order...?
Again. Holding, albeit rough.

> 4. One person deleting a node while another one moves it to a different
> location. Which change stays or to both stay?

Now, HERE we have a problem. Beats me.
Guess I would have to do it based on time... but if the delete is timed as
being later than the move then one ends up with disconnect islands of
nodes.... Hum.

> 5. One person deleting a node with children while someone else updates one
> of the children, adds children, or rearranges that portion of the tree?
Did
> the actions taken by the second person make the decision by the first
> invalid? What do you do with the children and all of the changes if in
fact
> you decide that the delete should happen?

I think by breaking the Edges into a secondary table and not keeping it so
closely linked to the Vertex, then the deleting a Record is not a direct
result of deleting a link, but rather a case of deleting the Record only
when the Valence of the Vertex becomes 0...sort of how MS handles COM
activex objects...
Or, more importantly, that these delete decisions are never handled on the
Client. Only on the server. It might have no more Edges to it on the Client,
hence is invisible /inaccessible, but the Vertex and its data is still there
until
the server does a cleanup routine and sees that there are Vertexes with
Valence=0, deletes them, and the Records that they are pointing to...
Who knows.

I'll keep messing around. Not everything can be solved -- I can see that --
but if I can get the number of "impossibles" down to "ok. So it will glitch
some times", but the overall usefullness is worth it", then I can work with
it until a better theory/plan of attach becomes available...

PS:
By the way Michael -- thanks for all the great help. I might not be getting
a "how to do it" response -- but I very much appreciate the fact that you
have put in so much considered time into your responses.
Thanks.
(Even if you are just treating my messages as an excuse to hit the bottle
again ;-)

"Michael Hotek" <mhotek@nomail.com> wrote in message
news:OHvHQ%23dIEHA.3356@TK2MSFTNGP11.phx.gbl...
> I'm debating this. Need to go get another glass of Scotch. Things seem
to
> make more sense after a couple of them. :)
>
> It wasn't making much sense until I changed my font to wingdings. Didn't
> make any more sense after doing that, but it was much more entertaining!
>
> I don't have any real answers on your manipulation of the trees. The
> comparison to a file system isn't accurate. Simply because you aren't
> allowed to take the file system offline like you can data, manipulate it,
> and upload it back. You simply aren't allowed to do that specifically
> because of the issue you are dealing with here. It causes instability of
> the structure as well as introducing many cases which are unsolvable.
>
> Allowing offline, full manipulation of the tree is going to land you in a
> completely unsolvable situation. No mater what method you use to render
the
> tree, you still have to come up with a solution several issues:
>
> 1. Someone adding a child node to a parent which someone else has moved
> which very may well render the business decision to add that child node
> irrelevant.
> 2. Two different people adding the same node to the tree. I'm not
referring
> to the hidden, technical ID thing which end users have no clue what it is.
> I'm talking about adding the same data value to the tree. This is mostly
> resolvable, but you are going to require the use of very sophisticated
data
> mining algorithms to determine that the information that two different
> people phrased completely differently is in fact the same data. You then
> need to merge that data together as well as notifying the people
generating
> the data that it was merged so that they can verify that is in fact what
> should occur.
> 3. Two people adding different nodes at the same initersection point in
the
> tree. Is it allowed? Does one addition cause the other to become
obsolete.
> 4. One person deleting a node while another one moves it to a different
> location. Which change stays or to both stay?
> 5. One person deleting a node with children while someone else updates one
> of the children, adds children, or rearranges that portion of the tree?
Did
> the actions taken by the second person make the decision by the first
> invalid? What do you do with the children and all of the changes if in
fact
> you decide that the delete should happen?
>
> These are just 5 scenarios. You'll note that none of these scenarios are
> based in any technological implementation. Every single scenario exists
> regardless of how you render the tree. Every situation happens as soon as
> you allow disconnected editing of the tree.
>
> In mathematics, there are problems which fall into the classification of
> "unsolvable". Is there a solution to them? No one knows. There are many
> mathematicians still working on them, some of which were posed over 2000
> years ago and while partial solutions exist, no complete solution has ever
> been achieved. Your problem falls into the same category. Is there a
> solution to it? No one knows, simply because the problem still has not
been
> solved. That isn't to say that there isn't a person capable of solving
it,
> it is to say that it is an INCREDIBLY difficult problem that thus far has
> zero solution. You may be the first one to solve the problem, but before
> you even get into the mathematics of the tree rendering, you have to get
> into the mathematics of how to handle the disconnected editing issue.
>
> --
> Mike
> Principal Mentor
> Solid Quality Learning
> "More than just Training"
> SQL Server MVP
> http://www.solidqualitylearning.com
> http://www.mssqlserver.com
>
>

Relevant Pages

  • Re: 30MB Mesh rendered..... slooooow
    ... I have to render some ... Quad tree works pretty simple... ... Create a bounding box around the entire geometry. ... and divide it into 4 equal sized boxes so ...
    (microsoft.public.win32.programmer.directx.graphics)
  • Re: About Replicating Graphs and Trees - (Reponse Part II)
    ... No mater what method you use to render the ... tree, you still have to come up with a solution several issues: ... These are just 5 scenarios. ... you even get into the mathematics of the tree rendering, ...
    (microsoft.public.sqlserver.replication)
  • Re: couldnt understand this code.
    ... rotations. ... each translation and rotation is relative to that of the caller. ... create a simple Tree Generator: www.treegenerator.com:) ... indeed, if you want performance, you should definitely store the mesh model and render it with VBOs. ...
    (comp.graphics.api.opengl)
  • Updating a JTree nodes text with a custom renderer
    ... I am using a custom subclass of DefaultTreeCellRenderer to render tree ... My renderer changes icons and text of some of the nodes. ...
    (comp.lang.java.gui)
  • Das Kalenderblatt 120105
    ... nodes is about 1 for any initial segment of the tree. ... its own, disconnected from mathematics. ... This is a mathematical result concerning an infinite set of numbers. ... like the four sequences representing the four numbers ...
    (de.sci.mathematik)