Recursive SQL for a menu system.

Question

I have a table for a menu system with the following structure, and some data.

ID, Text, ParentID, DestinationID
1, Applications, (null), (null)
2, Games, (null), (null)
3, Office, 1, (null)
4, Text Editing, 1, (null)
5, Media, (null), (null)
6, Word, 3, 1
7, Excel, 3, 2
8, Crysis, 2, 3

What I need is a query to which I can pass the menu ID, and it will return a list of items that have that ID as a child. BUT, I need it to only return children that have a valid path to a destination. So in the example above, the user will be presented initially with (Applications, Games), when he selects Applicaions, he is presented with (Office). Text Editing and Media should be omitted, because there are no valid destinations beneath them.

The trickiest thing about this, is that there is no predetermined depth to any given menu.

EDIT:Today, the problem came up for MS SQL 2008, but in the past 2 weeks I've needed similar solutions for SQLite and SQL CE. The ideal solution should not be tied to any specific SQL engine.

Answer 1

In Oracle:

SELECT m.*, level
FROM my_table m
START WITH
  Id = :startID
CONNECT BY
  ParentID = PRIOR Id
  AND DestinationID IS NOT NULL

There is no way to do it in ANSI SQL with a single query. You may create an additional column AccessPath for you table:

ID, Text, ParentID, DestinationID AccessPath
1, Applications, (null), (null), "1"
2, Games, (null), (null), "2"
3, Office, 1, (null), "1.3"
4, Text Editing, 1, (null), "1.4"
5, Media, (null), (null), "5"
6, Word, 3, 1, "1.3.6"
7, Excel, 3, 2, "1.3.7"
8, Crysis, 2, 3, "1.2.8"

, and query:

SELECT mp.Id, mp.Text
FROM my_table mp, my_table mc
WHERE mp.parentID = @startingParent
 AND mc.Id <> mp.Id
 AND SUBSTR(mc.AccessPath, LENGTH(mp.AccessPath)) = mp.AccessPath
GROUP BY
 mp.Id, mp.Text

It's a bad idea to start with NULL, as the index on ParentID cannot be used in this case. For a start, use a fake parentID of 0 instead of NULL.

Answer 2

SQL server only, but it sounds like a job for Common Table Expressions.

Answer 3

If this is a problem that interests you (or plagues you), you may want to check out: Joe Celko's Trees and Hierarchies in SQL for Smarties.

Answer 4

SQL is not very good at walking arbitrary depth hierarchies.

If there's less than 1000 of these records, I would grab them all to the application and construct the graph there.

If there's more than 1000 of these records, I'd group them into raw subtrees of approx 1000 (by adding a SubtreeID foreign key) and fetch each subtree... then construct the graph of the subtree in the application.

Answer 5

The first thing I'd do is strip out the destination column - it's meaningless in terms of hierarchy (it actually appears to be a kind of second primary key to signal a live child row the way you've represented it)

this would give

ID, Item, parentID
1, Applications, (null)
2, Games, (null)
3, Office, 1
4, Text Editing, 1
5, Media, (null)
6, Word, 3
7, Excel, 3
8, Crysis, 2

e.g...

word > office > applications and...

excel > office > applications

...should presumably be on the same menu item (parent id 3)

I'm not sure how you're selecting the menu but I'll work on the principle that there's an initial menu button set with (null) as it's parameter and each subsequent click holds the next parameter in sequence dynamically (which seems to match your comments)

e.g.

click top level menu :- value is (null)

click applications :- value is 1

click Office :- value is 3

etc.

Assuming the destinationID is doing nothing apart from showing an active child link (allowing you to remove it), the code would then be as follows:

with items (nodeID, PID, list) as
  (select id, ParentID, item
    from menu
    where id = 9
    union all
  select id, ParentID, item
    from menu
    inner join items on nodeID = menu.ParentID
  )
select *
from items 
where (pid = 9)
and nodeID in (select parentid from menu)

This works in MSSQL 2005+

If you need the destination id for some other reason then you can amend the code as follows (if you need to return the lowest level where a node id hasn't been set as a parent id, for instance):

with items (nodeID, PID, list, dest) as
  (select id, ParentID, item, destinationID
    from menu
    where id = 9
    union all
  select id, ParentID, item, destinationID
    from menu
    inner join items on nodeID = menu.ParentID
)
select *
from items 
where (pid = 9)
and (nodeID in (select parentid from menu) 
  or dest is not null)

Answer 6

As others have pointed out, there's no way in standard ANSI SQL to do what you want. For something like this, I once implemented on SQL 2000 a system for tracking components of products an ex employer made - each "product" could be atomic component like, say, screw A500. This component could be used in "composite" components: some A500 screws plus 6 B120 wood boards conformed a C90 "stylish tool box". That box, plus more screws and a motor "M500" could conform a carpetry tool.

I designed a table "Product" like this:

ID, PartName, Description
1, A500, "Screw A500"
2, B120, "Wood panel B120"
3, C90, "Stylish tool box C90"
4, M500, "Wood cutter M500"

And a "ProductComponent" table as follows:

Hierarchy, ComponentID, Amount
0301, 1, 24
0302, 2, 6
0401, 1, 3
0402, 3, 1
0403, 4, 1
040201, 1, 24
040202, 2, 6

The trick is: field hierarchy is a VARCHAR with first 2 chars representing each product's ID, each next pair of chars identify a node in the tree. So we see that product 3 depends on 2 other products. Product 4 depends on 2 others, also, one of which depends on its part on two others.

There's lots of redundancy in this model, but allows to easily calculate how many screws you need for a particular product, determine fastly which parts need wood panels or get the list of all components a product ultimately depends on (including indirect dependencies), etc. And scanning the tree below a certain level is a simple LIKE query!

By using 2 chars in a hexadecimal representation I limited a product to depend directly on maximum 256 other prods (which on turn can depend on something else). You could change that to use base 36 (the 26 letters plus 10 numbers) or base-64 if you need more than that.

Besides, this table model works very well on Access and mySQL, too. What you can not have is circular dependencies in any way.