|
|
|
SSCommitted
      
Group: General Forum Members
Last Login: Tuesday, January 15, 2013 11:11 AM
Points: 1,945,
Visits: 2,782
|
|
Let me propose higher level constraints to do the job. Trees have certain properties:
1) The tree has one and only one root node 2) The root node has in-degree = 0 (i.e. no parent node) 3) All non-root nodes have in-degree = 1 (i.e. exactly one parent)node 4) The number of edges is one less than the number of nodes in the tree
Let's declare the table with
CREATE TABLE AdjacencyListModel (parent_node CHAR(2), -- null means root child_node CHAR(2) NOT NULL UNIQUE, -- one parent CHECK (parent_node <> child_node)); -- shortest cycle check
The shortest cycle is more for the optimizer than data integrity, but it prevents graphs like this which meet rule #4, but are not trees. {a,b,c} is a cycle and {d} is an orphan.
A / \ D B - C
Now let's enforce the rules with aggregate functions instead of procedure code and BIT flags:
CREATE TRIGGER Valid_Tree_Check ON AdjacencyListModel FOR UPDATE, INSERT, DELETE AS BEGIN IF NOT EXISTS (SELECT * FROM AdjacencyListModel HAVING COUNT(*) = COUNT(parent_node) +1) BEGIN RAISERROR('invalid root', 16, 1); ROLLBACK; END;
IF NOT EXISTS (SELECT * FROM (SELECT parent_node FROM AdjacencyListModel UNION SELECT child_node FROM AdjacencyListModel) AS X(i) HAVING COUNT(i) = (SELECT COUNT(*) FROM AdjacencyListModel)) BEGIN RAISERROR('invalid edge and node counts', 16, 1); ROLLBACK; END; END; --Valid_Tree_Check
We could do this with a CREATE ASSERTION or full ANSI Standard CHECK(),
Books in Celko Series for Morgan-Kaufmann Publishing Analytics and OLAP in SQL Data and Databases: Concepts in Practice Data, Measurements and Standards in SQL SQL for Smarties SQL Programming Style SQL Puzzles and Answers Thinking in Sets Trees and Hierarchies in SQL
|
|
|
|
|
Ten Centuries
      
Group: General Forum Members
Last Login: Tuesday, June 04, 2013 10:52 AM
Points: 1,043,
Visits: 2,945
|
|
Well, now you're getting my poor old brain smoking. I had to think long and hard before realising the problem here.
I agree that in a true tree structure each node except the root will have one and only one parent. However, there are in practice many perfectly acceptable hierarchal situations where relationships mesh together so that a node can have more than one parent, and that's where I think this trigger would have an issue. However, I have to admit I'm by no means certain I haven't missed something in my understanding here.
Semper in excretia, sumus solum profundum variat
|
|
|
|
|
SSChampion
        
Group: General Forum Members
Last Login: Today @ 4:22 PM
Points: 11,789,
Visits: 28,063
|
|
For those of you who followed this thread, did anyone use this method to handle foreign keys with circular references? I adapted a couple of the posted examples, and against one of my databases which i know has circular references, I'm thinking this is not really going to give results in a hierarchy correctly; it seems that the hierarchy is more of the count of FK levels between the objects, and not necessarily the hiarchy order.
i was fiddling around with this trying to get all objects in a hierarchy, but It seems to me to be pretty inefficient; 20 plus minutes on a machine with no resources in use at all, along with 60,000 rows;
;WITH ChildrenAndParents AS ( SELECT parent_object_id AS object_id, convert(varchar(255),OBJECT_NAME(parent_object_id)) AS child, referenced_object_id AS referenced_major_id, convert(varchar(255),OBJECT_NAME(referenced_object_id)) AS parent FROM sys.foreign_keys ) ,GroupMembers (Child, ParentGroup, Level, hierarchypath) AS (-- Anchor member definition SELECT g.child, g.parent, 0 AS Level, convert(varchar(max), g.child + '->' + g.parent) AS hierarchypath FROM ChildrenAndParents AS g WHERE child not in (select parent from ChildrenAndParents) UNION ALL -- Recursive member definition SELECT g.child, g.parent, Level + 1, hierarchypath + '->' + g.parent -- Add '-->...' to end when recursion found + Case When gm.hierarchypath like '%->'+g.parent+'->%' Then '-->...' Else '' End FROM ChildrenAndParents as g INNER JOIN GroupMembers AS gm ON gm.parentgroup = g.child --Exclude if the hierarchypath text contains a recursion where gm.hierarchypath not like '%->...' )
select left(hierarchypath, charindex('->', hierarchypath) - 1) as child, parentgroup, level, hierarchypath from groupmembers option(maxrecursion 20);
Lowell
--There is no spoon, and there's no default ORDER BY in sql server either. Actually, Common Sense is so rare, it should be considered a Superpower. --my son
|
|
|
|