Rails - May 2005 - Finding objects *not* associated

Given a base object with a has_many or habtm association, I''d like to 
display a list of candidate objects that are not already related to the 
base object.

At SQL-level I can do this with a sub-select. In Ruby I can compute the 
difference Projects.find(:all) - developer.projects. It would be much 
nicer, though, if this was directly supported in ActiveRecord. Say 
through a method like Developer#projects.complement().

Has anyone considered implementing this functionality?

Michael

-- 
Michael Schuerig                             Those who call the shots
mailto:michael-q5aiKMLteq4b1SvskN2V4Q@public.gmane.org              Are never in
the line of fire
http://www.schuerig.de/michael/           --Ani DiFranco, Not So Soft

That''s a neat idea.  I haven''t heard of any implementation
plans for
such a method on this mailing list.  Are you volunteering? :)

Duane Johnson
(canadaduane)

On May 22, 2005, at 8:07 AM, Michael Schuerig wrote:
>
> Given a base object with a has_many or habtm association, I''d like
to
> display a list of candidate objects that are not already related to  
> the
> base object.
>
> At SQL-level I can do this with a sub-select. In Ruby I can compute  
> the
> difference Projects.find(:all) - developer.projects. It would be much
> nicer, though, if this was directly supported in ActiveRecord. Say
> through a method like Developer#projects.complement().
>
> Has anyone considered implementing this functionality?
>
> Michael
>
> -- 
> Michael Schuerig                             Those who call the shots
> mailto:michael-q5aiKMLteq4b1SvskN2V4Q@public.gmane.org              Are
never in the line of fire
> http://www.schuerig.de/michael/           --Ani DiFranco, Not So Soft
> _______________________________________________
> Rails mailing list
> Rails-1W37MKcQCpIf0INCOvqR/iCwEArCW2h5@public.gmane.org
> http://lists.rubyonrails.org/mailman/listinfo/rails
>

[MS: finding complement of associated objects]

On Monday 23 May 2005 01:09, Duane Johnson wrote:
> That''s a neat idea.  I haven''t heard of any
implementation plans for
> such a method on this mailing list.  Are you volunteering? :)
Yes, I think I''ll look into it.

Michael

-- 
Michael Schuerig                       Face reality and stare it down
mailto:michael-q5aiKMLteq4b1SvskN2V4Q@public.gmane.org        --Jethro Tull,
Silver River Turning
http://www.schuerig.de/michael/

On Monday 23 May 2005 02:11, Michael Schuerig wrote:
> [MS: finding complement of associated objects]
>
> On Monday 23 May 2005 01:09, Duane Johnson wrote:
> > That''s a neat idea.  I haven''t heard of any
implementation plans
> > for such a method on this mailing list.  Are you volunteering? :)
>
> Yes, I think I''ll look into it.
So here it is. Testing is only rudimentary and not automated :-/
I''ll submit it as a patch, when I''ve written some test cases
-- feel
free to beat me to it.

Michael


module ActiveRecord
  module Associations

    class AssociationProxy #:nodoc:
      def candidates
        @association_class.find(:all, :order => @options[:order])
      end
      # Overridden for BelongsToAssociation and 
HasAndBelongsToManyAssociation
      def complement
        conditions = 
"#{@association_class.table_name}.#{@association_class_primary_key_name} !=
#{@owner.quoted_id}"
        conditions << " AND
#{interpolate_sql(@options[:conditions])}"
if @options[:conditions]
        @association_class.find(:all, :conditions => conditions, :order 
=> @options[:order])
      end
    end

    class BelongsToAssociation #:nodoc:
      def complement
        conditions = 
"#{@association_class.table_name}.#{@association_class.primary_key} != 
#{@target.quoted_id}"
        conditions << " AND
