관계 모델과 관계대수의 집합 연산

SQL을 쓸 줄 알아도 SELECT가 관계대수(relational algebra)의 어떤 생각을 구현하는지 설명하기는 어렵습니다. 관계대수는 표 모양의 입력을 받아 다시 표 모양의 결과를 만드는 연산의 체계입니다. 연산의 결과를 다음 연산의 입력으로 쓸 수 있는 닫힘(closure)의 성질이 있어서, 작은 질의를 조합해 큰 질의를 설명할 수 있습니다.

이 글에서는 관계 모델의 용어를 정리한 뒤, 세 행짜리 회원 관계와 작은 두 집합으로 관계대수의 연산을 하나씩 계산합니다. 같은 연산을 MySQL 8.4로 실행해, 중복과 순서에서 SQL이 집합과 어떻게 다른지도 봅니다.

릴레이션의 용어와 SQL의 차이

릴레이션(relation)은 같은 속성 구조를 가진 튜플(tuple)의 집합입니다. 튜플은 한 행, 속성(attribute)은 한 열이고, 도메인(domain)은 그 속성이 가질 수 있는 값의 범위입니다. 회원(회원번호, 이름, 도시)는 스키마이고 지금 저장된 세 행은 인스턴스이며, 스키마의 열 수를 차수(degree), 인스턴스의 튜플 수를 카디널리티라고 합니다. 여기의 카디널리티는 ERD에서 말하는 1:N과는 문맥이 다릅니다.

수학의 릴레이션은 같은 튜플을 두 번 세지 않고, 행의 순서에 뜻을 두지 않습니다. 반면 SQL의 조회 결과는 기본적으로 중복을 남기는 다중집합(multiset)이며, ORDER BY가 없으면 결과의 순서를 약속하지 않습니다. SQL의 NULL과 세 값 논리도, 여기서 다루는 NULL 없는 집합의 예제와 구별합니다.

이 관계는 차수가 3이고 카디널리티도 3입니다. 이 세 행만 보면 이름이 정해지면 도시도 정해지는 것처럼 보이지만, 그렇게 일반화할 수는 없습니다. 키와 함수 종속은 지금의 데이터가 아니라 앞으로 들어올 수 있는 데이터까지 포함하는 업무의 규칙입니다.

선택과 투영

선택(selection) σ조건(R)은 조건에 맞는 행을 남기고, 투영(projection) π속성목록(R)은 필요한 속성만 남기며 집합의 중복을 없앱니다. 관계대수의 선택은 SQL 문장의 이름인 SELECT와 같지 않습니다. SQL에서는 주로 WHERE가 선택에, SELECT 목록이 투영에 해당합니다.

서울 회원을 선택하면 회원번호 1과 2의 두 행이 남고, 그 결과에서 도시만 투영하면 {서울}이라는 튜플 하나가 남습니다. 거꾸로 도시만 먼저 투영하면 회원번호와 이름이 사라져, 뒤에서 그 속성을 조건에 쓸 수 없습니다. 실습은 board_lab을 바꾸지 않도록 별도의 데이터베이스 cs_db_lab에서 합니다.

CREATE DATABASE IF NOT EXISTS cs_db_lab;
USE cs_db_lab;
DROP TABLE IF EXISTS cs_ra_people;
DROP TABLE IF EXISTS cs_ra_a;
DROP TABLE IF EXISTS cs_ra_b;
CREATE TABLE cs_ra_people (
  person_id INT NOT NULL PRIMARY KEY,
  name VARCHAR(20) NOT NULL,
  city VARCHAR(20) NOT NULL
) ENGINE=InnoDB;
INSERT INTO cs_ra_people VALUES (1,'민','서울'),(2,'준','서울'),(3,'솔','부산');
CREATE TABLE cs_ra_a (person_id INT NOT NULL) ENGINE=InnoDB;
CREATE TABLE cs_ra_b (person_id INT NOT NULL) ENGINE=InnoDB;
INSERT INTO cs_ra_a VALUES (1),(2),(2);
INSERT INTO cs_ra_b VALUES (2),(3);
SELECT person_id,name,city FROM cs_ra_people WHERE city='서울' ORDER BY person_id;
SELECT city FROM cs_ra_people ORDER BY person_id;
SELECT DISTINCT city FROM cs_ra_people ORDER BY city;

person_id | name | city
1         | 민   | 서울
2         | 준   | 서울

city
서울
서울
부산

city
부산
서울

두 번째 조회에는 서울이 두 번 나옵니다. SQL의 SELECT 목록은 중복을 남기므로, 순수한 관계대수의 투영과 같은 결과를 얻으려면 세 번째 조회처럼 DISTINCT가 필요합니다. 다음 도표는 선택이 행을, 투영이 속성을 남기는 과정을 단계별로 보여 줍니다.

합집합, 교집합, 차집합

집합 A를 {1,2}, B를 {2,3}이라고 해 봅시다. 합집합은 {1,2,3}, 교집합은 {2}, A−B는 {1}입니다. B−A는 {3}이므로, 차집합은 두 입력의 순서를 바꾸면 다른 연산이 됩니다. 세 연산을 원소가 들어가는 조건으로 정의하는 방법과, 이산수학에서 곱집합이라고 부르는 데카르트 곱은 집합의 표현과 연산에서 자세히 다룹니다.

