# Re: vehicle to autoparts relationships

Date: 22 Nov 2006 13:52:08 -0800

Message-ID: <1164232328.846361.218780_at_h54g2000cwb.googlegroups.com>

> Anybody noticed an implicit hierarchy of nested sets yet?

Nested Sets ^^^^^^^^^^^^^^

Another approach to a tree structure is modeling it as nested sets

A

.| ..---- B .|......| .|.......------ C .|......| .|.......------ D .| ..---- E

Figure 5.2a: A tree.

{ { [C] [D] } { [E] } }

Figure 5.2b: Nested sets structure for the tree at fig. 5.2a. Set elements are boxes, and sets are the ovals including them. Every parent set contains its children sets. (This is ASCII adaptation of the figure, of course)

Clearly set containment can clearly accommodate any tree. Whenever we need to grow a tree by adding a new child, we just nest one more set into the appropriate parent set.

A naive nested sets implementation would materialize a set of elements at each node. Aside from the fact that the RDBMS of your choice have has to be capable of operating on sets on the datatype level , this implementation would be quite inefficient. Every time a node is inserted into a tree, the chain of all the containing sets should be expanded to include (at least) one more element.