#{interpolate_sql(@options[:conditions])}"
if @options[:conditions]
        @association_class.find(:all, :conditions => conditions, :order 
=> @options[:order])
      end
    end

    class HasAndBelongsToManyAssociation #:nodoc:
      def complement
        @association_class.find_by_sql(@complement_sql)
      end
      protected
        alias_method :construct_sql_without_complement, :construct_sql
        def construct_sql
          construct_sql_without_complement
          @complement_sql             "SELECT t.* FROM
#{@association_table_name} t " +
            "WHERE t.#{@association_class.primary_key} NOT IN " +
            "(SELECT j.#{@association_foreign_key} FROM #{@join_table} j 
" +
            "WHERE j.#{@association_class_primary_key_name} = 
#{@owner.quoted_id})"
          @complement_sql << " AND 
#{interpolate_sql(@options[:conditions])}" if @options[:conditions]
          @complement_sql << " ORDER BY #{@order}" if @order
        end
    end

  end
end


-- 
Michael Schuerig                          Thinking is trying to make up
mailto:michael-q5aiKMLteq4b1SvskN2V4Q@public.gmane.org                for a gap
in one''s education.
http://www.schuerig.de/michael/                          --Gilbert Ryle

That code looks good.  Regarding the SQL itself: would a JOIN be  
faster than a subselect (especially on MySQL)?

  I''m not sure if this can be generalized, but I have once or twice  
been able to accomplish the same task by using a LEFT JOIN and then  
in the WHERE clause accepting only those rows whose foreign key (or  
keys) are nil.  Would this approach work?

Duane Johnson
(canadaduane)

I''ll toss in my $0.02 in favor of a left join-based solution, because
I''m still writing apps for deployment on mysql 4.0.  (I''d
write it
myself, but I''m still a relative ruby newbie :p)

Does rails support old versions of mysql, or am I just lucky that it
happens to work so far?

Tyler

On 5/25/05, Duane Johnson
<duane.johnson-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org>
wrote:
> That code looks good.  Regarding the SQL itself: would a JOIN be
> faster than a subselect (especially on MySQL)?
> 
>   I''m not sure if this can be generalized, but I have once or
twice
> been able to accomplish the same task by using a LEFT JOIN and then
> in the WHERE clause accepting only those rows whose foreign key (or
> keys) are nil.  Would this approach work?
> 
> Duane Johnson
> (canadaduane)
> _______________________________________________
> Rails mailing list
> Rails-1W37MKcQCpIf0INCOvqR/iCwEArCW2h5@public.gmane.org
> http://lists.rubyonrails.org/mailman/listinfo/rails
>

On Wednesday 25 May 2005 15:42, Duane Johnson wrote:
> That code looks good.  Regarding the SQL itself: would a JOIN be
> faster than a subselect (especially on MySQL)?
Agreed, I forgot to mention this. I have no experience with MySQL and 
with PostgreSQL a subselect is the natural thing to use. The code is 
very easy to change, please go ahead adapt it and post the result.

Michael

-- 
Michael Schuerig                 Nothing is as brilliantly adaptive
mailto:michael-q5aiKMLteq4b1SvskN2V4Q@public.gmane.org       as selective
stupidity.
http://www.schuerig.de/michael/    --A.O. Rorty, The Deceptive Self

On Wednesday 25 May 2005 15:50, Tyler Kiley wrote:
> I''ll toss in my $0.02 in favor of a left join-based solution,
because
> I''m still writing apps for deployment on mysql 4.0.  (I''d
write it
> myself, but I''m still a relative ruby newbie :p)
Can you give me a hint how to do with a left join what I''ve done with 
the subselect? I thought about it, but I''m stuck.

Michael

-- 
Michael Schuerig                 Not only does lightning not strike
mailto:michael-q5aiKMLteq4b1SvskN2V4Q@public.gmane.org       twice, it usually
doesn''t strike once.
http://www.schuerig.de/michael/  --Salman Rushdie, Fury

