Received: from maia.hub.org (unknown [200.46.204.183])
	by mail.postgresql.org (Postfix) with ESMTP id 6325C797B1E
	for <pgsql-sql-postgresql.org@mail.postgresql.org>;
	Wed, 17 Mar 2010 15:36:28 -0300 (ADT)
Received: from mail.postgresql.org ([200.46.204.86])
	by maia.hub.org (mx1.hub.org [200.46.204.183]) (amavisd-maia,
	port 10024) with ESMTP id 76299-01 for
	<pgsql-sql-postgresql.org@mail.postgresql.org>;
	Wed, 17 Mar 2010 18:36:17 +0000 (UTC)
X-Greylist: from auto-whitelisted by SQLgrey-1.7.6
Received: from shetland.sei.cmu.edu (shetland.sei.cmu.edu [192.58.107.44])
	by mail.postgresql.org (Postfix) with ESMTP id DC04B65A631
	for <pgsql-sql@postgresql.org>; Wed, 17 Mar 2010 15:36:17 -0300 (ADT)
Received: from ms02.sei.cmu.edu (ms02.sei.cmu.edu [128.237.22.38])
	by shetland.sei.cmu.edu (8.13.8/8.13.8/1294) with ESMTP id
	o2HIaD6t012818; Wed, 17 Mar 2010 14:36:13 -0400
Received: from lisa.yellow.cert.org (lisa.yellow.cert.org [10.20.10.153])
	by ms02.sei.cmu.edu (8.13.1/8.13.1/1295) with ESMTP id o2HIaCYS029490;
	Wed, 17 Mar 2010 14:36:12 -0400
Message-ID: <4BA1211C.20800@andrew.cmu.edu>
Date: Wed, 17 Mar 2010 14:36:12 -0400
From: Tony Cebzanov <tonyceb@andrew.cmu.edu>
User-Agent: Mozilla/5.0 (Macintosh; U; Intel Mac OS X 10.5; en-US;
	rv:1.9.1.8) Gecko/20100227 Thunderbird/3.0.3 Mnenhy/0.7.6.0
MIME-Version: 1.0
To: Tom Lane <tgl@sss.pgh.pa.us>
CC: Richard Huxton <dev@archonet.com>, pgsql-sql@postgresql.org
Subject: Re: Avoiding cycles in a directed graph
References: <4B9FDFDE.5030005@andrew.cmu.edu> <4B9FE752.4080709@archonet.com>
	<14113.1268771643@sss.pgh.pa.us> <4B9FEEE8.1060404@andrew.cmu.edu>
	<14550.1268773752@sss.pgh.pa.us> <4BA002DC.1050700@archonet.com>
	<15827.1268778132@sss.pgh.pa.us>
In-Reply-To: <15827.1268778132@sss.pgh.pa.us>
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
X-Virus-Scanned: Maia Mailguard 1.0.1
X-Spam-Status: No, hits=-2.599 tagged_above=-10 required=5
	tests=BAYES_00=-2.599
X-Spam-Level: 
X-Archive-Number: 201003/140
X-Sequence-Number: 33847

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