15.00 - Preventing Infinite Recursion Due To Cyclic Data - Teradata Database

Teradata Database SQL Data Definition Language Detailed Topics

Product
Teradata Database
Release Number
15.00
Content Type
Programming Reference
Publication ID
B035-1184-015K
Language
English (United States)

Preventing Infinite Recursion Due To Cyclic Data

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” on page 500). 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, though such a problem presents a simple, though highly artificial, 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.

    Consider the following informal definitions.

     

    A graph is …

    WHEN …

    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” on page 769 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.