Get rid of circular parent/child in MYSQL

Question

I have a table like this:

 Attribute  |  Type   | Modifier
------------+---------+----------
 id         | integer | not null
 title      | text    | not null
 parent     | integer |

The parent field is a foreign key referencing the same table.

How can I ensure that no loops (circular parent/child references) are ever inserted? For example:

 id         | title   | parent
------------+---------+----------
 1          | A       | 3 or 2
 2          | B       | 1
 3          | C       | 2

I'm using PHP and MySQL.

My english is not so good, let's think i want to create a parent/child category list, when i'm trying to get parent of a category, if this situation happens, system getting hung and php will stuck in an infinity loop — Pejman, Jun 09 '15 at 08:29
Ok, so what do you want to happen when someone tries to insert a record that makes a loop? — Dan Getz, Jun 09 '15 at 08:37
Related: http://stackoverflow.com/questions/546655/finding-all-cycles-in-graph — Basti, Jun 09 '15 at 08:59
To prevent loops from ever occuring you just have to check when moving nodes that have children in your tree. For the node to be moved check if the new parent node is a descendant (child, or child of child, or child of child of child...). If it is, abort. If it isn't, no loops can occure. — Basti, Jun 09 '15 at 09:07
You could register a before trigger to check this condition and then you can signal out. This post might give you an idea: http://stackoverflow.com/questions/2538786/how-to-abort-insert-operation-in-mysql-trigger/8559284#8559284 — Ilyas Serter, Jun 15 '15 at 18:09

score 0 · Accepted Answer · answered Jun 20 '15 at 19:26

First, assume that the table has no loops initially. If it does, then you'll need to fix any loops manually. Then,when you try to set the parent for a child, first fetch the child's potential parent. Then keeping fetching the parent's parent. If you reach a node that has no parent, then everything is ok, and you can set the child's parent. If you reach the child, then you know that a loop would be created if you set that parent.

function canSetParent($child, $parent)
{
    $node = $parent;
    while($node != null)
    {
        if($node->id == $child->id) return false;  //Looped back around to the child
        $node = $node->parent;
    }
    return true;  //No loops found
}

Get rid of circular parent/child in MYSQL

1 Answers1