On RDBMS, SQL and the DRY Principle, and Query Networks

I saw a link a week ago or so on my Twitter feed to an article published by one Lance Gutteridge on 1 June 2018: What I’m Telling Business People About Why Relational Databases Are So Bad. The article is written in a inflammatory style, here’s a sample quote:

Relational databases have been the worst technology to ever poison a field of endeavor

He classifies the ‘badness’ in three main categories:

  • SQL Injection
  • SQL “is a total violation of the DRY principle”
  • Object-Relational Impedance Mismatch

In this article I want to briefly discuss his criticisms under each of these categories, and then move on to discuss some interesting features of SQL queries and joins arising from the fact that SQL plainly does NOT violate the DRY principle. I’ll also discuss how the concept of the network, initially applied to table relationships, can be a very useful design concept in both data modelling and query design.

Part I: Comments on the Lance Gutteridge article
SQL Injection
From Wikipedia, SQL injection:

SQL injection is a code injection technique, used to attack data-driven applications, in which nefarious SQL statements are inserted into an entry field for execution (e.g. to dump the database contents to the attacker).

SQL injection has indeed been a real vulnerability for database systems in the past, but it is an avoidable problem today. As the Wikipedia article puts it:

An SQL injection is a well known attack and easily prevented by simple measures.

SQL “is a total violation of the DRY principle”
Dr. Gutteridge notes that relationships are defined in an RDBMS by foreign keys and primary keys on the tables, and that having to make join relations explicitly in SQL is a repetition of information already known, and hence violates the “Don’t Repeat Yourself” principle.

This criticism is easily dealt with: In general the table relationships do not in fact fully determine the joins in a query. A simple, and very common, example arises in order entry systems. Consider the following simplified 3-table data model:

Here we have an order entity with a foreign key link to a customer, and two foreign key links to the address entity. A customer may have multiple addresses that can serve as shipping or billing addresses on any given order. A particular query may require one or other, or both, or neither of the addresses for the order. The primary key/foreign key relationships cannot determine which tables and links to include without the query specifying them.

The usual way to specify this information in ANSI-standard SQL is to use JOIN/ON-clauses like this:

JOIN addresses add_b ON add_b.address_id = ord.billing_address_id

There are also situations in which joins can be expressed more concisely, and we’ll look at some of them in part II, but it’s clear that these clauses do not in any meaningful way violate the DRY principle.

Object-Relational Impedance Mismatch
In one of the few views on which I am inclined to agree with Dr. Gutteridge, he regards the term as “technobabble”, but it does describe a real phenomenon. Dr. Gutteridge expresses it thus:

…the data in a relational database is stored in ways more in keeping with a 1980s programming language than with a modern, object-oriented language

Though this mismatch does exist, it’s unlikely that dropping the relational model is the answer, because it solves a more fundamental problem. An article from 29 November 2017, Important Papers: Codd and the Relational Model, includes the following:

…Codd motivates the search for a better model by arguing that we need “data independence,” which he defines as “the independence of application programs and terminal activities from growth in data types and changes in data representation.” The relational model, he argues, “appears to be superior in several respects to the graph or network model presently in vogue,” partly because, among other benefits, the relational model “provides a means of describing data with its natural structure only.” By this he meant that programs could safely ignore any artificial structures (like trees) imposed upon the data for storage and retrieval purposes only.

I remember when I started my programming career in 1984 most of the work on any application was spent in writing code simply to store and retrieve data in application-specific formats. Within a few years that effort became largely unnecessary with the introduction of the Oracle RDBMS and SQL. Although modern big data requirements mean other approaches to data storage are also needed, the relational model isn’t going away.

In one of the unwitting ironies in Dr. Gutteridge’s article, he states towards the end that:

there are programmers who have never really seen any other kind of database and believe that all databases are relational

while apparently believing that all modern programming language are object-oriented. They aren’t, and while OOP isn’t going away, it has real deficiencies in modelling the real world that have led to growing interest in other paradigms such as functional programming, as well as old fashioned imperative programming. Here’s an interesting review of some of those deficiencies from 23 July 2016:
Goodbye, Object Oriented Programming

