title: SQL query to look for a Kevin Bacon number of 2
body: <p>Using the IMDB database, I have tables <code>actor</code>, <code>casts</code>, and <code>movie</code>, and I need to select actors with a Kevin Bacon number of 2. I thought this should do it, but I'm getting 0 rows returned. What is my error? </p>
  
  <pre><code>select fname, lname
  from actor join casts on pid=actor.id
  where actor.id in (
      select a3.id  --actors who have a kb number of 2
      from casts c3 join actor a3 on c3.pid=a3.id,
      (
       (select c1.mid --actors who have a kb number of 1
       from (casts c1 join actor a1 on c1.pid=a1.id), (casts c2 join actor a2 on c2.pid=a2.id)
       where c1.mid=c2.mid and a2.fname='Kevin' and a2.lname='Bacon')
      )Level1 where c3.mid=Level1.mid
  )
  and actor.id not in (select a4.id --and only a kb number of 2
       from (casts c4 join actor a4 on c4.pid=a4.id), (casts c5 join actor a5 on c5.pid=a5.id)
       where c4.mid=c5.mid and a5.fname='Kevin' and a5.lname='Bacon');
  </code></pre>
  
  <p>Here are the table schemas:</p>
  
  <pre><code>ACTOR (id, fname, lname, gender)
  MOVIE (id, name, year)
  CASTS (pid, mid, role)
  </code></pre>
  
  <p><code>mid</code> is a foreign key to a movie id and <code>pid</code> is a foreign key to actor id.</p>
  
  <p>Note that restrictions on the question prohibit me from using temp tables or recursion: the query should be done with subselects.</p>
  
  <hr>
  
  <p>I also tried</p>
  
  <pre><code>select count(distinct pid) from casts join actor on pid=actor.id where mid in (
      select mid from casts where pid in (
          select distinct pid from casts where mid in (
              select mid from casts join actor on pid=actor.id where fname='Kevin' and lname='Bacon')))
  
  and pid not in  
      (select distinct pid from casts where mid in (
          select mid from casts join actor on pid=actor.id where fname='Kevin' and lname='Bacon'));
  </code></pre>
  
  <p>which also seems like it should work, but it's not finishing.</p>
  
  <hr>
  
  <p>I finally managed to get some working code:</p>
  
  <pre><code>select count(distinct pid) from casts where mid in (
      select mid from casts where pid in (
          select distinct pid from casts where mid in (
              select mid from casts join actor on pid=actor.id where fname='Kevin' and lname='Bacon')))
  
  and pid not in  
      (select distinct pid from casts where mid in (
          select mid from casts join actor on pid=actor.id where fname='Kevin' and lname='Bacon'));
  </code></pre>
  
  <p>The subqueries return sensible answers, at least. But it's taking forever. Each subquery took under 30 seconds, but together they're taking 6 minutes and counting. Why?</p>
  
  <hr>
  
  <p>Note: This was given to me as homework. To avoid any semblence of academic misconduct on my part, I'd prefer if people didn't post complete/exact solutions, but rather pointed out general things that I'm doing wrong/make general suggestions as to how I should go about this.</p>