Design

Flexibility was the primary focus in the design of account grouping functionality, but to keep the interface sane, I've implemented some rules:

  • Account groups cannot be a parent of a group that it is a descendent of - this would cause a loop.
  • Inversely, groups cannot be a child of a group that they are an anscestor of - this would also cause a loop.
  • Account groups can have multiple children and multiple parents.

While this "hierarchy" of parent child relationships might conjure up the image of a family tree, but that model is inappropriate, as the nodes in this data set can have multiple parents or "trunks" in the true nature of a tree. Sort of like if a trees branches grew back into each other.

Extended Nested Sets

This model is more of a mesh, and to help design the database model, I leaned on this great post from an OpenACS developer Sebastian Skracic:

http://openacs.org/forums/message-view?message_id=16801

I always read through material related to OpenACS - while a bit dated (above post was from 2000!), the concepts are strong.

Their case involved privileges, not groups, but the concepts are similar. From the post:

Gotcha! Nested set model (as described above) won't work in this case. Nested sets represent flattened hierarchy tree where every item is supposed to appear exactly once. Back to the privilege hierarchy: each privilege can have arbitrary number of child privileges, but some privileges can be child of (i.e. implied by) more than one parent privileges.

Exactly like our situation. What we need here is the ability to quickly find all the ancestors of a node to prevent any of them being selected as descendants, and visa versa. Let's check back to that post and examine their solution, aptly named the "slightly extended nested set data model":

Additional table to store sets themselves:

create table acs_privilege_hierarchy_index (
        privilege       varchar(100) not null
                        constraint acs_priv_hier_ndx_priv_fk
                        references acs_privileges (privilege),
        child_privilege varchar(100) not null
                        constraint acs_priv_hier_ndx_child_priv_fk
                        references acs_privileges (privilege),
        l_node          integer not null,
        r_node          integer not null
);

Reading on, I unfortunately find that this solution uses stored procedures, which I have no experience with, and it falls outside of my time frame for completing this today.

With a little XML / XSLT and Nexista magic, I was able to make this happen without using stored procedures. XSLT has the advantage of being a functional language, so it is able to "see" the entire tree at once, without having to discover it, whereas a procedural language would discover the tree (as is stored procedures). For more on this topic see:

http://www.ibm.com/developerworks/xml/library/x-tiploop.html

This has some drawbacks of course, so I'll try to add some constraints into the data model to prevent infinite recursion at the rendering stage.

List of Unique Accounts in a Group

This posed a '''unique''' challenge, no pun intended. When viewing a group, it would be helpful to know what sub-group(s) is contains, as well as what accounts are in the group. While it would be no problem to show the exhaustive list of account - child relationships, it is only necessary to know if an account is contained within the group.

With the help of the awesome XLST information at http://www.dpawson.co.uk/index.html, I was used an XML document of all the account groups, then created a unique list of their primary keys and then simply tested whether or not they were a descendant of a selected group. It actually worked really well, and the solution is quite novel (in my humble opinion) because it uses XSL to create an XML document, which is then grabbed via curl, and manipulated with XSL again. Can you say RESTful? :-)

The list of unique account groups that are sub-groups of a specific account is useful as it can be used to prevent cyclical relationships.

This resulted in a list of unique account groups, but what if an account is associated as the child of two of those accounts? That still results in an account appearing more than once, so I'll have to review the XSL transformation at the account level. Alternatively, I could specify that each account can only have one parent group. Since groups can have multiple parents, accounts could indirectly have multiple parent groups. This might be a good solution for the time being.

Other Uses

I'm going to try and further clarify and abstract this strategy for use with other category / group / nested set solutions. Other solutions include "nested sets" and "adjacency list" models.

I did find a couple of useful articles while I was researching this matter, including:

http://dev.mysql.com/tech-resources/articles/hierarchical-data.html http://www.edutech.ch/contribution/nstrees/index.php http://sqllessons.com/categories.html