Part II: On SQL and DRY – Joins via NATURAL/USING/ON
In this second part we’ll use two subsets of Oracle’s HR demo schema as examples, and we’ll ignore any links in the tables to tables other than those depicted in the ERDs. Let’s see how, in some cases, we can use ANSI join syntax to avoid explicitly listing all the join column names, but that there are drawbacks to doing so.

Tree Data Model – Department 110, Location, Country, Region – NATURAL JOIN
The ERD below shows a simple linear tree structure.

Let’s start by considering a situation where we don’t need to specify the full join clause with fields on both sides.

 DEPARTMENT_NAME                STREET_ADDRESS                           CITY                           COUNTRY_NAME                             REGION_NAME
------------------------------ ---------------------------------------- ------------------------------ ---------------------------------------- -------------------------
Accounting                     2004 Charade Rd                          Seattle                        United States of America                 Americas

  1  SELECT department_name, street_address, city, country_name, region_name
  2    FROM departments
  3      NATURAL JOIN locations
  4      NATURAL JOIN countries
  5      NATURAL JOIN regions
  6*  WHERE department_id = 110

Here in this simple (linear) tree-structured data model we were able to join the three subsequent tables to the driving table, departments, simply by adding the table names after NATURAL JOIN.

So is this a case of the SQL engine reading the data model and constructing the joins without the need for repetition? No, it isn’t. As the documentation tells you, NATURAL JOIN joins by matching fields with the same names on either side. This can be dangerous as the next example shows.

The second example has only two tables, but there is a loop in the structure.

[In the underlying HR schema from which this is extracted there is also a self-join on employees, which we are excluding]
Department 110 employees: NATURAL JOIN gives wrong answer
There are two employees in department 110:

  COUNT(*)
----------
         2

  1  SELECT COUNT(*)
  2    FROM employees
  3*  WHERE department_id = 110

Let’s try to get the employees using NATURAL JOIN, like this:

DEPARTMENT_NAME                LAST_NAME                 FIRST_NAME           MANAGER_ID
------------------------------ ------------------------- -------------------- ----------
Accounting                     Gietz                     William                     205

  1  SELECT department_name, last_name, first_name, manager_id
  2    FROM departments
  3     NATURAL JOIN employees
  4*  WHERE department_id = 110

This returns only one of the two employees because NATURAL JOIN is matching on both department_id and manager_id as they appear in both tables.

Department 110 employees: USING department_id gives right answer
We can get the right answer by joining with the USING keyword, which assumes the column name to join on is the same on both tables, and mentions it explicitly.

DEPARTMENT_NAME                LAST_NAME                 FIRST_NAME
------------------------------ ------------------------- --------------------
Accounting                     Higgins                   Shelley
Accounting                     Gietz                     William

  1  SELECT department_name, last_name, first_name
  2    FROM departments
  3     JOIN employees USING (department_id)
  4*  WHERE department_id = 110

This example shows how USING resolves the earlier NATURAL JOIN error by specifying the field names in common to be used. The next example shows how this does not always work.

Department 110 manager: USING manager_id gives wrong answer

DEPARTMENT_NAME                LAST_NAME                 FIRST_NAME           MANAGER_ID
------------------------------ ------------------------- -------------------- ----------
Accounting                     Gietz                     William                     205

  1  SELECT department_name, last_name, first_name, manager_id
  2    FROM departments dep
  3     JOIN employees USING (manager_id)
  4*  WHERE dep.department_id = 110

From the first query above we know that the manager of department 110 is Shelley Higgins. It’s reported here instead as William Gietz, because his manager is the same as the department’s manager, but Shirley’s is not.

Department 110 manager: ON mgr.employee_id = dep.manager_id gives right answer

DEPARTMENT_NAME                LAST_NAME                 FIRST_NAME
------------------------------ ------------------------- --------------------
Accounting                     Higgins                   Shelley

  1   SELECT department_name, last_name, first_name
  2     FROM departments dep
  3     JOIN employees mgr ON mgr.employee_id = dep.manager_id
  4*  WHERE dep.department_id = 110

Here we we specify the join with the ON-clause linking the columns explicitly on each side of the join. This is the most usual approach to ANSI joins.

