관계대수와 관계해석

관계대수와 관계해석의 관점

관계형 데이터베이스의 질의 이론은 크게 관계대수(Relational Algebra)와 관계해석(Relational Calculus)의 관점으로 설명할 수 있다.

관계대수가 절차적이라는 말은 고수준의 논리 연산을 어떤 순서로 조합했는지 표현한다는 뜻이다. 파일을 어느 블록부터 읽을지, 어떤 인덱스를 사용할지, 중첩 루프·해시·병합 중 어떤 물리 조인을 사용할지까지 지정한다는 뜻은 아니다. 같은 결과를 만드는 동치 관계대수식이 여러 개 존재할 수 있고, DBMS는 이를 변환해 더 유리한 실행계획을 선택할 수 있다.

관계해석은 결과를 얻는 연산 순서보다 결과가 만족해야 하는 조건을 기술한다. SQL도 일반적으로 원하는 결과를 선언하고 실제 접근 방법은 DBMS가 결정한다는 점에서 관계해석적·선언적 성격을 가진다.

관계대수의 폐쇄성

관계대수는 릴레이션을 입력받아 다시 릴레이션을 반환한다. 결과를 다음 연산의 입력으로 쓸 수 있는 성질이 폐쇄성이다.

π_name(σ_dept='CS'(STUDENT))는 학과가 CS인 튜플을 선택한 뒤 이름을 투영한다. 고전 관계대수는 집합 의미이므로 중복 튜플과 저장 순서에 의미가 없다. 일반 SQL 조회는 중복을 허용할 수 있다.

폐쇄성은 그래프에서 도달 가능한 경로를 구하는 전이 폐쇄와 다른 개념이다.

관계대수 연산의 두 가지 분류 축

시험 자료에서는 관계대수 연산을 서로 다른 기준으로 분류한다. 다음 두 분류를 같은 기준처럼 섞으면 안 된다.

집합 연산과 순수 관계 연산

이 분류는 연산의 성격과 기원을 기준으로 한다.

기본 연산과 유도 연산

일반적으로 다음 연산 집합만으로 다른 여러 관계대수 연산을 표현할 수 있다.

선택 σ, 투영 π, 합집합 ∪, 차집합 −, 카티션 곱 ×

속성·릴레이션 이름 충돌을 해결하기 위해 **이름 변경 ρ**도 기본 연산에 함께 포함해 설명하는 경우가 많다.

다음 연산은 위 기본 연산을 조합해 유도할 수 있다.

• 교집합: 차집합을 반복해 표현 가능
• 세타 조인: 카티션 곱 후 선택으로 표현 가능
• 자연 조인: 동등 조인 후 중복 공통 속성을 투영으로 제거
• 디비전: 투영·곱·차집합을 조합해 표현 가능

따라서 조인이 순수 관계 연산이라는 사실과 조인이 유도 연산이라는 사실은 동시에 성립할 수 있다. 집합/순수와 기본/유도는 서로 다른 분류 축이다.

핵심 관계대수 연산

다음 표에서 차수(Degree)는 속성 수, 카디널리티(Cardinality)는 튜플 수를 뜻한다.

선택: 행을 고른다

선택(Selection)은 조건을 만족하는 튜플만 남기는 단항 연산이다.

σ_dept='CS'(STUDENT)

• 속성은 제거하지 않으므로 결과 차수는 원래 릴레이션과 같다.
• 조건을 만족하는 튜플만 남으므로 결과 카디널리티는 원래보다 커질 수 없다.
• 조건에는 비교식과 논리 연산 ∧, ∨, ¬ 등을 사용할 수 있다.

관계대수의 선택은 SQL의 WHERE에 대응한다. 이름이 같다고 SQL의 SELECT 절과 연결하면 안 된다.

SELECT *
FROM student
WHERE dept = 'CS';

투영: 열을 고른다

투영(Projection)은 필요한 속성만 남기는 단항 연산이다.

π_name,dept(STUDENT)

고전적 관계대수는 집합 의미를 사용하므로 투영 결과에서 같은 튜플이 생기면 중복을 제거한다.

원본 dept 값: {CS, EE, CS}
π_dept(STUDENT): {CS, EE}

따라서 투영은 차수를 줄일 뿐 아니라 중복 제거 때문에 카디널리티도 줄일 수 있다. SQL에서 관계대수의 투영과 같은 집합 결과를 의도한다면 보통 DISTINCT가 필요하다.

SELECT DISTINCT dept
FROM student;

이름 변경: 같은 이름의 충돌을 막는다

이름 변경(Rename)은 릴레이션이나 속성에 새로운 이름을 부여한다.

ρ_S(sid, sname, department)(STUDENT)

자기 조인을 표현하거나, 집합 연산의 속성 이름을 맞추거나, 카티션 곱에서 같은 속성 이름을 구분할 때 사용한다. 이름만 바꾸며 튜플 수와 값은 바꾸지 않는다.

