관계 대수

Relational Algebra

관계 대수는 관계형 데이터베이스에서 데이터를 조회하고 조작하기 위한 수학적 언어를 말한다. 관계 대수는 테이블(관계)에 대한 여러 가지 연산을 정의하며, 이러한 연산을 통해 데이터를 필터링하고 조합할 수 있다.

개요

릴레이션 조작을 위한 연산의 집합으로 피연산자와 결과가 모두 릴레이션이다.
일반 집합 연산과 순수 관계 연산으로 구분된다.
질의에 대한 해를 구하기 위해 수행해야 할 연산의 순서를 명시한다.
원하는 정보와 그 정보를 어떻게 유도하는가를 기술하는 절차적 특징을 가지고 있다.
기본적으로 관계해석과 관계대수는 관계 데이터베이스를 처리하는 기능과 능력 면에서 동일하다.

요약

순수 관계 연산자

연산자	기호	표기법	설명	예시
SELECT	σ(시그마)	σ_<조건>(R)	조건을 만족하는 행(투플)을 고른다	σ_DNO=4(EMP)
PROJECT	π(파이)	π_<리스트>(R)	지정한 속성(열)만 뽑는다	π_DNO,NAME(EMP)
JOIN	⋈(보타이)	R⋈_<조건>S	두 릴레이션 결합	DEPT⋈_dssn=essn EMP
DIVISION	÷(나누기)	R÷S	R 중 S 기준 교집합	EMP÷DEPT

일반 집합 연산자

연산자	표기법	집합 표현	카디널리티
합집합	∪	R∪S = {t\|t∈R∨t∈S}	\|R∪S\|≤\|R\|+\|S\|
교집합	∩	R∩S = {t\|t∈R∧t∈S}	\|R∩S\|≤MIN(\|R\|,\|S\|)
차집합	-	R-S = {t\|t∈R∧t∉S}	\|R-S\|≤\|R\|
교차곱(=카티션 프로덕트, 크로스 조인)	×	R×S = {rs\|r∈R∧s∈S}	\|R×S\|=\|R\|×\|S\|

설명

DIVISION

DIVISION, 즉 DIVIDE 연산은 관계 대수(Relational Algebra)에서 특정 조건을 만족하는 모든 값을 가지는 튜플을 찾는 데 사용되는 연산이다. 특히, 이 연산은 "A가 B의 모든 조건을 만족하는가?"와 같은 상황을 처리하는 데 유용하다. 예를 들어, 모든 과목을 들은 학생이나 모든 상품을 구매한 고객을 찾는 문제에서 사용할 수 있다.

Divide 연산의 기본 개념

R ÷ S는 R의 속성 중 S의 속성들과 일치하는 속성들을 기준으로 나눈다는 의미이다.
R은 피제수(dividend)라고 하며, 이 관계는 전체 데이터가 포함되어 있다.
S는 제수(divisor)라고 하며, 이 관계는 조건을 나타낸다.
R ÷ S의 결과는 S에 있는 모든 값과 일치하는 R의 튜플들을 반환한다.

예시

R(학생 이름, 과목): 학생이 수강한 과목 정보 릴레이션
S(과목): 특정 과목들의 릴레이션 (예: {과목: 수학, 과학})
우리는 S에 있는 모든 과목을 들은 학생들을 찾고자 한다.

R

DIVIDED-BY

S

R÷S

학생 이름	과목
Alice	수학
Alice	영어
Bob	수학
Bob	과학
Charlie	수학
Charlie	영어
Charlie	과학

÷

과목
수학
영어

학생 이름
Alice
Charlie

DIVISION 을 기본 연산으로 나타내기

관계 대수의 기본 연산은 선택(σ), 추출(π), 합집합(∪), 차집합(-), 카티션 프로덕트(×), 개명(ρ)의 여섯 가지이고, 이 집합만으로 모든 관계 대수 질의를 나타낼 수 있다(완전 집합). 교집합, 조인, 디비전은 이것들로 바꿔 쓸 수 있는 유도 연산이다. R(X, Y) ÷ S(Y) 는 다음 세 단계로 나타낸다.

T1 = π_X(R) - R 에 나오는 X 값 후보 전부

T2 = π_X((T1 × S) - R) - S 의 Y 값 가운데 하나라도 짝이 없는 X 값

R ÷ S = T1 - T2

쓰이는 연산은 추출(π), 카티션 프로덕트(×), 차집합(-) 셋뿐이다. 선택(σ), 합집합(∪), 개명(ρ)은 필요 없다.
위 예에서 T1 = {Alice, Bob, Charlie} 이고, T1 × S 가운데 R 에 없는 행은 (Bob, 영어) 하나이므로 T2 = {Bob}, 결과는 T1 - T2 = {Alice, Charlie} 이다.
교집합은 R ∩ S = R - (R - S) 로, 세타 조인은 σ_조건(R × S) 로 나타낸다.

