조인·디비전과 관계해석

"한 과목이라도 수강했다"와 "필수 과목을 모두 수강했다"는 다른 질문입니다. 앞의 질문은 맞는 행 하나를 찾으면 끝나지만, 뒤의 질문은 빠진 필수 과목이 하나도 없어야 합니다. 이 글에서는 이 차이를 중간 결과와 논리식으로 따라가며, 관계대수의 디비전(division)이 SQL에서 어떻게 표현되는지 봅니다.

조인의 조건과 결과의 열

세타 조인(theta join)은 두 관계의 곱에서 비교 조건을 만족하는 쌍을 고르며, 비교에는 =뿐 아니라 <나 >도 쓸 수 있습니다. 그 가운데 같다는 조건만 쓰는 것이 동등 조인(equi join)입니다. 자연 조인(natural join)은 이름이 같은 속성끼리 자동으로 같다고 비교하고, 그 공통 속성을 결과에 한 번만 둡니다.

학생.이름과 교사.이름처럼 열의 이름이 우연히 같다고 같은 관계의 키라는 뜻은 아닙니다. SQL의 NATURAL JOIN은 공통 열이 새로 생기면 조인의 조건까지 저절로 바뀌므로, 서비스의 SQL에서는 명시적인 ON 조건이 변경의 의도를 더 잘 드러냅니다. 자연 조인이라는 논리와 그 문법의 편의는 구별합니다.

세미 조인(semi join)은 짝이 되는 상대가 있는 왼쪽 튜플만 남기며, 상대가 셋이라고 왼쪽 행을 세 번 복제하지 않습니다. SQL에서는 6장 2편의 EXISTS가 이 뜻을 나타냅니다. OUTER JOIN이 NULL로 채우는 것은 순수한 집합의 조인 정의에는 없는 확장이므로, COUNT(*)와 COUNT(오른쪽 키)의 차이도 이 관점에서 이해할 수 있습니다.

실습 데이터와 일치하는 행

학생 네 명과 필수 과목 두 개, 수강 기록 네 개를 별도의 데이터베이스 cs_db_lab에 만듭니다. 민은 DB와 OS를 모두, 준은 DB만, 솔은 OS만 수강했고, 라는 아무것도 수강하지 않았습니다.

CREATE DATABASE IF NOT EXISTS cs_db_lab;
USE cs_db_lab;
DROP TABLE IF EXISTS cs_div_enroll;
DROP TABLE IF EXISTS cs_div_required;
DROP TABLE IF EXISTS cs_div_students;
CREATE TABLE cs_div_students (student_id INT PRIMARY KEY,name VARCHAR(20) NOT NULL);
CREATE TABLE cs_div_required (course VARCHAR(20) PRIMARY KEY);
CREATE TABLE cs_div_enroll (
  student_id INT NOT NULL,course VARCHAR(20) NOT NULL,
  PRIMARY KEY(student_id,course),
  FOREIGN KEY(student_id) REFERENCES cs_div_students(student_id)
);
INSERT INTO cs_div_students VALUES (1,'민'),(2,'준'),(3,'솔'),(4,'라');
INSERT INTO cs_div_required VALUES ('DB'),('OS');
INSERT INTO cs_div_enroll VALUES (1,'DB'),(1,'OS'),(2,'DB'),(3,'OS');
SELECT s.student_id,s.name,e.course
FROM cs_div_students AS s JOIN cs_div_enroll AS e ON e.student_id=s.student_id
ORDER BY s.student_id,e.course;
SELECT s.student_id,s.name FROM cs_div_students AS s
WHERE EXISTS(SELECT 1 FROM cs_div_enroll AS e WHERE e.student_id=s.student_id)
ORDER BY s.student_id;

student_id | name | course
1          | 민   | DB
1          | 민   | OS
2          | 준   | DB
3          | 솔   | OS

student_id | name
1          | 민
2          | 준
3          | 솔

조인은 수강의 쌍마다 한 행을 만들어 민이 두 번 나오는 4행이고, EXISTS는 수강한 적이 있는 학생마다 한 행을 남겨 3행입니다. 수강 기록이 없는 라는 두 결과 모두에서 빠졌습니다. 중복을 DISTINCT로 무작정 지우기 전에, 조회하려는 것이 수강이라는 사실인지 학생이 있다는 것인지부터 정합니다.

디비전을 빠진 쌍으로 이해한다

