SQL Tree Structure Table

Question

I am new to SQL, would like any help with the following problem. I have the following code to create a table for the nodes and the tree but not sure how to implement the following rules in my code.

create table Node(
    NodeId int not null,
    ParentId int null,
    NodeName varchar(255) not null,
    constraint PK_Node primary key(NodeId),
    constraint UK_NodeName unique(NodeName)
)
go

create table Tree(
    NodeId int not null,
    ParentId int not null,
    Level int not null,
    constraint PK_Tree primary key(NodeId, ParentId),
    constraint UK_Level unique(NodeId, Level)
)
go}

alter table Node
	add constraint FK_NodeNode foreign key(ParentId) references Node(NodeId) --on delete cascade;

alter table Tree
	add constraint FK_NodeTreeNode foreign key(NodeId) references Node(NodeId) on delete cascade;

Imagine a tree structure that has the following properties:

• a) Single root node
• b) Each node may have multiple children nodes
• c) Nodes may not be deleted
• d) All non-root nodes have a property max children nodes - new nodes are defaulted to a fixed default value
• e) The max children nodes property may be changed at any time - if the new value is less than the current number of children nodes, the children are distributed up the chain respecting the property for all nodes along the way. If the property is set to zero, the node is made a direct child of the root node
• f) When adding a new node, it is added to a node as close to the root's level as possible ordered by percentage quota of children filled ascending. If all nodes have met their quota, it is placed directly under the root node.

Create tables and indexes to store this information and procedures to perform the following operations as efficiently as possible:

• i. Add a node to a tree
• ii. Change the max children node property of a node

Answer 1

Not all of your constrains can be set in SQL server. The logic of a, d, e, f should be cater in application instead.

A tree is just a combination of Nodes. So we just have to define the storage of Node.

create table Node(
    NodeId int not null identity(1,1), -- Identity, auto generate Id for new Node
    ParentId int null, -- If null, it is the root of the tree
    MaxChild int not null default(-1),
    NodeName varchar(255) not null,
    constraint PK_Node primary key(NodeId),
    constraint UK_NodeName unique(NodeName),
    constraint FK_Node foreign key(ParentId) references Node(NodeId) 
    -- How the `Node` to be related and form the tree can be done 
    -- by adding the `Foreign Key` of `Node` itself
    -- A node cannot be simply deleted if it is a parent.
)

To add a node:

-- Add root
insert Node (NodeName) VALUES ('root')

-- Add child
insert Node (ParentId, NodeName) VALUES 
((SELECT NodeId FROM Node WHERE NodeName = 'Root'), 'ChildA')

insert Node (ParentId, NodeName) VALUES 
((SELECT NodeId FROM Node WHERE NodeName = 'Root'), 'ChildB')

insert Node (ParentId, NodeName) VALUES 
((SELECT NodeId FROM Node WHERE NodeName = 'ChildA'), 'ChildA-A')

insert Node (ParentId, NodeName) VALUES 
((SELECT NodeId FROM Node WHERE NodeName = 'ChildA-A'), 'ChildA-A-A')

To get the level of the Nodes and child count

;WITH 
CountLevel AS
(
    SELECT *, 1 AS Level FROM Node WHERE ParentId IS NULL

    UNION ALL

    SELECT child.*, parent.Level + 1 
    FROM Node child INNER JOIN CountLevel parent ON 
        child.ParentId = parent.NodeId
), 
CountChild AS
(
    SELECT NodeId, ParentId, 0 AS ChildCount 
    FROM Node leaf 
    WHERE NOT EXISTS(SELECT * FROM Node WHERE ParentId = leaf.NodeId)

    UNION ALL

    SELECT child.ParentId, (SELECT ParentId FROM Node WHERE NodeId = child.ParentId), child.ChildCount + 1 
    FROM CountChild child
    WHERE child.ParentId IS NOT NULL
)
SELECT *, (SELECT SUM(ChildCount) FROM CountChild WHERE NodeId = CountLevel.NodeId) Child FROM CountLevel

Result

NodeId      ParentId    MaxChild    NodeName             Level       Child
----------- ----------- ----------- -------------------- ----------- -----------
1           NULL        -1          Root                 1           4
2           1           -1          ChildA               2           2
3           1           -1          ChildB               2           0
4           2           -1          ChildA-A             3           1
5           4           -1          ChildA-A-A           4           0