Solved

Need help with a recursive type of query

Posted on 2006-11-25
2
259 Views
Last Modified: 2012-08-13
Hello...

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

SRC  PATH  DEST
----- -------- -------
  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

SRC  PATH  DEST
----- -------- -------
  1       2        2
  1       2        3
  1       2        4
  1       2        5
  1       2        8
  1       2        9
  1       2        10
  1       2        11

Thanks,
Abhijit
0
Comment
Question by:abhitlya
2 Comments
 
LVL 22

Expert Comment

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

This enables an Oracle like connect by prior hierarchical query syntax

http://gppl.moonbone.ru/hier-Pg8.1.2-0.5.5.diff.gz
0
 
LVL 19

Accepted Solution

by:
grant300 earned 250 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

SELECT 1, SYS_CONNECT_BY_PATH (DEST, '-')
  FROM NormalizeTable
 WHERE START WITH SRC = 1
     AND CONNECT BY PRIOR DEST = SRC
     AND (CONNECT_BY_ISLEAF = 0 OR DEST = 11)
     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,
Bill

0

Featured Post

Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

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…
Many developers have database experience, but are new to PostgreSQL. It has some truly inspiring capabilities. I have several years' experience with Microsoft's SQL Server. When I began working with MySQL, I wanted a quick-reference to MySQL (htt…
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.
This video demonstrates how to create an example email signature rule for a department in a company using CodeTwo Exchange Rules. The signature will be inserted beneath users' latest emails in conversations and will be displayed in users' Sent Items…

932 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

Need Help in Real-Time?

Connect with top rated Experts

11 Experts available now in Live!

Get 1:1 Help Now