Найдите пару студентов, которые берут одинаковые классы

Question

Я должен найти пару студентов, которые берут те же классы из таблицы, которая имеет studentID а также courseID,

studentID | courseID
    1           1
    1           2
    1           3
    2           1
    3           1
    3           2
    3           3 

Запрос должен вернуться (1, 3),
Результат также не должен иметь повторяющихся строк, таких как (1,3) а также (3,1),

Answer 1

Приведенные примеры данных:

CREATE TABLE student_course (
   student_id integer,
   course_id integer,
   PRIMARY KEY (student_id, course_id)
);

INSERT INTO student_course (student_id, course_id)
VALUES (1, 1), (1, 2), (1, 3), (2, 1), (3, 1), (3, 2), (3, 3) ;

Использовать агрегацию массивов

Одним из вариантов является использование CTE для присоединения к упорядоченным спискам курсов, которые проходит каждый студент:

WITH student_coursearray(student_id, courses) AS (
  SELECT student_id, array_agg(course_id ORDER BY course_id)
  FROM student_course
  GROUP BY student_id
)
SELECT a.student_id, b.student_id
FROM student_coursearray a INNER JOIN student_coursearray b ON (a.courses = b.courses)
WHERE a.student_id > b.student_id;

array_agg на самом деле является частью стандарта SQL, как и WITH синтаксис выражения общей таблицы. Ни один из них не поддерживается MySQL, поэтому вам придется выразить это по-другому, если вы хотите поддерживать MySQL.

Найти недостающие пары курсов для каждого учащегося

Еще один способ думать об этом: "для каждого студента в паре выяснить, если один посещает класс, а другой нет". Это даст себя FULL OUTER JOIN, но это довольно неловко выразить. Вы должны определить пары идентификаторов учащихся, представляющих интерес, затем для каждой пары выполнить полное внешнее объединение для набора классов, которые каждый принимает. Если есть какие-либо пустые строки, то один занял класс, другой нет, так что вы можете использовать это с NOT EXISTS фильтр, чтобы исключить такие пары. Это дает вам этого монстра:

WITH student_id_pairs(left_student, right_student) AS (
  SELECT DISTINCT a.student_id, b.student_id
  FROM student_course a 
  INNER JOIN student_course b ON (a.student_id > b.student_id)
)
SELECT left_student, right_student 
FROM student_id_pairs 
WHERE NOT EXISTS (
  SELECT 1
  FROM (SELECT course_id FROM student_course WHERE student_id = left_student) a
  FULL OUTER JOIN (SELECT course_id FROM student_course b WHERE student_id = right_student) b
    ON (a.course_id = b.course_id)
  WHERE a.course_id IS NULL or b.course_id IS NULL
);

CTE является необязательным и может быть заменен CREATE TEMPORARY TABLE AS SELECT ... или что угодно, если ваша БД не поддерживает CTE.

Какой использовать?

Я очень уверен, что массивный подход будет работать лучше во всех случаях, особенно потому, что для действительно большого набора данных вы можете взять WITH выражение, вместо этого создайте временную таблицу из запроса, добавьте индекс (courses, student_id) и делать сумасшедший быстрый поиск равенства, который окупит затраты времени на создание индекса. Вы не можете сделать это с помощью подхода подзапросов.

Answer 2

select courses,group_concat(studentID) from
(select studentID, 
group_concat(courseID order by courseID) as courses
from Table1 group by studentID) abc
group by courses having courses like('%,%');

играть на скрипке

Answer 3

Прецедент:

Я создал несколько реалистичный тестовый пример:

CREATE TEMP TABLE student_course (
   student_id integer
  ,course_id integer
  ,PRIMARY KEY (student_id, course_id)
);

INSERT INTO student_course
SELECT *
FROM (VALUES (1, 1), (1, 2), (1, 3), (2, 1), (3, 1), (3, 2), (3, 3)) v
      -- to include some non-random values in test
UNION  ALL
SELECT DISTINCT student_id, normal_rand((random() * 30)::int, 1000, 35)::int
FROM   generate_series(4, 5000) AS student_id;

DELETE FROM student_course WHERE random() > 0.9; -- create some dead tuples
ANALYZE student_course; -- needed for temp table

Обратите внимание на использование normal_rand() заполнить фиктивную таблицу с нормальным распределением значений. Он поставляется с модулем tablefunc, и так или иначе я собираюсь использовать его дальше...

Также обратите внимание на жирный акцент на числах, которыми я собираюсь манипулировать для теста для имитации различных тестовых случаев.

Простой SQL

Вопрос довольно простой и неясный. Найти первых двух студентов с соответствующими курсами? Или найти все? Находите пары из них или группы студентов, посещающие одни и те же курсы? Крейг отвечает на:
Найти все пары, проходящие одинаковые курсы

C1 - первый запрос Крейга

Простой SQL С CTE и группированием по массивам, слегка отформатированным:

WITH student_coursearray(student_id, courses) AS (
   SELECT student_id, array_agg(course_id ORDER BY course_id)
   FROM   student_course
   GROUP  BY student_id
   )
SELECT a.student_id, b.student_id
FROM   student_coursearray a
JOIN   student_coursearray b ON (a.courses = b.courses)
WHERE  a.student_id < b.student_id
ORDER  BY a.student_id, b.student_id;

Второй вопрос в ответе Крейга сразу выпал из гонки. С более чем несколькими строками производительность быстро ухудшается. CROSS JOIN это яд

E1 - улучшенная версия

Есть одна главная слабость, ORDER BY на агрегат плохой исполнитель, поэтому я переписал с ORDER BY в подзапросе:

WITH cte AS (
   SELECT student_id, array_agg(course_id) AS courses
   FROM  (SELECT student_id, course_id FROM student_course ORDER BY 1, 2) sub
   GROUP  BY student_id
   )
SELECT a.student_id, b.student_id
FROM   cte a
JOIN   cte b USING (courses)
WHERE  a.student_id < b.student_id
ORDER  BY 1,2;

E2 - Альтернативная интерпретация вопроса

Я думаю, что в целом более полезный случай:
Найти всех студентов, проходящих одни и те же курсы.
Поэтому я возвращаю массивы студентов с соответствующими курсами.

WITH s AS (
   SELECT student_id, array_agg(course_id) AS courses
   FROM  (SELECT student_id, course_id FROM student_course ORDER BY 1, 2) sub
   GROUP  BY student_id
   )
SELECT array_agg(student_id)
FROM   s
GROUP  BY courses
HAVING count(*) > 1
ORDER    BY array_agg(student_id);

F1 - Динамическая функция PL/pgSQL

Чтобы сделать это универсальным и быстрым, я обернул его в функцию plpgsql с динамическим SQL:

CREATE OR REPLACE FUNCTION f_same_set(_tbl regclass, _id text, _match_id text)
  RETURNS SETOF int[] AS
$func$
BEGIN

RETURN QUERY EXECUTE format(
   $f$
   WITH s AS (
      SELECT %1$I AS id, array_agg(%2$I) AS courses
      FROM   (SELECT %1$I, %2$I FROM %3$s ORDER BY 1, 2) s
      GROUP  BY 1
      )
   SELECT array_agg(id)
   FROM   s
   GROUP  BY courses
   HAVING count(*) > 1
   ORDER    BY array_agg(id)
   $f$
   ,_id, _match_id, _tbl
   );
END
$func$  LANGUAGE plpgsql;

Вызов:

SELECT * FROM f_same_set('student_course', 'student_id', 'course_id');

Работает для любой таблицы с числовыми столбцами. Это тривиально для других типов данных.

crosstab()

Для относительно небольшого количества courses (и сколь угодно большое количество студентов) crosstab() предоставленный дополнительным модулем tablefunc является еще одним вариантом в PostgreSQL. Более общая информация здесь:
PostgreSQL Crosstab Query

Простой случай

Простой случай для простого примера в вопросе, очень похожий на объяснение в связанном ответе:

SELECT array_agg(student_id)
FROM   crosstab('
     SELECT student_id, course_id, TRUE
     FROM   student_course
     ORDER  BY 1'

   ,'VALUES (1),(2),(3)'
   )
AS t(student_id int, c1 bool, c2 bool, c3 bool)
GROUP  BY c1, c2, c3
HAVING count(*) > 1;

F2 - Динамическая функция кросс-таблицы

В простом случае кросс-таблица была быстрее, поэтому я создал функцию plpgsql с динамическим SQL и включил ее в тест. Функционально идентичен с F1.

CREATE OR REPLACE FUNCTION f_same_set_x(_tbl regclass, _id text, _match_id text)
  RETURNS SETOF int[] AS
$func$
DECLARE
   _ids int[];   -- for array of match_ids (course_id in example)
BEGIN

-- Get list of match_ids
EXECUTE format(
   'SELECT array_agg(DISTINCT %1$I ORDER BY %1$I) FROM %2$s',_match_id, _tbl)
INTO _ids;

-- Main query
RETURN QUERY EXECUTE format(
   $f$
   SELECT array_agg(%1$I)
   FROM   crosstab('SELECT %1$I, %2$I, TRUE FROM %3$s ORDER BY 1'
                  ,'VALUES (%4$s)')
      AS t(student_id int, c%5$s  bool)
   GROUP  BY c%6$s
   HAVING count(*) > 1
   ORDER    BY array_agg(student_id)
   $f$
   ,_id
   ,_match_id
   ,_tbl
   ,array_to_string(_ids, '),(')     -- values
   ,array_to_string(_ids, ' bool,c') -- column def list
   ,array_to_string(_ids, ',c')      -- names
   );
END
$func$  LANGUAGE plpgsql;

