선택 심화: 다치 종속과 무손실 분해 반례

이 글은 앞의 함수 종속과 3NF, BCNF를 이해한 뒤에 읽는 선택 심화입니다. 정규형의 번호가 높다는 이유로 모든 테이블을 계속 나누는 단계가 아닙니다. 한 사람의 기술과 사용 언어처럼 서로 독립인 여러 값이 같은 표에 저장될 때, 함수 종속만으로는 설명하기 어려운 반복이 생깁니다.

4NF와 다치 종속

민이 기술로 Python과 SQL을, 언어로 한국어와 영어를 갖고, 두 목록이 서로 독립이라는 업무 규칙을 가정합니다. 모든 기술과 언어의 조합을 한 표로 나타내면 네 행입니다.

사람이 기술 하나를 함수적으로 정하지는 않습니다. 대신 사람별 기술의 집합이 언어와 독립적으로 조합된다는 규칙을 다치 종속(multivalued dependency) 사람 →→ 기술로 나타냅니다. 관계 R의 비자명한 다치 종속 X →→ Y마다 X가 슈퍼 키여야 제4정규형(4NF)이며, Y가 X에 포함되거나 X와 Y를 합쳐 R의 전체 속성이 되는 자명한 경우는 제외합니다.

이 예에서 사람은 한 행의 기술과 언어를 모두 정하지 못하므로 슈퍼 키가 아닙니다. (사람, 기술)과 (사람, 언어)로 나누면 기술 두 행과 언어 두 행을 한 번씩만 저장하고, JOIN으로 네 조합을 되살립니다. 새 기술 Rust를 더할 때도 언어의 수만큼 같은 기술을 여러 번 쓰지 않아도 됩니다. 실습은 board_lab을 바꾸지 않도록 cs_db_lab에 만듭니다.

CREATE DATABASE IF NOT EXISTS cs_db_lab;
DROP TABLE IF EXISTS cs_db_lab.cs_nf_skills;
DROP TABLE IF EXISTS cs_db_lab.cs_nf_languages;

CREATE TABLE cs_db_lab.cs_nf_skills (
  person VARCHAR(20),
  skill VARCHAR(20),
  PRIMARY KEY (person, skill)
);
CREATE TABLE cs_db_lab.cs_nf_languages (
  person VARCHAR(20),
  language VARCHAR(20),
  PRIMARY KEY (person, language)
);
INSERT INTO cs_db_lab.cs_nf_skills VALUES ('민', 'Python'), ('민', 'SQL');
INSERT INTO cs_db_lab.cs_nf_languages VALUES ('민', '한국어'), ('민', '영어');

SELECT s.person, s.skill, l.language
FROM cs_db_lab.cs_nf_skills AS s
JOIN cs_db_lab.cs_nf_languages AS l ON l.person = s.person
ORDER BY s.skill, l.language;

person | skill  | language
민     | Python | 영어
민     | Python | 한국어
민     | SQL    | 영어
민     | SQL    | 한국어

결과는 앞의 표와 같은 네 조합입니다. 정렬 규칙 utf8mb4_0900_ai_ci에서 '영어'가 '한국어'보다 앞서므로 언어는 영어부터 나옵니다. 이 JOIN이 원래의 관계를 되살리는 이유는 기술과 언어가 독립이라는 전제 하나뿐입니다.

"민은 Python으로 영어 프로젝트만, SQL로 한국어 프로젝트만 한다"처럼 기술과 언어의 조합 자체가 사실이라면, 두 표로 나눈 JOIN은 없던 조합 두 개를 만들어 잘못됩니다. 그래서 지금 저장된 행만 보고 독립이라고 가정하지 않고, 업무 규칙으로 독립을 확인합니다.

5NF와 조인 종속

