Ch 08. 관계 대수와 관계 해석

1. 관계 대수와 관계 연산자

• 관계 대수
  • 관계를 조작하기 위한 연산자
  • 검색 요구를 명세하는데 사용
  • 질의 결과는 릴레이션 형태로 표현됨
• 관계 연산자
  • SELECT($\sigma$), PROJECT($\pi\$)
  • 집합 연산자 - 합집합(UNION) $\cup$, 교집합(INTERSECTION) $\cap$, 차집합(DIFFERENCE) -, 카티션 곱(CARTESIAN PRODUCT) $\times$
  • JOIN 연산자 $\Join$ 
  • 그 외 다른 관계 연산자들 - DIVISION, OUTER JOIN, AGGREGATE FUNCTIONS

 

 

2. 관계 연산자 SELECT

• $\sigma_{<selection \; condition>}$(R) 로 표현함
• <선택 조건>은 다음와 같은 형태를 갖는 여러 개의 절로 구성되어 있음
  • <애트리뷰트 이름> <비교 연산자> <상수값>
  • <애트리뷰트 이름> <비교 연산자> <애트리뷰트 이름>
•  ex) EMPLOYEE 테이블에서 4번 부서에 속하면서 급여가 25000달러 초과이거나, 5번 부서에 속하면서 급여가 3만 달러 초과인 사람
  • $\sigma_{(Dno=4 \; AND \; Salary>25000)\;OR\;(Dno=5\;AND\;Salary>30000)}$(EMPLOYEE)
  • = SELECT * FROM EMPLOYEE WHERE <선택 조건>
• 임의의 조건 C에 대해서 $\sigma_c(R)\;\leq\;|R|$을 만족함
  • 선택된 튜플 수의 비율을 선택률(selectivity)이라고 함 -> $|\sigma_c(R)| \;/ \;|R|$
• 교환 법칙이 성립함 $\sigma_{<cond1>}(\sigma_{<cond2>}(R))\;=\sigma_{<cond2>}(\sigma_{<cond1>}(R))$ 교환적임(commutative)
• SELECT 연산들의 연속은 항상 AND 조건을 가진 하나의 SELECT 연산으로 결합할 수 있음
  • $\sigma_{<cond1>}(\sigma_{<cond2>}(...(\sigma_{<condn>}(R))...)\;=\;\sigma_{<cond1>\;AND\;<cond2>\;AND\;...\;AND\;<condn>}(R)$

 

3. 프로젝트 연산자 PROJECT

• SELECT 연산이 일부 행들을 선택하고 나머지를 버리는 연산이면, PROJECT 연산은 일부 열들을 선택하고 나머지를 버리는 연산임(거기다가 중복된 튜플도 제거함)
• $\pi_{<attribute\;list>}$(R)로 표현함
  • ex) $\pi_{Sex, Salary}$(EMPLOYEE)
  • = SELECT DINSTINCT Sex, Salary FROM EMPLOYEE
• 리스트2가 리스트1을 포함할 경우 $\pi_{<list1>}(\pi_{<list2>}(R))\;=\;\pi_{list1}(R)$을 만족함

 

4. 연산의 순서와 이름 변경 연산

연산의 순서

• 관계 대수식은 여러 개의 연산을 연산한 것으로 표현되어짐
  • ex) $\pi_{Fname, Lname, Salary}(\sigma_{Dno=5}(EMPLOYEE))$
• 중간 결과 릴레이션에 이름을 부여할 수도 있음
  • ex) $TEMP\;\leftarrow\;\sigma_{Dno=5}(EMPLOYEE)$
  • ex) $RESURT\;\leftarrow\;\pi_{Fname,\;Lname,\;Salary}(TEMP)$

이름 변경 연산

