Re: Adding history/versioning to a Nested Set model (is it possible?)
Date: Sat, 31 Oct 2009 11:17:11 -0700 (PDT)
Message-ID: <05da7834-6453-4095-8de3-36df9d3d963d_at_j19g2000yqk.googlegroups.com>
On Oct 30, 5:37 pm, Ed Lucas <edward.lu..._at_gmail.com> wrote:
> On 30 Oct, 16:04, Tegiri Nenashi <tegirinena..._at_gmail.com> wrote:
>
>
>
>
>
> > On Oct 28, 9:55 am, Ed Lucas <edward.lu..._at_gmail.com> wrote:
>
> > > Hi All,
>
> > > I'm trying to implement a tree structure, hence I'd like the Nested
> > > Set model, but I need to be able to record the history of the tree
> > > structure *somehow* so that I can access previous versions.
>
> > > I've searched up and down online but all I can find are transactions
> > > +rollbacks.
>
> > > As far as I can see...
>
> > > The simplest option would be to add a version number to the model, but
> > > then every member of the set would have to be updated each time a
> > > change is made - not feasible because of how fast that would make the
> > > table would grow, and how slow that would make it to update?
>
> > > I imagine I could log each action and then replay all the log actions
> > > in a temporary table when I needed them, but that would get pretty
> > > slow after a few updates.
>
> > > The previous Nested Set could be serialised to an blob and stored.
> > > That's currently looking like the best option, but only by process of
> > > elimination...
>
> > > I've probably missed something obvious that's staring me in the face
> > > here! - any suggestions?
>
> > > Thanks for taking the time to read this far, best regards,
> > > Ed
>
> > When you make even small change to a tree (e.g. insert a node), you
> > have to recalculate half of the node encodings on average. This
> > feature alone invalidates nested sets approach for temporal
> > hierarchies. Google nested intervals.
>
> Aha! Thank you very much to you and Vladimir!
>
> Now I just need to sit in a darkened room with a lot of coffee while I
> get my head round it all...- Hide quoted text -
>
> - Show quoted text -
Because there are many kinds of hierarchies, I can suggest the most
common example of this kind of data – an organizational chart. Let me
give an example which maybe can give a better idea about my solution.
Mary Smith is a boss of 100 employees, and one employee is Jane Jones. Try to solve the following using my solution: 1. Mary Smith changed her last name (she got divorced)
Jane Jones changed her last names (she got married)
Generally, every attribute of an entity can be changed at any
time.
2. One week Jane Jones works the morning shift. From 8-12 she works with
customers and her boss is Mary Smith. From 12- 4pm Jane does data entry
and her boss is Jim.
Every second week she works the afternoon shift and also has two
different bosses.
(Note that Jane can have in different periods some new bosses)
3. Jane can enter false data, to get a better salary. Or generally,
solve the problem of any
kind of crime, false data or tries to broke the DB solution.
Now try to apply my solution so that it keeps all information from1.,
2. and 3.
Note that Mary Smith --- Jane Jones is just one line in this hierarchy
and this example is a simple hierarchy, but this is a kind of the real
world example. Hope this example will help.
Vladimir Odrljin Received on Sat Oct 31 2009 - 19:17:11 CET