수강 R(학생, 과목)을 필수 과목 D(과목)로 나누면, D의 모든 과목과 짝이 있는 학생을 얻습니다. 전통적인 관계대수의 디비전에서 후보 C는 수강한 학생인 π학생(R)이므로 {1,2,3}입니다. C와 D의 곱은 6쌍이고, 그 가운데 R에 없는 쌍은 (2,OS)와 (3,DB)입니다. 빠진 쌍에 나온 학생 {2,3}을 C에서 빼면 {1}이 남습니다.

식으로 쓰면 C − π학생((C × D) − R)입니다. 수강 기록에 필수가 아닌 과목이 더 있어도 필수의 조건을 방해하지 않습니다. SQL에서는 이 "빠진 쌍이 없다"를 두 겹의 NOT EXISTS로 씁니다.

SELECT DISTINCT c.student_id
FROM cs_div_enroll AS c
WHERE NOT EXISTS (
  SELECT 1 FROM cs_div_required AS r
  WHERE NOT EXISTS (
    SELECT 1 FROM cs_div_enroll AS e
    WHERE e.student_id=c.student_id AND e.course=r.course
  )
)
ORDER BY c.student_id;

student_id
1

안쪽의 NOT EXISTS는 "이 학생이 수강하지 않은 필수 과목"을 찾고, 바깥의 NOT EXISTS는 그런 과목이 하나도 없다는 뜻입니다. 민은 빠진 과목이 0개이고 준과 솔은 하나씩이므로 결과는 학생 1입니다.

관계해석과 빈 필수 집합

관계대수가 어떤 연산을 조합하는지를 설명한다면, 관계해석(relational calculus)은 결과가 만족해야 할 논리 조건을 적습니다. 같은 질의를 "학생 s가 후보이고, 모든 필수 과목 r에 대해 수강(s, r)이 존재한다"라고 쓸 수 있습니다. "모든 항목을 만족한다"는 조건은 양화사의 부정 규칙에 따라 "빠진 항목이 존재하지 않는다"로 바꿀 수 있으므로, 그대로 이중 NOT EXISTS와 이어집니다.

관계해석의 조건은 저장된 관계의 값과 정해진 후보의 범위 안에서 결과를 구하는 안전한(safe) 식으로 씁니다. 저장되지 않은 모든 정수 가운데 어떤 값을 뺀 집합처럼, 끝없는 결과를 요구하는 식은 쓰지 않습니다.

필수 과목의 집합이 비면 반례가 하나도 없으므로 모든 후보가 통과합니다. 위 조회의 후보는 수강 테이블에 있는 1, 2, 3이므로, 수강 기록이 없는 라는 그때도 돌아오지 않습니다. 등록된 학생 모두를 후보로 삼는 것이 업무의 규칙이라면, 다음처럼 학생 테이블에서 시작합니다.

SELECT s.student_id,s.name FROM cs_div_students AS s
WHERE NOT EXISTS (
  SELECT 1 FROM cs_div_required AS r
  WHERE NOT EXISTS (
    SELECT 1 FROM cs_div_enroll AS e
    WHERE e.student_id=s.student_id AND e.course=r.course
  )
)
ORDER BY s.student_id;

student_id | name
1          | 민

지금의 결과는 여전히 민입니다. 그러나 START TRANSACTION; DELETE FROM cs_div_required;를 실행한 뒤 두 조회를 다시 비교하면, 앞의 조회는 1, 2, 3을, 이 조회는 1, 2, 3, 4를 돌려줍니다. 확인한 뒤에는 ROLLBACK으로 필수 목록을 되살립니다. 필수 목록이 비었을 때 아무도 통과시키지 않는 것이 규칙이라면, EXISTS (SELECT 1 FROM cs_div_required)라는 조건을 따로 더해야 합니다.

COUNT로 같은 조건을 구성한다

같은 "모두" 조건을 건수의 비교로도 만들 수 있습니다. 먼저 등록된 학생 전체를 후보로 정하고 LEFT JOIN으로 남긴 뒤, 필수 과목과 일치하는 서로 다른 수강 과목만 셉니다. 이렇게 하면 필수가 아닌 과목은 세지 않고, 수강 기록이 없는 후보도 중간 결과에서 사라지지 않습니다.

WITH matched AS (
  SELECT s.student_id,
         COUNT(DISTINCT r.course) AS matched_required
  FROM cs_div_students AS s
  LEFT JOIN cs_div_enroll AS e ON e.student_id=s.student_id
  LEFT JOIN cs_div_required AS r ON r.course=e.course
  GROUP BY s.student_id
)
SELECT student_id,matched_required,
       (SELECT COUNT(*) FROM cs_div_required) AS required_count
FROM matched ORDER BY student_id;