Department 110 manager: NATURAL JOIN subqueries
In a recent article (A tribute to Natural Join, 20 August 2018) Frank Pachot suggested that NATURAL JOIN could be more widely used if tables were replaced by subqueries in which all the columns were aliased in such a way that the join columns only would have the same names in the joined tables. The query above, implemented in this way might be written:

DEPARTMENT_NAME                MGR_LAST_NAME             MGR_FIRST_NAME
------------------------------ ------------------------- --------------------
Accounting                     Higgins                   Shelley

  1  SELECT department_name, mgr_last_name, mgr_first_name
  2    FROM
  3  (SELECT department_id, department_name, manager_id
  4     FROM departments) dep
  5    NATURAL JOIN
  6  (SELECT employee_id manager_id, last_name mgr_last_name, first_name mgr_first_name
  7     FROM employees) mgr
  8*  WHERE dep.department_id = 110

This version is much more verbose and it’s much harder to see which are the join columns by scanning the select lists, compared with specifying them in ON clauses.

Conclusions on Joins via NATURAL/USING/ON

  • Very few people use NATURAL JOIN due to the limitation that the join column names, and only those, in each table or subquery have to be the same
  • USING tends to be used in simple ad hoc queries with small numbers of tables, and improves on NATURAL JOIN by listing the join columns explicitly, but again relies on the join column names being the same
  • The most commonly used join mechanism is the ON clause, with column names specified on each side. This avoids the possible pitfalls of the other mechanisms and for complex, real world queries generally results in more maintainable code

Regarding the DRY principle in SQL more generally, I wrote this,
Modularity in SQL: Patterns, Anti-Patterns and the Kitchen Sink, in September 2013 [tl;dr: Functions and complex views are fine as entry-points but using them as building blocks in SQL is usually a bad idea, and subquery factors (WITH clause) are a better approach to SQL modularity].

Part III: On Data Models and Queries Viewed as Networks
In the examples above we saw that when there are two ways of joining a pair of tables it’s no longer possible for the data model alone to determine the join. An entity relationship structure can be represented as a directed network, with entities as nodes and the relationships between them as links. The second example corresponds to a loop in the network, in which there are two ways of getting from the driving node, departments, to the employees node.

Where the relationships between tables are stored in constraints metadata we can use network analysis PL/SQL to show the network structure and then make diagrams to help in understanding schema structures, as I showed here in May 2015:
PL/SQL Pipelined Function for Network Analysis. This diagram, extracted from that article, shows the structure of Oracle’s demo schemas, with what’s known in graph theory as a spanning tree marked in red, and loop-closing links in blue.

Networks - PLSQL, v1.0 - HR

Queries as Networks
In 2009 I was asked to extend the functionality of an Oracle ERP invoice print report in order to support a move to a multi-org ERP structure. The report had a large number (I think around 30) of small queries in various places, such as format triggers and formula columns as well as in the main data model, and I started by combining most of them into a single, fairly complex query plus one smaller, global data query. The report ran much more quickly and I felt was more maintainable since almost all the logic was in one place, and the query could be tested through tools such as Toad. However, as the query was quite complex I was asked to produce some documentation on how it worked. This got me thinking about how ERDs are used to document data models, and whether we could extend those ideas to document queries too.

My initial thought was that a query can be thought of as a route through the data model network, with looping corresponding to repeated table instances in the query. However, it turns out to be much clearer to represent each table instance as its own node on a new network diagram. After I left the company I wrote my ideas up in a general form in a word document on Scribd in May 2009, A Structured Approach to SQL Query Design. Since then I have extended these ideas to include coverage of query constructs such as unions and subquery factors, and use of annotations for clarity. I wrote another article in August 2012 where I apply these extended ideas to some example queries taken from the OTN forum, Query Structure Diagramming. Here’s a diagram from that article:

You can also find examples in several of the articles on combinatorial SQL referenced in Knapsacks and Networks in SQL from December 2017.

