Retrieve Hierarchical Data, (How can I...?)

[StevieK]

I want to make up a (dynamic) HTML page of hyperlinks to look something like this:

|--

http://www.ask.com

|--

http://www.google.com

| |--

http://www.google.com/search?q=cheese

| | |--

http://www.google.com/search?q=cheese+brie

| | |--

http://www.google.com/search?q=cheese+cheddar

| |--

http://www.google.com/search?q=fruit

| |--

http://www.google.com/search?q=fruit+apple

[Figure 1. Daft Example]

The idea is that the links on each branch are somehow associated within that website, and the user will be able to add a link at any level in the tree. There are two database tables to handle this:

-------------- --------------------------
| weblink | | weblinksWeblinks |
-------------- --------------------------
|weblinkID | |childWeblinkID |
|name | |parentWeblinkID |
|URL | |... |
|... | ---------------------------
--------------

The weblink table holds all the hyperlinks, and the weblinksWeblinks table associates one hyperlink with one child hyperlink - if there is one. (n.b. Each hyperlink can have many children, but no more than one parent).

So, the problem is... How can I retrieve all of the hyperlink data in the correct order in one go? It has to include the top-level links (that have no parents in weblinksWeblinks), the bottom-level links (that have no children) and all the others.

I think that the standard approach to this kind of thing is usually to expand each branch only as the user clicks on it (as in a message forum), but to me that smells just as bad as firing a separate

SELECT

statement for each hyperlink you come across: effectively hitting the database 8 times for the daft example data that I've shown above (Once for the top-level hyperlinks, then once for every hyperlink you retrieve after that).

In case you're still not sure what I'm on (about)... If weblink and webLinksWeblinks looked like this...


weblink table
---------------------------------------------------------------------
| weblinkID | name | URL ...
----------------------------------------------------------------------
| 1 | Ask Jeeves |

http://...

| 2 | Google |
| 3 | Google Cheese Search |
| 4 | Google Fruit Search |
| 5 | Google Cheddar Cheese Search|
| 6 | Google Brie Cheese Search |
| 7 | Google Apple Fruit Search |
----------------------------------------------------------------------


weblinksWeblinks table
-----------------------------------------------
| parentWeblinkID | childWeblinkID | ...
-----------------------------------------------
| 2 | 3
| 2 | 4
| 3 | 5
| 3 | 6
| 4 | 7
-----------------------------------------------

... Then the dataset I really want back is this:

------------------------------------------------------------------------------------
| parentWeblinkID | weblinkID | name | URL ...
------------------------------------------------------------------------------------
| NULL | 1 | Ask Jeeves |

http://...

| NULL | 2 | Google |
| 2 | 3 | Google Cheese Search |
| 3 | 5 | Google Cheddar Cheese Search|
| 3 | 6 | Google Brie Cheese Search |
| 2 | 4 | Google Fruit Search |
| 4 | 7 | Google Apple Fruit Search |
------------------------------------------------------------------------------------


If anyone out there knows how to do this, then I'll either bow to your mastery of table joins, or laugh at my own pitiful understanding of them.

I know another hacky way of doing this would be to sort by the URL strings - but that doesn't guarantee that the hierarchy will be correct (e.g. the user would have been quite entitled to submit either

http://www.google.com/search?q=apple+fruit

or

http://www.google.com/search?q=fruit+apple

without it affecting the hierarchy).

Thanks in advance,
Stephen

 

[r937]

since it's a strict hierarchy (at most one parent per entry), you don't need a separate table, just move the parent foreign key into the main table

other than that, i have nothing to offer you, sorry

there is no satisfactory way to recursively list a subtree, except in oracle, which has proprietary syntax for this purpose

if you can limit the depth of the tree, e.g. no more than 5 levels deep, then you can use a 5-way reflexive left outer join quite satisfatorily

i've seen developers fall into two camps on this issue -- one side is quite happy to limit the number of levels, quickly builds a working system, and moves on, while the other side says, no, let's make it work for any number of levels, and they end up writing really sophisticated stored procedures, taking much longer to deliver a finished product, but they also know they'll never have to come back and make it work for that 6th level...

both sides are right, if you ask me

there are links all over the web for both approaches, holler if you can't find one on your own

rudy

 

[petersJazz]

On the other hand, programming a solution to this type of problem is rather easy using recursive programming. Heres an example in Java:

Table
-----
xID       -- primary key
xTopID    -- points to top level xID
xParentID -- points to father xID
wSubject  -- subject
wMessage  -- text

public DbDiscuss[] getWholeThread(String xid) {
  int cnt = DbDiscuss.getRowCount("where xTopID = " + xid + " and xID != " + xid);
  //System.out.println("Number of child : " + cnt);
  DbDiscuss ret[] = new DbDiscuss[cnt];
  wholeThreadLoaded = 0;
  if (cnt > 0) {
     getChild(xid, 0, ret);
  }
  return ret;
}
    
private void getChild(String xID, int level, DbDiscuss ret[]) {
  DbDiscuss d[] = DbDiscuss.getRows("where xParentID = " + xID + " and xID != " + xID);
  if (d != null) {
    for (int i=0; i<d.length; i++) {
      ret[wholeThreadLoaded] = d[i];
      ret[wholeThreadLoaded].setLevel(level);
      wholeThreadLoaded++;
      getChild(d[i].getXid(), level + 1, ret);
    }
  }
}

