Ancestry allows the records of a ActiveRecord model to be organised in a tree structure, using a single, intuitively formatted database column. It exposes all the standard tree structure relations (ancestors, parent, root, children, siblings, descendants) and all of them can be fetched in a single sql query. Additional features are named_scopes, integrity checking, integrity restoration, arrangement of (sub)tree into hashes and different strategies for dealing with orphaned records.
To apply Ancestry to any ActiveRecord model, follow these simple steps:
-
Install gem
-
Install gemcutter gem: sudo gem install gemcutter (maybe you need: gem update –system)
-
Add gemcutter.org as default gem source: gem tumble
-
Add to config/environment.rb: config.gem ‘ancestry’
-
Install required gems: sudo rake gems:install
-
Alternatively: sudo gem install ancestry
-
If you don’t want gemcutter: config.gem ‘ancestry’, :source => ‘gemcutter.org’
-
Alternatively: sudo gem install ancestry –source gemcutter.org
-
-
Add ancestry column to your table
-
Create migration: ./script/generate migration add_ancestry_to_ ancestry:string
-
Add index to migration: add_index [table], :ancestry / remove_index [table], :ancestry
-
Migrate your database: rake db:migrate
-
-
Add ancestry to your model
-
Add to app/models/.rb: acts_as_tree
-
Your model is now a tree!
You can use the parent attribute to organise your records into a tree. If you have the id of the record you want to use as a parent and don’t want to fetch it, you can also use parent_id. Like any virtual model attributes, parent and parent_id can be set using parent= and parent_id= on a record or by including them in the hash passed to new, create, create!, update_attributes and update_attributes!. For example:
TreeNode.create! :name => 'Stinky', :parent => TreeNode.create!(:name => 'Squeeky')
You can also create children through the children relation on a node:
node.children.create :name => 'Stinky'
To navigate an Ancestry model, use the following methods on any instance / record:
*parent* Returns the parent of the record *root* Returns the root of the tree the record is in *root_id* Returns the id of the root of the tree the record is in *is_root?* Returns true if the record is a root node, false otherwise *ancestor_ids* Returns a list of ancestor ids, starting with the root id and ending with the parent id *ancestors* Scopes the model on ancestors of the record *path_ids* Returns a list the path ids, starting with the root is and ending with the node's own id *path* Scopes model on path records of the record *children* Scopes the model on children of the record *child_ids* Returns a list of child ids *has_children?* Returns true if the record has any children, false otherwise *is_childless?* Returns true is the record has no childen, false otherwise *siblings* Scopes the model on siblings of the record, the record itself is included *sibling_ids* Returns a list of sibling ids *has_siblings?* Returns true if the record's parent has more than one child *is_only_child?* Returns true if the record is the only child of its parent *descendants* Scopes the model on direct and indirect children of the record *descendant_ids* Returns a list of a descendant ids *subtree* Scopes the model on descendants and itself *subtree_ids* Returns a list of all ids in the record's subtree
Where possible, the navigation methods return scopes instead of records, this means additional ordering, conditions, limits, etc. can be applied and that the result can be either retrieved, counted or checked for existence. For example:
node.children.exists?(:name => 'Mary') node.subtree.all(:order => :name, :limit => 10).each do; ...; end node.descendants.count
For convenience, a couple of named scopes are included at the class level:
*roots* Only root nodes *ancestors_of(node)* Only ancestors of node, node can be either a record or an id *children_of(node)* Only children of node, node can be either a record or an id *descendants_of(node)* Only descendants of node, node can be either a record or an id *siblings_of(node)* Only siblings of node, node can be either a record or an id
Thanks to some convenient rails magic, it is even possible to create nodes through the children and siblings scopes:
node.children.create node.siblings.create! TestNode.children_of(node_id).new TestNode.siblings_of(node_id).create
The acts_as_tree methods supports two options:
*ancestry_column* Pass in a symbol to instruct Ancestry to use a different column name to store record ancestry *orphan_strategy* Instruct Ancestry what to do with children of a node that is destroyed: *:destroy* All children are destroyed as well (default) *:rootify* The children of the destroyed node become root nodes *:restrict* An AncestryException is raised if any children exist
Ancestry can arrange an entire subtree into nested hashes for easy navigation after retrieval from the database. TreeNode.arrange could for example return:
{ #<TreeNode id: 100018, name: "Stinky", ancestry: nil>
=> { #<TreeNode id: 100019, name: "Crunchy", ancestry: "100018">
=> { #<TreeNode id: 100020, name: "Squeeky", ancestry: "100018/100019">
=> {}
}
}
}
The arrange method also works on a scoped class, for example:
TreeNode.find_by_name('Crunchy').subtree.arrange
I currently don’t see any way Ancestry tree integrity could get compromised without explicitly setting cyclic parents but I included code for detecting integrity problems and restoring integrity just to be sure. To check integrity use: [Model].check_ancestry_integrity. An AncestryIntegrityException will be raised if there are any problems. To restore integrity use: [Model].restore_ancestry_integrity.
For example, from IRB:
>> stinky = TreeNode.create :name => 'Stinky' $ #<TreeNode id: 1, name: "Stinky", ancestry: nil> >> squeeky = TreeNode.create :name => 'Squeeky', :parent => stinky $ #<TreeNode id: 2, name: "Squeeky", ancestry: "1"> >> stinky.update_attribute :parent, squeeky $ true >> TreeNode.all $ [#<TreeNode id: 1, name: "Stinky", ancestry: "1/2">, #<TreeNode id: 2, name: "Squeeky", ancestry: "1/2/1">] >> TreeNode.check_ancestry_integrity !! Ancestry::AncestryIntegrityException: Conflicting parent id in node 1: 2 for node 1, expecting nil >> TreeNode.restore_ancestry_integrity $ [#<TreeNode id: 1, name: "Stinky", ancestry: 2>, #<TreeNode id: 2, name: "Squeeky", ancestry: nil>]
The Ancestry gem comes with a unit test suite consisting of about 1400 assertions in 18 tests. It takes about 4 seconds to run on sqlite. To run it yourself, install Ancestry as a plugin, go to the ancestry folder and type ‘rake’. The test suite is located in ‘test/acts_as_tree_test.rb’.
As can be seen in the previous section, Ancestry stores a path from the root to the parent for every node. This is a variation on the materialised path database pattern. It allows Ancestry to fetch any relation (siblings, descendants, etc.) in a single sql query without the complicated algorithms and incomprehensibility associated with left and right values. Additionally, any inserts, deletes and updates only affect nodes within the affected node’s own subtree.
In the example above, the ancestry column is created as a string. This puts a limitation on the depth of the tree of about 40 or 50 levels, which I think may be enough for most users. To increase the maximum depth of the tree, increase the size of the string that is being used or change it to a text to remove the limitation entirely. Changing it to a text will however decrease performance because a index cannot be put on the column in that case.
I will try to keep Ancestry up to date with changing versions of Rails and Ruby and also with any bug reports I might receive. I will implement new features on request as I see fit. Something that definitely needs to be added in the future is constraints on depth, something like: tree_node.subtree.to_depth(4)
For questions, bug reports and feature requests, please contact me at s.a.kroesgmail.com
Copyright © 2009 Stefan Kroes, released under the MIT license