• 릴레이션 이름이나 애트리뷰트 이름, 또는 두 개 모두의 이름을 변경하는 이름 변경 연산자는 단항 연산자로 정의할 수 있음
• 일반적인 차수가 n인 릴레이션 R에 적용된 이름 변경 연산은 다음과 같은 세 가지 중 하나로 표현 가능
  • $\rho_{S(B1,B2,...,Bn)}(R)\;or\;\rho_s(R)\;or\;\rho_{(B1,B2,...,Bn)}(R)$
  • S는 새로운 릴레이션의 이름
  • B는 새로운 애트리뷰트들의 이름

 

5. 집합 이론과 관계 대수 연산

• 합집합, 교집합, 차집합 : 결합 가능해야함(Union compatibility)
  • 애트리뷰트의 개수가 같아야함
  • 도메인이 서로 같아야함
• 카티션 곱 : 차수가 n인 릴레이션과 차수가 m인 릴레이션이 카티션 곱을 하면 차수는 n+m임
  • 카티션 곱만 사용하면 의미가 없지만, 이 연산을 수행한 후 SELECT 연산을 수행하면 의미를 갖게 됨
  • ex) 각 여성 노동자의 이름과 그녀의 부양가족 이름을 구하라
  • FEMALE_EMPS $\; \leftarrow \; \sigma_{Sex='F'}($EMPLOYEE$)$
  • EMPNAMES $\; \leftarrow \; \pi_{Fname, Lname, Ssn}($FEMALE_EMPS$)$
  • EMP_DEPENDENTS $\; \leftarrow \; $EMPNAMES$ \times $DEPENDENT
  • ACTUAL_DEPENDENTS $\; \leftarrow \; \sigma_{Ssn=Essn}($EMP_DEPENDENTS$)$
  • RESULT $\; \leftarrow \pi_{Fname,Lname, DependentName}($ACTUAL_DEPENDENTS$)$

 

 

6. 이항관계 연산: 조인과 디비전 연산

조인 연산(theta join, 세타 조인)

• 조인 연산은 카티션 곱에 SELECT 연산을 한 것과 비슷함
  • $Q(A_1, A_2, ..., A_n, B_1, B_2,...,B_m) \;\leftarrow\;R(A_1,A_2,...,A_n)\Join_c S(B_1,B_2,...,B_m)$
  •  c = <condition> = ($A_i \theta B_j$), $\theta \in {=, <, \leq, >, \geq, \not\equiv}$ 
• 동등 조인(EQUIJOIN)
  • $\theta$의 값이 =일 때 EQUIJOIN이라고 부름
• 자연 조인(NATURAL JOIN) *
  • 두 개의 조인 애트리뷰트 이름이 양쪽 릴레이션에서 같을 것을 요구함(같지 않으면 이름이 같도록 함)
  • 이름을 같게 RENAME을 할 수 있음

 

 

7. 관계 대수 연산의 완전 집합(complete set)

집합 연산 4가지, 관계 연산 4가지는 모두 SELECT, PROJECT, UNION(합집합), SET DIFFERENCE(차집합), CARTESIAN PRODUCT(곱집합)로 표현할 수 있음. 이 5개의 연산을 관계 대수 연산의 완전 집합이라고 함

이 다섯가지 기능을 제공한다면 relationally complete라고도 함

 

 

 

8. DIVISION 연산

튜플들이 나누어 떨어지면 충족하는 연산

ex) 과목 C1, C2, C3을 수강하는 학생의 번호를 검색하라

ex) 'John Smith가 근무하는 모든 프로젝트에서 근무하는 사원들의 이름을 검색하라'

1. SMITH $\leftarrow \; \sigma_{Fname='John'\;AND\;Lname='Smith'}$(EMPLOYEE)
2. SMITH_PNOS $\leftarrow \; \pi_{Pno}(WORKS_ON \Join_{Essn=Ssn}$SMITH)
3. SSN_PNOS $\leftarrow \;\pi_{Essn, PNO}$(WORKS_ON)
4. SSNS(Ssn) $\leftarrow$ SSN_PNOS $\div$ SMITH_PNOS
5. RESULT $\leftarrow \pi_{Fname,Lname}$(SSNS & EMPLOYEE)

 