Class DbDiscuss is a database tool where one object is one row in table.

 

[StevieK]

Thanks r937. Good call: I'm wasting a table there.

Unfortunately, I'm not using Oracle, or SQL Server (in which I could probably write a procedure to build up this result set). I'm using PHP/MySQL.

Thanks petersJazz: I know how easy tree programming is... But I'm stuck with a PHP/MySQL system and wanted to do this whole thing in the database, on the basis that I thought it would be possible. What I could do, is retrieve all the rows in own go (I can do that easily, and order it by tree branch in the database), and then I could construct the tree in PHP or (even better) JavaScript - letting the client do all the work.

But what I'll do for the moment, is just have two branch levels. That's less hassle, although I don't exactly know how to do that

SELECT

either. I'll try hunting for the examples that r937 was on about, and post an update as to how I got on.

The new table will look something like:

-------------------
| hyperlink       |
-------------------
|

hyperlinkID

         |
|parentHyperlinkID|
|name             |
|URL              |
|...              |
-------------------

 

[petersJazz]

What you should do is a "self join", try something like this (do it first in a query tool to find out how it works):

select a.hyperlinkID,
b.hyperlinkID b
from hyperlink a,
hyperlink b
where a.hyperlinkID = b.parentHyperlinkID
and a.parentHyperlinkID is null;

If you want three levels you do:

select a.hyperlinkID,
b.hyperlinkID b,
c.hyperlinkID c
from hyperlink a,
hyperlink b,
hyperlink c
where a.hyperlinkID = b.parantHyperlinkID
and b.hyperlinkID = c.parentHyperlinkID
and a.parentHyperlinkID is null;

 

[StevieK]

Thanks petersJazz: That is the way to select the branch levels... However, I wanted to make all this happen in a single SQL statement, because I can't store procedures on the MySQL database and wanted all of the levels of the tree together, so I could sort them. So here's how I did it:

Unfortunately, the version of MySQL that I have to use does not even implement

UNION

, so I had to create a Temp Table, then add each level of the tree, one at a time, into this table - along with the parentID used for each of the branches above it. I then sorted the data by branch name and branch ID for each level of the tree that I was using. Here's the SQL:

Create a temp table to store the entire tree of links:

CREATE TEMPORARY TABLE weblinkTree (
 branch1ID       INT       NOT NULL,
 branch2ID       INT       NULL,
 branch3ID       INT       NULL,
 branch1Name     TINYBLOB  NOT NULL,
 branch2Name     TINYBLOB  NULL,
 branch3Name     TINYBLOB  NULL,
 weblinkID       INT       NOT NULL PRIMARY KEY,
 parentWeblinkID INT       NULL,
 name            TINYBLOB  NOT NULL,
 comment         TINYBLOB  NOT NULL,
 URL             TINYBLOB  NOT NULL,
 ...
)

Next, add each of the levels of the tree to it. Add the top-level links:

INSERT INTO weblinkTree(
       branch1ID,
       branch2ID,
       branch3ID,
       branch1Name,
       branch2Name,
       branch3Name,
       weblinkID,
       parentWeblinkID,
       name,
       comment,
       URL,
       ...
)
SELECT a.weblinkID       branch1ID,
       NULL              branch2ID,
       NULL              branch3ID,
       a.name            branch1Name,
       NULL              branch2Name,
       NULL              branch3Name,
       a.weblinkID       weblinkID,
       a.parentWeblinkID parentWeblinkID,
       a.name            name,
       a.comment         comment,
       a.URL             URL,
       ...
FROM   weblink a
WHERE  a.parentWeblinkID IS NULL

... and the 2nd-level links:

INSERT INTO weblinkTree (
       branch1ID,
       branch2ID,
       branch3ID,
       branch1Name,
       branch2Name,
       branch3Name,
       weblinkID,
       parentWeblinkID,
       name,
       comment,
       URL,
       ...
)
SELECT a.parentWeblinkID branch1ID,
       a.weblinkID       branch2ID,
       NULL              branch3ID,
       b.name            branch1Name,
       a.name            branch2Name,
       NULL              branch3Name,
       a.weblinkID       weblinkID,
       a.parentWeblinkID parentWeblinkID,
       a.name            name,
       a.comment         comment,
       a.URL             URL,
       ...
FROM   weblink a,
       weblink b
WHERE  a.parentWeblinkID = b.weblinkID
AND    b.parentWeblinkID IS NULL

.. and so on. Then sort the entire tree by name and then branch, for each level of the tree:

SELECT branch1ID,
       branch2ID,
       branch3ID,
       branch1Name,
       branch2Name,
       branch3Name,
       weblinkID,
       parentWeblinkID,
       name,
       comment,
       URL,
       ...
FROM weblinkTree
ORDER BY branch1Name, branch1ID,
         branch2Name, branch2ID,
         branch3Name, branch3ID

... And voila! Shame that this takes multiple database hits, and uses a temp table, but I couldn't find another way of being able to sort by the branches.

Thanks for the help, and I hope this helps someone else,
Stephen