좌우로 이동해 그림을 확인하세요.그림 크게 보기

선택과 투영의 결과

원본 (1,A)·(2,A)·(3,B)에서 dept=A를 선택하면 모든 열을 유지한 (1,A)·(2,A)가 남는다. dept를 투영하면 중복을 제거한 A·B가 남는다. 이는 고전 관계대수의 집합 의미이며 일반 SQL에는 DISTINCT가 필요할 수 있다.

집합 연산과 합병 가능성

합집합·교집합·차집합은 두 릴레이션이 합병 가능(Union Compatible)해야 한다.

1. 두 릴레이션의 속성 수, 즉 차수가 같아야 한다.
2. 대응하는 위치의 속성 도메인이 서로 호환되어야 한다.
3. 표기 체계에 따라 속성 이름까지 맞추어야 할 때에는 이름 변경 연산을 사용한다.

예를 들어 다음 두 단항 릴레이션을 보자.

R = {1, 2, 3}
S = {2, 3, 4}

차집합은 방향이 있으므로 일반적으로 교환법칙이 성립하지 않는다.

R − S ≠ S − R

합병 가능성은 합집합에만 필요한 조건이 아니다. 합집합·교집합·차집합 모두 같은 구조의 튜플을 비교하므로 필요하다. 카티션 곱과 조인은 합병 가능성을 요구하지 않는다.

카티션 곱과 조인

카티션 곱

카티션 곱(Cartesian Product)은 R의 각 튜플과 S의 각 튜플을 가능한 모든 조합으로 연결한다.

|R × S| = |R| × |S|
차수(R × S) = 차수(R) + 차수(S)

R이 3행·3열이고 S가 2행·1열이면 결과는 다음과 같다.

튜플 수: 3 × 2 = 6
속성 수: 3 + 1 = 4

한쪽 릴레이션이 0행이면 가능한 쌍이 없으므로 결과도 0행이다. 같은 속성 이름이 양쪽에 있으면 이름 변경으로 구분한 뒤 사용하는 것이 안전하다.

카티션 곱은 모든 조합을 만들기 때문에 단독으로는 불필요한 튜플이 많이 생길 수 있다. 조인은 보통 이 곱에서 조건을 만족하는 튜플만 남기는 방식으로 이해할 수 있다.

세타 조인과 동등 조인

세타 조인(Theta Join)은 비교 조건 θ를 만족하는 튜플 쌍만 결합한다.

R ⋈_θ S = σ_θ(R × S)

조건이 등호만으로 구성된 세타 조인이 동등 조인(Equi Join)이다.

EMPLOYEE ⋈_EMPLOYEE.dept_id=DEPARTMENT.dept_id DEPARTMENT

동등 조인은 비교에 사용한 두 속성을 모두 결과에 남길 수 있다.

자연 조인

자연 조인(Natural Join)은 두 릴레이션에서 이름이 같은 모든 속성을 동등 조건으로 비교하고, 결과에서는 공통 속성을 한 번만 남긴다.

R ⋈ S

공통 속성이 하나도 없다면 자연 조인은 카티션 곱과 같은 결과가 된다. 반대로 같은 이름의 속성이 여러 개라면 모두 조인 조건에 포함되므로, 의도하지 않은 동일 이름이 있으면 이름 변경 후 조인해야 한다.

조인의 결과 행 수는 단순히 두 입력 중 작은 행 수와 같다고 계산할 수 없다. 일치하는 행이 없으면 0행이고, 한 튜플이 상대 릴레이션의 여러 튜플과 일치하면 행 수가 증가할 수 있으며, 최대 카티션 곱의 행 수까지 가능하다.

디비전: ‘모든 조건’을 만족하는 대상

디비전(Division)은 “어떤 집합의 모든 값과 관계를 맺은 대상”을 찾는 연산이다.

R(X, Y) ÷ S(Y) → 결과 스키마 X

결과에는 S의 모든 Y값과 연결된 X값이 들어간다.

다음 릴레이션을 사용한다.

ENROLL

REQUIRED

ENROLL(student_id, course_id) ÷ REQUIRED(course_id)

결과는 {1, 3}이다.

• 학생 1: DB와 OS를 모두 수강 → 포함
• 학생 2: OS가 없음 → 제외
• 학생 3: DB와 OS를 모두 수강하고 AI도 수강 → 포함

추가 과목을 수강했다고 제외되는 것이 아니다. 디비전은 S의 모든 값을 포함하는지 확인하며, S에 없는 값을 추가로 갖는 것은 허용한다.

관계대수식 읽기와 동치 변환

관계대수식은 가장 안쪽 연산부터 결과 릴레이션을 추적한다.

π_name(σ_dept='CS'(STUDENT))

1. σ_dept='CS'(STUDENT): CS 학생의 모든 속성
2. π_name(...): 그 결과에서 이름만 남김

다음 식은 결과가 다를 수 있다.

