module Sequel::Plugins::RcteTree

Overview

The rcte_tree plugin deals with tree structured data stored in the database using the adjacency list model (where child rows have a foreign key pointing to the parent rows), using recursive common table expressions to load all ancestors in a single query, all descendants in a single query, and all descendants to a given level (where level 1 is children, level 2 is children and grandchildren etc.) in a single query.

Usage

The rcte_tree plugin adds four associations to the model: parent, children, ancestors, and descendants. Both the parent and children are fairly standard many_to_one and one_to_many associations, respectively. However, the ancestors and descendants associations are special. Both the ancestors and descendants associations will automatically set the parent and children associations, respectively, for current object and all of the ancestor or descendant objects, whenever they are loaded (either eagerly or lazily). Additionally, the descendants association can take a level argument when called eagerly, which limits the returned objects to only that many levels in the tree (see the Overview).

Model.plugin :rcte_tree

# Lazy loading
model = Model.first
model.parent
model.children
model.ancestors # Populates :parent association for all ancestors
model.descendants # Populates :children association for all descendants

# Eager loading - also populates the :parent and children associations
# for all ancestors and descendants
Model.where(id: [1, 2]).eager(:ancestors, :descendants).all

# Eager loading children and grandchildren
Model.where(id: [1, 2]).eager(descendants: 2).all
# Eager loading children, grandchildren, and great grandchildren
Model.where(id: [1, 2]).eager(descendants: 3).all

Options

You can override the options for any specific association by making sure the plugin options contain one of the following keys:

:parent

hash of options for the parent association

:children

hash of options for the children association

:ancestors

hash of options for the ancestors association

:descendants

hash of options for the descendants association

Note that you can change the name of the above associations by specifying a :name key in the appropriate hash of options above. For example:

Model.plugin :rcte_tree, parent: {name: :mother},
 children: {name: :daughters}, descendants: {name: :offspring}

Any other keys in the main options hash are treated as options shared by all of the associations. Here's a few options that affect the plugin:

:key

The foreign key in the table that points to the primary key of the parent (default: :parent_id)

:primary_key

