# Optimization Problems with Items and Categories in Oracle – Intro

I recently posted a series of eight articles on my GitHub Pages blog.

## [Here is the general introduction to the articles…]

The knapsack problem is a problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.

• Knapsack problem
• The knapsack problem and many other problems in combinatorial optimization require the selection of a subset of items to maximize an objective function subject to constraints. A common approach to solving these problems algorithmically involves recursively generating sequences of items of increasing length in a search for the best subset that meets the constraints.

I applied this kind of approach using SQL for a number of problems, starting in January 2013 with A Simple SQL Solution for the Knapsack Problem (SKP-1), and I wrote a summary article, Knapsacks and Networks in SQL
, in December 2017 when I put the code onto GitHub, sql_demos – Brendan’s repo for interesting SQL.

Here is a series of eight articles that aim to provide a more formal treatment of algorithms for item sequence generation and optimization, together with practical implementations, examples and verification techniques in SQL and PL/SQL.

### GitHub

• Optimization Problems with Items and Categories in Oracle

• ## [Here is the conclusion to the articles…]

We can list here some of the features and concepts considered in the whole series.

### Sequence Generation

• 4 types of sequence defined
• sequence generation explained via recursion…
• …implemented by recursion and by iteration

### Optimization Problems

• sequence truncation using simple maths
• value filtering techniques with approximation and bounding
• two-level iterative refinement methods

### SQL

• recursive SQL
• materializing subqueries via hints or use of temporary tables
• cycles and some anomalies
• storing sequences of items in SQL by concatenation, nested tables, and linking tables
• index organised tables
• partitioned outer joins
• splitting concatenated lists into items via row-generation
• combining lists of items into concatenated strings by aggregation
• passing bind variables into views via system contexts
• automated generation of execution plans

### PL/SQL

• PL/SQL with embedded SQL as alternative solution methods to recursive SQL…
• …with sequence generation by both recursion and iteration, with performance comparisons
• use of arrays and temporary tables for intermediate storage, with performance comparisons
• methods for compact storage of sequences of items
• use of PL/SQL functions in SQL and performance effects of context switching
• automated code timing

### Automation

• installation
• running the solution methods
• code instrumentation
• unit testing

# Recursive SQL for Network Analysis, and Duality

In March 2013 I wrote an article on the use of SQL to group network-structured records into their distinct connected subnetworks, SQL for Network Grouping. I looked at two solution approaches commonly put forward on Oracle forums for these types of problem, using Oracle’s Connect By recursion, and the more recent recursive subquery factoring, and also put forward a new solution of my own using the Model clause. I noted however that SQL solutions are generally very inefficent compared with a good PL/SQL solution, such as I posted here, PL/SQL Pipelined Function for Network Analysis. For the first two methods, I noted:

1. Non-hierarchical networks have no root nodes, so the traversal needs to be repeated from every node in the network set
2. Hierarchical queries retrieve all possible routes through a network

I also noted that Connect By is more inefficient than recursive subquery factoring, but did not say why, promising a more detailed explanation at a later date. In this article I illustrate the behaviour of both recursive SQL methods through a series of five elementary networks, followed by a simple combination of the five. I then use the foreign key network from Oracle’s HR demo (v12 version, with OE and PM schemas included) as a final example.

In this article I consider traversal of a single connected network from a given root node (or several if each root node is specified).

It is shown that the behaviour of Connect By can be understood best by considering it to traverse all paths through a network that is dual to the original network.

Dual Networks

Dual network definition

The dual network consists of a set of nodes and links (d-nodes and d-links say) defined thus:

• the d-nodes correspond to each link in the original network that is adjacent (via a node) to at least one other link, including itself if its start and end nodes are the same

Dual network SQL

The d-node identifiers are just the link identifiers, while the d-link identifiers use the adjacency-defining node identifiers with a sequential number (partitioned by node) attached.

SELECT	DISTINCT CASE WHEN lin_2.node_fr IN (lin_1.node_fr, lin_1.node_to) THEN lin_2.node_fr ELSE lin_2.node_to END link_node,
lin_1.id node_fr_d,
lin_2.id node_to_d
ON lin_2.node_fr IN (lin_1.node_fr, lin_1.node_to)
OR lin_2.node_to IN (lin_1.node_fr, lin_1.node_to)
WHERE lin_2.id >= lin_1.id
AND (lin_2.id != lin_1.id OR lin_2.node_fr = lin_1.node_to)
)
ORDER BY node_fr_d, node_to_d) || '-' || Substr (link_node, -1),
node_fr_d,
node_to_d

Dual network characteristics

Dual networks defined as above are generally larger than the original networks and are usually more heavily looped, which explains the inferior performance of Connect by compared with recursive subquery factor solutions. The PL/SQL solution mentioned above, while traversing the entire network, does not traverse all possible routes through it and its performance is thus not adversely affected by the degree of looping.

SQL Queries

The recursive SQL queries return all routes through the network from the roots supplied. In my attached script I also have versions that filter out repeated links. The pipelined function query returns a single, exhaustive route through the network, distinguishing a set of tree links from loop-closing links; it also returns all subnetworks without requiring input roots.

Pipelined Function Query (PLF)

See PL/SQL Pipelined Function for Network Analysis for the Pl/SQL function.

SELECT root_node_id             "Network",
Count (DISTINCT node_id) OVER (PARTITION BY root_node_id) "#Nodes",
LPad (dirn || ' ', 2*node_level, ' ') || node_id || loop_flag "Node",
node_level               "Lev"
FROM TABLE (Net_Pipe.All_Nets)
ORDER BY line_no

Recursive Subquery Factor Query (RSF)

WITH rsf (node_id, prefix, id, lev) AS (
SELECT node_id, '', 'ROOT_' || Substr (node_id, 4, 1), 0
FROM nodes_v
WHERE Substr (node_id, 2, 1) = '1'
UNION ALL
SELECT CASE WHEN l.node_id_to = r.node_id THEN l.node_id_fr ELSE l.node_id_to END,
CASE WHEN l.node_id_fr = l.node_id_to THEN '= ' WHEN l.node_id_fr = r.node_id THEN '> ' ELSE '< ' END,
FROM rsf r
ON (l.node_id_fr = r.node_id OR l.node_id_to = r.node_id)
AND l.link_id != Nvl (r.id, '0')
) SEARCH DEPTH FIRST BY node_id SET line_no
CYCLE node_id SET is_cycle TO '*' DEFAULT ' '
SELECT LPad (r.prefix || ' ', 2*r.lev) || r.node_id || is_cycle "Node",
line_no
FROM rsf r
ORDER BY line_no