Вызов:

SELECT * FROM f_same_set_x('student_course', 'student_id', 'course_id');

эталонный тест

Я тестировал на своем небольшом тестовом сервере PostgreSQL. PostgreSQL 9.1.9 для Debian Linux на ~ 6-летнем сервере AMD Opteron. Я выполнил 5 тестовых наборов с указанными выше настройками и каждым из представленных запросов. Лучший из 5 с EXPLAIN ANALYZE,

Я использовал эти значения для жирных чисел в приведенном выше тесте для заполнения:

Н.Р.. студентов / макс. Н.Р.. курсов / стандартное отклонение (приводит к более четким course_ids)
1. 1000/30/35
2. 5000/30/50
3. 10000/30/100
4. 10000/10/10
5. 10000/5/5

С1
1. Общее время работы: 57 мс
2. Общее время работы: 315 мс
3. Общее время работы: 663 мс
4. Общее время работы: 543 мс
5. Общее время работы: 2345 мс (!) - ухудшается со многими парами

E1
1. Общее время работы: 46 мс
2. Общее время работы: 251 мс
3. Общее время работы: 529 мс
4. Общее время работы: 338 мс
5. Общее время работы: 734 мс

E2
1. Общее время работы: 45 мс
2. Общее время работы: 245 мс
3. Общее время работы: 515 мс
4. Общее время работы: 218 мс
5. Общее время работы: 143 мс

Победитель F1
1. Общее время работы: 14 мс
2. Общее время выполнения: 77 мс
3. Общее время работы: 166 мс
4. Общее время работы: 80 мс
5. Общее время работы: 54 мс

F2
1. Общее время работы: 62 мс
2. Общее время выполнения: 336 мс
3. Общее время выполнения: 1053 мс (!) Кросс-таблица () ухудшается со многими различными значениями
4. Общее время работы: 195 мс
5. Общее время выполнения: 105 мс (!), Но работает хорошо с меньшим количеством различных значений

Функция PL/pgSQL с динамическим SQL, сортировка строк в подзапросе является очевидной победой.

Answer 4

Наивная реализация реляционного деления, с CTE:

WITH pairs AS (
        SELECT DISTINCT a.student_id AS aaa
        , b.student_id AS bbb
        FROM student_course a
        JOIN student_course b ON a.course_id = b.course_id
        )
SELECT *
FROM pairs p
WHERE p.aaa < p.bbb
AND NOT EXISTS (
        SELECT * FROM student_course nx1
        WHERE nx1.student_id = p.aaa
        AND NOT EXISTS (
                SELECT * FROM student_course nx2
                WHERE nx2.student_id = p.bbb
                AND nx2.course_id = nx1.course_id
                )
        )
AND NOT EXISTS (
        SELECT * FROM student_course nx1
        WHERE nx1.student_id = p.bbb
        AND NOT EXISTS (
                SELECT * FROM student_course nx2
                WHERE nx2.student_id = p.aaa
                AND nx2.course_id = nx1.course_id
                )
        )
        ;

То же без CTE:

SELECT *
FROM (
        SELECT DISTINCT a.student_id AS aaa
        , b.student_id AS bbb
        FROM student_course a
        JOIN student_course b ON a.course_id = b.course_id
        ) p
WHERE p.aaa < p.bbb
AND NOT EXISTS (
        SELECT * FROM student_course nx1
        WHERE nx1.student_id = p.aaa
        AND NOT EXISTS (
                SELECT * FROM student_course nx2
                WHERE nx2.student_id = p.bbb
                AND nx2.course_id = nx1.course_id
                )
        )
AND NOT EXISTS (
        SELECT * FROM student_course nx1
        WHERE nx1.student_id = p.bbb
        AND NOT EXISTS (
                SELECT * FROM student_course nx2
                WHERE nx2.student_id = p.aaa
                AND nx2.course_id = nx1.course_id
                )
        )
        ;

Версия без CTE быстрее, очевидно.

Answer 5

Процесс, чтобы сделать это в MySQL

Create table student_course_agg 
( 
student_id int,
courses varchar(150)
);

INSERT INTO student_course_agg
select studentID ,GROUP_CONCAT(courseID ORDER BY courseID) courses
FROM STUDENTS 
GROUP BY 1;

SELECT master.student_id m_student_id,child.student_id c_student_id
FROM student_course_agg master 
JOIN student_course_ag child 
    ON master.student_id<child.student_id and master.courses=child.courses;

Прямой запрос.

SELECT master.student_id m_student_id,child.student_id c_student_id
FROM (select studentID ,GROUP_CONCAT(courseID ORDER BY courseID) courses
FROM STUDENTS 
GROUP BY 1) master
JOIN (select studentID ,GROUP_CONCAT(courseID ORDER BY courseID) courses
FROM STUDENTS 
GROUP BY 1) child 
   ON master.studentID <child.studentID and master.courses=child.courses;