Oracle FAQ | Your Portal to the Oracle Knowledge Grid |
Home -> Community -> Usenet -> comp.databases.theory -> Re: vehicle to autoparts relationships
> Anybody noticed an implicit hierarchy of nested sets yet?
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.
A more sophisticated variant of Nested Sets has been widely popularized by Joe Celko. The main idea behind this encoding is representing nested sets as intervals of integers... Received on Wed Nov 22 2006 - 15:52:08 CST