Preventing Infinite Recursion Due To Cyclic or Acyclic Data | Teradata Vantage - 17.10 - Preventing Infinite Recursion Due To Cyclic Data - Advanced SQL Engine - Teradata Database

Teradata Vantage™ - SQL Data Definition Language Detailed Topics

Product
Advanced SQL Engine
Teradata Database
Release Number
17.10
Release Date
July 2021
Content Type
Programming Reference
Publication ID
B035-1184-171K
Language
English (United States)

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.

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 have just 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 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.


Four-node hierarchy of cyclic/acyclic data

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.

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