On 26/05/05, Michael Schuerig
<michael-q5aiKMLteq4b1SvskN2V4Q@public.gmane.org>
wrote:
> On Wednesday 25 May 2005 15:50, Tyler Kiley wrote:
> > I''ll toss in my $0.02 in favor of a left join-based solution,
because
> > I''m still writing apps for deployment on mysql 4.0. 
(I''d write it
> > myself, but I''m still a relative ruby newbie :p)
> 
> Can you give me a hint how to do with a left join what I''ve done
with
> the subselect? I thought about it, but I''m stuck.
Give this a shot:
@complement_sql = 
	"SELECT t.* FROM #{@association_table_name} t " +
	"LEFT JOIN #{@join_table} j " +
	" ON j.#{@association_class_primary_key_name} != #{@owner.quoted_id}"
	@complement_sql << " AND
#{interpolate_sql(@options[:conditions])}"
if @options[:conditions]
	@complement_sql << " ORDER BY #{@order}" if @order

-- 
Phillip Hutchings
http://www.sitharus.com/
sitharus-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org /
sitharus-QrR4M9swfipWk0Htik3J/w@public.gmane.org

On Wednesday 25 May 2005 23:25, Phillip Hutchings wrote:
> On 26/05/05, Michael Schuerig
<michael-q5aiKMLteq4b1SvskN2V4Q@public.gmane.org> wrote:
> > On Wednesday 25 May 2005 15:50, Tyler Kiley wrote:
> > > I''ll toss in my $0.02 in favor of a left join-based
solution,
> > > because I''m still writing apps for deployment on mysql
4.0.  (I''d
> > > write it myself, but I''m still a relative ruby newbie
:p)
> >
> > Can you give me a hint how to do with a left join what I''ve
done
> > with the subselect? I thought about it, but I''m stuck.
>
> Give this a shot:
[1]
> @complement_sql > 	"SELECT t.* FROM #{@association_table_name} t
" +
> 	"LEFT JOIN #{@join_table} j " +
> 	" ON j.#{@association_class_primary_key_name} !=
#{@owner.quoted_id}"
Even after some head scratching, I don''t quite understand what this 
statement matches in practical terms.

The other suggestion I received by mail finds all the objects of the 
association class that are not associated to *any* owner object (via 
the given join table):

[2]
>  "SELECT t.* FROM #{@association_table_name} t LEFT 
JOIN  #{@join_table} j " +
>            "ON t.#{@association_class.primary_key} >
j.#{@association_class_primary_key_name} WHERE
> j.#{@association_class_primary_key_name} IS NULL "
Let''s think of employees and tasks. then [2] finds all tasks that are 
not assigned to any employee. What I''m looking for is an expression 
that finds all tasks not currently associated to a specific employee.

Thinking of it in these terms, both operations are relevant and I''ll 
probably add what [2] does to the (someday) upcoming patch.

During my experimentation, I''ve come to the conclusion that the
original
problem cannot be solved without a subselect.

Consider the cartesian product of all involved tables: employees, 
employees_tasks, and tasks. Now take a single row from this product and 
try to decide whether the contained task is already associated with the 
contained employee. If you''ve hit a row where employee and task are 
suitably related by the contained employees_tasks mapping, then you can 
decide that, yes, the task is assigned to the employee. If the mapping 
doesn''t relate employee and task in this way, though, you
can''t be sure
that there''s no other row that does this. Thus, from looking only at 
individual rows, the relevant decision can''t be made. You''d
have to
keep a list of all tasks and cross off those where you found that they 
are assigned to an employee. After going through all the rows, the 
remaining tasks on the list are the ones that are not assigned to any 
employee. -- The vagaries of the closed-world assumption where failure 
to prove something means it''s false.

Michael

-- 
Michael Schuerig                             Those who call the shots
mailto:michael-q5aiKMLteq4b1SvskN2V4Q@public.gmane.org              Are never in
the line of fire
http://www.schuerig.de/michael/           --Ani DiFranco, Not So Soft