Connect By Query (CBY)

SELECT node_id_fr || ' > ' || node_id_to  "Nodes",
LPad (' ', 2 * (LEVEL-1)) || link_id || CASE WHEN CONNECT_BY_ISCYCLE = 1 THEN '*' ELSE ' ' END "Link Path"
CONNECT BY NOCYCLE ((node_id_fr = PRIOR node_id_to OR node_id_to = PRIOR node_id_fr OR
node_id_fr = PRIOR node_id_fr OR node_id_to = PRIOR node_id_to) /*AND link_id != PRIOR link_id*/)
START WITH Substr (node_id_fr, 2, 1) = '1' AND Substr (node_id_to, 2, 1) = '2'
ORDER SIBLINGS BY node_id_to

Five Elementary Networks

Oracle’s two forms of SQL recursion treat cycles differently

Connect By Cycles

The CONNECT_BY_ISCYCLE pseudocolumn returns 1 if the current row has a child which is also its ancestor. Otherwise it returns 0

Connect By queries do not return loop-closing nodes, and the prior node is marked as the cycle node.

Recursive Subquery Factor Cycles

A row is considered to form a cycle if one of its ancestor rows has the same values for the cycle columns.

Recursive Subquery Factor queries do return loop-closing nodes, and these nodes are marked as the cycle nodes.

We will see this differing behaviour clearly in the following examples. We will also see that the Connect By output on the original network has exactly the same structure as recursive subquery factor output on the dual network if the loop-closing rows are disregarded. Cycle nodes on both definitions are marked with a ‘*’ in the outputs below.

Network 1: 3 nodes in line

Network 2: Simple fork

Network 3: 2-node loop

Network 4: 3-node loop

Network 5: 2 nodes with a self-loop

Combination of Elementary Networks

Combination Network 6

This network has 10 links with 3 loops.

Combination Network 6: PLF Output

----------------- ----------
N1-6
> N2-6            L12-6
= N2-6*         L22-6
> N3-6          L23-6
> N4-6        L34-6
> N6-6      L46-6
> N4-6*   L64-6
> N5-6        L35-6
> N7-6      L57-6
> N8-6    L78-6
< N5-6* L58-6

Combination Network 6: RSF Output

----------------- ----------
N1-6
> N2-6            L12-6
=  N2-6*         L22-6
>  N3-6          L23-6
>  N4-6        L34-6
<  N6-6      L64-6
<  N4-6*   L46-6
>  N6-6      L46-6
>  N4-6*   L64-6
>  N5-6        L35-6
>  N7-6      L57-6
>  N8-6    L78-6
<  N5-6* L58-6
>  N8-6      L58-6
<  N7-6    L78-6
<  N5-6* L57-6

Combination Network 6: CBY Output

--------------- --------------------
N1-6 > N2-6     L12-6*
N2-6 > N2-6       L22-6*
N2-6 > N3-6         L23-6*
N3-6 > N4-6           L34-6*
N6-6 > N4-6             L64-6*
N4-6 > N6-6               L46-6*
N3-6 > N5-6             L35-6*
N5-6 > N7-6               L57-6*
N5-6 > N8-6                 L58-6*
N7-6 > N8-6                   L78-6*
N7-6 > N8-6                 L78-6*
N5-6 > N8-6                   L58-6*
N5-6 > N8-6               L58-6*
N5-6 > N7-6                 L57-6*
N7-6 > N8-6                   L78-6*
N7-6 > N8-6                 L78-6*
N5-6 > N7-6                   L57-6*
N4-6 > N6-6             L46-6*
N6-6 > N4-6               L64-6*
N3-6 > N5-6           L35-6*
N3-6 > N4-6             L34-6*
N6-6 > N4-6               L64-6*
N4-6 > N6-6                 L46-6*
N4-6 > N6-6               L46-6*
N6-6 > N4-6                 L64-6*
N5-6 > N7-6             L57-6*
N5-6 > N8-6               L58-6*
N7-6 > N8-6                 L78-6*
N7-6 > N8-6               L78-6*
N5-6 > N8-6                 L58-6*
N5-6 > N8-6             L58-6*
N5-6 > N7-6               L57-6*
N7-6 > N8-6                 L78-6*
N7-6 > N8-6               L78-6*
N5-6 > N7-6                 L57-6*
N2-6 > N3-6       L23-6*
N2-6 > N2-6         L22-6*
N3-6 > N4-6         L34-6*
N6-6 > N4-6           L64-6*
N4-6 > N6-6             L46-6*
N3-6 > N5-6           L35-6*
N5-6 > N7-6             L57-6*
N5-6 > N8-6               L58-6*
N7-6 > N8-6                 L78-6*
N7-6 > N8-6               L78-6*
N5-6 > N8-6                 L58-6*
N5-6 > N8-6             L58-6*
N5-6 > N7-6               L57-6*
N7-6 > N8-6                 L78-6*
N7-6 > N8-6               L78-6*
N5-6 > N7-6                 L57-6*
N4-6 > N6-6           L46-6*
N6-6 > N4-6             L64-6*
N3-6 > N5-6         L35-6*
N3-6 > N4-6           L34-6*
N6-6 > N4-6             L64-6*
N4-6 > N6-6               L46-6*
N4-6 > N6-6             L46-6*
N6-6 > N4-6               L64-6*
N5-6 > N7-6           L57-6*
N5-6 > N8-6             L58-6*
N7-6 > N8-6               L78-6*
N7-6 > N8-6             L78-6*
N5-6 > N8-6               L58-6*
N5-6 > N8-6           L58-6*
N5-6 > N7-6             L57-6*
N7-6 > N8-6               L78-6*
N7-6 > N8-6             L78-6*
N5-6 > N7-6               L57-6*

Dual Combination Network 6

This network has 15 links with 6 loops, whereas the original had 10 links with 3 loops.

Dual Combination Network 6: PLF Output

------------------------- ------
L12-6
> L22-6                   N2-1-6
= L22-6*                N2-3-6
> L23-6                 N2-4-6
< L12-6*              N2-2-6
> L34-6               N3-1-6
> L35-6             N3-3-6
< L23-6*          N3-2-6
> L57-6           N5-1-6
> L58-6         N5-3-6
< L35-6*      N5-2-6
> L78-6       N8-1-6
< L57-6*    N7-1-6
> L46-6             N4-1-6
> L64-6           N6-1-6
< L34-6*        N4-2-6

