On 1/4/2005 at 08:48 D. Richard Hipp wrote:
>Peter Bartholdsson wrote:
>>
>> [H]ow would [limiting recursion depth] not be enough?
>>
>
>Limiting the recursion depth would be sufficient to prevent
>infinite loops. But it seems overly restrictive.
>
>Consider the following case:
>
> CREATE TABLE list(
> id INTEGER PRIMARY KEY,
> next INTEGER REFERENCES list,
> data BLOB
> );
>
>The table above lets you look up BLOB data given an integer
>ID. It also keeps all of the entries on a linked list.
>(Never mind why you would want to do this - it comes up.)
>Suppose that when you delete an entry you also want to
>delete all subsequent entries in the list. We have:
>
> CREATE TRIGGER deep BEFORE DELETE ON list BEGIN
> DELETE FROM list WHERE id=old.next;
> END;
>
>This trigger is guaranteed to terminate because it will
>eventually run out of entries to delete. But given any
>recursion limit, we can always construct a case where
>the trigger will want to run longer than the limit.
>
>So do we put recursion limits on UPDATE and INSERT triggers
>only and let DELETE triggers run as long as they like?
>That works as far as I know, but it seems kind of arbitrary.
>
>Surely somebody else has been down this road before me and
>can offer a little guidance?
I haven't been down this road, but I have some ideas. First, we
cannot solve the halting problem in the general case. All we can do is
various combinations of special cases where we can solve it, and
recursion limits to deal with the rest.
It seems to me that recursion that never touches the same row twice is
less an issue. That is a trigger that just updates all other rows in
the table once should be fine. So one (I suspect hard to implement)
idea would be to keep track of which rows have been touched as part of
a trigger. Any row touched N times breaks out. This works for both
your delete case, and update cases.
It doesn't solve infinite inserts though:
CREATE TRIGGER infinite BEFORE INSERT ON foo BEGIN
INSERT INTO foo VALUES (...);
END;
With recursion limits we need some way to specify the limit as part of
the SQL. Something like:
CREATE TRIGGER deep BEFORE DELETE ON list BEGIN
DELETE FROM list WHERE id=old.next
RECURSION LIMIT SELECT COUNT FROM list;
END;
I don't like the above syntax, but you get the idea.
This requires support for SELECT COUNT, which I believe isn't a part of
sqlite. (It is a part of MSSQL)
In general a recursion limit should default to infinite (put the burden
on the programer to not write them, but if he must it can be set), or
very low (so even a 2 row test table will hit the recursion limit and
cause the programer to re-think what is happening)
This all ignores what should happen if the limit is reached. There
needs to be some way to specify ON CONFLICT for when recursion limits
are reached.
