[데이타베이스론] CH5. 관계 대수와 관계 해석

관계 데이터 연산

-연산(operation)과 데이터 언어(data language)

• 연산: 시스템 입장
• 데이터 언어: 사용자 입장

-관계 데이터 언어(relational data language)

• 정형어(formal language)

1. 관계 대수(formal language)

절차 언어: how, what

2. 관계 해석(relational algebra)투플 관계 해석(tuple relational calculus)

도메인 관계 해석(domain relational calculus)

비절차 언어: what

⇒ 관계 해석과 관계 대수는 표현과 기능 면에서 동등

 

사용자 -데이터 언어→ 요청 → 질의어 처리기/컴파일러 → 연산으로 transform(변환)

dbms; 데이터베이스 연산 수행

관계 대수(Relational Algebra)

릴레이션을 처리하기 위한 연산의 집합

• 릴레이션: 투플의 집합

피연산자 연산 결과가 투플의 집합 → 테이블(릴레이션)

 

-기본 연산

• 일반 집합 연산자교집합(INTERSECT, ∩)카티션 프로덕트(CARTESIAN PRODUCT, ×)

차집합(DIFFERENCE, -)

합집합(UNION, ∪)

• 순수 관계 연산자프로젝트(PROJECT, $\Pi$) 조인(JOIN, $\Join$)

디비전(DIVISION, $\div$)

셀렉트(SELECT, $\sigma$)

 

-폐쇄 성질(closure property)

어떤 자연수에 대해 덧셈의 결과가 항상 자연수 ⇒ 닫혀있다(폐쇄 성질을 가진다)

피연산자나 연산 결과의 집합이 똑같아야 한다

• 피연산자와 연산 결과가 모두 릴레이션
• ㄴ증명되어 있을 경우 → 중첩(nested)된 수식의 표현 가능

일반 집합 연산자

t; 투플 약자/ |...|; 투플의 개수

1. 합집합(UNION, )

중복 경우 없애기 때문에 작아질 수 있다

$R∪S=\{t|t∈R∨t∈S\}$

$|R∪S|≤|R|+|S|$

 

2. 교집합(INTERSECT, )

$R∩S=\{t|t∈R∧t∈S\}$

$|R∩S|≤min\{|R|,|S|\}$

 

3. 차집합(DIFFERENCE, )

R이 S에 완전히 포함될 때(속할 때) 같다

$R-S=\{t|t∈R∧t∉S\}$

$|R-S|≤|R|$

 

4. 카티션 프로덕트(CARTESIAN PRODUCT, )

R; 학생 S; 등록 → R의 속성 + S의 속성 ⇒ 차수: R의 차수 + S의 차수

$R×S=\{r⋅s|r∈R∧s∈S\}⋅:접속(concatenation)$

$|R×S|=|R|×|S|$

차수(degree) = R의 차수 + S의 차수

 

*Note

-합병가능(union-compatible)한 릴레이션

릴레이션은 속성이 있는 투플에 대해 집합 연산

• $\cap, \cup, \times$연산의 피연산자들은

1. 차수가 같아야 함
2. 대응 애트리뷰트 쌍 별로 도메인이 같아야 함

ㄴint와 int 가능 But, int와 char 불가능

 

-결합적(associative): $\cap, \cup, \times$

$R∪S∪T=(R∪S)∪T=R∪(S∪T)$

$R∩S∩T=(R∩S)∩T=R∩(S∩T)$

$R×S×T=(R×S)×T=R×(S×T)$

 

-교환적(commutative): $\cap, \cup, \times$

$R∪S=S∪R, R∩S=S∩R, R×S=S×R$

순수 관계 연산자

릴레이션: $R(X)=R(A_1,...,A_n)$

R의 투플: $r: <a_1,a_2,...,a_n>$

$R=\{r|r=<a_1,...,a_n>\}$

• $a_i:$ 투플 r에 대한 애트리뷰트 $A_i$의 값
• $a_i = r.A_i =r[A_i]$

일반적으로

$<r.A_1,r.A_2,...,r.A_n> = <r[A_1],r[A_2],...,r[A_n]>$

$=r[A_1,A_2,...,A_n] = r[X]$

1. 셀렉트(SELECT: σ: sigma)

-A, B가 릴레이션 R의 애트리뷰트일 때,