How many tables is too many?
Have you ever heard the view expressed, usually by a DBA, that you should not put more than a small number of tables, say 10, in any query? The reasoning given is that the number of join orders for N tables is N!, which for N=10 is 3,628,800 and the query optimiser (CBO) won’t be able to handle that number of permutations. You will probably know from the discussion above why this reasoning is incorrect: The cost optimization problem is really a network path problem, rather than a permutation problem – you look to join (large) tables that are linked to the current rowset rather than than making cartesian joins, so most permutations are never considered.






Knapsacks and Networks in SQL

I opened a GitHub account, Brendan’s GitHub Page last year and have added a number of projects since then, in PL/SQL and other 3GL languages. Partly in response to a request for the code for one of my blog articles on an interesting SQL problem, I decided recently to create a new repo for the SQL behind a group of articles on solving difficult combinatorial optimisation problems via ‘advanced’ SQL techniques such as recursive subquery factoring and model clause, sql_demos – Brendan’s repo for interesting SQL. It includes installation scripts with object creation and data setup, and scripts to run the SQL on the included datasets. The idea is that anyone with the pre-requisites should be able to reproduce my results within a few minutes of downloading the repo.

[Left image from Knapsack problem; right image copied from Chapter 11 Dynamic Programming]

In this article I embed each of the earlier articles relevant to the GitHub repo with a brief preamble.

The first two articles are from January 2013 and use recursive subquery factoring to find exact solutions for the single and multiple knapsack problem, and also include PL/SQL solutions for comparison. They avoid the ‘brute force’ approach by truncating search paths as soon as limit constraints are exceeded. The cumulative paths are stored in string variables passed through the iterations (which would not be possible with the older Connect By hierarchical syntax).

In these articles I illustrate the nature of the problems using Visio diagrams, and include dimensional performance benchmarking results, using a technique that I presented on at last year’s Ireland OUG conference: Dimensional Performance Benchmarking of SQL – IOUG Presentation. I also illustrate the queries using my own method for diagramming SQL queries.

A Simple SQL Solution for the Knapsack Problem (SKP-1), January 2013

An SQL Solution for the Multiple Knapsack Problem (SKP-m), January 2013

The next article uses Model clause to find a more general solution to a problem posed on AskTom, as a ‘bin fitting’ problem. I also solved the problem by other methods including recursive subquery factoring. I illustrate the problem itself, as well as the Model iteration scheme using Visio diagrams, and again include dimensional performance benchmarking. The results show how quadratic performance variation can be turned into much faster linear variation by means of a temporary table in this kind of problem.

SQL for the Balanced Number Partitioning Problem, May 2013

This article arose from a question on OTN, and concerns a type of knapsack or bin-fitting problem that is quite tricky to solve in SQL, where the items fall into categories on which there are separate constraints. I introduced a new idea here, to filter out unpromising paths within recursive subquery factoring by means of analytic functions, in order to allow the technique to be used to generate solutions for larger problems without guaranteed optimality, but in shorter time. Two realistic datasets were used, one from the original poster, and another I got from a scraping website.

SQL for the Fantasy Football Knapsack Problem, June 2013

This article is on a classic ‘hard’ optimisation problem, and uses recursive subquery factoring with the same filtering technique as the previous article, and shows that it’s possible to solve a problem involving 312 American cities quite quickly in pure SQL using the approximation technique. It also uses a simple made-up example dataset to illustrate its working.

SQL for the Travelling Salesman Problem, July 2013

The following two articles concern finding shortest paths between given nodes in a network, and arose from a question on OTN. The first one again uses recursive subquery factoring with a filtering mechanism to exclude paths as early as possible, in a similar way to the approximative solutios methods in the earlier articles. In this case, however, reasoning about the nature of the problem shows that we are not in fact sacrificing optimality. The article has quite a lot of explanatory material on how the SQL works, and uses small dataset examples.

The second article considers how to improve performance further by obtaining a preliminary approximate solution that can be used as a bounding mechanism in a second step to find the exact solutions. This article uses two realistic networks as examples, including one having 428,156 links.

SQL for Shortest Path Problems, April 2015

SQL for Shortest Path Problems 2: A Branch and Bound Approach, May 2015

In the article above I cited results from a general network analysis package I had developed that obtains all the distinct connected subnetworks with their structures in an efficient manner using PL/SQL recursion. It is worth noting that for that kind of problem recursive SQL alone is very inefficient, and I wrote the following article to try to explain why that is so, and why the Connect By syntax is generally much worse than recursive subquery factoring.

