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      | [1]
3  |     Alice     | [1,2]
4  |       Rose    | [1,2,3]
5  |     Bob       | [1,2]
6  |   Sally       | [1]
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.

Depth

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 path.length:

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

Parents

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]

Children

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.

Moving Records

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      | [1]
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.

Our record’s new_path will be the new parent’s path plus the parent’s id, which we will call the record’s full_path. Bob’s full_path is [1,2,5].

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 move! method.

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.

          |  Old    | New

--------------|---------|-------- Alice’s path: | [1,2] | [1,2,5] Rose’s path: | [1,2,3] | [1,2,5,3]

Rose’s path will be split up into [1,2] and [3]. The [1,2] portion needs to be replaced with Alice’s new path, [1,2,5]. The ARRAY[:new_path] gives us the [1,2,5]. We get the second part of Rose’s new path by slicing everything after the [1,2], 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 move!.

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.