Adjacency list tree - how to prevent circular references?

Question

I have an adjacency list in a database with ID and ParentID to represent a tree structure:

-a
--b
---c
-d
--e

Of course in a record the ParentID should never be the same as ID, but I also have to prevent circular references to prevent an endless loop. These circular references could in theory involve more than 2 records. ( a->b, b->c, c->a , etc.)

For each record I store the paths in a string column like this :

a    a
b    a/b
c    a/b/c
d    d
e    d/e

My question is now : when inserting/updating, is there a way to check if a circular reference would occur?

I should add that I know all about the nested set model, etc. I chose the adjacency method with stored path's because I find it much more intuitive. I got it working with triggers and a separate paths-table, and it works like a charm, except for the possible circular references.

Answer 1

If you're storing the path like that, you could put in a check that the path does not contain the id.

Answer 2

If you are using Oracle you can implement a check for cycles using the CONNECT BY syntax. The count of nodes should be equal to the count of decendents from the root node.

CHECK (
(SELECT COUNT(*) Nodes
 FROM Tree) =
(SELECT COUNT(*) Decendents
 FROM Tree
 START WITH parent_node IS NULL -- Root Node
 CONNECT BY parent_node = PRIOR child_node))

Note, you will still need other checks to enforce the tree. IE

Single root node with null. Node can have exactly one parent.

You cannot create a check constraint with a subquery, so this will need to go to a view or trigger.