[데이터베이스] #4. 관계 대수

1. 관계 대수 연산

- 릴레이션을 내부적으로 처리하기 위한 연산들의 집합

- SQL 데이터베이스 언어의 이론적 토대를 제공

- 모든 연산의 적용 대상도 릴레이션이고, 연산 결과 또한 릴레이션

- 2개의 그룹으로 분류; 수학 집합 이론에 기반을 둔 집합 연산 그룹과 관계형 데이터 모델을 위해 추가된 관계 연산 그룹

 

1.1 집합 연산

- 일반적인 수학의 집합 연산과 의미와 기능이 같음

- 합집합, 교집합, 차집합 연산은 두 입력 릴레이션이 서로 합병 가능(union compatible)해야 함

- 합병 가능하려면, 두 릴레이션의 차수가 같고 대응하는 속성의 순서와 도메인이 같아야 함

- 속성 이름은 서로 달라도 되며 연산 적용 후 결과 릴레이션의 속성 이름은 첫번째 릴레이션의 속성 이름을 따름

 

합집합

- 두 릴레이션을 합병하여 하나의 릴레이션을 반환

- 튜플 기준으로 합병; 두 릴레이션에 속하는 모든 튜플들로 구성된 릴레이션이 결과

- 중복된 튜플은 자동으로 제거

 

 

교집합

- 결과는 두 릴레이션에 동시에 속하는 공통 튜플로만 구성된 릴레이션

 

 

차집합

- 첫번째 릴레이션에만 속하고 두번째에는 속하지 않는 튜플로만 구성된 릴레이션

 

 

카티션 프로덕트(X)

- 결과는 두 릴레이션 튜플들의 모든 조합으로 구성된 릴레이션

 

 

차집합을 제외한 합집합, 교집합, 카티션 프로덕트 연산은 교환 법칙, 결합 법칙이 성림

 

R1 Op R2 = R2 Op R1 -> 교환 법칙

(R1 Op R2) Op R3 = R1 Op (R2 Op R3) -> 결합 법칙

 

 

1.2 관계 연산

- 릴레이션의 구조적 특성에 기반은 둔 연산

- 관계형 데이터 모델을 위해 고안된 연산들

 

SELECT

- 하나의 릴레이션만을 대상으로 하는 단항 연산

- 특정 튜플들을 추출하는 연산

PROJECT

- 특정 속성들을 추출하는 연산

JOIN

- 두 릴레이션의 공통 속성을 기준으로 조인 조건을 만족하는 튜플을 수평으로 결합하는 연산

- 원하는 데이터가 둘 이상의 릴레이션에 흩어져 있는 경우, 두 릴레이션의 관련 튜플을 조합하여 하나의 릴레이션을 구성하고 싶을 때 사용

- 카티션 프로젝트 결과에 조건식으로 SELECT한 결과와 동일

- 보통 조인 조건식으로 기본키와 외래키를 사용 - 속성 이름이 다르더라도 도메인만 같으면 됨

 

세타 조인

- 조인 조건식에 6개의 비교 연산자 중 하나를 사용 하는 조인

 

동등 조인

- 조인 조건식에 특별히 '=' 비교연산자만을 사용하는 세타 조인

- 보통 말하는 조인 연산이 동등 조인

자연 조인

- 동등 조인의 결과 릴레이션에서 중복 속성이 나오지 않도록 제거한 결과

 

 

 

 

디비전

- R1 Op R2일 때, R1이 R2의 모든 속성을 포함하고 있어야 연산 적용 가능

 

기본 연산과 복합 연산

- 복합 연산은 여러 기본 연산들의 조합으로 대체 가능한 연산을 말함

 

기본 연산

- 어떤 연산을 조합하더라도 같은 결과를 반환할 수 없는 기본 연산

- 합집합, 차집합, 카티션 프로덕트, 셀렉트, 프로젝트

 

복합 연산

- 여러 연산들을 조합하여 같은 연산 결과를 반환할 수 있는 연산

- 교집합, 조인, 디비전

 

 

1.3 확장 연산

- 기존 관계 대수 연산을 확장하여 추가로 정의한 몇 가지 유용한 확장 연산

 

세미 조인

- 자연 조인이 반환하는 결과 릴레이션 중에서 한 쪽 릴레이션 속성만으로 한정하여 반환하는 제한적 자연 조인 연산

 

왼쪽 세미 조인

- 자연 조인 결과 중 왼쪽 릴레이션의 속성만 반환

 

 

오른쪽 세미 조인 

- 자연 조인 결과 중 오른쪽 릴레이션의 속성만 반환

 

 

외부 조인

- 자연 조인 결과에 포함되지 않는, 조인에 실패한 튜플까지 모두 포함하도록 확장한 연산

- 대응 속성없이 추가된 튜플들은 널 값을 채워 반환

- 외부 조인이 아닌 모든 조인들은 조인 조건을 만족하는 튜플만을 결과 릴레이션에 포함하므로 내부 조인

- 모든 튜플을 반환하는 대상 릴레이션의 위치에 따라 완전 외부 조인, 왼쪽 외부 조인, 오른쪽 외부 조인으로 분류

 

완전 외부 조인

 

 

왼쪽 외부 조인

 

 

오른쪽 외부 조인

 

외부 합집합(U+)

- 합병 가능하지 않은, 즉 부분적으로만 합병 가능한 두 릴레이션의 튜플을 합병

- 대응하는 속성이 없는 경우도 널 값을 채워 모든 튜플을 결과 릴레이션에 포함

- 따라서 각 릴레이션의 모든 튜플이 결과 릴레이션에 포함

 

2. DBMS가 관계 대수를 어떻게 활용하는지?

- 데이터베이스 사용자는 사용자의 요청 사항을 SQL 데이터베이스 언어를 사용하여 DBMS에게 전달한다. 사용자가 요청한 SQL 문장은 DBMS 내부에서 해석되어 처리된다. 절차가 명세되지 않은 SQL 문장을 내부적으로 처리하기 위해서 DBMS는 그 처리 순서와 방법을 결정해야 한다. DBMS는 SQL 질의문을 처리하기 위해 내부적으로 관계 대수식을 스스로 작성하고 연산자를 순서대로 적용함으로써 질의 결과를 생성해낸다.

 

질의 요청을 여러 관계 대수식으로 표현하고, 여러 관계 대수식 중에서 최적의 관계 대수식 하나를 질의 트리를 통해 선정함

질의 트리에서, 가장 먼저 실행되어야 하는 연산은 leaf 노드

실행 순서는 질의 트리의 맨 아래쪽 릴레이션을 대상으로 시작해서 한 단계씩 위쪽의 연산자를 순차적으로 적용해 나간다

 

질의 트리에서 단말 노드는 릴레이션, 중간 노드는 관계 대수 연산자.

질의 트리의 실행은 단말 노드의 릴레이션을 대상으로 부모 노드의 연산자를 적용하고 그 결과에 다시 상위 노드의 연산자를 적용하는 과정을 계속 반복

 

질의 최적화의 핵심은 연산 순서를 조정함으로써 연산으로 생기는 중간 릴레이션의 크기를 최소화하는 것