Click here to monitor SSC
SQLServerCentral is supported by Red Gate Software Ltd.
 
Log in  ::  Register  ::  Not logged in
 
 
 
        
Home       Members    Calendar    Who's On


Add to briefcase «««123

Common table expressions and circular references Expand / Collapse
Author
Message
Posted Tuesday, February 1, 2011 1:34 PM


SSCommitted

SSCommittedSSCommittedSSCommittedSSCommittedSSCommittedSSCommittedSSCommittedSSCommitted

Group: General Forum Members
Last Login: Today @ 7:09 AM
Points: 1,946, Visits: 3,009
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
Post #1057050
Posted Wednesday, February 2, 2011 5:25 AM


Ten Centuries

Ten CenturiesTen CenturiesTen CenturiesTen CenturiesTen CenturiesTen CenturiesTen CenturiesTen Centuries

Group: General Forum Members
Last Login: Thursday, September 25, 2014 8:35 AM
Points: 1,049, Visits: 3,008
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
Post #1057386
Posted Sunday, March 18, 2012 10:01 AM


SSChampion

SSChampionSSChampionSSChampionSSChampionSSChampionSSChampionSSChampionSSChampionSSChampionSSChampion

Group: General Forum Members
Last Login: Today @ 6:44 AM
Points: 12,901, Visits: 32,135
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
Post #1268738
« Prev Topic | Next Topic »

Add to briefcase «««123

Permissions Expand / Collapse