03_관계 대수

Supplementary Materials

Database System Concepts (7th Edition)

• 2. Introduction to the Relational Model

1. 관계 대수의 기본 개념

질의 언어의 종류

절차적 질의 언어

• 원하는 결과/데이터(what)와 그 결과/데이터를 어떻게 찾을지(how)를 기술한다.

비절차적·선언적 질의 언어

• 원하는 결과/데이터(what)만 기술한다. 그 결과/데이터를 어떻게 찾을지(how)는 DBMS가 결정한다.
• RDBMS의 SQL(Structured Query Language)이 대표적인 예이다.
• SQL만으로 사용자 입력, 화면 출력, 네트워크 통신 등을 처리하기는 어려우므로 Java·Python 등의 언어에서 JDBC·ODBC 같은 인터페이스를 통해 사용한다.

관계형 질의 언어

대표적인 순수 관계형 질의 언어는 다음과 같다.

• 관계대수
• 튜플 관계해석
• 도메인 관계해석
• 세 언어의 계산 능력은 서로 동등하며, 이 자료는 관계대수를 중심으로 설명한다.

관계 해석 (Relational Calculus)

• 원하는 데이터가 무엇인지 명시하는 선언적 언어

관계 대수 (Relational Algebra)

• 결과를 얻는 연산 절차를 명시하는 절차적 언어
• RDBMS들에서 널리 사용되는 SQL의 이론적인 기반이다.

2. 관계 대수의 연산

관계 대수 연산

• 피연산자: 단항 연산자는 1개의 릴레이션, 이항 연산자는 2개의 릴레이션을 입력받는다.
• 연산 결과: 1개의 새로운 릴레이션을 반환한다.
• 릴레이션은 중복 튜플을 허용하지 않으므로, 결과 릴레이션도 중복을 갖지 않는다.
• 연산 결과를 다시 다른 연산의 입력으로 사용할 수 있다. (중첩/합성/폐쇄성)

2.1. 관계 대수의 완전성을 위한 연산

기본 연산은 다음과 같다.

• 셀렉션, 프로젝션, 합집합, 차집합, 카티션 곱

관계적으로 완전 (relationally complete)

• 어떤 질의어가 이 필수 연산자만큼의 표현력을 가지면 관계적으로 완전하다고 한다.

다른 연산자는 이들을 조합해 표현할 수 있다.

• 교집합은 차집합을 이용해 표현 가능
• 조인은 셀렉션 + 카티션 곱
• 디비전은 프로젝션 + 카티션 곱 + 차집합

셀렉션

셀렉션 (selection; $\sigma$; 선택) ${\sigma }_{<\text{predicate}>}(\text{relation})$

• 한 릴레이션에서, 셀렉션 조건을 만족하는 튜플을 선택한다.
  • 릴레이션의 수평적 부분집합(행)을 구한다.
• 차수 유지
  • 원 릴레이션 차수 == 결과 릴레이션 차수
• 카디널리티 감소 가능
  • 원 릴레이션 카디널리티 >= 결과 릴레이션 카디널리티

조건

• =, <>, <, <=, >, >=

복합 조건에는 다음 연산자를 사용할 수 있다.

• ∧(AND), ∨(OR), ¬(NOT)
• 여러 셀렉션 조건은 한 번에 적용하거나 순차적으로 적용할 수 있다.
• 속성과 상수뿐 아니라 두 속성끼리도 비교할 수 있다.

프로젝션

프로젝션 (projection; $\pi$; 투영) ${\pi }_{<\text{attribute list}>}(\text{relation})$

• 필요한 속성만 남긴다.
  • 릴레이션의 수직적 부분집합(열)을 구한다.
  • (속성들의 부분 집합으로 구성된 튜플을 구한다.)

관계는 집합이므로, 프로젝션 결과에서 동일한 튜플이 생기면 중복을 제거한다.

• 차수 감소
• 원 릴레이션의 카디널리티 >= 결과 릴레이션 카디널리티

유니언

합집합 호환(union compatible)

• 집합 연산(합집합·차집합·교집합)이 가능하려면,
• 두 릴레이션의 차수가 같고, 대응하는 속성의 도메인이 같아야 한다.

유니언 (union; $\cup$; 합집합) $R\cup S$

• 두 관계의 튜플을 결합한다.

결과

• 차수는 R 또는 S의 차수와 같다.
• 카디널리티는 R과 S의 카디널리티를 더한 것과 같거나 적다.