Dual Combination Network 6: RSF Output

------------------------- ------
L12-6
> L22-6                   N2-1-6
=  L22-6*                N2-3-6
>  L23-6                 N2-4-6
<  L12-6*              N2-2-6
>  L34-6               N3-1-6
>  L35-6             N3-3-6
<  L23-6*          N3-2-6
>  L57-6           N5-1-6
>  L58-6         N5-3-6
<  L35-6*      N5-2-6
>  L78-6       N8-1-6
<  L57-6*    N7-1-6
>  L78-6         N7-1-6
<  L58-6       N8-1-6
<  L35-6*    N5-2-6
<  L57-6*    N5-3-6
>  L58-6           N5-2-6
<  L57-6         N5-3-6
<  L35-6*      N5-1-6
>  L78-6       N7-1-6
<  L58-6*    N8-1-6
>  L78-6         N8-1-6
<  L57-6       N7-1-6
<  L35-6*    N5-1-6
>  L58-6*    N5-3-6
>  L46-6             N4-1-6
>  L64-6           N6-1-6
<  L34-6*        N4-2-6
>  L64-6             N4-2-6
<  L46-6           N6-1-6
<  L34-6*        N4-1-6
>  L35-6               N3-2-6
<  L34-6             N3-3-6
<  L23-6*          N3-1-6
>  L46-6           N4-1-6
>  L64-6         N6-1-6
<  L34-6*      N4-2-6
>  L64-6           N4-2-6
<  L46-6         N6-1-6
<  L34-6*      N4-1-6
>  L57-6             N5-1-6
>  L58-6           N5-3-6
<  L35-6*        N5-2-6
>  L78-6         N8-1-6
<  L57-6*      N7-1-6
>  L78-6           N7-1-6
<  L58-6         N8-1-6
<  L35-6*      N5-2-6
<  L57-6*      N5-3-6
>  L58-6             N5-2-6
<  L57-6           N5-3-6
<  L35-6*        N5-1-6
>  L78-6         N7-1-6
<  L58-6*      N8-1-6
>  L78-6           N8-1-6
<  L57-6         N7-1-6
<  L35-6*      N5-1-6
>  L58-6*      N5-3-6
> L23-6                   N2-2-6
<  L22-6                 N2-4-6
<  L12-6*              N2-1-6
=  L22-6*              N2-3-6
>  L34-6                 N3-1-6
>  L35-6               N3-3-6
<  L23-6*            N3-2-6
>  L57-6             N5-1-6
>  L58-6           N5-3-6
<  L35-6*        N5-2-6
>  L78-6         N8-1-6
<  L57-6*      N7-1-6
>  L78-6           N7-1-6
<  L58-6         N8-1-6
<  L35-6*      N5-2-6
<  L57-6*      N5-3-6
>  L58-6             N5-2-6
<  L57-6           N5-3-6
<  L35-6*        N5-1-6
>  L78-6         N7-1-6
<  L58-6*      N8-1-6
>  L78-6           N8-1-6
<  L57-6         N7-1-6
<  L35-6*      N5-1-6
>  L58-6*      N5-3-6
>  L46-6               N4-1-6
>  L64-6             N6-1-6
<  L34-6*          N4-2-6
>  L64-6               N4-2-6
<  L46-6             N6-1-6
<  L34-6*          N4-1-6
>  L35-6                 N3-2-6
<  L34-6               N3-3-6
<  L23-6*            N3-1-6
>  L46-6             N4-1-6
>  L64-6           N6-1-6
<  L34-6*        N4-2-6
>  L64-6             N4-2-6
<  L46-6           N6-1-6
<  L34-6*        N4-1-6
>  L57-6               N5-1-6
>  L58-6             N5-3-6
<  L35-6*          N5-2-6
>  L78-6           N8-1-6
<  L57-6*        N7-1-6
>  L78-6             N7-1-6
<  L58-6           N8-1-6
<  L35-6*        N5-2-6
<  L57-6*        N5-3-6
>  L58-6               N5-2-6
<  L57-6             N5-3-6
<  L35-6*          N5-1-6
>  L78-6           N7-1-6
<  L58-6*        N8-1-6
>  L78-6             N8-1-6
<  L57-6           N7-1-6
<  L35-6*        N5-1-6
>  L58-6*        N5-3-6

Combination Network 6: CBY Original with RSF Dual Output

In the output below I deleted all the loop rows from the RSF output for the dual network and placed the result beside the output for CBY for the original network, using a column-wise copy and paste. It's easy to see then their equivalent structure. Both have 69 rows.