조인 종속(join dependency)은 관계를 여러 투영으로 나누었다가 JOIN하면 원래의 관계와 정확히 같아진다는 조건입니다. 제5정규형(5NF)은 비자명한 조인 종속이 후보 키로부터 함의되는 경우만 허용합니다. 후보 키와 다치 종속, 조인 종속은 업무상 가능한 모든 관계를 대상으로 판단하며, 데이터 표본 하나에서 JOIN이 우연히 맞았다고 증명되지 않습니다.

공급자와 부품, 프로젝트의 관계를 공급자-부품, 공급자-프로젝트, 부품-프로젝트의 세 쌍으로 나누면 언제나 무손실일까요? 다음은 그렇지 않은 반례입니다.

DROP TABLE IF EXISTS cs_db_lab.cs_nf_supplies;
CREATE TABLE cs_db_lab.cs_nf_supplies (
  supplier VARCHAR(10),
  part VARCHAR(10),
  project VARCHAR(10),
  PRIMARY KEY (supplier, part, project)
);
INSERT INTO cs_db_lab.cs_nf_supplies VALUES
  ('A', 'X', 'P'), ('A', 'Y', 'Q'), ('B', 'X', 'Q');

WITH sp AS (SELECT DISTINCT supplier, part FROM cs_db_lab.cs_nf_supplies),
sj AS (SELECT DISTINCT supplier, project FROM cs_db_lab.cs_nf_supplies),
pj AS (SELECT DISTINCT part, project FROM cs_db_lab.cs_nf_supplies)
SELECT sp.supplier, sp.part, sj.project
FROM sp
JOIN sj ON sj.supplier = sp.supplier
JOIN pj ON pj.part = sp.part AND pj.project = sj.project
ORDER BY sp.supplier, sp.part, sj.project;

supplier | part | project
A        | X    | P
A        | X    | Q
A        | Y    | Q
B        | X    | Q

원래의 관계는 세 행인데 결과는 네 행입니다. 새로 생긴 (A, X, Q)는 AX, AQ, XQ라는 쌍이 각 투영에 있어서 만들어졌지만, 실제 공급 사실로 저장된 적은 없습니다. 이런 가짜 튜플(spurious tuple)은 SQL 오류 없이 생기며, 세 쌍에 유일성을 선언해도 이 조합의 뜻을 저절로 증명하지 못합니다.

업무 규칙이 "세 쌍이 모두 허용되면 그 세 값의 공급도 언제나 허용된다"라면, 관계에는 (A, X, Q)까지 들어 있어야 합니다. 이 규칙 아래에서는 세 투영을 통한 무손실 분해를 논의할 수 있습니다. 그러나 실제 공급 승인처럼 세 값의 조합을 따로 승인한다면 원래의 삼중 관계를 유지하며, 허용할 수 있는 조합과 실제로 일어난 기록도 섞지 않습니다.

기호를 예제의 키와 중간 표로 풀기

4NF 예제의 전체 속성을 R = {사람, 기술, 언어}, X = {사람}, Y = {기술}로 놓습니다. Y가 X에 들어 있지 않고 X와 Y를 합쳐도 R 전체가 아니므로 사람 →→ 기술은 비자명합니다. 사람만으로는 같은 사람의 네 행을 구별할 수 없으므로 슈퍼 키가 아니며, 다른 함수 종속이 없다면 세 속성을 모두 가져야 행을 구별합니다. 이것이 네 행의 표가 4NF를 어기는 지점입니다.

두 투영은 (민, Python), (민, SQL)과 (민, 한국어), (민, 영어)이고, 같은 사람의 기술과 언어를 교차해 네 행을 만듭니다. 다치 종속의 독립성은, 같은 사람의 두 행에서 기술과 언어를 서로 바꾼 행도 유효한 관계에 있어야 한다는 조건입니다. 이 규칙이 모든 유효한 관계에 적용될 때, 분해한 관계의 JOIN은 없던 사실을 더하지 않습니다. 두 가지 조합만 승인하는 규칙에서는 이 조건이 성립하지 않습니다.

5NF 반례의 세 투영은 다음과 같습니다.