$\sigma_{A\theta v}(R) = \{r|r∈R\land r.A\theta v\}$

$\sigma_{A\theta B}(R) = \{r|r∈R\land r.A\theta r.B\}$

단, θ(theta) : 비교 연산자 {<, >, ≤, ≥, =, ≠}/ v: 상수

데이터베이스 사용 목적; 검색하기 위함 ⇒ select 연산 ↑ 사용

-셀렉트($\sigma$)의 결과는 선택 조건을 만족하는 릴레이션의 수평적 부분집합(horizontal subset)

-example

• $\sigma_{학과='컴퓨터'}(학생)$
• $\sigma_{학번=300\land 과목번호='C312'}(등록)$
• $\sigma_{중간성적<기말성적}(등록)$

-데이터 언어 형식의 표현

• R WHERE 조건식

$\sigma_{조건2}(\sigma_{조건1}(R))=\sigma_{조건1}(\sigma_{조건2}(R))=\sigma_{(조건1\land 조건2)}(R)$

-선택도(selectivity)

• 선택 조건에 의해 검색되는 투플의 비율

-학생, 등록 릴레이션에 대한 셀렉트 연산 예

 

2. 프로젝트(PROJECT: $\Pi$: pi)

릴레이션 $R(X)$에서 $Y\subseteq X$ 이고 $Y=\{B_1,B_2,...,B_m\}$이면,

$\Pi_Y(R)=\{<r.B_1,...,r.B_m>|r∈R\}$

-example

학생(학번,이름,학년,학과)에서 $\Pi_{이름,학과}(학생)$

-릴레이션의 수직적 부분집합(vertical subset)

-결과에 투플이 중복되는 경우에는 제거

• 결과도 투플의 집합(릴레이션)-폐쇄성

$\Pi_Y(\Pi_X(R))=\Pi_Y(R)$

-학생, 과목 릴레이션에 대한 프로젝트 연산 예

 

3. 조인(JOIN: $\Join$)

-세타 조인(theta join)

$R(X),S(Y),A∈X,B∈Y$에 대하여

$R\Join_{A\theta B}S=\{r⋅s|r∈R \land s∈S \land (r.A\theta s.B)\}$

• A, B: 조인 애트리뷰트(join attribute)
• 결과 차수 = R의 차수 + S의 차수
• 결과 릴레이션의 애트리뷰트는 원 소속 릴레이션 이름을 애트리뷰트 앞에 한정어로 붙여 일관성 유지

$학생\Join_{학번=학번}등록$

이 연산의 결과 릴레이션이 갖는 애트리뷰트는 학생.학번, 학생.이름, 학생.학년, 학생. 학과, 등록.과목번호, 등록.성적, 등록.중간성적, 등록.기말성적으로 표현

• 그러마 상이한 애트리뷰트는 보통 그 이름만 사용
• 세타 조인에서 $\theta$가 “=”인 경우

$R\Join_{A=B}S=\{r⋅s|r∈R \land s∈S \land (r.A\theta s.B)\}$

• 릴레이션 학생과 등록의 동일 조인 예

-자연 조인(natural join: $\Join_N$)

$R(X),S(Y)$의 조인 애트리뷰트를 $Z(=X\cap Y)$라 하면

$R\Join_N S$

$=\{<r⋅s>[X\cup Y]|r∈R \land s∈S \land r[Z] =s[Z]\}$

$=\Pi_{X\cup Y}(\sigma_{Z=Z}(R\times S))$

$= \Pi_{X\cup Y}(R\Join_{Z=Z} S)$

즉, 동일 조인의 결과에서 중복되는 애트리뷰트를 제거

일반적으로 조인이라 하면 자연 조인 의미

• 릴레이션 학생과 등록의 자연조인 예

4. 디비전(DIVISION: $\div$)

릴레이션 $R(X),S(Y)$에 대하여

$Y\subseteq X$ 이고 $D=X-Y$라고 하면 $R(X)=R(D,Y)$

$R\div S = \{t|t∈\Pi_D(R)\cap t⋅s∈R for all s∈S\}$

$Note: ((R\div S)\times S)\subseteq R$

 

5. 개명 연산(RENAME: $\rho$: rho)

: 중간 처리 결과 릴레이션에 이름을 지정하거나 애트리뷰터 이름을 변경할 때 사용

1) $\Rho_S(E)$