Network 6: CBY                         Dual Network 6: RSF with loop rows deleted
==============                         ==========================================
--------------- --------------------   ------------------------- ------
N1-6 > N2-6     L12-6*                 L12-6
N2-6 > N2-6       L22-6*	       > L22-6                   N2-1-6
N2-6 > N3-6         L23-6*	        >  L23-6                 N2-4-6
N3-6 > N4-6           L34-6*	          >  L34-6               N3-1-6
N6-6 > N4-6             L64-6*	            >  L35-6             N3-3-6
N4-6 > N6-6               L46-6*              >  L57-6           N5-1-6
N3-6 > N5-6             L35-6*	                >  L58-6         N5-3-6
N5-6 > N7-6               L57-6*                  >  L78-6       N8-1-6
N5-6 > N8-6                 L58-6*              >  L78-6         N7-1-6
N7-6 > N8-6                   L78-6*              <  L58-6       N8-1-6
N7-6 > N8-6                 L78-6*            >  L58-6           N5-2-6
N5-6 > N8-6                   L58-6*            <  L57-6         N5-3-6
N5-6 > N8-6               L58-6*                  >  L78-6       N7-1-6
N5-6 > N7-6                 L57-6*              >  L78-6         N8-1-6
N7-6 > N8-6                   L78-6*              <  L57-6       N7-1-6
N7-6 > N8-6                 L78-6*          >  L46-6             N4-1-6
N5-6 > N7-6                   L57-6*          >  L64-6           N6-1-6
N4-6 > N6-6             L46-6*	            >  L64-6             N4-2-6
N6-6 > N4-6               L64-6*              <  L46-6           N6-1-6
N3-6 > N5-6           L35-6*	          >  L35-6               N3-2-6
N3-6 > N4-6             L34-6*	            <  L34-6             N3-3-6
N6-6 > N4-6               L64-6*              >  L46-6           N4-1-6
N4-6 > N6-6                 L46-6*              >  L64-6         N6-1-6
N4-6 > N6-6               L46-6*              >  L64-6           N4-2-6
N6-6 > N4-6                 L64-6*              <  L46-6         N6-1-6
N5-6 > N7-6             L57-6*	            >  L57-6             N5-1-6
N5-6 > N8-6               L58-6*              >  L58-6           N5-3-6
N7-6 > N8-6                 L78-6*              >  L78-6         N8-1-6
N7-6 > N8-6               L78-6*              >  L78-6           N7-1-6
N5-6 > N8-6                 L58-6*              <  L58-6         N8-1-6
N5-6 > N8-6             L58-6*	            >  L58-6             N5-2-6
N5-6 > N7-6               L57-6*              <  L57-6           N5-3-6
N7-6 > N8-6                 L78-6*              >  L78-6         N7-1-6
N7-6 > N8-6               L78-6*              >  L78-6           N8-1-6
N5-6 > N7-6                 L57-6*              <  L57-6         N7-1-6
N2-6 > N3-6       L23-6*	       > L23-6                   N2-2-6
N2-6 > N2-6         L22-6*	        <  L22-6                 N2-4-6
N3-6 > N4-6         L34-6*	        >  L34-6                 N3-1-6
N6-6 > N4-6           L64-6*	          >  L35-6               N3-3-6
N4-6 > N6-6             L46-6*	            >  L57-6             N5-1-6
N3-6 > N5-6           L35-6*	              >  L58-6           N5-3-6
N5-6 > N7-6             L57-6*	                >  L78-6         N8-1-6
N5-6 > N8-6               L58-6*              >  L78-6           N7-1-6
N7-6 > N8-6                 L78-6*              <  L58-6         N8-1-6
N7-6 > N8-6               L78-6*            >  L58-6             N5-2-6
N5-6 > N8-6                 L58-6*            <  L57-6           N5-3-6
N5-6 > N8-6             L58-6*	                >  L78-6         N7-1-6
N5-6 > N7-6               L57-6*              >  L78-6           N8-1-6
N7-6 > N8-6                 L78-6*              <  L57-6         N7-1-6
N7-6 > N8-6               L78-6*          >  L46-6               N4-1-6
N5-6 > N7-6                 L57-6*          >  L64-6             N6-1-6
N4-6 > N6-6           L46-6*	          >  L64-6               N4-2-6
N6-6 > N4-6             L64-6*	            <  L46-6             N6-1-6
N3-6 > N5-6         L35-6*	        >  L35-6                 N3-2-6
N3-6 > N4-6           L34-6*	          <  L34-6               N3-3-6
N6-6 > N4-6             L64-6*	            >  L46-6             N4-1-6
N4-6 > N6-6               L46-6*              >  L64-6           N6-1-6
N4-6 > N6-6             L46-6*	            >  L64-6             N4-2-6
N6-6 > N4-6               L64-6*              <  L46-6           N6-1-6
N5-6 > N7-6           L57-6*	          >  L57-6               N5-1-6
N5-6 > N8-6             L58-6*	            >  L58-6             N5-3-6
N7-6 > N8-6               L78-6*              >  L78-6           N8-1-6
N7-6 > N8-6             L78-6*	            >  L78-6             N7-1-6
N5-6 > N8-6               L58-6*              <  L58-6           N8-1-6
N5-6 > N8-6           L58-6*	          >  L58-6               N5-2-6
N5-6 > N7-6             L57-6*	            <  L57-6             N5-3-6
N7-6 > N8-6               L78-6*              >  L78-6           N7-1-6
N7-6 > N8-6             L78-6*	            >  L78-6             N8-1-6
N5-6 > N7-6               L57-6*              <  L57-6           N7-1-6

Dual Combination Network 6: CBY Output

34547 rows selected.

[See attached file if interested in detail.]

Oracle's HR/OE/PM Demo Network

Original Demo Network

This network has 21 links with 6 loops.

Original Demo Network: PLF Output

--------------------------------------------- ----------------------------------- ----
COUNTRIES|HR                                  ROOT                                   0
< LOCATIONS|HR                                loc_c_id_fk|HR                         1
< DEPARTMENTS|HR                            dept_loc_fk|HR                         2
> EMPLOYEES|HR                            dept_mgr_fk|HR                         3
< CUSTOMERS|OE                          customers_account_manager_fk|OE        4
< ORDERS|OE                           orders_customer_id_fk|OE               5
> EMPLOYEES|HR*                     orders_sales_rep_fk|OE                 6
< ORDER_ITEMS|OE                    order_items_order_id_fk|OE             6
> PRODUCT_INFORMATION|OE          order_items_product_id_fk|OE           7
< INVENTORIES|OE                inventories_product_id_fk|OE           8
> WAREHOUSES|OE               inventories_warehouses_fk|OE           9
> LOCATIONS|HR*             warehouses_location_fk|OE             10
< ONLINE_MEDIA|PM               loc_c_id_fk|PM                         8
< PRINT_MEDIA|PM                printmedia_fk|PM                       8
< PRODUCT_DESCRIPTIONS|OE       pd_product_id_fk|OE                    8
> DEPARTMENTS|HR*                       emp_dept_fk|HR                         4
= EMPLOYEES|HR*                         emp_manager_fk|HR                      4
> JOBS|HR                               emp_job_fk|HR                          4
< JOB_HISTORY|HR                      jhist_job_fk|HR                        5
> DEPARTMENTS|HR*                   jhist_dept_fk|HR                       6
> EMPLOYEES|HR*                     jhist_emp_fk|HR                        6
> REGIONS|HR                                  countr_reg_fk|HR                       1

22 rows selected.

Elapsed: 00:00:00.15

Original Demo Network: RSF Output