디퍼런스

디퍼런스 (difference; $-$; 차집합) $R-S$

• 첫 번째 릴레이션에는 있지만, 두 번째 릴레이션에는 없는 튜플을 반환한다.
• 결과 릴레이션의 차수는 R 또는 S의 차수와 같다.

차집합은 교환법칙이 성립하지 않는다. 순서에 따라 결과가 달라진다. ($R-S\ne S-R$)

• R–S의 카디널리티는 릴레이션 R의 카디널리티와 같거나 적다.
• S–R의 카디널리티는 릴레이션 S의 카디널리티와 같거나 적다.

카테시안 곱

카테시안 곱 (cartesian product; $\times$) $R\times S$

• 두 릴레이션의 가능한 모든 튜플 조합을 만든다.

  • (R의 각 튜플과 S의 모든 튜플을 연결한다.)

• 결과가 매우 커질 수 있으며, 일반적으로 선택 연산과 결합해 조인을 표현한다.

  • (R ⋈조건 S = σ조건(R × S))

결과

• 차수와 카디널리티가 크게 증가한다.
• R의 차수가 $a$, 카디널리티가 $n$이고 S의 차수가 $b$, 카디널리티가 $m$라면:
• 카티션 곱의 차수 = $a+b$
• 카티션 곱의 카디널리티 = $n\times m$

두 관계에 같은 속성명이 있으면 관계 이름을 붙여 구분한다. (관계명.속성명)

2.2. 기본 연산에서 유도된 연산

인터섹션

인터섹션 (intersection; 교집합) $R\cap S$

• 두 릴레이션에 모두 존재하는 튜플을 반환한다.

결과

• 차수는 R 또는 S의 차수와 같다.
• 카디널리티는 R과 S의 어떤 카디널리티보다 크지 않다. (같거나 적다.)

조인

조인 (join) $R\bowtie S$

• 카테시안 곱 중, 조건에 맞는 튜플만 선택한다.

세타 조인 (theta join) $R{\bowtie }_{A𝜽B}S$

• 비교 연산자 $\theta$가 사용되며, =, ≠, <, >, ≤, ≥ 등의 비교 조건으로 튜플을 결합한다.

동등 조인 (equi join) $R{\bowtie }_{A=B}S$

• 세타 조인 중 비교 연산자가 $=$인 경우의 조인이다.

자연 조인 (natural join) $R\bowtie S$

• 동등 조인에서 중복되는 조인 속성 하나를 제외한다.

세미 조인

• 조인 결과 중 한쪽 릴레이션의 애트리뷰트만 반환

디비전

디비전 (division) $R÷S$

• 디비전은 “주어진 조건을 모두 만족하는 튜플”을 찾을 때 사용한다.

R(A, B) ÷ S(B)

S에 포함된 모든 B값과 관계를 맺고 있는 A값을 반환한다.

대표적인 질의:

• 필수 교과목을 모두 수강한 학생
• 지정된 도시를 모두 방문한 여행객
• 지정된 제품을 모두 주문한 고객 따라서 문제에 “모두”, “전부”, “모든 항목”이라는 표현이 나오면 디비전을 먼저 떠올리면 된다.

2.3. 추가로 지원하는 연산

전통적인 관계 대수의 한계는 다음과 같다.

• 산술 연산을 직접 표현하기 어렵다.
• SUM, AVG, MIN, COUNT 같은 집단 함수를 지원하지 않는다.
• 정렬을 표현할 수 없다.
• 데이터 삽입·수정·삭제를 표현하지 않는다.
• 중복을 의도적으로 유지하기 어렵다.

SQL은 이러한 한계를 보완해 집단 함수, 그룹화, 정렬, 외부 조인, 데이터 변경 등을 지원한다.

외부 조인

외부 조인 (outer join)

• 일반 조인은 대응되는 튜플이 없으면, 해당 튜플이 결과에서 제외된다.
• 외부 조인은 대응되는 튜플이 없어도, 외부 조인 방향의 튜플을 결과에 보존하고, 나머지를 NULL값으로 채운다.

왼쪽 외부 조인 (left outer join) $R⟕S$

• 왼쪽 릴레이션의 모든 튜플을 결과에서 보존한다.
• 대응되는 값이 없는 부분(오른쪽)을 NULL로 채운다.

오른쪽 외부 조인 (right outer join) $R⟖S$

