Want to protect your cyber security and still get fast solutions? Ask a secure question today.Go Premium


Need help with a recursive type of query

Posted on 2006-11-25
Medium Priority
Last Modified: 2012-08-13

I have a table TEST with 5 numeric columns namely, SRC, F, L, R, U

Each row in this table represents a direct link between SRC and the other columns (F, L, R, U). A value of 0 means no link exists. The values of F, L, R, U may (or may not) be the SRC in subsequent rows. In case F/L/R/U does not appear as a value of SRC, it indicates last node.

Here are some sample values from this table (I have padded them with leading 0 for the sake of alignment):

SRC  F     L     R    U
---   ---   ---   ---   ---
 01   04   00   02   20
 02   00   00   00   03
 03   04   00   00   00
 04   05   00   00   00
 05   08   00   06   00
 08   00   00   09   00
 09   00   10   00   00
 10   00   00   11   00
 11   00   00   00   12
 12   00   00   13   00
 13   00   00   14   00

Now the way one would read this table is...

SRC 1 is connected to F:4, R:2 and U:20
SRC 2 is connected to U:3
SRC 3 is connected to F:4

...and so on.

Now the query I need is for the following:

Given a value for SRC and any other value that would be present in either F, L, R or U, I need to find the possible paths.

For example, if SRC = 1 and we need to reach to 11 then we would have the following traversal paths:

1 - 4 - 5 - 8 - 9 - 10 - 11
1 - 2 - 3 - 4 - 5 - 8 - 9 - 10 - 11

I don't think it would be possible with a single query and hence we may use a table to hold the results, and this table would look something like:

For path 1 - 4 - 5 - 8 - 9 - 10 - 11

----- -------- -------
  1       1        4
  1       1        5
  1       1        8
  1       1        9
  1       1        10
  1       1        11

For path 1 - 2 - 3 - 4 - 5 - 8 - 9 - 10 - 11

----- -------- -------
  1       2        2
  1       2        3
  1       2        4
  1       2        5
  1       2        8
  1       2        9
  1       2        10
  1       2        11

Question by:abhitlya
LVL 22

Expert Comment

by:earth man2
ID: 18014098
Try the hier patch.

This enables an Oracle like connect by prior hierarchical query syntax

LVL 19

Accepted Solution

grant300 earned 1000 total points
ID: 18015325
This turns out to be a member of an enormously tough class of problems because the size grows exponentially with the allowed path length.

In order to find all the paths between any two nodes, you have to build ALL possible paths until you are sure they do not arrive at the destination.  You also have to find a way to avlid loops.

You examples above seems to imply the assumption that the paths can be limited to nodes in sorted order.  If that is the case, you have caught a break.  That constraint would imply a flat graph with relationships that only need be navigated one direction.  earthman2 is correct that "connect by prior" extension can be useful, however, be careful for it is a highly non-relational language element.  The order of the results is part of the data which means that it cannot behave like a table.  (For reference on this point, you can look up Codd and Date's 12 rules of relational databases.  "Order is irrelevant")

If I had to solve this, I would approach it the following way:
1)  Build a normalized table containing the simplifed relationships, e.g. CREATE TABLE Relate AS (SRC number, DEST number) and populate it with the valid SRC/DEST pairs.  You can do this with a four select statements using a UNION ALL between them.
2) Make sure you have a unique index on the table with both columns (SRC, DEST).
3) Use the connect-by-prior and start-with syntax as well as the SYS_CONNECT_BY_PATH function in a SELECT statement

  FROM NormalizeTable
     AND DEST <= 11

I am not sure how complete the implementation of this is for PostgreSQL beyond the CONNECT BY PRIOR and the START WITH clauses.  Oracle supports the CONNECT_BY_ISLEAF function that returns a value of one if you are at a leaf node.  It also supports a SYS_CONNECT_BY_PATH function that can return the path in the form of "1-4-5-8-9-10-11" which, I suspect, is the only way you can get the specific paths you want back as paths.

If you choose not to (or the patch does not implement it) the hierarchies are returned in top-to-bottom, left-to-right order.  That means you will get the root node, then the direct children as siblings, then the grand children, etc.

Another approach that might prune the problem down in size and run faster is to work the paths from the destination to the source.  To do this, you need to:
 - reverse the order of the columns in the index on the normalized table
 - reverse the terms of the CONNECT BY PRIOR clause to be "CONNECT BY PRIOR SRC = DEST"
 - change the condition ORed with the CONNECT_BY_ISLEAF = 0 to be "OR SRC = 1"

Of course, through all of this, you can drop variables in for constants 1 and 11 for SRC and DEST.

Get the extension and see how much functionality it supports.

Best of luck,


Featured Post

Get your problem seen by more experts

Be seen. Boost your question’s priority for more expert views and faster solutions

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Best database to use for Maps is PostgreSQL. This is an open source database. Comes as a package with most Linux OS. For more info visit the following site: http://www.postgresql.org/ (http://www.postgresql.org/) This requires some add-o…
By, Vadim Tkachenko. In this article we’ll look at ClickHouse on its one year anniversary.
Steps to create a PostgreSQL RDS instance in the Amazon cloud. We will cover some of the default settings and show how to connect to the instance once it is up and running.
Whether it be Exchange Server Crash Issues, Dirty Shutdown Errors or Failed to mount error, Stellar Phoenix Mailbox Exchange Recovery has always got your back. With the help of its easy to understand user interface and 3 simple steps recovery proced…
Suggested Courses

581 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question