--------------------------------------------- -----------------------------------
COUNTRIES|HR
< LOCATIONS|HR                                loc_c_id_fk|HR
< DEPARTMENTS|HR                            dept_loc_fk|HR
< EMPLOYEES|HR                            emp_dept_fk|HR
< CUSTOMERS|OE                          customers_account_manager_fk|OE
< ORDERS|OE                           orders_customer_id_fk|OE
> EMPLOYEES|HR*                     orders_sales_rep_fk|OE
< ORDER_ITEMS|OE                    order_items_order_id_fk|OE
> PRODUCT_INFORMATION|OE          order_items_product_id_fk|OE
< INVENTORIES|OE                inventories_product_id_fk|OE
> WAREHOUSES|OE               inventories_warehouses_fk|OE
> LOCATIONS|HR*             warehouses_location_fk|OE
< ONLINE_MEDIA|PM               loc_c_id_fk|PM
< PRINT_MEDIA|PM                printmedia_fk|PM
< PRODUCT_DESCRIPTIONS|OE       pd_product_id_fk|OE
< DEPARTMENTS|HR*                       dept_mgr_fk|HR
= EMPLOYEES|HR*                         emp_manager_fk|HR
> JOBS|HR                               emp_job_fk|HR
< JOB_HISTORY|HR                      jhist_job_fk|HR
> DEPARTMENTS|HR*                   jhist_dept_fk|HR
> EMPLOYEES|HR*                     jhist_emp_fk|HR
< JOB_HISTORY|HR                        jhist_emp_fk|HR
> DEPARTMENTS|HR*                     jhist_dept_fk|HR
> JOBS|HR                             jhist_job_fk|HR
< EMPLOYEES|HR*                     emp_job_fk|HR
< ORDERS|OE                             orders_sales_rep_fk|OE
> CUSTOMERS|OE                        orders_customer_id_fk|OE
> EMPLOYEES|HR*                     customers_account_manager_fk|OE
< ORDER_ITEMS|OE                      order_items_order_id_fk|OE
> PRODUCT_INFORMATION|OE            order_items_product_id_fk|OE
< INVENTORIES|OE                  inventories_product_id_fk|OE
> WAREHOUSES|OE                 inventories_warehouses_fk|OE
> LOCATIONS|HR*               warehouses_location_fk|OE
< ONLINE_MEDIA|PM                 loc_c_id_fk|PM
< PRINT_MEDIA|PM                  printmedia_fk|PM
< PRODUCT_DESCRIPTIONS|OE         pd_product_id_fk|OE
> EMPLOYEES|HR                            dept_mgr_fk|HR
< CUSTOMERS|OE                          customers_account_manager_fk|OE
< ORDERS|OE                           orders_customer_id_fk|OE
> EMPLOYEES|HR*                     orders_sales_rep_fk|OE
< ORDER_ITEMS|OE                    order_items_order_id_fk|OE
> PRODUCT_INFORMATION|OE          order_items_product_id_fk|OE
< INVENTORIES|OE                inventories_product_id_fk|OE
> WAREHOUSES|OE               inventories_warehouses_fk|OE
> LOCATIONS|HR*             warehouses_location_fk|OE
< ONLINE_MEDIA|PM               loc_c_id_fk|PM
< PRINT_MEDIA|PM                printmedia_fk|PM
< PRODUCT_DESCRIPTIONS|OE       pd_product_id_fk|OE
> DEPARTMENTS|HR*                       emp_dept_fk|HR
= EMPLOYEES|HR*                         emp_manager_fk|HR
> JOBS|HR                               emp_job_fk|HR
< JOB_HISTORY|HR                      jhist_job_fk|HR
> DEPARTMENTS|HR*                   jhist_dept_fk|HR
> EMPLOYEES|HR*                     jhist_emp_fk|HR
< JOB_HISTORY|HR                        jhist_emp_fk|HR
> DEPARTMENTS|HR*                     jhist_dept_fk|HR
> JOBS|HR                             jhist_job_fk|HR
< EMPLOYEES|HR*                     emp_job_fk|HR
< ORDERS|OE                             orders_sales_rep_fk|OE
> CUSTOMERS|OE                        orders_customer_id_fk|OE
> EMPLOYEES|HR*                     customers_account_manager_fk|OE
< ORDER_ITEMS|OE                      order_items_order_id_fk|OE
> PRODUCT_INFORMATION|OE            order_items_product_id_fk|OE
< INVENTORIES|OE                  inventories_product_id_fk|OE
> WAREHOUSES|OE                 inventories_warehouses_fk|OE
> LOCATIONS|HR*               warehouses_location_fk|OE
< ONLINE_MEDIA|PM                 loc_c_id_fk|PM
< PRINT_MEDIA|PM                  printmedia_fk|PM
< PRODUCT_DESCRIPTIONS|OE         pd_product_id_fk|OE
< JOB_HISTORY|HR                          jhist_dept_fk|HR
> EMPLOYEES|HR                          jhist_emp_fk|HR
< CUSTOMERS|OE                        customers_account_manager_fk|OE
< ORDERS|OE                         orders_customer_id_fk|OE
> EMPLOYEES|HR*                   orders_sales_rep_fk|OE
< ORDER_ITEMS|OE                  order_items_order_id_fk|OE
> PRODUCT_INFORMATION|OE        order_items_product_id_fk|OE
< INVENTORIES|OE              inventories_product_id_fk|OE
> WAREHOUSES|OE             inventories_warehouses_fk|OE
> LOCATIONS|HR*           warehouses_location_fk|OE
< ONLINE_MEDIA|PM             loc_c_id_fk|PM
< PRINT_MEDIA|PM              printmedia_fk|PM
< PRODUCT_DESCRIPTIONS|OE     pd_product_id_fk|OE
< DEPARTMENTS|HR*                     dept_mgr_fk|HR
> DEPARTMENTS|HR*                     emp_dept_fk|HR
= EMPLOYEES|HR*                       emp_manager_fk|HR
> JOBS|HR                             emp_job_fk|HR
< JOB_HISTORY|HR*                   jhist_job_fk|HR
< ORDERS|OE                           orders_sales_rep_fk|OE
> CUSTOMERS|OE                      orders_customer_id_fk|OE
> EMPLOYEES|HR*                   customers_account_manager_fk|OE
< ORDER_ITEMS|OE                    order_items_order_id_fk|OE
> PRODUCT_INFORMATION|OE          order_items_product_id_fk|OE
< INVENTORIES|OE                inventories_product_id_fk|OE
> WAREHOUSES|OE               inventories_warehouses_fk|OE
> LOCATIONS|HR*             warehouses_location_fk|OE
< ONLINE_MEDIA|PM               loc_c_id_fk|PM
< PRINT_MEDIA|PM                printmedia_fk|PM
< PRODUCT_DESCRIPTIONS|OE       pd_product_id_fk|OE
> JOBS|HR                               jhist_job_fk|HR
< EMPLOYEES|HR                        emp_job_fk|HR
< CUSTOMERS|OE                      customers_account_manager_fk|OE
< ORDERS|OE                       orders_customer_id_fk|OE
> EMPLOYEES|HR*                 orders_sales_rep_fk|OE
< ORDER_ITEMS|OE                order_items_order_id_fk|OE
> PRODUCT_INFORMATION|OE      order_items_product_id_fk|OE
< INVENTORIES|OE            inventories_product_id_fk|OE
> WAREHOUSES|OE           inventories_warehouses_fk|OE
> LOCATIONS|HR*         warehouses_location_fk|OE
< ONLINE_MEDIA|PM           loc_c_id_fk|PM
< PRINT_MEDIA|PM            printmedia_fk|PM
< PRODUCT_DESCRIPTIONS|OE   pd_product_id_fk|OE
< DEPARTMENTS|HR*                   dept_mgr_fk|HR
> DEPARTMENTS|HR*                   emp_dept_fk|HR
= EMPLOYEES|HR*                     emp_manager_fk|HR
< JOB_HISTORY|HR*                   jhist_emp_fk|HR
< ORDERS|OE                         orders_sales_rep_fk|OE
> CUSTOMERS|OE                    orders_customer_id_fk|OE
> EMPLOYEES|HR*                 customers_account_manager_fk|OE
< ORDER_ITEMS|OE                  order_items_order_id_fk|OE
> PRODUCT_INFORMATION|OE        order_items_product_id_fk|OE
< INVENTORIES|OE              inventories_product_id_fk|OE
> WAREHOUSES|OE             inventories_warehouses_fk|OE
> LOCATIONS|HR*           warehouses_location_fk|OE
< ONLINE_MEDIA|PM             loc_c_id_fk|PM
< PRINT_MEDIA|PM              printmedia_fk|PM
< PRODUCT_DESCRIPTIONS|OE     pd_product_id_fk|OE
< WAREHOUSES|OE                             warehouses_location_fk|OE
< INVENTORIES|OE                          inventories_warehouses_fk|OE
> PRODUCT_INFORMATION|OE                inventories_product_id_fk|OE
< ONLINE_MEDIA|PM                     loc_c_id_fk|PM
< ORDER_ITEMS|OE                      order_items_product_id_fk|OE
> ORDERS|OE                         order_items_order_id_fk|OE
> CUSTOMERS|OE                    orders_customer_id_fk|OE
> EMPLOYEES|HR                  customers_account_manager_fk|OE
< DEPARTMENTS|HR              dept_mgr_fk|HR
< EMPLOYEES|HR*             emp_dept_fk|HR
< JOB_HISTORY|HR            jhist_dept_fk|HR
> EMPLOYEES|HR*           jhist_emp_fk|HR
> JOBS|HR                 jhist_job_fk|HR
< EMPLOYEES|HR*         emp_job_fk|HR
> LOCATIONS|HR*             dept_loc_fk|HR
> DEPARTMENTS|HR              emp_dept_fk|HR
> EMPLOYEES|HR*             dept_mgr_fk|HR
< JOB_HISTORY|HR            jhist_dept_fk|HR
> EMPLOYEES|HR*           jhist_emp_fk|HR
> JOBS|HR                 jhist_job_fk|HR
< EMPLOYEES|HR*         emp_job_fk|HR
> LOCATIONS|HR*             dept_loc_fk|HR
= EMPLOYEES|HR*               emp_manager_fk|HR
> JOBS|HR                     emp_job_fk|HR
< JOB_HISTORY|HR            jhist_job_fk|HR
> DEPARTMENTS|HR          jhist_dept_fk|HR
< EMPLOYEES|HR*         emp_dept_fk|HR
> EMPLOYEES|HR*         dept_mgr_fk|HR
> LOCATIONS|HR*         dept_loc_fk|HR
> EMPLOYEES|HR*           jhist_emp_fk|HR
< JOB_HISTORY|HR              jhist_emp_fk|HR
> DEPARTMENTS|HR            jhist_dept_fk|HR
< EMPLOYEES|HR*           emp_dept_fk|HR
> EMPLOYEES|HR*           dept_mgr_fk|HR
> LOCATIONS|HR*           dept_loc_fk|HR
> JOBS|HR                   jhist_job_fk|HR
< EMPLOYEES|HR*           emp_job_fk|HR
< ORDERS|OE*                  orders_sales_rep_fk|OE
> EMPLOYEES|HR                    orders_sales_rep_fk|OE
< CUSTOMERS|OE                  customers_account_manager_fk|OE
< ORDERS|OE*                  orders_customer_id_fk|OE
< DEPARTMENTS|HR                dept_mgr_fk|HR
< EMPLOYEES|HR*               emp_dept_fk|HR
< JOB_HISTORY|HR              jhist_dept_fk|HR
> EMPLOYEES|HR*             jhist_emp_fk|HR
> JOBS|HR                   jhist_job_fk|HR
< EMPLOYEES|HR*           emp_job_fk|HR
> LOCATIONS|HR*               dept_loc_fk|HR
> DEPARTMENTS|HR                emp_dept_fk|HR
> EMPLOYEES|HR*               dept_mgr_fk|HR
< JOB_HISTORY|HR              jhist_dept_fk|HR
> EMPLOYEES|HR*             jhist_emp_fk|HR
> JOBS|HR                   jhist_job_fk|HR
< EMPLOYEES|HR*           emp_job_fk|HR
> LOCATIONS|HR*               dept_loc_fk|HR
= EMPLOYEES|HR*                 emp_manager_fk|HR
> JOBS|HR                       emp_job_fk|HR
< JOB_HISTORY|HR              jhist_job_fk|HR
> DEPARTMENTS|HR            jhist_dept_fk|HR
< EMPLOYEES|HR*           emp_dept_fk|HR
> EMPLOYEES|HR*           dept_mgr_fk|HR
> LOCATIONS|HR*           dept_loc_fk|HR
> EMPLOYEES|HR*             jhist_emp_fk|HR
< JOB_HISTORY|HR                jhist_emp_fk|HR
> DEPARTMENTS|HR              jhist_dept_fk|HR
< EMPLOYEES|HR*             emp_dept_fk|HR
> EMPLOYEES|HR*             dept_mgr_fk|HR
> LOCATIONS|HR*             dept_loc_fk|HR
> JOBS|HR                     jhist_job_fk|HR
< EMPLOYEES|HR*             emp_job_fk|HR
< PRINT_MEDIA|PM                      printmedia_fk|PM
< PRODUCT_DESCRIPTIONS|OE             pd_product_id_fk|OE
> REGIONS|HR                                  countr_reg_fk|HR