관계 대수식 E의 결과 릴레이션의 이름을 S로 지정

2) $\Rho_{S(B_1,B_2,...,B_m)}(E)$

관계 대수식 E의 결과 릴레이션의 이름을 S로 지정하고 애트리뷰트 이름은 각각 $B_1,B_2,...,B_m$으로 지정

3) $\Rho_{(B_1,B_2,...,B_m)}(R)$

릴레이션 R의 애트리뷰트 이름을 각각 $B_1,B_2,...,B_m$으로 변경

기본 연산과 복합 연산

-기본 연산(primitive operations)

• 다른 연산으로 대체할 수 없는 하나의 논리적 기능을 수행하는 연산
• $\cup,-,×,\Pi,\sigma$

-복합 연산(composite operations)

• 몇 개의 기본 연산으로 대체할 수 있는 연산

$R\cap S = R(RS) = S(SR) =(R\cup S)((RS)\cup(SR))$$R(Z,Y)\div S(Y) =R[Z]-((R[Z]\times S)-R)[Z]$

$R\Join_{A\theta B}S=\sigma_{A\theta B} (R\times S)$

$교집합(\cap), 조인(\Join), 디비전(\div)$

• 연산력 < 표현력 증대

관계 대수의 확장

1. 세미 조인과 외부 조인

-세미 조인(semijoin,)

-외부 조인(outerjoin)

• 한 릴레이션에 있는 투플이 조인할 상대 릴레이션에 대응되는 투플이 없을 경우, 상대를 널(null) 투플로 만들어 결과 릴레이션에 포함
• 누락 정보를 처리하기 위한 조인의 확장
• 두 조인 릴레이션의 투플들이 전부 결과 릴레이션에 포함됨

2. 외부 합집합(outer-union, $\cup^+$)

-합병 가능하지 않은(not union-compatible) 두 릴레이션의 모든 애트리뷰트를 포함하는 확장된 릴레이션으로 만듦

-확장된 릴레이션에 해당하는 애트리뷰트 값이 없을 때는 널 값으로 채움

 

3. 집계(aggregation) 연산

$AVG_{성적}(등록)$

• 등록 릴레이션의 성적 애트리뷰트 값들에 대해 평균값 계산

$GROUP_{학년}(학생)$

• 학생 릴레이션의 투플들은 학년 값에 따라 그룹을 만듦

$GROUP_{과목번호}AVG_{성적}(등록)$

• 등록 릴레이션에서 과목별 그룹에 대한 평균성적
• 실행 순서는 GORUP, AVG 순서임

-일반형식: $G_AF_B(E)$

• E: 관계 대수식
• F: 집계 함수(SUM, AVG, MAX, MIN, COUNT)
• B: 집계 함수의 적용 대상 애트리뷰트
• G: 그룹 함수 GROUP
• A: 그룹 함수가 적용할 애트리뷰트

관계 대수의 질의문 표현

: 사용자의 질의문을 관계 대수식으로 표현

모든 학생의 ‘이름’과 ‘학과를 검색하라.

• $\Pi_{이름, 학과}(학생)$

‘과목번호’가 C413인 과목에 등록한 학생의 ‘이름’과 ‘성적’은 무엇인가?

• $\Pi_{이름,성적}(\sigma_{과목번호='C413'}(학생\Join_N등록))$

‘화일구조’ 과목을 가르치는 ‘담당교수’를 검색하라.

• $\Pi_{담당교수}(\sigma_{과목이름='화일구조'}(과목))$

모든 과목에 수강한 학생의 ‘학번’과 ‘이름’을 검색하라

• $\Pi_{학번,이름}((\Pi_{학번,과목번호}(등록)\div\Pi_{과목번호}(과목))\Join_N학생)$

‘학번’이 600, ‘이름’이 ‘김영호’, ‘학년’이 4, ‘학과’가 ‘컴퓨터’인 학생을 삽입하라.

• $학생∪\{<600,'김영호',4,'컴퓨터'>\}$

‘데이터베이스’ 과목을 삭제하라.

• $과목-(\sigma_{과목이름='데이터베이스'}(과목))$

관계 해석(Relational Calculus)

-predicate calculus에 기반

• Predicate

실행 결과가 반드시 참(true)이나 거짓(false)인 함수

a function whose value is true or false