σ_dept='CS'(π_name(STUDENT))

먼저 이름만 투영하면 dept 속성이 사라져 뒤의 선택 조건을 평가할 수 없기 때문이다. 연산 순서를 임의로 바꾸려면 동치 조건을 확인해야 한다.

대표적인 동치 법칙은 다음과 같다.

σ_p∧q(R) = σ_p(σ_q(R)) = σ_q(σ_p(R))

선택 조건의 결합은 여러 선택으로 나눌 수 있고 순서를 바꾸어도 결과가 같다.

π_A(π_B(R)) = π_A(R)    단, A ⊆ B

안쪽 투영이 바깥에서 필요한 모든 속성을 보존할 때 투영을 합칠 수 있다.

σ_p(R ⋈ S) = σ_p(R) ⋈ S

위 변환은 p가 R의 속성만 참조하는 내부 조인 문맥에서 적용할 수 있다. 조건을 조인 전에 내려 보내면 중간 릴레이션이 줄어들 수 있다. 외부 조인이나 양쪽 속성을 함께 참조하는 조건에는 같은 변환을 무조건 적용할 수 없다.

관계대수식의 연산 순서는 논리적 표현이다. 동치 변환으로 결과를 유지하면서 더 작은 중간 릴레이션을 만들 수 있고, 실제 DBMS는 이러한 원리를 질의 최적화에 활용한다.

관계해석의 기본 구조

관계해석은 결과가 만족할 조건을 술어 논리로 표현하는 비절차적 언어다. ∧는 AND, ∨는 OR, ¬는 NOT, ∃는 존재, ∀는 모든 값에 대한 조건을 뜻한다.

자유 변수는 결과를 구성하고, 한정자에 묶인 구속 변수는 조건 판정에 쓰인다. 필기에서는 변수의 단위와 조건 중심 표현을 구분한다.

관계해석의 안전성과 표현력

관계해석은 결과를 구하는 순서보다 결과가 만족할 조건을 기술하는 비절차적 언어다. 변수가 튜플 전체를 나타내면 튜플 관계해석, 속성값을 나타내면 도메인 관계해석이다.

데이터베이스 질의에서는 결과가 유한하게 정해지도록 변수의 범위를 실제 관계의 값과 조건으로 제한하는 안전한 식을 사용한다. 아무 범위 제한 없이 '저장되지 않은 모든 값'을 요구하면 무한한 결과가 생길 수 있다.

고전적인 관계대수와 안전한 관계해석은 표현력이 동등하다. 이것은 문법과 실행계획이 같다는 뜻이 아니다. 관계대수의 절차성도 디스크 읽기 순서를 직접 지정한다는 뜻이 아니라 선택·투영·조인 등의 논리 연산을 조합한다는 뜻이다.

관계대수와 SQL 대응

다음 질의는 같은 업무 요구를 관계대수와 SQL로 표현한 것이다.

요구: CS 학과 학생의 이름

관계대수:
π_name(σ_dept='CS'(STUDENT))

SELECT DISTINCT name
FROM student
WHERE dept = 'CS';

DISTINCT는 이름이 같은 학생이 여러 명일 때 관계대수의 집합 투영처럼 중복 이름을 한 번만 남기기 위해 사용했다. 실제 업무에서 동명이인을 구분해야 한다면 student_id를 함께 선택하는 등 요구 결과의 스키마를 다시 정해야 한다.

관계 연산에서 남는 속성과 후보를 확인하기

차집합 R−S는 R에 있고 S에는 없는 튜플을 남긴다. S−R과는 일반적으로 다르다. 합집합·교집합·차집합에서는 합병 가능성을, 카티션 곱·조인에서는 속성 충돌과 연결 조건을 확인한다.

디비전 R(X,Y)÷S(Y)는 S의 모든 Y와 짝을 이루는 X를 결과로 낸다. 나누는 릴레이션 S에 포함된 속성 Y는 결과에서 빠진다. R에 S가 요구하지 않은 추가 Y값이 있어도 요구된 모든 Y를 가졌다면 그 X를 배제하지 않는다. 이는 '정확히 같은 집합만 가지는가'와 다른 조건이다.

튜플 관계해석의 변수는 튜플 전체를, 도메인 관계해석의 변수는 개별 속성의 값을 나타낸다. 전칭 조건 '모든 y에 대해 P(y)'는 'P(y)가 아닌 반례 y가 존재하지 않는다'로 바꿀 수 있다. 후보 범위와 한정자의 적용 범위를 함께 적어야 한다.

세타 조인 R ⋈θ S는 이름 충돌을 정리했다는 전제에서 σθ(R × S)로 표현한다. 두 입력의 행 쌍을 모두 만든 뒤 조건을 만족하는 쌍을 남긴다는 논리적 의미다. DBMS가 실제로 모든 카티션 곱 행을 먼저 저장해야 한다는 뜻은 아니다.