Hierarchical data using closure table, how to ensure that a column is unique within the parent node?

Question

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?

Answer 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.

Answer 2

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