SELECT s.student_id,s.name
FROM cs_div_students AS s
LEFT JOIN cs_div_enroll AS e ON e.student_id=s.student_id
LEFT JOIN cs_div_required AS r ON r.course=e.course
GROUP BY s.student_id,s.name
HAVING COUNT(DISTINCT r.course)=(SELECT COUNT(*) FROM cs_div_required)
ORDER BY s.student_id;

student_id | matched_required | required_count
1          | 2                | 2
2          | 1                | 2
3          | 1                | 2
4          | 0                | 2

student_id | name
1          | 민

일치한 필수 과목의 수가 필수의 수 2와 같은 민만 통과합니다. 이 실습 테이블은 기본 키가 같은 학생과 과목의 중복을 막지만, 중복이 생길 수 있는 원래의 수강 로그에 같은 논리를 쓸 때는 COUNT(DISTINCT r.course)가 꼭 필요합니다. 다음 CTE는 실제 테이블을 바꾸지 않고, 필수가 아닌 과목과 중복된 기록을 함께 넣어 확인합니다.

WITH raw_enroll AS (
  SELECT student_id,course FROM cs_div_enroll
  UNION ALL SELECT 1,'DB'
  UNION ALL SELECT 2,'NETWORK'
)
SELECT s.student_id,COUNT(DISTINCT r.course) AS matched_required
FROM cs_div_students AS s
LEFT JOIN raw_enroll AS e ON e.student_id=s.student_id
LEFT JOIN cs_div_required AS r ON r.course=e.course
GROUP BY s.student_id ORDER BY s.student_id;

student_id | matched_required
1          | 2
2          | 1
3          | 1
4          | 0

민의 DB가 두 번 기록되어도 서로 다른 필수 과목은 2개이고, 준의 NETWORK는 필수가 아니어서 짝이 없으므로 세지 않습니다. 필수 목록을 트랜잭션 안에서 비운 뒤 다시 실행하면, 네 후보 모두 일치한 수와 필수의 수가 0이어서 1, 2, 3, 4가 모두 통과합니다. 필수 과목 테이블에서 INNER JOIN으로 시작하면 목록이 비었을 때 후보가 모두 사라져 이 뜻을 나타내지 못합니다.

전통적인 디비전의 후보만 쓰려면 학생 조회의 GROUP BY 앞에 WHERE EXISTS (SELECT 1 FROM cs_div_enroll AS c WHERE c.student_id = s.student_id)를 넣습니다. 그러면 빈 필수 목록에서 1, 2, 3만 통과합니다. 빈 목록에서 아무도 통과시키지 않으려면 HAVING에 AND (SELECT COUNT(*) FROM cs_div_required) > 0을 더합니다. 어느 SQL 기법을 쓸지보다, 후보와 빈 집합의 규칙을 먼저 고릅니다.

정리

• 조인은 조건에 맞는 쌍을, 세미 조인은 상대가 있다는 것을, 디비전은 정해진 후보가 모든 조건을 만족한다는 것을 나타냅니다.
• 디비전은 "빠진 쌍이 없다"로 바꾸어 C − π학생((C × D) − R)이나 이중 NOT EXISTS로 씁니다.
• COUNT로 풀 때는 필수 과목과 일치한 서로 다른 과목만 세고, 후보는 LEFT JOIN으로 남깁니다.
• 필수 목록이 비면 반례가 없어 모든 후보가 통과하므로, 후보의 범위와 빈 집합의 규칙을 먼저 정합니다.

연습 문제

1. 수강과 필수 목록이 바뀌면

필수 과목을 {DB, OS}로 두고 준에게 OS 수강을 더하면, 본문의 이중 NOT EXISTS 두 조회는 누구를 돌려주나요? 이어서 필수 과목에 NETWORK를 더하면 어떤 중간 집합이 바뀌나요? COUNT로 풀 때 필수가 아닌 과목과 중복된 수강을 어떻게 다루어야 하는지도 설명해 보세요.

2. 자연 조인의 조건이 바뀌는 순간

cs_div_students NATURAL JOIN cs_div_enroll은 지금 어떤 조건으로 조인하나요? 나중에 누군가 cs_div_enroll에 수강 화면에 보여 줄 과목 이름을 담으려고 name 열을 더하면 어떻게 되나요?

조인은 맞는 쌍을, 세미 조인은 상대가 있는지를, 디비전은 정해진 후보의 모든 조건을 나타내므로, 결과의 행 수와 빈 집합의 규칙을 함께 확인합니다. 실습을 마친 뒤 누적 모델로 돌아가려면 USE board_lab;을 실행합니다. 다음 글 B+Tree 인덱스에서는 지금까지 만든 조회가 실제로 어떻게 데이터를 찾는지, 인덱스의 구조부터 살펴봅니다.