• 오른쪽 릴레이션의 모든 튜플을 결과에서 보존한다.
• 대응되는 값이 없는 부분(왼쪽)을 NULL로 채운다.

완전 외부 조인 (full outer join) $R⟗S$

• 양쪽 릴레이션의 모든 튜플을 결과에서 보존한다.

집계 함수와 그룹화

주요 집계 함수는 다음과 같다.

• avg: 평균
• min: 최솟값
• max: 최댓값
• sum: 합계
• count: 개수

관계 자체는 중복이 없는 집합이지만, 집계 함수는 특정 열의 값들을 중복을 포함하는 다중집합으로 취급할 수 있다는 점에 주의해야 한다.

2.4. 기타 연산

대입

복잡한 관계대수 표현식의 중간 결과를 임시 관계에 저장한다.

Physics ← σ dept_name="Physics" (instructor)
Music   ← σ dept_name="Music" (instructor)
Physics ∪ Music

질의를 여러 단계로 나눠 읽기 쉽게 만들 수 있다.

이름 변경

이름 변경 ($\rho$)

• 관계나 속성의 이름을 변경한다.
• 자기 자신과의 조인처럼 같은 관계를 여러 번 사용할 때 특히 중요하다.

3. 질의

3.1. 복합 질의

관계대수 연산 결과는 다시 관계이므로 연산을 중첩할 수 있다.

관계 대수식은 보통 안쪽 연산부터 실행한다.

“개발 부서에서 근무하는 사원의 이름”:

πEMPNAME(
  EMPLOYEE ⋈DNO=DEPTNO
  (σDEPTNAME='개발'(DEPARTMENT))
)

실행 순서는 다음과 같다.

1. 개발 부서를 선택한다.
2. 사원 릴레이션과 부서번호로 조인한다.
3. 사원 이름만 프로젝션한다.

즉, 일반적으로 선택 → 조인 → 프로젝션 순서로 생각하면 복합 질의를 작성하기 쉽다.

3.2. 동치 질의

표현 방법이 달라도 모든 데이터베이스 인스턴스에서 같은 결과가 나오면 두 질의는 동치이다. 동치 질의는 결과가 같지만 실행 비용은 다를 수 있다.

다음 두 식은 같은 결과를 낸다.

• σ dept_name=“Physics” ∧ salary>90000 (instructor)
• σ dept_name=“Physics” (σ salary>90000 (instructor))

조인에서도 선택 연산을 먼저 수행할 수 있다.

• σ dept_name=“Physics” (instructor ⋈ instructor.ID=teaches.ID teaches)
• (σ dept_name=“Physics” (instructor)) ⋈ instructor.ID=teaches.ID teaches 두 번째 방식은 조인 전에 데이터의 양을 줄일 수 있어 일반적으로 실행 효율이 좋다. 이런 동치 변환이 데이터베이스의 질의 최적화에 활용된다.

예제

강의 예제

질의: 주문 수량이 10개 미만인 주문 내역을 제외하고 검색하시오.

• 일단은 ${\sigma }_{\text{수량}\ge 10}(\text{주문})$인데
• 차집합 연산을 포함해서 풀라고 하면 $주문-{\sigma }_{\text{수량}<10}(주문)$
• 이런 식으로 유연성 있는 시험 문제 풀이 필요

과제 예제

Q. 다음 릴레이션 스키마를 보고 질의에 관계대수식으로 표현하시오.

CUSTOMER(CUSTOMER_ID, NAME, ADDRESS, PHONE)
VIDEO(VIDEO_ID, TITLE, GENRE)
RESERVED(CUSTOMER_ID, VIDEO_ID, DATE)

*단, alias로 C, V, R, CID, VID 사용*

1. 제목이 ‘Twilight’인 비디오 테이프의 장르를 검색하시오.

\sigma_{TITLE='Twilight'}(V) )$$ 2. 예약되지 않은 비디오 테이프의 ID를 검색하시오. $$\pi_{VID}(V)-\pi_{VID}(R)$$ 3. 비디오 테이프를 예약한 고객의 이름과 주소를 검색하시오. $$\pi_{NAME,ADDRESS}( C⋈_{C.CID=R.CID}R )$$ 4. 장르가 ‘Fantasy’인 비디오 테이프를 예약한 고객의 이름을 검색하시오. $$\pi_{NAME}( \sigma_{GENRE='Fantasy'}(V) ⋈_{V.VID=R.VID}R ⋈_{R.CID=C.CID}C )$$