1

I store hierarchical data in a Node-table, combined with a closure table (NodeClosure). Each node has a column "name" that should be unique among the sibling nodes (link to parent-Node + name should be unique).

This is definition of the tables:

  • Table "Node"
    • Column "nodeID" (int not null, autoincrement, primary key)
    • Column "name" (text not null)
  • Table "NodeClosure"
    • Column "ancestorID" (int not null, primary key, foreign key to Node)
    • Column "descendantID" (int not null, primary key, foreign key to Node)
    • Column "depth" (int not null)

For each parent node, I want the names of its direct child nodes to be unique for that parent node.

Do I have to add a parentID-column to Node (and duplicate the parent/child information) to be able to add a unique index on parentID + name, or is there a different solution?

  • Is a given Node allowed to have more than 1 "parent"? – Kirk Saunders Jun 18 at 14:12
  • No, each node has a single parent. – Tommy Carlier Jun 19 at 9:51
  • It sounds like your choice of model here is based on things you haven't mentioned. Please edit your question to identify what constraints you have, especially what DBMS you are using, and why you choose this Node Closure model. – Rusty Jun 19 at 12:58
1

I'm assuming (from the fact you considered adding a parentId column) that each Node has a single parent.

Two things to do:

  • Add parent column to Node, with a self-referencing foreign key to the nodeID column. This ensures that each Node links to a single parent Node. This should be null for the root node.
  • Get rid of NodeClosure table. Seriously, you don't need it.

So your design becomes simply:

Node

  • nodeID (int not null, autoincrement, primary key)
  • parentID (int null, foreign key to Node(nodeID))
  • name (text not null)

Now you can indeed enforce unique names among siblings by adding a unique constraint on parent + name.

You can derive the ancestor/descendent relationship and level that was previously in NodeClosure using queries against the Node table. Syntax for this varies depending on database.

| improve this answer | |
1

Here's how I would typically model a hierarchy with a closure table:

CREATE TABLE nodes
( node_id int not null primary key
, node_name int not null
, -- other attributes of a node
);

CREATE TABLE parent_nodes
( node_id int not null primary key
      references node (node_id)
, parent_id int not null 
      references nodes (node_id)
);

CREATE TABLE ancestor_nodes
( node_id int not null
     references nodes (node_id)
, ancestor_id not null
     references nodes (node_id) 
);

ancestor_nodes can be maintained by triggers. Adding a node x to parent y implies that x cross join (ancestors of y union y) should be added to ancestor_nodes. Deleting a node is also trivial, and moving a node is more or less the same as adding and deleting a node. Example of an insert trigger for maintaining transitive closure of parent_nodes:

create trigger add_closure
after insert on parent_nodes
referencing new as n
for each row
begin
    insert into ancestor_nodes (node_id, ancestor_id)
    values (n.node_id, n.parent_id)
    union all
    select n.node_id, ancestor_id
    from ancestor_nodes
    where node_id = n.parent_id
    union all
    select node_id, n.parent_id
    from ancestor_nodes
    where ancestor_id = n.node_id
    union all
    select a.node_id, b.ancestor_id
    from ancestor_nodes a
    cross join ancestor_nodes b
    where a.ancestor_id = n.node_id
      and b.node_id = n.parent_id; --
end;

The exact syntax will vary between vendors, but it should be easy to port to other ones. The above syntax is for Db2, and I added a Fiddle

If you want to express the rule "two nodes with the same parent cannot have the same name", you could either use a validation trigger for that or merge nodes and parent_nodes into one relation, say Nodes.

One of the problems with merging this into one relation is how to represent the parent of a root_node? There are basically two options:

a) parent(x) := x
b) parent(x) := null

If your DBMS does not allow you to use NULL in a UNIQUE constraint, it leaves you with option a) You could then add a unique constraint like:

UNIQUE (parent_id, node_name)

EDIT: A third option is to denormalize name so that it becomes an attribute of parent. I've updated a small example of this at: Fiddle2

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.