SP와 SJ를 공급자로 먼저 JOIN하면 AXP, AXQ, AYP, AYQ, BXQ의 다섯 후보가 나옵니다. 그중 PJ에 없는 YP 쌍을 가진 AYP를 빼면 AXP, AXQ, AYQ, BXQ의 네 행이 남습니다. AXQ는 AX와 AQ, XQ가 각 투영에 있어 만들어지지만 원래의 관계에는 없습니다.

AXQ를 채운 네 행에서는 SP가 프로젝트를 정하지 못하고(AX에서 P와 Q), SJ가 부품을 정하지 못하며(AQ에서 X와 Y), PJ가 공급자를 정하지 못합니다(XQ에서 A와 B). 다른 함수 종속이 없다는 업무 가정에서 후보 키는 세 속성 전체입니다. 원래의 세 행도 전체 키로는 유일하지만 JOIN의 일치가 깨졌으므로, 세 속성 키의 유일성만으로 이 세 투영의 조인 종속이 함의되지는 않습니다.

반대로 "세 쌍의 허용이 곧 삼중의 허용"을 모든 유효한 관계의 규칙으로 정하면, 비자명한 조인 종속이 따로 생기고 그 규칙에 맞추어 세 쌍의 표로 분해할 수 있습니다. 표본에 AXQ를 더하는 것과 그 업무 규칙을 채택하는 것은 서로 다른 결정입니다. 이 전개는 이 예제의 키와 종속, 중간 JOIN을 판정한 것이며, 임의의 스키마에서 모든 후보 키와 조인 종속을 찾는 일반 알고리즘이나 증명을 대신하지 않습니다(교재 저자의 정규화 슬라이드).

분해를 검토하는 순서

세 번째 단계가 앞의 두 단계와 따로 있는 이유가 있습니다. 현재 등급 Gold의 할인율이 20%와 5%의 두 값이라면 등급 → 할인율이라는 규칙을 이미 어긴 것이므로, 그 상태를 정상 관계로 가정하고 정규형의 분해를 진행하면 안 됩니다. 데이터를 교정하거나 "등급과 기간별 할인" 같은 실제 규칙을 다시 정하는 것이 먼저이며, 함수 종속 본문이 이런 업무 가정과 무손실, 종속 보존을 구분합니다.

정리

• 다치 종속 X →→ Y는 X가 같은 행들 사이에서 Y의 값과 나머지 속성의 값이 서로 독립으로 조합된다는 규칙입니다.
• 4NF는 비자명한 다치 종속마다 결정자가 슈퍼 키이길 요구하며, 독립인 목록을 따로 저장하게 합니다.
• 5NF는 비자명한 조인 종속이 후보 키로부터 함의되기를 요구하고, 세 투영의 JOIN은 가짜 튜플을 만들 수 있습니다.
• 표본 하나의 JOIN 일치는 무손실의 증명이 아니며, 독립과 조합의 허용은 업무 규칙으로 정합니다.
• 높은 정규형은 번호를 외우는 것보다, 독립인 사실과 실제로 일어난 조합의 사실을 구별하는 도구로 씁니다.

연습 문제

1. 기술 하나를 더하면

기술과 언어 예제에서 민의 기술로 Rust를 더하면, 분리한 표에 더해지는 행의 수와 JOIN 결과가 늘어나는 행의 수는 각각 얼마인가요? 분리하지 않은 네 행의 표였다면 몇 행을 더해야 하나요?

2. 표본이 맞으면 안전한가

공급 반례에 (A, X, Q)를 더하면 세 투영의 JOIN이 원래의 관계와 같은 네 행이 됩니다. 그렇다면 앞으로의 모든 데이터에서도 세 쌍으로 나누어 저장해도 안전하다고 할 수 있을까요? 이어서 (B, Y, P)를 더하면 JOIN은 몇 행이 되나요?

다음 글 공통 코드 테이블부터는 13장의 설계 패턴으로 넘어가, 상태와 분류 같은 코드 값을 어디에 어떻게 저장할지 다룹니다.