Exposé de la situation :
Une base de données pour représenter un arbre, 0 comme PARENT indique la racine, un autre nombre indique que l'élément possède un autre élément parent :

 
Ce qui donne l'arbre suivant :

 
Le problème :
Supposons que je modifie le PARENT de 1 de la manière suivante :

 
Voila qui me fait perdre ma racine et par conséquent l'ensemble de ma structure logique en créant une boucle.
 
La question :
Quelle méthode efficace existe-il pour détecter la circularité et empêcher que celà puisse se produire lors d'un UPDATE ? Existe-il une meilleure solution de représenter un arbre ?
 
 
Note : c'est pour un code en PHP, mais en fin de compte peu importe le langage.

faut faire un trigger déclenché lors des update (et des insert aussi probablement), qui contiendra le code PL/SQL permettant de lister la liste des ID fils, et si le parent est dedans, de renvoyer une erreur ...
 
pas évident à première vue

Et plus amont ne pas laisser les utilisateurs tenter d'insérer un père dans la liste des fils (pas trop clair mais on se comprend ^^)

J'ai eu une idée... en fait je vais probablement créer une fonction récursive en PHP.
 
La fonction parcourt l'arbre depuis le futur parent d'un élément, en remontant de parent en parent jusqu'à la racine (PARENT = 0, est la condition d'arrêt), si je retombe sur mon élément de départ c'est qu'il y a  circularité et donc erreur.
 
J'ignore si il existe une méthode plus efficace qui nécessiterait moins de traitement... toutefois vue mon application la charge induite par ce traitement me semble acceptable.

de manière générale, il existe 2 grandes techniques pour détecter les cycles dans un graphe.
 
1) avec un set, on parcourt le graphe et on met les noeud dans un set au fur et à mesure de l'avancement, si le noeud est déjà dans le set, il y a un cycle. (concome de la mémoire)
 
2) le lièvre et la tortue : on fait partir un lièvre qui passe les noeuds 2 par 2, et une tortue qui parcourt les noeuds 1 par 1, s'ils se retrouvent sur le même noeud, c'est que le lièvre a fait le tour et a rattrapé la tortue, s'il tappe le bout, c'est qu'il y avait un bout. évidement, cet algo nécessite plus d'un tour de cycle de parcourt, mais ne consome pas de mémoire.

 
excellent le second je connaissais pas complexité ?

sur un hypodrôme, la tortue se fait rattraper à la fin de son premier tour, soit 2 tours pour le lièvre.

le premier je connaissais, pas le second...

Question con: si c'est une DB, pourquoi ne pas mettre le parent à NULL quand c'est la racine? Ton update serait nettement simplifié...

ça a été un devoir de smalltalk quand j'étais en début de deuxième année d'IUP (implémenter les 2 algos, ce qui se fait en 5 min).
 
Depuis, je me prends régulièrement des cuites avec le prof de l'époque ...

gizmo -> Car je n'aime pas le néant... je préfère définir mon intervalle de travail dans les nombres entiers positifs et interdire NULL
 
Sinon voici la fonction dans sa première mouture :  

Ouais, enfin, de toute façon, j'atais un peu fatigué, avec 0 ca merche aussi.
 
Il suffit de faire un update table set col=value where id=blabla and col!=0. Ainsi tu évites de modifier la racine.

oui mais il faut pouvoir modifier la racine ... mais sans créer de cycle