February 9, 2010
The problem is thus: there are various users, each in a vertical hierarchy. For example, kinds of users or roles might be owner, manager, supervisor, and staff. Each user, except owner, has a parent. And each user, except staff, has a child. This way the hierarchy would be owner is parent of manager; manager is parent of supervisor; and supervisor is parent of staff. One user can be assigned one role only. So user John could be one of the roles mentioned. If we want to find the children of John, how can we do so?
First we create an example table in our database.
create table users (user varchar(50) unique, parent varchar(50));
Now let’s put some data in there:
insert into users values ('john', 'amy'), ('amy', null), ('adam', 'amy'), ('jane', 'john'), ('jennifer', 'john'), ('jethro', 'jane');
By looking at the data, we can see that John’s children are Jane, Jennifer, and Jethro. Why Jethro? Because Jane is a child of John, and Jethro is a child of Jane. So in effect, we are looking for all children of John, be they directly his children or the children of his children, and so on. Please note that we assume there are no many-to-many relationships here. So each user can only have one direct parent, while each parent may have many children (many-to-one).
The code in Python is implemented using SQLalchemy to connect to database. But the idea should remain the same no matter what technology you use. I use a very naive recursive implementation here, which should get you started.
def user_children(user=None, kid_list= None, session=None): query = session.query(users).filter_by(parent=user) children_list =  for result in query: children_list.append(result.username) kid_list.append(result.username) for name in children_list: user_children(name, kid_list, session) return kid_list def main(): kid_list =  # We assume session stuff for SQLalchemy has already been taken care of # prior to following statement session = mydb.mysession() all_children = user_children('john', kid_list, session) session.close() return all_children if __name__ == "__main__": main()
When we run the above code for user John, we get Jane, Jennifer, and Jethro.
Similarly, we can implement something which returns all parents of a user. Since there can only be one actual parent of a user, what we want is to continue upward until we get to a user who has no parent. The implementation is as below:
def user_parents(user=None, parent_list= None, session=None): query = session.query(users).filter_by(user=user) parents_list =  for result in query: parents_list.append(result.parent) # We don't want a NULL or None parent if result.parent: parent_list.append(result.parent) for name in parents_list: user_parents(name, parent_list, session) return parent_list def main(): parent_list =  # We assume session stuff for SQLalchemy has already been taken care of # prior to following statement session = mydb.mysession() all_parents = user_parents('jethro', parent_list, session) session.close() return all_parents if __name__ == "__main__": main()
When we run the above code for user Jethro, we get Jane, John, and Amy.
This seems to work for me. Of course, the data I tested this code on was very small. Don’t look at the efficiency of the code (although any suggestions on how to improve it are always welcome) but look the at general idea of how you might achieve the same results. I will also try to provide code for when there are many-to-many relationships.