Oracle FAQ Your Portal to the Oracle Knowledge Grid
HOME | ASK QUESTION | ADD INFO | SEARCH | E-MAIL US
 

Home -> Community -> Usenet -> comp.databases.theory -> Re: vehicle to autoparts relationships

Re: vehicle to autoparts relationships

From: Vadim Tropashko <vadimtro_invalid_at_yahoo.com>
Date: 22 Nov 2006 13:52:08 -0800
Message-ID: <1164232328.846361.218780@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.

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

Original text of this message

HOME | ASK QUESTION | ADD INFO | SEARCH | E-MAIL US