Hierarchies With Rails
Previously we looked at modeling hierarchies in Postgres using a materialized path. Now, we'll put this into practice using ActiveRecord.
First a quick recap. A materialized path, is an array containing the IDs of all the parent records. The hierarchy and path looked like this:
id | name | path ---+---------------+----------- 1 | Harold |  2 | Arthur |  3 | Alice | [1,2] 4 | Rose | [1,2,3] 5 | Bob | [1,2] 6 | Sally |  7 | Mortimer | [1,6] 8 | Penny | [1,6]
The astute observer might notice that previously we encoded each record's id into its own path. While it was useful to have the record's id in the path when aggregating hierarchies, it is more natural not to include it when dealing with ActiveRecord. Converting between the two representations is pretty straightforward.
Since ActiveRecord 4.x has added support for Postgres arrays, finding the depth of a record is trivial. We can find the depth by looking at the
class Employee < ActiveRecord::Base def depth path.length end ...
That's simple enough, now you can find Bob's depth:
# Bob is ID 5 Employee.find(5).depth #=> 2
The parents of a record are equally easy to find since they are encoded in the path:
class Employee < ActiveRecord::Base ... def parents Employee.find(path) end
Now you can find Bob's parents:
# Bob is ID 5 Employee.find(5).parents #=> [Harold, Arthur, Bob]
The children are slightly trickier. The materialized path has the ids of all the parents, so if we want to find a record's children we look for all the records that contain that id in the path.
class Employee < ActiveRecord::Base ... def children Employee.where('path && ARRAY[?]', id) end
It is worth noting that
children returns a proxy object, and as you will see below can be chained with other ActiveRecord operations.
The final piece is moving a record. We have optimized for making queries easy at the expense of making updating the hierarchy more complicated. Take a look at the full
move! method, then we will step through it.
class Employee < ActiveRecord::Base ... def move!(new_parent) if new_parent.path.include?(id) throw ArgumentError "Cannot move under a child record" end new_path = new_parent.full_path Employee.transaction do children.update_all [ 'path = ARRAY[:new_path] || path[:depth + 1 : array_length(path,1)]', new_path: new_path, depth: depth ] self.path = new_path self.save! end end
As an example we will move Alice under Bob:
id | name | path ---+---------------+----------- 1 | Harold |  2 | Arthur |  3 | Alice | [1,2] 4 | Rose | [1,2,3] 5 | Bob | [1,2] ...
The first step is to verify that the new parent is valid.
new_parent.path.include?(id) will return true if
new_parent is one of this record's children. This prevents moving a record under one of its own children. Bob's path
[1,2] does not contain Alice (
id:3), so this is a valid operation.
new_path will be the new parent's path plus the parent's id, which we will call the record's
class Employee < ActiveRecord::Base ... def full_path path + [id] end
Since we make two database calls, we use a transaction,
Employee.transaction do ... end. If for any reason either update fails, all the records will be rolled back, and the exception will bubble out of our
We will update the children first, then update our record. We can use the
children method defined earlier to scope our update.
Each record's path is split into two parts the first is the new path, the second is the part that doesn't need to change.
Rose's path will be split up into
[1,2] portion needs to be replaced with Alice's new path,
ARRAY[:new_path] gives us the
[1,2,5]. We get the second part of Rose's new path by slicing everything after the
path[:depth + 1 : array_length(path,1)].
Finally we set the new path on our record and save it.
save! will throw an exception if the record is invalid, this is quite useful because that will force the transaction to rollback. You should however be prepared to handle the exception one way or another when calling
Now you can wrap up materialized path hierarchies in rails. There are a lot of different ways to handle updating the hierarchy, so by all means, play around with it and look for one that fits your code base.
If you want to see the full code example, check it out on Github.blog comments powered by Disqus