Efficient persistable recursive data structure

Question

The usual approach with recursive data structures is to have a parent pointer in each object. My problem is that the usual implementation can't answer the questions below in a single operation; instead I need to query my database several times. Is there a solution which gives me the result in a single query?

• Get a list of all children of a node

• Find all parent nodes (== shortest path to the root node)

Note: I'm in the planning stage, so I'm not yet limited to a certain database.

Answer 1

At least Oracle can do hierarchical queries. Consider example of db users' roles:

CREATE TABLE my_dba_role_privs(
   grantee        VARCHAR2(30),
   granted_role   VARCHAR2(30)
);   

-- assigning roles to roles
INSERT INTO my_dba_role_privs( grantee, granted_role ) VALUES('CLIENT', 'SELECT_ORDERS');
INSERT INTO my_dba_role_privs( grantee, granted_role ) VALUES('COMMERCIAL_DEP', 'CREATE_ORDERS');
INSERT INTO my_dba_role_privs( grantee, granted_role ) VALUES('COMMERCIAL_DEP', 'CLIENT');

-- assigning roles to users
INSERT INTO my_dba_role_privs( grantee, granted_role ) VALUES('CL_MATT', 'CLIENT');
INSERT INTO my_dba_role_privs( grantee, granted_role ) VALUES('CL_JOHN', 'CLIENT');
INSERT INTO my_dba_role_privs( grantee, granted_role ) VALUES('CM_MARY', 'COMMERCIAL_DEP');

Now select all roles of user 'CM_MARY':

SELECT DISTINCT GRANTED_ROLE role_name
  FROM my_dba_role_privs
 START WITH GRANTEE = 'CM_MARY'
       CONNECT BY GRANTEE = PRIOR GRANTED_ROLE;   

Result:
COMMERCIAL_DEP
CREATE_ORDERS
CLIENT
SELECT_ORDERS

Select all roles and users, who owns role 'CLIENT'

SELECT GRANTEE role_name
  FROM my_dba_role_privs
 START WITH GRANTED_ROLE = 'CLIENT'
       CONNECT BY GRANTED_ROLE = PRIOR GRANTEE;   

Result:
CL_JOHN
CL_MATT
COMMERCIAL_DEP
CM_MARY

UPDATE:
Since you mentioned, tree will be pretty static, it may be interesting to try Joe Celko's Trees (aprox 180 lines to read). It doesn't require self joins at all! So, I expect it to perform times faster then CONNECT BY. Though I've just read about it just 30 min ago, and don't know how good it is in real world

Update2: "Nested Set Models" with MySQL: Managing Hierarchical Data in MySQL This is the same as Joe Celko's Trees above but with more examples and explanation.

Answer 2

If "all children" means only direct children, simply put a list of children, as well as a pointer to the parent on each node. Note that this will make moving a node to another parent more expensive, as all (grand)-children must be updated as well.

If "all children" really means all children, one option would be to build a string of the IDs of each parent, and add it as an indexed column. For example, if you have A, with the child B, with the grandchild C, you'd have in C a column with value A/B/C. Now to find all children of A you can simply do a LIKE query on "A/%". Again, though, this is expensive when you need to change the parent of a node with children.

If you need to be able to change parents quickly, you're going to need to maintain parent information as a linked list, I think. You could, however, use a stored procedure to perform this query operation with only one database round trip.