Hi,

I need to represent a data structure in sql server which I think is
called a "heterogeneous tree", and I don't know how to efficiently do
this in sql.

I have a Container table :

ContainerName
C1
C2
C3

and each Container can have any amount of compartments in an
ContainerCompartment Table:

ContainerName CompartmentName
C1            C1P1
C1            C1P2
C2            C2P1
C2            C2P2

Each container can be sticked into a compartment of another container.
Now I am trying to represent this tree in SQL:

          C1
        /   \
       C1P1 C1P2
      /
     C2
    /  \
C2P1 C2P2
  /     \
C3      C3

I came up with this table "Tree":

ContainerName  ParentContainer ParentContainerCompartment
C1             NULL            NULL
C2             C1              C1P1
C3             C2              C2P1
C3             C2              C2P2

But this is bad... I can set up a foreign key relationship between
ParentContainer and ContainerName in "Tree" but I cannot set up a
relationship between ParentContainerCompartment and the Compartment of
the ParentContainer. I think I got the whole ER design wrong.

TIA for any hint on this!

Regards
DC

Get a copy of TREES & HIERARCHIES IN SQL.  Since you want to do math on
the containers, uses the Nested sets model.

I got SQL for smarties, excellent book but it says "it all depends..."
about the tree choice to make. I would like to try out the nested set
model as a kind of optimization, but as you can see from my post my
current problem is not so much about performance but about data
integrity. Will your book about trees & hierachies answer this question
(optimal data structure for representing a tree with nodes of different
types)?

Regards
DC

A basic principle is that the nodes are separate from the tree
structure.  With a varying, mixed tree is little messy but the
complexity can be hidden in VIEWs.  It is a bit of work, but soooo much
easier than procedural code in a few hundred front end apps.

Buy the TREES book, look at the various models.  If that does not help,
hire me so I will make my house note next month :)

Show quote Hide quote You're pretty close: you can use a foreignn key between (ParentContainer,
ParentContainerCompartment) referencing the container table.

Try something like this:

create table Container
(
  Container varchar(20) not null primary key
)


create table Compartment
(
  Container varchar(20) not null
    references Container on delete cascade,
  Compartment varchar(20) not null,
  constraint pk_Compartment primary key (Container,Compartment)
)

create table ContainerCompartment
(
  Container varchar(20) not null primary key
    references Container on delete cascade,
  ParentContainer varchar(20) not null,
  ParentCompartment varchar(20) not null,
  constraint fk_ContainerCompartment foreign key
    (ParentContainer,ParentCompartment) references
Compartment(Container,Compartment)
)
GO

insert into Container(Container) values ('C1')
insert into Container(Container) values ('C2')
insert into Container(Container) values ('C3')

insert into Compartment(Container,Compartment) values ('C1','C1P1')
insert into Compartment(Container,Compartment) values ('C1','C1P2')
insert into Compartment(Container,Compartment) values ('C2','C2P1')
insert into Compartment(Container,Compartment) values ('C2','C2P2')

insert into
ContainerCompartment(Container,ParentContainer,ParentCompartment)
  values('C2','C1','C1P1')


insert into
ContainerCompartment(Container,ParentContainer,ParentCompartment)
  values('C3','C2','C2P1')

David

Hi David,

thanks a lot for the suggestion. I also wanted to make sure that a
compartment is only added to the tree if the parent is a container that
actually owns such a compartment, I can implement that with a trigger.

What do you think about a modification, where the Tree table contains
references to either a container or a compartment, example:

Node   ParentNodeId ContainerId   CompartmentId
1         null                1                  null
2         1                    null              1
3         1                    null              2

This way I could use the coalesce expression to either pick a
containerid or a compartmentid and add other parts (like a
CompartmentDrawer) to the hierarchy by adding a CompartmentDrawerId
column the the Tree table.

Regards
DC

Another case for IDENTITY
Find duplicates
When was a database accessed last
Good or Bad practice?
How to: CrossTab or Pivot