세 연산 모두 두 입력의 열 수와 대응하는 도메인이 호환되어야 합니다. 회원번호의 집합에 이름의 집합을 같은 뜻의 값처럼 합치지 않습니다. SQL이 타입을 암묵적으로 바꾸어 실행해 주더라도, 뜻이 호환되는지는 쓰는 사람이 정해야 합니다.

SELECT person_id FROM cs_ra_a
UNION SELECT person_id FROM cs_ra_b ORDER BY person_id;
SELECT person_id FROM cs_ra_a
INTERSECT SELECT person_id FROM cs_ra_b ORDER BY person_id;
SELECT person_id FROM cs_ra_a
EXCEPT SELECT person_id FROM cs_ra_b ORDER BY person_id;
SELECT person_id FROM cs_ra_a
UNION ALL SELECT person_id FROM cs_ra_b ORDER BY person_id;

person_id
1
2
3

person_id
2

person_id
1

person_id
1
2
2
2
3

SQL의 A는 1, 2, 2의 세 행이지만, UNION과 INTERSECT, EXCEPT는 기본으로 중복을 없애므로 결과가 집합의 연산과 같습니다. 마지막 UNION ALL의 2 세 개는 A의 두 행과 B의 한 행입니다. MySQL 8.4는 INTERSECT와 EXCEPT도 지원하며, 여러 연산을 섞을 때는 우선순위를 짐작하지 말고 괄호로 의도한 중간 집합을 적습니다(MySQL 집합 연산 문서).

카티션 곱과 조인의 출발점

카티션 곱이라고도 부르는 데카르트 곱(Cartesian product) A × B는 A의 튜플마다 B의 모든 튜플과 짝을 짓습니다. 집합으로 보면 2×2=4쌍인 (1,2), (1,3), (2,2), (2,3)입니다. 그러나 SQL의 A는 세 행이므로, DISTINCT 없는 CROSS JOIN은 3×2=6행을 만듭니다.

SELECT a.person_id AS a_id,b.person_id AS b_id
FROM cs_ra_a AS a CROSS JOIN cs_ra_b AS b
ORDER BY a_id,b_id;
SELECT DISTINCT a.person_id AS a_id,b.person_id AS b_id
FROM cs_ra_a AS a CROSS JOIN cs_ra_b AS b
ORDER BY a_id,b_id;

a_id | b_id
1    | 2
1    | 3
2    | 2
2    | 2
2    | 3
2    | 3

a_id | b_id
1    | 2
1    | 3
2    | 2
2    | 3

두 번째 조회가 집합의 네 쌍을 남깁니다. 실제 테이블의 조인은 이 곱에서 관계의 조건을 만족하는 쌍을 선택한 것이라고 설명할 수 있습니다. 다만 이것은 결과의 뜻을 설명하는 것이며, 옵티마이저가 모든 곱을 먼저 물리적으로 만든다는 뜻은 아닙니다. 실습을 마친 뒤 누적 모델로 돌아가려면 USE board_lab;을 실행합니다.

정리

• 릴레이션은 같은 속성 구조를 가진 튜플의 집합이며, 열 수를 차수, 튜플 수를 카디널리티라고 합니다.
• 관계대수의 선택은 SQL의 WHERE에, 투영은 SELECT 목록에 해당하며, 투영의 중복 제거는 SQL에서 DISTINCT가 맡습니다.
• 합집합과 교집합, 차집합은 열 수와 도메인이 호환되는 두 입력에만 적용하며, 차집합은 입력의 순서에 따라 결과가 다릅니다.
• SQL의 결과는 중복을 남기는 다중집합이므로, 집합의 결과와 같은지는 중복의 규칙까지 따져서 확인합니다.

연습 문제

1. 세 원소 집합의 연산

집합 A={1,2,4}, B={2,3,4}에서 A−B와 B−A, A와 B의 교집합을 구해 보세요.

2. 중복이 늘어나면

SQL의 cs_ra_a에 4를 두 번 더 넣으면, cs_ra_b와의 UNION과 UNION ALL의 결과는 각각 몇 행이 되나요?

3. 투영을 먼저 하면

서울 회원의 이름을 구하려는데, 회원 관계에서 도시만 먼저 투영했습니다. 이 순서로는 왜 답을 구할 수 없나요?

4. 다중집합의 교집합과 차집합

MySQL 8.4는 중복을 남기는 INTERSECT ALL과 EXCEPT ALL도 지원합니다. 원래의 cs_ra_a(1, 2, 2)와 cs_ra_b(2, 3)에 대해 두 연산의 결과를 예상해 보세요.

관계대수는 집합을 조합하는 논리의 설명이고, SQL의 결과는 중복과 NULL, 정렬을 따로 설계합니다. 다음 글 조인·디비전과 관계해석에서는 관계의 조건과 "모두 만족한다"는 조건을 이 원리로 구성합니다.