The primary key to use (default: the model's primary key)

:key_alias

The symbol identifier to use for aliasing when eager loading (default: :x_root_x)

:cte_name

The symbol identifier to use for the common table expression (default: :t)

:level_alias

The symbol identifier to use when eagerly loading descendants up to a given level (default: :x_level_x)

Public Class Methods

apply(model, opts=OPTS) click to toggle source

Create the appropriate parent, children, ancestors, and descendants associations for the model.

    # File lib/sequel/plugins/rcte_tree.rb
 77 def self.apply(model, opts=OPTS)
 78   model.plugin :tree, opts
 79 
 80   opts = opts.dup
 81   opts[:class] = model
 82   opts[:methods_module] = Module.new
 83   model.send(:include, opts[:methods_module])
 84   
 85   key = opts[:key] ||= :parent_id
 86   prkey = opts[:primary_key] ||= model.primary_key
 87   ka = opts[:key_alias] ||= :x_root_x
 88   t = opts[:cte_name] ||= :t
 89   c_all = if model.dataset.recursive_cte_requires_column_aliases?
 90     # Work around Oracle/ruby-oci8 bug that returns integers as BigDecimals in recursive queries.
 91     conv_bd = model.db.database_type == :oracle
 92     col_aliases = model.dataset.columns
 93     model_table = model.table_name
 94     col_aliases.map{|c| SQL::QualifiedIdentifier.new(model_table, c)}
 95   else
 96     [SQL::ColumnAll.new(model.table_name)]
 97   end
 98   
 99   bd_conv = lambda{|v| conv_bd && v.is_a?(BigDecimal) ? v.to_i : v}
100 
101   key_array = Array(key)
102   prkey_array = Array(prkey)
103   if key.is_a?(Array)
104     key_conv = lambda{|m| key_array.map{|k| m[k]}}
105     key_present = lambda{|m| key_conv[m].all?}
106     prkey_conv = lambda{|m| prkey_array.map{|k| m[k]}}
107     key_aliases = (0...key_array.length).map{|i| :"#{ka}_#{i}"}
108     ancestor_base_case_columns = prkey_array.zip(key_aliases).map{|k, ka_| SQL::AliasedExpression.new(k, ka_)} + c_all
109     descendant_base_case_columns = key_array.zip(key_aliases).map{|k, ka_| SQL::AliasedExpression.new(k, ka_)} + c_all
110     recursive_case_columns = prkey_array.zip(key_aliases).map{|k, ka_| SQL::QualifiedIdentifier.new(t, ka_)} + c_all
111     extract_key_alias = lambda{|m| key_aliases.map{|ka_| bd_conv[m.values.delete(ka_)]}}
112   else
113     key_present = key_conv = lambda{|m| m[key]}
114     prkey_conv = lambda{|m| m[prkey]}
115     key_aliases = [ka]
116     ancestor_base_case_columns = [SQL::AliasedExpression.new(prkey, ka)] + c_all
117     descendant_base_case_columns = [SQL::AliasedExpression.new(key, ka)] + c_all
118     recursive_case_columns = [SQL::QualifiedIdentifier.new(t, ka)] + c_all
119     extract_key_alias = lambda{|m| bd_conv[m.values.delete(ka)]}
120   end
121   
122   parent = opts.merge(opts.fetch(:parent, OPTS)).fetch(:name, :parent)
123   childrena = opts.merge(opts.fetch(:children, OPTS)).fetch(:name, :children)
124   
125   opts[:reciprocal] = nil
126   a = opts.merge(opts.fetch(:ancestors, OPTS))
127   ancestors = a.fetch(:name, :ancestors)
128   a[:read_only] = true unless a.has_key?(:read_only)
129   a[:eager_grapher] = proc do |_|
130     raise Sequel::Error, "the #{ancestors} association for #{self} does not support eager graphing"
131   end
132   a[:eager_loader_key] = key
133   a[:dataset] ||= proc do
134     base_ds = model.where(prkey_array.zip(key_array.map{|k| get_column_value(k)}))
135     recursive_ds = model.join(t, key_array.zip(prkey_array))
136     if c = a[:conditions]
137       (base_ds, recursive_ds) = [base_ds, recursive_ds].map do |ds|
138         (c.is_a?(Array) && !Sequel.condition_specifier?(c)) ? ds.where(*c) : ds.where(c)
139       end
140     end
141     table_alias = model.dataset.schema_and_table(model.table_name)[1].to_sym
142     model.from(SQL::AliasedExpression.new(t, table_alias)).
143      with_recursive(t, col_aliases ? base_ds.select(*col_aliases) : base_ds.select_all,
144       recursive_ds.select(*c_all),
145       :args=>col_aliases)
146   end
147   aal = Array(a[:after_load])
148   aal << proc do |m, ancs|
149     unless m.associations.has_key?(parent)
150       parent_map = {prkey_conv[m]=>m}
151       child_map = {}
152       child_map[key_conv[m]] = m if key_present[m]
153       m.associations[parent] = nil
154       ancs.each do |obj|
155         obj.associations[parent] = nil
156         parent_map[prkey_conv[obj]] = obj
157         if ok = key_conv[obj]
158           child_map[ok] = obj
159         end
160       end
161       parent_map.each do |parent_id, obj|
162         if child = child_map[parent_id]
163           child.associations[parent] = obj
164         end
165       end
166     end
167   end
168   a[:after_load] ||= aal
169   a[:eager_loader] ||= proc do |eo|
170     id_map = eo[:id_map]
171     parent_map = {}
172     children_map = {}
173     eo[:rows].each do |obj|
174       parent_map[prkey_conv[obj]] = obj
175       (children_map[key_conv[obj]] ||= []) << obj
176       obj.associations[ancestors] = []
177       obj.associations[parent] = nil
178     end
179     r = model.association_reflection(ancestors)
180     base_case = model.where(prkey=>id_map.keys).
181      select(*ancestor_base_case_columns)
182     recursive_case = model.join(t, key_array.zip(prkey_array)).
183      select(*recursive_case_columns)
184     if c = r[:conditions]
185       (base_case, recursive_case) = [base_case, recursive_case].map do |ds|
186         (c.is_a?(Array) && !Sequel.condition_specifier?(c)) ? ds.where(*c) : ds.where(c)
187       end
188     end
189     table_alias = model.dataset.schema_and_table(model.table_name)[1].to_sym
190     ds = model.from(SQL::AliasedExpression.new(t, table_alias)).
191       with_recursive(t, base_case, recursive_case,
192        :args=>((key_aliases + col_aliases) if col_aliases))
193     ds = r.apply_eager_dataset_changes(ds)
194     ds = ds.select_append(ka) unless ds.opts[:select] == nil
195     model.eager_load_results(r, eo.merge(:loader=>false, :initialize_rows=>false, :dataset=>ds, :id_map=>nil)) do |obj|
196       opk = prkey_conv[obj]
197       if idm_obj = parent_map[opk]
198         key_aliases.each{|ka_| idm_obj.values[ka_] = obj.values[ka_]}
199         obj = idm_obj
200       else
201         obj.associations[parent] = nil
202         parent_map[opk] = obj
203         (children_map[key_conv[obj]] ||= []) << obj
204       end
205       
206       id_map[extract_key_alias[obj]].each do |root|
207         root.associations[ancestors] << obj
208       end
209     end
210     parent_map.each do |parent_id, obj|
211       if children = children_map[parent_id]
212         children.each do |child|
213           child.associations[parent] = obj
214         end
215       end
216     end
217   end
218   model.one_to_many ancestors, a
219   
220   d = opts.merge(opts.fetch(:descendants, OPTS))
221   descendants = d.fetch(:name, :descendants)
222   d[:read_only] = true unless d.has_key?(:read_only)
223   d[:eager_grapher] = proc do |_|
224     raise Sequel::Error, "the #{descendants} association for #{self} does not support eager graphing"
225   end
226   la = d[:level_alias] ||= :x_level_x
227   d[:dataset] ||= proc do
228     base_ds = model.where(key_array.zip(prkey_array.map{|k| get_column_value(k)}))
229     recursive_ds = model.join(t, prkey_array.zip(key_array))
230     if c = d[:conditions]
231       (base_ds, recursive_ds) = [base_ds, recursive_ds].map do |ds|
232         (c.is_a?(Array) && !Sequel.condition_specifier?(c)) ? ds.where(*c) : ds.where(c)
233       end
234     end
235     table_alias = model.dataset.schema_and_table(model.table_name)[1].to_sym
236     model.from(SQL::AliasedExpression.new(t, table_alias)).
237      with_recursive(t, col_aliases ? base_ds.select(*col_aliases) : base_ds.select_all,
238       recursive_ds.select(*c_all),
239       :args=>col_aliases)
240     end
241   dal = Array(d[:after_load])
242   dal << proc do |m, descs|
243     unless m.associations.has_key?(childrena)
244       parent_map = {prkey_conv[m]=>m}
245       children_map = {}
246       m.associations[childrena] = []
247       descs.each do |obj|
248         obj.associations[childrena] = []
249         if opk = prkey_conv[obj]
250           parent_map[opk] = obj
251         end
252         if ok = key_conv[obj]
253           (children_map[ok] ||= []) << obj
254         end
255       end
256       children_map.each do |parent_id, objs|
257         parent_obj = parent_map[parent_id]
258         parent_obj.associations[childrena] = objs
259         objs.each do |obj|
260           obj.associations[parent] = parent_obj
261         end
262       end
263     end
264   end
265   d[:after_load] = dal
266   d[:eager_loader] ||= proc do |eo|
267     id_map = eo[:id_map]
268     associations = eo[:associations]
269     parent_map = {}
270     children_map = {}
271     eo[:rows].each do |obj|
272       parent_map[prkey_conv[obj]] = obj
273       obj.associations[descendants] = []
274       obj.associations[childrena] = []
275     end
276     r = model.association_reflection(descendants)
277     base_case = model.where(key=>id_map.keys).
278      select(*descendant_base_case_columns)
279     recursive_case = model.join(t, prkey_array.zip(key_array)).
280      select(*recursive_case_columns)
281     if c = r[:conditions]
282       (base_case, recursive_case) = [base_case, recursive_case].map do |ds|
283         (c.is_a?(Array) && !Sequel.condition_specifier?(c)) ? ds.where(*c) : ds.where(c)
284       end
285     end
286     if associations.is_a?(Integer)
287       level = associations
288       no_cache_level = level - 1
289       associations = {}
290       base_case = base_case.select_append(SQL::AliasedExpression.new(Sequel.cast(0, Integer), la))
291       recursive_case = recursive_case.select_append(SQL::AliasedExpression.new(SQL::QualifiedIdentifier.new(t, la) + 1, la)).where(SQL::QualifiedIdentifier.new(t, la) < level - 1)
292     end
293     table_alias = model.dataset.schema_and_table(model.table_name)[1].to_sym
294     ds = model.from(SQL::AliasedExpression.new(t, table_alias)).
295       with_recursive(t, base_case, recursive_case,
296         :args=>((key_aliases + col_aliases + (level ? [la] : [])) if col_aliases))
297     ds = r.apply_eager_dataset_changes(ds)
298     ds = ds.select_append(ka) unless ds.opts[:select] == nil
299     model.eager_load_results(r, eo.merge(:loader=>false, :initialize_rows=>false, :dataset=>ds, :id_map=>nil, :associations=>OPTS)) do |obj|
300       if level
301         no_cache = no_cache_level == obj.values.delete(la)
302       end
303       
304       opk = prkey_conv[obj]
305       if idm_obj = parent_map[opk]
306         key_aliases.each{|ka_| idm_obj.values[ka_] = obj.values[ka_]}
307         obj = idm_obj
308       else
309         obj.associations[childrena] = [] unless no_cache
310         parent_map[opk] = obj
311       end
312       
313       if root = id_map[extract_key_alias[obj]].first
314         root.associations[descendants] << obj
315       end
316       
317       (children_map[key_conv[obj]] ||= []) << obj
318     end
319     children_map.each do |parent_id, objs|
320       objs = objs.uniq
321       parent_obj = parent_map[parent_id]
322       parent_obj.associations[childrena] = objs
323       objs.each do |obj|
324         obj.associations[parent] = parent_obj
325       end
326     end
327   end
328   model.one_to_many descendants, d
329 end