SQL 에는 나누기 연산자가 없어 NOT EXISTS 의 이중 부정으로 쓴다. "1번 부서의 모든 프로젝트에 참가한 직원"은 다음과 같다.

SELECT ENO FROM E
WHERE NOT EXISTS ( (SELECT PNO FROM P WHERE DNO = 1)
                   EXCEPT
                   (SELECT PNO FROM W WHERE W.ENO = E.ENO) );

1번 부서 프로젝트 집합에서 그 직원이 참가한 프로젝트를 뺀 결과가 비어 있으면(NOT EXISTS) 그 직원은 모든 프로젝트에 참가한 것이다. 두 번째 부속 질의는 바깥 E.ENO 를 참조하는 상관 부속 질의이며, 관계 대수로는 π_{ENO, PNO}(W) ÷ π_PNO(σ_DNO=1(P)) 와 같다. "참가하지 않은 직원"을 찾는 질의가 아니다 → 데이터베이스 서브 쿼리, SQL 집합 연산자

집계 및 그룹 함수

Aggregate Functions and Grouping

원래 그룹핑과 집계는 관계 대수에서 지원되지 않는다. 하지만 DB에서 흔하게 사용되는 SUM, AVERAGE, MAXIMUM, MINIMUM, COUNT 등을 표현하기 위해 후대에 생겨났다. 표현법은 아래와 같다.

_{<그루핑 속성>} ℑ _{<집계 함수>} (R)

예를 들어 SUM과 COUNT를 표현하려면 아래와 같이 할 수 있다.

SELECT SUM(RECORD) FROM EMP_PERFORM GROUP BY SSN -- 사람으로 묶여서 RECORD의 합을 구한다 _SSN ℑ _{SUM RECORD} (EMP_PERFORM)

SELECT COUNT(RECORD_NO) FROM EMP_PERFORM -- 특정 그룹핑 기준이 없을 경우 ℑ _{COUNT RECORD_NO} (EMP_PERFORM)

현대 SQL에서의 GROUP BY와 같이 집계 결과와, 집계 기준이 되는 속성만 SELECT를 할 수 있다. 집계된 결과들은 그 자체로 속성 명이 없기 때문에 별도로 부여할 수 있다. 새롭게 정의하는 속성명으로 구성된 집합을 만드는 것이다.

ρ_{R(Dno, No_of_employees, Average_sal)} (_Dno ℑ _{COUNT Ssn, AVERAGE Salary} (EMPLOYEE))

예시

아래 두 릴레이션을 사용하여 몇 가지 관계 대수 연산의 예를 살펴본다.

1. EMPLOYEE 테이블

Ssn	Name	Age	Dept_no
123-45-6789	Alice	30	1
234-56-7890	Bob	40	2
345-67-8901	Charlie	35	1
456-78-9012	David	28	3
567-89-0123	Eva	50	2

2. DEPARTMENT 테이블

Dept_no	Dept_name
1	HR
2	IT
3	Finance

예시 1: 선택 조건 (Selection)

조건: 나이가 30세 이상인 직원의 정보를 선택한다.

관계 대수:

σ_{(Age ≥ 30)}(EMPLOYEE)

결과:

Ssn	Name	Age	Dept_no
123-45-6789	Alice	30	1
234-56-7890	Bob	40	2
345-67-8901	Charlie	35	1
567-89-0123	Eva	50	2

예시 2: 속성 선택 (Projection)

쿼리: 직원의 이름과 나이만 선택한다.
관계 대수:
π_{(Name, Age)}(EMPLOYEE)

결과:

Name	Age
Alice	30
Bob	40
Charlie	35
David	28
Eva	50

예시 3: 선택 조건과 선택 속성 (Selection and Projection)

쿼리: 나이가 40세 이상인 직원의 이름만 선택한다.
- 조건을 먼저 정하고 선택된 결과 중 속성을 선택하는 것이 일반적이다.
관계 대수:
π_{(Name, Age)}(σ_{(Age ≥ 40)}(EMPLOYEE))

결과:

Name	Age
Bob	40
Eva	50

예시 3: 조인 (Join)

쿼리: 각 직원의 이름과 소속 부서 이름을 함께 출력한다.
관계 대수:
EMPLOYEE ⨝ _{(EMPLOYEE.Dept_no = DEPARTMENT.Dept_no)} DEPARTMENT

결과:

Ssn	Name	Age	Dept_no	Dept_name
123-45-6789	Alice	30	1	HR
234-56-7890	Bob	40	2	IT
345-67-8901	Charlie	35	1	HR
456-78-9012	David	28	3	Finance
567-89-0123	Eva	50	2	IT

관계대수와 관계해석 비교

구분	관계 대수	관계 해석
예시	δLev=4(EMP)	EMP(t) and t.Lev>3 }
목적	어떻게(How)	무엇을(What)
기반	집합과 관계연산	프레디킷 논리
접근법	절차적	비절차적
관점	규범적	기술적
표현력	동일

같이 보기