관계 데이터 모델의 연산 표현 방법

 

-비절차적(non-procedural)

• 원하는 정보가 무엇이라는 것만 선언
• 투플 관계 해석(tuple relational calculus)
• 도메인 관계 해석(domain relational calculus)

투플 관계 해석(tuple relational calculus)

원하는 릴레이션을 투플 해석 식(tuple calculus expression)으로 정의하는 표기법

 

-투플 해석식 구성요소

1. 투플 변수(tuple variable) OR 범위 변수(range variable): tR: t의 범위 릴레이션(range relation)

범위식(range formula) : R(t)

 

2. 한정 애트리뷰트(qualified attribute): $t.A 또는t[A]$-STUDENT(s)

s.Sno

투플 변수 t가 나타나는 투플의 애트리뷰트 A의 값

 

3. 원자식(atomic formula)

1) 범위 식: $R(t)$

t: 투플 변수

R: t의 범위 릴레이션

2) 조건 식: $t.A\theta u.B$

$A, B:$ 애트리뷰트

$\theta :$ 비교 연산자(=, ≠, <, ≤, >, ≥)

3) 조건 식: $t.A\theta c$

$c:$ 상수

⇒ 원자식의 실행 결과는 반드시 참(True) OR 거짓(False)

 

4. 정형식(WFF, well-formed formula)

: : 원자식, 불리언 연산자($\vee,\land,\lnot$), 정량자($\forall,\exists$)를 다음 규칙에 따라 결합하여 표현한 식

1) 모든 원자 식은 WFF

2) F가 WFF이면, (F)와 $\lnot F$도 WFF

3) F와 G가 WFF이면, $F\land G$와 $F\vee G$도 WFF

4) 도메인 변수 x가 자유변수로 사용된 $F(X)$가 WFF이면, $(\forall x)(F(x))와 (\exists x)(F(x))$도 WFF

5) 위의 규칙만을 적용해서 만들어진 식은 WFF

-example

*Notes

-자유변수(free variable)

• 정량자(quantifier)로 한정되지 X 투플 변수
• 전칭 정량자(Universal quantifier): $\forall$: for all
• 존재 정량자(Existential quantifier): $\exists$: there exists, for some

-속박변수(bound variable)

• 정량자($\forall t, \exists t)$로 한정된 투플 변수
• 프리닉스 정규형(prenex noraml form)

정량자 앞 에 먼저 기술한 WFF

1) $(\forall t)(F(t))\land(\forall t)(H(t)) = (\forall t)(F(t)\land H(t))$

2) $(\exist t)(F(t))\lor (\exist t)(H(t)) = (\exist t)(F(t)\lor H(t))$

-투플 해석식(suple calculus expression)

$\{t_1.A_1,t_2.A_2,...,t_n.A_n|F(t_1,...t_n,t_{n+1},...,t_{n+m})\}$

$t_i:$ 투플 변수

$F(t_1,...t_n,t_{n+1},...,t_{n+m}): t_i$가 연관된 정형식으로 조건을 명세

• 막대(|) 왼편에 명세된 한정 애트리뷰트들은 목표 리스트(target list)로서 막대(|) 오른편에 명세된 조건을 만족하는 투플로부터 추출됨
• example

목표 리스트에는 자유 변수만 나올 수 있음

투플 관계 해석식의 질의문 표현

과목 C413에서 성적이 A인 학생의 학번을 모두 검색하라.

과목 C413을 등록한 학생의 이름과 학과를 모두 검색하라.

모든 과목에 등록한 학생의 이름을 전부 검색하라.

과목 ‘C413’에 등록하지 않은 학생의 이름을 전부 검색하라.

도메인 관계 해석(domain relational calculus)

원하는 릴레이션을 도메인 해석식(domain calculus expression)으로 정의하는 표기법

 

-도메인 해석식 구성요소

1. 도메인 변수(domain variable)

-지정된 애트리뷰트 도메인의 한 원소만을 취하는 변수

• xSno, xSname, xDept, xYear, ...

범위식

• 도메인 변수 선언 식
• STUDENT(xSno, xSname, xDept, xYear)

2. 원자 식(atomic formula)

1) 범위 식, $R(x_1,x_2,...,x_n)$

$x_i:$ 도메인 변수/ $R: x_i$의 범위 릴레이션

