Guarenteeing ordering constraints

["Joris Dobbelsteen" <Joris@xxxxxxxxxxxxxxxxxxxxx>]

I have some trouble guarenteeing that an ordering constraint is enforced
on the database. On the table ordering (see below) I want to enforce
that for every tuple t, all tuples u where u.position < t.position this
implies u.cumvalue <= t.cumvalue.

Unfortunally postgresql gives me a choice between concurrency or
consistency. Given the trigger procedure below (written for simplicity,
not speed) it will fail to guarentee consistency when using serializable
isolation.
Just load the initial dataset (the failing operations are only to test
the constraints).
The next step is to execute transactions 1 and 2 in parallel (step by
step). This will cause the constraint to be violated.

It does work in the default isolation level (read committed).
Alternatively one can use the second LOCK statement in the trigger,
which does an ACCESS EXCLUSIVE. Obviously this completely defeats
concurrency (causes one of the transactions to be retried).

Is there any way that will both guarentee consistency and provide some
better concurrency?

- Joris

===

CREATE PROCEDURAL LANGUAGE plpgsql;

CREATE TABLE ordering (
    "position" integer NOT NULL,
    cumvalue integer NOT NULL
);

CREATE FUNCTION tr_ordering_cumvalue_simple() RETURNS "trigger"
    AS $$BEGIN
	-- position is unique (index enforced)
	-- cumvalue constraint
	--
	-- Let p,q be an element of ordering,
	-- where p.position < q.position implies p.cumvalue <=
q.cumvalue

	-- Thus for every new tuple t
	-- we need to ensure
	-- For all p (of ordering) p.position < t.position implies
p.cumvalue <= t.cumvalue
	--		and        p.position > t.position implies
p.cumvalue >= t.cumvalue
	--
	-- note (p implies q) <=> (!p or q)

	-- lock full table, no others updating it...
	LOCK TABLE ordering IN EXCLUSIVE MODE;
	--LOCK TABLE ordering IN ACCESS EXCLUSIVE MODE;

	IF EXISTS (SELECT *
		   FROM ordering o
		   WHERE	-- violates constraints
			(o.position < NEW.position and o.cumvalue >
NEW.cumvalue)
		   OR
			(o.position > NEW.position and o.cumvalue <
NEW.cumvalue)
		  )
	THEN
		RAISE EXCEPTION 'Constraint violation detected by %',
TG_name;
	END IF;

	RETURN NEW;
END$$
    LANGUAGE plpgsql;

CREATE TRIGGER tr_ordering_cumvalue
    BEFORE INSERT OR UPDATE ON ordering
    FOR EACH ROW
    EXECUTE PROCEDURE tr_ordering_cumvalue_simple();


-- initial dataset
BEGIN;
DELETE FROM ordering;
INSERT INTO ordering VALUES (0,0);
INSERT INTO ordering VALUES (10,100);
INSERT INTO ordering VALUES (20,200);
COMMIT;

-- failing operation
BEGIN;
INSERT INTO ordering VALUES (-1,1);
INSERT INTO ordering VALUES (15,1);
INSERT INTO ordering VALUES (16,201);
INSERT INTO ordering VALUES (21,-1);
ROLLBACK;

-- transaction 1
BEGIN ISOLATION LEVEL SERIALIZABLE;;
SELECT * FROM ordering;
INSERT INTO ordering VALUES (19,101);
SELECT * FROM ordering;
COMMIT;

-- transaction 2
BEGIN ISOLATION LEVEL SERIALIZABLE;
SELECT * FROM ordering;
INSERT INTO ordering VALUES (11,199);
SELECT * FROM ordering;
COMMIT;