Thread: Avoiding cycles in a directed graph
I'm using the following table to represent an acyclic directed graph: CREATE TABLE edge( id SERIAL PRIMARY KEY, child INTEGER NOT NULL, parent INTEGER, UNIQUE (child,parent) ); I see there is an example in the online docs for detecting cycles in recursive queries, and I've adapted the example query to the table above: WITH RECURSIVE search_graph(parent, child, id, depth, path, cycle) AS ( SELECT e.parent, e.child, e.id, 1, ARRAY[e.id], false FROM edge e UNION ALL SELECT e.parent, e.child,e.id, sg.depth + 1, path || e.id, e.id = ANY(path) FROM edge e, search_graph sg WHERE e.parent = sg.child AND NOT cycle ) SELECT * FROM search_graph; That's great to avoid looping forever on queries, but what about preventing anyone from inserting edges that would create cycles in the first place? I reckon I'll need a trigger of some sort, but nothing I've tried has enabled me to do the cycle check as part of the trigger to avoid inserting an edge that would create a cycle. I tried having the non-recursive SELECT use NEW.parent, NEW.child, etc. but that isn't working. Is there any way to do this, or do I have to just insert the edge, check if it cycles, and delete it if it does? Thanks. -Tony
On 16/03/10 19:45, Tony Cebzanov wrote: > I'm using the following table to represent an acyclic directed graph: [snip] > I see there is an example in the online docs for detecting cycles in > recursive queries, and I've adapted the example query to the table above: [snip] > That's great to avoid looping forever on queries, but what about > preventing anyone from inserting edges that would create cycles in the > first place? I reckon I'll need a trigger of some sort, but nothing > I've tried has enabled me to do the cycle check as part of the trigger > to avoid inserting an edge that would create a cycle. You've got the right idea. If you know that the table doesn't contain any cycles at the moment, then all the trigger has to do is: 1. Check "parent" <> "child" 2. Build the set of parents of "parent". 3. Check "child" isn't in that set. 4. If there is a cycle, raise an error (which will abort the insert or update) If you have a "before" trigger, then step 4 could return NULL rather than raise an error. That would just skip the insert. Also, step #1 could be done with a CHECK constraint which would be checked before your trigger gets run. -- Richard Huxton Archonet Ltd
Richard Huxton <dev@archonet.com> writes: > On 16/03/10 19:45, Tony Cebzanov wrote: >> That's great to avoid looping forever on queries, but what about >> preventing anyone from inserting edges that would create cycles in the >> first place? I reckon I'll need a trigger of some sort, but nothing >> I've tried has enabled me to do the cycle check as part of the trigger >> to avoid inserting an edge that would create a cycle. > You've got the right idea. > If you know that the table doesn't contain any cycles at the moment, > then all the trigger has to do is: > 1. Check "parent" <> "child" > 2. Build the set of parents of "parent". > 3. Check "child" isn't in that set. > 4. If there is a cycle, raise an error (which will abort the insert or > update) The problem with this approach is that it's not safe against concurrent insertions. If concurrent transactions T1 and T2 each insert a row that, taken together (and in combination with existing entries), create a cycle, then neither of their triggers will see the other's row so they'll both think they can commit. The same kind of problem exists for unique and foreign key constraints, both of which use low-level locking mechanisms to catch such cases. There's no way that I can see to express the "no cycle" constraint as a uniqueness constraint unfortunately. You could solve limited forms of it using the exclusion-constraint mechanism that's new in 9.0, but AFAICS not the general case :-( regards, tom lane
On 3/16/10 4:34 PM, Tom Lane wrote: > The same kind of problem exists for unique and foreign key constraints, > both of which use low-level locking mechanisms to catch such cases. > There's no way that I can see to express the "no cycle" constraint as a > uniqueness constraint unfortunately. You could solve limited forms of > it using the exclusion-constraint mechanism that's new in 9.0, but > AFAICS not the general case :-( Are you saying there's no way to avoid cycles at all, or just no way to do it using uniqueness constraints? I'm okay with running the big, fat WITH RECURSIVE query in my insert trigger if I have to -- it won't be great for performance, but I don't expect this to be a frequent operation, so I'll accept the performance hit if it works. Unfortunately I can't even get that working. Here's the (not at all functional) trigger I've got right now, which only detects the cycle *after* it's been inserted, which is of no help at all. Any way I can modify this to do the right thing? CREATE OR REPLACE FUNCTION check_edge_cycle() RETURNS trigger AS $$ DECLARE cycles INTEGER; BEGIN WITH RECURSIVE search_graph(parent, child, id, depth, path, cycle) AS ( SELECT NEW.parent, NEW.child, NEW.id,1, ARRAY[NEW.id], false UNION ALL SELECT g.parent, g.child, g.id, sg.depth + 1, path || g.id, g.id = ANY(path) FROM catalog_edge g, search_graph sg WHERE g.parent = sg.childAND NOT cycle ) SELECT INTO cycles COUNT(*) FROM search_graph WHERE cycle=true; RAISE NOTICE 'cycles: %', cycles; IF cycles > 0 THEN RAISE EXCEPTION 'cycle'; END IF; RETURN NEW; END $$ LANGUAGE plpgsql;
Tony Cebzanov <tonyceb@andrew.cmu.edu> writes: > I'm okay with running the big, fat WITH RECURSIVE query in my insert > trigger if I have to -- it won't be great for performance, but I don't > expect this to be a frequent operation, so I'll accept the performance > hit if it works. > Unfortunately I can't even get that working. Here's the (not at all > functional) trigger I've got right now, which only detects the cycle > *after* it's been inserted, which is of no help at all. Any way I can > modify this to do the right thing? Run it in an AFTER trigger? If you don't expect this to be common, maybe you could fix the concurrency issue by taking a table-wide lock that locks out other writers. regards, tom lane
On 16/03/10 21:09, Tom Lane wrote: > Tony Cebzanov<tonyceb@andrew.cmu.edu> writes: >> I'm okay with running the big, fat WITH RECURSIVE query in my insert >> trigger if I have to -- it won't be great for performance, but I don't >> expect this to be a frequent operation, so I'll accept the performance >> hit if it works. > >> Unfortunately I can't even get that working. Here's the (not at all >> functional) trigger I've got right now, which only detects the cycle >> *after* it's been inserted, which is of no help at all. Any way I can >> modify this to do the right thing? > > Run it in an AFTER trigger? > > If you don't expect this to be common, maybe you could fix the > concurrency issue by taking a table-wide lock that locks out > other writers. Surely SELECT FOR UPDATE on the parents would be sufficient? If there's no overlap between (currently non-cyclic) graphs being altered then there can't be any conflict. -- Richard Huxton Archonet Ltd
Richard Huxton <dev@archonet.com> writes: > On 16/03/10 21:09, Tom Lane wrote: >> If you don't expect this to be common, maybe you could fix the >> concurrency issue by taking a table-wide lock that locks out >> other writers. > Surely SELECT FOR UPDATE on the parents would be sufficient? If there's > no overlap between (currently non-cyclic) graphs being altered then > there can't be any conflict. Um, what if the cycle is being formed from whole cloth? For instance T1 inserts an edge A->B while T2 is inserting B->A. There are no pre-existing rows to lock, but there will still be a cycle after they both commit. Also it seems pretty deadlock-prone if there are multiple existing rows to try to lock. Perhaps you could work around the risk by locking those rows one at a time in an application-defined ordering ... but I'm afraid the performance would be poor, unless the connected graphs are always very small. On the whole I think Tony's better off with a KISS approach, ie just lock the whole table against other writers. regards, tom lane
On 3/16/10 6:22 PM, Tom Lane wrote: > Richard Huxton <dev@archonet.com> writes: > > > Um, what if the cycle is being formed from whole cloth? For instance > T1 inserts an edge A->B while T2 is inserting B->A. There are no > pre-existing rows to lock, but there will still be a cycle after they > both commit. For what it's worth, when I did give the "FOR UPDATE" strategy a try, but with the recursive query rather than the simpler approach Richard suggested, I got the following error (v8.4.2): ERROR: FOR UPDATE/SHARE in a recursive query is not implemented I'm sticking with the recursive query, because it seems to me the only way to ensure there are no cycles is to check the whole graph for cycles, and the only way I know how to do that is the recursive approach. Since "FOR UPDATE" isn't implemented for recursive queries, I'll just lock the entire table for now. Thanks, all! -Tony