Preventing Infinite Recursion Due To Cyclic Data | VantageCloud Lake - Preventing Infinite Recursion Due to Cyclic Data - Teradata Vantage

Teradata® VantageCloud Lake
Deployment
VantageCloud
Edition
Lake
Product
Teradata Vantage
Published
January 2023
ft:locale
en-US
ft:lastEdition
2024-12-11
dita:mapPath
phg1621910019905.ditamap
dita:ditavalPath
pny1626732985837.ditaval
dita:id
phg1621910019905

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 can take by means of a transportation system. Such cycles are very unlikely to appear in a bill of material problem, but the following example shows the issues.

For example, suppose you have the following parts table.

Parts
Major Minor Quantity
p1 p2 2
p1 p3 3
p1 p4 2
p2 p3 3
p3 p5 2
p3 p1 3
p4 p2 4

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 defined, px.

SELECT major, minor
FROM px;
A quick analysis of the data indicates a loop, or cycle, in the data among parts p1, p2, and p3 as follows.
  • 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 following graph shows these cycles symbolically:
  • p1 p2 p3 p1 p2 p3 and so on.
  • p1 p4 p2 p3 p1 p4 p2 and so on.


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.

Only cyclic graphs can 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 cause infinite recursion. Ignoring spool overflow, the query loops forever if not stopped.

How can you make sure a runaway infinite recursion does not happen? Trying to determine whether there are cycles in base table data often requires extraordinary effort, 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 optional, good programming practice dictates that you specify a constraint in the recursive query portion of a recursive view definition that limits the depth of recursion.

The following guidelines apply to coding a recursive view to control for infinite recursion by limiting recursion depth.
  • Initialize a counter for each SELECT request in the seed query to a constant value. For most applications,initialize the constant 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 is one of the following.
    • counter < condition
    • counter <= condition

    Determine the optimum value of condition through prototyping or estimation.

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). 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.