Recursive views can recurse infinitely when there are cycles in the underlying data they are processing, as they can with acyclic data. See Preventing Infinite Recursion With Acyclic Data. For example, there are likely to be many different routes one could take by means of a transportation system. Such cycles are very unlikely to appear in a bill of material problem, but the example below is presented as means of illustrating the issues.
For example, suppose you have the following parts table.
You want to write a recursive view to process the data in this table, so you write the following recursive view definition.
CREATE RECURSIVE VIEW px (major, minor) AS ( SELECT major, minor FROM parts WHERE major = 'p1' UNION ALL SELECT px.major, parts.minor FROM px, parts WHERE parts.major = px.minor);
Suppose you then ran the following SELECT request against the recursive view you have just defined, px.
SELECT major, minor FROM px;
- Part p3 has part p1 as a minor, or child, constituent.
- Part p4 has part p2 as a child constituent.
- Part p2 has part p3 as a child constituent.
- As noted in the first bullet, part p3 also has part p1 as a child constituent.
The cycles are perhaps easier to visualize when presented symbolically as follows.
p1 p2 p3 p1 p2 p3 and so on.
Similarly, there is a second cycle, as follows.
p1 p4 p2 p3 p1 p4 p2 and so on.
A graph of the hierarchy looks like this.
Consider the following informal definitions.
|Type of Graph||Description|
|cyclic||one or more of its nodes feeds back onto itself, either directly or indirectly.|
|acyclic||none of its nodes feeds back onto itself.|
It is only cyclic graphs that present the possibility for infinite recursion; acyclic graphs, by definition, cannot recurse infinitely.
In this example, node p3 feeds back onto node p1 and node p4 feeds back onto node p1 by traversing nodes p2 and p3, so the graph is cyclic.
The cyclic relationships among these parts would cause an infinite recursion to occur, and, ignoring spool overflow, the query would loop forever if not stopped. Harkening back to The Concept of Recursion, it could be said that the fixpoint of this recursion is.
So, what can be done to ensure that a runaway infinite recursion does not happen? After all, attempting to determine whether there are cycles in base table data would often require an extraordinary effort, and to little end.
One possible change to the definition for the example definition for the recursive view px is the following.
CREATE RECURSIVE VIEW px (major, minor, mycount) AS ( SELECT major, minor, 0 AS mycount FROM parts WHERE major = 'p1' UNION ALL SELECT px.major, parts.minor, px.mycount + 1 FROM px, parts WHERE parts.major = px.minor AND px.mycount <= 40);
The AND condition px.mycount <= 40 limits the recursion to 41 or fewer cycles. Forty-one because the condition is applied on px.mycount, which is initialized to 0, not 1.
Although not mandatory, good programming practice dictates that you always specify a constraint in the recursive query portion of a recursive view definition that limits the depth of recursion.
- Initialize a counter for each SELECT request in the seed query to a constant value. For most applications, the constant should be initialized to 0.
- Code each SELECT request in the recursive query to increment the counter by 1.
- Code each SELECT request in the recursive query to specify a condition that tests the value of the counter.The form of this test condition should be one of the following.
- counter < condition
- counter ≤ condition
The value for condition is something that must be determined through prototyping or estimation. It is generally not possible to determine an optimum value without experimentation.
Without a limiting condition, runaway recursion is limited only by the quantity of spool space specified for the user who performs the query against the recursive view (see CREATE USER for information about assigning spool space to a user). Keep in mind that specifying a limiting condition does not eliminate the maximum quantity of spool space allotted to a user, so if you specify too large a value for the condition, a user can overflow its spool maximum without ever reaching the terminal value specified by that condition.