199 rows selected.

Elapsed: 00:00:00.30

The output above shows that RSF returned 199 rows unfiltered in 0.3s.

Original Demo Network: CBY Output

One tree by Connect By

-------------------------------------------------- ----------------------------------------------------------------------
COUNTRIES|HR > REGIONS|HR                          countr_reg_fk|HR*
LOCATIONS|HR > COUNTRIES|HR                          loc_c_id_fk|HR*
DEPARTMENTS|HR > LOCATIONS|HR                          dept_loc_fk|HR*
EMPLOYEES|HR > DEPARTMENTS|HR                            emp_dept_fk|HR*
JOB_HISTORY|HR > DEPARTMENTS|HR                            jhist_dept_fk|HR*
DEPARTMENTS|HR > EMPLOYEES|HR                                dept_mgr_fk|HR*
EMPLOYEES|HR > EMPLOYEES|HR                                    emp_manager_fk|HR*
CUSTOMERS|OE > EMPLOYEES|HR                                      customers_account_manager_fk|OE*
ORDERS|OE > CUSTOMERS|OE                                           orders_customer_id_fk|OE*
ORDERS|OE > EMPLOYEES|HR                                             orders_sales_rep_fk|OE*
JOB_HISTORY|HR > EMPLOYEES|HR                                          jhist_emp_fk|HR*
EMPLOYEES|HR > JOBS|HR                                                   emp_job_fk|HR*
JOB_HISTORY|HR > JOBS|HR                                                   jhist_job_fk|HR*
JOB_HISTORY|HR > JOBS|HR                                                 jhist_job_fk|HR*
EMPLOYEES|HR > JOBS|HR                                                     emp_job_fk|HR*
EMPLOYEES|HR > JOBS|HR                                                 emp_job_fk|HR*
JOB_HISTORY|HR > EMPLOYEES|HR                                            jhist_emp_fk|HR*
JOB_HISTORY|HR > JOBS|HR                                                   jhist_job_fk|HR*
JOB_HISTORY|HR > JOBS|HR                                                 jhist_job_fk|HR*
JOB_HISTORY|HR > EMPLOYEES|HR                                              jhist_emp_fk|HR*
ORDER_ITEMS|OE > ORDERS|OE                                             order_items_order_id_fk|OE*
ORDER_ITEMS|OE > PRODUCT_INFORMATION|OE                                  order_items_product_id_fk|OE*
INVENTORIES|OE > PRODUCT_INFORMATION|OE                                    inventories_product_id_fk|OE*
PRINT_MEDIA|PM > PRODUCT_INFORMATION|OE                                      printmedia_fk|PM*
.
.
.
ORDERS|OE > CUSTOMERS|OE                                                           orders_customer_id_fk|OE*
EMPLOYEES|HR > EMPLOYEES|HR                                                        emp_manager_fk|HR*
PRINT_MEDIA|PM > PRODUCT_INFORMATION|OE                        printmedia_fk|PM*
ONLINE_MEDIA|PM > PRODUCT_INFORMATION|OE                         loc_c_id_fk|PM*
PRODUCT_DESCRIPTIONS|OE > PRODUCT_INFORMATION|OE                   pd_product_id_fk|OE*
PRODUCT_DESCRIPTIONS|OE > PRODUCT_INFORMATION|OE                 pd_product_id_fk|OE*
ONLINE_MEDIA|PM > PRODUCT_INFORMATION|OE                           loc_c_id_fk|PM*
ONLINE_MEDIA|PM > PRODUCT_INFORMATION|OE                       loc_c_id_fk|PM*
PRINT_MEDIA|PM > PRODUCT_INFORMATION|OE                          printmedia_fk|PM*
PRODUCT_DESCRIPTIONS|OE > PRODUCT_INFORMATION|OE                   pd_product_id_fk|OE*
PRODUCT_DESCRIPTIONS|OE > PRODUCT_INFORMATION|OE                 pd_product_id_fk|OE*
PRINT_MEDIA|PM > PRODUCT_INFORMATION|OE                            printmedia_fk|PM*
PRODUCT_DESCRIPTIONS|OE > PRODUCT_INFORMATION|OE               pd_product_id_fk|OE*
PRINT_MEDIA|PM > PRODUCT_INFORMATION|OE                          printmedia_fk|PM*
ONLINE_MEDIA|PM > PRODUCT_INFORMATION|OE                           loc_c_id_fk|PM*
ONLINE_MEDIA|PM > PRODUCT_INFORMATION|OE                         loc_c_id_fk|PM*
PRINT_MEDIA|PM > PRODUCT_INFORMATION|OE                            printmedia_fk|PM*

