SQL-запрос для поиска числа Кевина Бэкона 2 - PullRequest
Новая
       23

SQL-запрос для поиска числа Кевина Бэкона 2

24 голосов
/ 04 февраля 2012

Используя базу данных IMDB, у меня есть таблицы actor, casts и movie, и мне нужно выбрать актеров с числом Кевина Бэкона, равным 2. Я думал, что это следует сделать, но я получаю 0 строк возвращено. В чем моя ошибка? 

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');

Вот схемы таблиц: 

ACTOR (id, fname, lname, gender)
MOVIE (id, name, year)
CASTS (pid, mid, role)

mid - это внешний ключ для идентификатора фильма, а pid - это внешний ключ для идентификатора актера.

Обратите внимание, что ограничения по этому вопросу запрещают мне использовать временные таблицы или рекурсию: запрос должен выполняться с помощью подвыборов.

Я тоже пытался 

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'));

, который также кажется, что он должен работать, но это не конец.

Мне наконец удалось получить какой-то рабочий код: 

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'));

Подзапросы возвращают разумные ответы, по крайней мере. Но это займет вечность. Каждый подзапрос занимал менее 30 секунд, но вместе они занимали 6 минут и считали. Почему?

Примечание: это было дано мне как домашнее задание. Чтобы избежать каких-либо проявлений академического проступка с моей стороны, я бы предпочел, чтобы люди не публиковали полные / точные решения, а скорее указывали на общие вещи, которые я делаю неправильно / делали общие предложения относительно того, как мне поступить в этом .

1 Ответ

9 голосов
/ 04 февраля 2012

Чтобы дать набросок решения, а не точного решения, я бы использовал этот общий подход 

SELECT *
FROM   ACTOR
WHERE  id IN (
SELECT id 
       /* ... of actors that have worked on a film worked 
         on by actors that have worked on a KB film*/
EXCEPT
SELECT id
 /* ... of all actors that have worked on a KB film
         including KB himself*/ )

Кроме того, поскольку вам все равно запрещено использовать рекурсивные CTE, вот ответ с их использованием. 

WITH RecursiveCTE
     AS (SELECT C.pid,
                C.mid,
                0 as Level
         FROM   CASTS C
                JOIN ACTOR A
                  ON A.id = C.pid
         WHERE  A.fname = 'Kevin'
                and A.lname = 'Bacon'
         UNION ALL
         SELECT c1.pid,
                c2.mid,
                R.Level + 1
         FROM   RecursiveCTE R
                JOIN CASTS c1
                  ON c1.mid = R.mid
                     AND R.Level < 2
                JOIN CASTS c2
                  ON c1.pid = c2.pid)
SELECT *
FROM   ACTOR
WHERE  id IN (SELECT pid
              FROM   RecursiveCTE
              GROUP  BY pid
              HAVING MIN(Level) = 2)
...