Efficient parent/child/ancestral relationship DB algorithms

From: <nfwatson_at_my-deja.com>
Date: Fri, 25 Jun 1999 06:49:16 GMT
Message-ID: <7kv8pa$s7h$1@nnrp1.deja.com>

All,

I am interested in developing an efficient distributed system with an RDBMS as the primary data storage mechanism. There are a number of situations where I will confront the following scenario (note that I'm not an experienced RDMBS programmer). I will try to be brief.

• There are a number of items (roles) arranged in a parent/child hierarchy, of arbitrary depth, the only rule being that no node may be an ancestor of itself -- this generally will form a "lattice", and could be represented like this:

    ParentRoleID        ChildRoleID
       1                   3
       1                   2
       3                   5
       2                   7
       2                   5
       7                   8
       9                   8

• There may be tables of the following form:

   SplatTable

     SplatID AccessRoleID

     "item 1"               3
     "item 2"               7
     "item 3"               9
      etc. etc.

• I will want at a certain point to, for example, find, given a particular role X, the SplatID's of all items accessible to X, or any of the ancestors of X.
• The role hierarchy (parent/child relationship) may change at any point during execution of the distributed system, though this will be rare.
• If the depth of the parent/child hierarchy were fixed, I could contrive a SQL query joining the parent/child table to itself (right terminology?) zero, one, two, three, ..., [depth - 1] times along with other tables to produce queries with desired results -- but I suppose this wouldn't be very efficient. But, the depth of the table is arbitrary, so even this option isn't available.
• The best solution I can think of is to have a RoleID-to-AncestorRoleID table computed at distributed app startup, and each time a parent/child relationship is created or destroyed (with appropriate locking to prevent use of table during recompute). I'm supposing my problem is quite common. What do RDMBS developers typically do in this situation? The table I propose would look something like (to avoid extra clauses, in this table only we'll consider a role to be an ancestor of itself):

   AncestorTable

     RoleID       AncestorRoleID
       1                1
       3                3
       3                1
       2                2
       2                1
       5                5
       5                3
       5                1
       5                2
       7                7
       7                2
       7                1
       8                8
       8                7
       8                2
       8                1
       8                9
       9                9

• To fulfill the above data requirements, the SQL statement would look something like:

    select SplatID from AncestorTable, SplatTable     where AncestorTable.RoleID = X and

          SplatTable.AccessRoleID =
              AncestorTable.AncestorRoleID

MY QUESTIONS:

• Is this standard practice?
• What are implications for efficiency? Role hierarchy doesn't change often, but there might be some delay while table is recomputed. Once table is reconstructed, though, queries involving access to roles or role ancestors should be very fast.
• Is there a way of marking a table in most commercial RDBMS (Oracle et. al.) as transient, throwaway, don't-be-careful-with-crash-recovery- and-integrity-issues?

Thank you for your time. I am an
experienced software developer, but
haven't done much with RDBMS programming, and look forward to more.

Nathan Watson
nwatson_at_actuate.com

Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't. Received on Fri Jun 25 1999 - 01:49:16 CDT