$<x_1,x_2,...,x_n>$에 대응하는 값의 리스트는 릴레이션 R의 투플</x_1,x_2,...,x_n>

2) 조건 식, $x \theta y$

$x, y:$ 도메인 변수

$\theta:$ 비교 연산자(=, ≠, <, ≤, >, ≥)

3) 조건 식, $x\theta c$

$x:$ 도메인 변수

$c: x$ 가 정의된 도메인 값의 상수

⇒ 원자 식의 실행 결과는 반드시 참(True) OR 거짓(False)

 

3. 정형식(WFF, Well-formed formula)

: 원자식, 불리언 연산자($\vee,\land,\lnot$), 정량자($\forall,\exists$)를 다음 규칙에 따라 결합하여 표현한 식

1) 모든 원자 식은 WFF

2) F가 WFF이면, (F)와 $\lnot F$도 WFF

3) F와 G가 WFF이면, $F\land G$와 $F\vee G$도 WFF

4) 도메인 변수 x가 자유변수로 사용된 $F(X)$가 WFF이면, $(\forall x)(F(x))와 (\exists x)(F(x))$도 WFF

5) 위의 규칙만을 적용해서 만들어진 식은 WFF

 

-도메인 해석식(domain calculus expression)

$\{x_1,x_2,...,x_n|F(x_1,...,x_n,x_{n+1},...,n_{n+m})\}$

$x_i:$ 도메인 변수

$F(x_1,...,x_n,x_{n+1},...,n_{n+m}): x_i$가 관련된 정형식

• 막대(|) 왼편에 명세된 n 도메인 변수들은 목표 리스트로서 막대(|) 오른편에 명세된 조건(정형식)을 만족하는 도메인 값으로 만들어지는 투플 표현
• example

도메인 관계 해석식의 질의문 표현

-컴퓨터학과 3,4 학년(Year)의 이름(Sname)을 검색하라.

과목번호(Cno) C413에서 성적(Grade)이 A인 학생의 학번(Sno)을 모두 검색하라.

기말 성적(Final)이 90점 이상인 학생의 학번(Sno)과 이름(Sname)을 검색하라.

과목번호(Cno) C324에 등록하지 않은 학생의 이름(Sname)을 검색하라.

QBE(Query By Example)

IBM의 Zloof가 1975년 개발

도메인 관계 해석 사용

그래픽 디스플레이 단말기 사용

이차원 구문(two-dimensional syntax) 언어

테이블 형태 “skeleton”

예(example)를 질의문 명세에 사용

• 예제 원소(example element): 도메인 변수

데이터 검색

-단순 조건 검색

• 컴퓨터학과 4학년 학생의 학번과 이름을 검색하라.

-테이블 전체의 검색

• 학생 테이블을 전부 검색하라.

-복수 조건 검색

• ‘QR’ 조건: 두 개의 행이나 상이한 예제 원소를 사용
• 기말성적이 85점 이상이거나 과목번호 ‘C413’에 등록한 학생의 학번을 검색하라.

• ‘AND’ 조건: 하나의 행이나 같은 예제 원소 사용
• 과목번호가 ‘C413’이고 기말성적이 85점 이상인 학생의 학번 검색하라.

• 조건 상자(condition box)로 명세

-복수 테이블에서 검색

• 기말성적이 85점 이상이거나 과목 ‘C413’을 등록한 학생의 이름을 검색해라.

데이터 삽입(Insert)

-단순 레코드의 삽입

• 학번이 100이고 과목번호가 ‘C413’인 투플을 삽입하라.

*Note: 기본 키(Sno)가 null이어서는 안됨

-투플 검색을 이용한 삽입

• 4학년 학생의 학번을 학생 테이블로부터 검색해서 SENIOR 테이블에 삽임하라.

데이터 삭제(Delete)

-한 테이블에서의 삭제

• 학번이 100인 학생을 학생 테이블에서 삭제하라.

-복수 테이블에서의 레코드 삭제

• 기말 성적이 60점 미만인 학생을 등록 테이블과 학생 테이블에서 삭제하라.

데이터 갱신(Update)

-필드 값의 단순 갱신(투플은 기본 키로 명세)

• 학번이 300인 학생의 학년을 2로 변경하라.

-산술식을 이용한 갱신

• 과목 ‘C413’에 등록한 학생의 기말 성적(Final)에 5점을 가산하라.