9. 질의 트리 표기법(Query Trees)

ex) 'Stafford'에 위치한 모든 프로젝트에 대하여 프로젝트 번호와 관리 부서 번호, 부서 관리자의 성, 주소, 생년월일을 나타내는 관계 대수식으  표현하라

 

$\pi_{Pnumber,\;Dnum,\;Lname,\;Address,\;Bdate}(((\sigma_{Plocation='Stafford'}($PROJECT$))\Join_{Dnum=Dnumber}($DEPARTMENT$))\Join_{Mgr_ssn=Ssn}($EMPLOYEE$))$

 

 

위의 관계 대수식을 질의 트리로 표현하라

 

 

10. 추가적인 관계 연산

• Aggregate functions
• grouping
• OUTER JOIN
• OUTER UNION
• SEMIJOIN

이 다섯가지 내용은 위에 있는 내용으로 설명이 불가능하여 따로 정의를 함

1. OUTER JOIN
   • LEFT OUTER JOIN: R1 ⟕ R2
   • RIGHT OUTER JOIN: R1 ⟖ R2
   • FULL OUTER JOIN: R1 ⟗ R2 (또는 $\Join^+$로도 표현)
2. OUTER UNION : not union compatible한 튜플 두 개를 합집합으로 하는 것
   • $\cup^+$으로 표현
   • FULL OUTER JOIN과 비슷함
3. SEMIJOIN
   • R(X) ⋉$_{A=B}$ S(Y) = $\pi_x$(R$\Join_{A=B}$S)
   • A와 B를 자연 조인하는 것에서 R에서만 있는 애트리뷰트만 뽑아내는 것
   • 교환법칙이 성립하지 않음

 

11. 튜플 관계 해석

비절차적인 언어, 선언적인 언어, 어떻게 쿼리를 표현해야할지 설명하지 않음

(반면에 관계 대수는 절차적인 언어고, 연산의 순서를 표현함)

 

종류

• Tuple relational calculus
• Domain relational calculus

 

ex) EMPLOYEE 테이블에서 이름이 John B. Smith인 사람의 생년월일과 주소를 출력해라

쿼리 표현

SELECT Bdate, Address

FROM EMPLOYEE

WHERE Fname='John' AND Minit='B' AND Lname='Smith';

 

관계 대수 표현

$\pi_{BDATE, ADDRESS}(\sigma_{Fname='John'\;AND\;MINIT='B'\;AND\;LNAME='Smith'}($EMPLOYEE$))$

 

 

튜플 관계 해석 표현식

{t.BDATE, t.ADDRESS | EMPLOYEE(t) AND t.FNAME='John' AND t.MINIT='B' AND t.LNAME='Smith'}

 

 

 

관계 해석이나 관계 대수로 표현된 어떤 쿼리라도 주어진 질의어 L로 표현할 수 있으면 Relationally complete라고 함(관계적으로 완전함)

 

 

 

2. 도메인 관계 해석

왼쪽엔 애트리뷰트, 오른쪽엔 조건
Query 0 여기서 E는 E의 반대를 뜻 함
{u, v | (Eq) (Er) (Es) (Et) (Ew) (Ex) (Ey) (Ez) (EMPLOYEE(qrstuvwxyz) AND q ='John' AND r = 'B' AND s ='Smith')}
원래 EMPLOYEE(q, r, s, t, u, v, w, x, y, z)로 표현해야하지만 편의상 콤마 없이 사용 가능
애트리뷰트들 선언은 무조건 전부 해줘야함

Query 0 A
{u, v | EMPLOYEE(q, r, s, t, u, v, w, x, y, z) AND q = 'John' AND r = 'B' AND s ='Smith')}

조인할 때는 변수 다 써주고 합침
Q1 
{q, s, v | (Ez) (El) (Em) (EMPLOYEE(qrstuvwxyz) AND DEPARTMENT(lmno) AND l='Research' AND m=z)}