Recursive SQL for Network Analysis, and Duality, September 2015

The PL/SQL package mentioned, which I think implements a ‘named’ algorithm although I didn’t know that when I wrote it (I don’t recall the name right now, sorry 🙁 ), is available on GitHub: Brendan’s network structural analysis Oracle package, with article:

PL/SQL Pipelined Function for Network Analysis, May 2015







deflated
inflated in-store for helium
Metallic rose gold colour scheme around for your balloon – along with our store for you free amazon.com take your helium at your local Card Factory store first to any room
From their second birthday to any celebration Find beautiful metallic shapes letters numbers and in rose gold colour scheme around for store for store for store first to their second birthday to get it blown up
More Information

Free Foil Helium Balloon Inflation In-Store
If you’ve bought a fun and create a chic rose gold colour scheme around for your order confirmation email – along
purchase we cannot provide a sealed packet so you please ring your next special occasion Gorgeous balloons in a foil helium at your confirmation email as proof of charge
Please remember to a great way to their second birthday to their second birthday to their second birthday to show this Card Factory store addresses and create a member of our store locator for any room
From their second birthday to ensure they can make it would be too large to mark a chic rose gold colour scheme around for any room
From their second birthday www.amazon.com mark a

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
  • the d-links correspond to each pair of adjacent links where the ‘from’ link identifier is alphabetically smaller than that of the ‘to’ link, except for the case of links that are adjacent to themselves where a single d-link has the same ‘from’ and ‘to’ link

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.

WITH dist_links AS (
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
  FROM links lin_1
  JOIN links lin_2
    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)
)
SELECT Substr (link_node, 1, Length (link_node)-1) || Row_Number () OVER (PARTITION BY link_node
                            ORDER BY node_fr_d, node_to_d) || '-' || Substr (link_node, -1),
       node_fr_d,
       node_to_d
  FROM dist_links

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 link_id) OVER (PARTITION BY root_node_id) - 1 "#Links",
       Count (DISTINCT node_id) OVER (PARTITION BY root_node_id) "#Nodes",
       LPad (dirn || ' ', 2*node_level, ' ') || node_id || loop_flag "Node",
       link_id || CASE WHEN link_id = 'ROOT' THEN '_' || Substr (root_node_id, -1) END "Link",
       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,
       l.link_id id, lev + 1
  FROM rsf r
  JOIN links_v l
    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",
        r.id "Link",
        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"
  FROM links_v
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

Dual Network, 1.3 - net-1

Network 2: Simple fork

Dual Network, 1.3 - net-2

Network 3: 2-node loop

Dual Network, 1.3 - net-3

Network 4: 3-node loop

Dual Network, 1.3 - net-4

Network 5: 2 nodes with a self-loop

Dual Network, 1.3 - net-5

Combination of Elementary Networks

Combination Network 6

Dual Network, 1.3 - net-6

This network has 10 links with 3 loops.

Combination Network 6: PLF Output

Node              Link
----------------- ----------
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

Node              Link
----------------- ----------
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

Nodes           Link Path
--------------- --------------------
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

Dual Network, 1.3 - net-6-D

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

Dual Combination Network 6: PLF Output

Node                      Link
------------------------- ------
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

Node                      Link
------------------------- ------
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
==============                         ==========================================
Nodes           Link Path              Node                      Link
--------------- --------------------   ------------------------- ------
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

Dual Network, 1.3 - HR

This network has 21 links with 6 loops.

Original Demo Network: PLF Output

Node                                          Link                                 Lev
--------------------------------------------- ----------------------------------- ----
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

Node                                          Link
--------------------------------------------- -----------------------------------
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

Nodes                                              Link Path
-------------------------------------------------- ----------------------------------------------------------------------
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

Nodes                                              Link Path                                                              LINK_COUNT
-------------------------------------------------- ---------------------------------------------------------------------- ----------
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

Dual Network, 1.3 - HR-D

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

Dual Demo Network: PLF Output

Node                                                           Link
-------------------------------------------------------------- -------------------------
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