4414420 rows selected.

Elapsed: 00:29:33.41

One tree by Connect By filtered

-------------------------------------------------- ---------------------------------------------------------------------- ----------
COUNTRIES|HR > REGIONS|HR                          countr_reg_fk|HR*                                                               1
LOCATIONS|HR > COUNTRIES|HR                          loc_c_id_fk|HR*                                                               1
DEPARTMENTS|HR > LOCATIONS|HR                          dept_loc_fk|HR*                                                        214178
EMPLOYEES|HR > DEPARTMENTS|HR                            emp_dept_fk|HR*                                                      169932
JOB_HISTORY|HR > DEPARTMENTS|HR                            jhist_dept_fk|HR*                                                  272162
DEPARTMENTS|HR > EMPLOYEES|HR                                dept_mgr_fk|HR*                                                  169932
EMPLOYEES|HR > EMPLOYEES|HR                                    emp_manager_fk|HR*                                             207910
CUSTOMERS|OE > EMPLOYEES|HR                                      customers_account_manager_fk|OE*                             132490
ORDERS|OE > CUSTOMERS|OE                                           orders_customer_id_fk|OE*                                   85298
ORDERS|OE > EMPLOYEES|HR                                             orders_sales_rep_fk|OE*                                   72234
JOB_HISTORY|HR > EMPLOYEES|HR                                          jhist_emp_fk|HR*                                       164660
EMPLOYEES|HR > JOBS|HR                                                   emp_job_fk|HR*                                       182784
JOB_HISTORY|HR > JOBS|HR                                                   jhist_job_fk|HR*                                   333192
ORDER_ITEMS|OE > ORDERS|OE                                             order_items_order_id_fk|OE*                             26804
ORDER_ITEMS|OE > PRODUCT_INFORMATION|OE                                  order_items_product_id_fk|OE*                         26804
INVENTORIES|OE > PRODUCT_INFORMATION|OE                                    inventories_product_id_fk|OE*                      428354
PRINT_MEDIA|PM > PRODUCT_INFORMATION|OE                                      printmedia_fk|PM*                                428384
ONLINE_MEDIA|PM > PRODUCT_INFORMATION|OE                                       loc_c_id_fk|PM*                                428384
PRODUCT_DESCRIPTIONS|OE > PRODUCT_INFORMATION|OE                                 pd_product_id_fk|OE*                         428384
INVENTORIES|OE > WAREHOUSES|OE                                               inventories_warehouses_fk|OE*                    428354
WAREHOUSES|OE > LOCATIONS|HR                                                   warehouses_location_fk|OE*                     214178

21 rows selected.

Elapsed: 00:03:03.16

The output above shows that CBY returned 4,414,420 rows unfiltered in 29m33s. Adding filtering reduced the time to 3m03s.

Dual Demo Network

This network has 52 links with 32 loops, whereas the original had 21 links with 6 loops.

Dual Demo Network: PLF Output

-------------------------------------------------------------- -------------------------
countr_reg_fk|HR                                               ROOT
> loc_c_id_fk|HR                                               COUNTRIES|HR-1
< dept_loc_fk|HR                                             LOCATIONS|HR-1
> dept_mgr_fk|HR                                           DEPARTMENTS|HR-1
< customers_account_manager_fk|OE                        EMPLOYEES|HR-1
> emp_dept_fk|HR                                       EMPLOYEES|HR-2
< dept_loc_fk|HR*                                    DEPARTMENTS|HR-2
< dept_mgr_fk|HR*                                    EMPLOYEES|HR-7
> emp_job_fk|HR                                      EMPLOYEES|HR-12
< customers_account_manager_fk|OE*                 EMPLOYEES|HR-3
< dept_mgr_fk|HR*                                  EMPLOYEES|HR-8
> emp_manager_fk|HR                                EMPLOYEES|HR-16
< customers_account_manager_fk|OE*               EMPLOYEES|HR-4
< dept_mgr_fk|HR*                                EMPLOYEES|HR-9
< emp_dept_fk|HR*                                EMPLOYEES|HR-13
= emp_manager_fk|HR*                             EMPLOYEES|HR-19
> jhist_emp_fk|HR                                EMPLOYEES|HR-20
< customers_account_manager_fk|OE*             EMPLOYEES|HR-5
< dept_mgr_fk|HR*                              EMPLOYEES|HR-10
< emp_dept_fk|HR*                              EMPLOYEES|HR-14
< emp_job_fk|HR*                               EMPLOYEES|HR-17
< jhist_dept_fk|HR                             JOB_HISTORY|HR-1
< dept_loc_fk|HR*                            DEPARTMENTS|HR-3
< dept_mgr_fk|HR*                            DEPARTMENTS|HR-4
< emp_dept_fk|HR*                            DEPARTMENTS|HR-5
> jhist_job_fk|HR                            JOB_HISTORY|HR-2
< emp_job_fk|HR*                           JOBS|HR-1
< jhist_emp_fk|HR*                         JOB_HISTORY|HR-3
> orders_sales_rep_fk|OE                       EMPLOYEES|HR-22
< customers_account_manager_fk|OE*           EMPLOYEES|HR-6
< dept_mgr_fk|HR*                            EMPLOYEES|HR-11
< emp_dept_fk|HR*                            EMPLOYEES|HR-15
< emp_job_fk|HR*                             EMPLOYEES|HR-18
< emp_manager_fk|HR*                         EMPLOYEES|HR-21
< order_items_order_id_fk|OE                 ORDERS|OE-2
> order_items_product_id_fk|OE             ORDER_ITEMS|OE-1
< inventories_product_id_fk|OE           PRODUCT_INFORMATION|OE-2
> inventories_warehouses_fk|OE         INVENTORIES|OE-1
> warehouses_location_fk|OE          WAREHOUSES|OE-1
< dept_loc_fk|HR*                  LOCATIONS|HR-2
< loc_c_id_fk|HR*                  LOCATIONS|HR-3
> loc_c_id_fk|PM                       PRODUCT_INFORMATION|OE-1
> order_items_product_id_fk|OE*      PRODUCT_INFORMATION|OE-5
> pd_product_id_fk|OE                PRODUCT_INFORMATION|OE-6
< inventories_product_id_fk|OE*    PRODUCT_INFORMATION|OE-3
< order_items_product_id_fk|OE*    PRODUCT_INFORMATION|OE-8
> printmedia_fk|PM                 PRODUCT_INFORMATION|OE-10
< inventories_product_id_fk|OE*  PRODUCT_INFORMATION|OE-4
< loc_c_id_fk|PM*                PRODUCT_INFORMATION|OE-7
< order_items_product_id_fk|OE*  PRODUCT_INFORMATION|OE-9
> orders_customer_id_fk|OE                 ORDERS|OE-1
< customers_account_manager_fk|OE*       CUSTOMERS|OE-1
> orders_sales_rep_fk|OE*                ORDERS|OE-3

53 rows selected.

Elapsed: 00:00:00.27

Dual Demo Network: RSF and CBY Results

Neither of the two SQL recursion methods completed within a period of an hour and had to be terminated. The result for CBY on the original network suggests that RSF on the dual network should return somewhere above 4,414,420 rows.

Conclusions

• We have shown by examples how network traversal by the Connect By (CBY) approach in SQL corresponds to traversal of all routes in a type of dual version of the original network
• This dual version, which has forks converted to loops, tends to be larger and more heavily looped, resulting in worse performance compared with solution by recursive subquery factors (RSF)
• The examples illustrate the different treatment of loop-closing links between the two types of SQL recursion
• The RSF solutions on the dual network in the simpler examples where it completes is seen to be equivalent to the CBY solution on the original network, after allowing for the different treatment of loop-closing links
• On the foreign key network for Oracle's HR/OE/PM demo, which has 21 links, RSF returns 199 rows while CBY returns 4,414,420 rows
• On the dual version of the foreign key network for Oracle's HR/OE/PM demo, which has 52 links, RSF and CBY fail to complete in reasonable times
• The pipelined function method returns the solution on both original and dual in a small fraction of a second

SQL files: SQL for network duality
Output files: Output for network duality

Oracle version used: Oracle Database 12c Enterprise Edition Release 12.1.0.1.0 - 64bit Production