[Lecture 07] Relational algebra

Objectives

Relational algebra: relational DB로부터 원하는 정보를 끄집어 내는 데 사용되는 operator들의 집합

• Operators of relational algebra
• Query expressions with relational algebra

"relational algebra의 operator들로 query라는 것을 어떻게 표현하는가"

---

Relational Algebra

다시 한 번 정의하면, relational DB로부터 원하는 정보를 끄집어 낼 때 사용하는 operator들의 집합이다.

즉, basic set of operations for the relational model이다.

retrieval requests를 위해 사용된다.

relational algebra를 통해서 검색된 결과 역시 a new relation 이다. (이게 중요!!)

 

Types

• SELECT
• PROJECT
• Set operations
• JOIN
• ...

---

SELECT Operation

Format $$\sigma_{<selection\ condition>}\left ( R \right )$$

Meaning

relation R로부터 selection condition c를 만족하는 tuple들을 골라라.

이때, selection condition c는 Boolean expression이다.

• <attribute name> <comparision op> <constant value>
• ex) grade > 3.5
• <attribute name> <comparision op> <attrubute name>
• ex) 수입 > 지출

resulting relation은 r(R)에서 c를 만족하는 튜플로만 구성된다. 

Examples 

• $\sigma_{Dno=4}\left ( EMPLOYEE \right )$
• $\sigma _{Salary>30000}\left ( EMPLOYEE \right )$

EMPLOYEE라는 table에서 Dno value가 4인 사람들을 골라라. ↔  4번 department에서 일하는 사람 정보를 달라.

Salary가 30000불 이상인 사람들을 골라달라. ↔ 연봉 30000불 넘는 사람 정보좀 줘.

 

$\sigma_{(Dno=4\ AND\ Salary>25000)OR(DNO=5\ AND\ Salary>30000)}\left ( EMPLOYEE \right )$

---

PROJECT Operation

Format $$\pi _{<attribute\ list>}\left ( R \right )$$

table R에서 attribute list에 있는 attribute들의 value만 보여줘.

기존에 100개의 tuple이 있었다면 결과 relation의 tuple 개수는 얼마일까? → 100개 (기본적으로는) >> 'PROJECT'

 

Meaning

relation R로부터 attribute list L에 있는 column들만 골라라.

• discards the other columns

resulting relation은 해당 attribute들로만 이루어진 tuple들로 구성된다.

PROJECT operation의 결과는 distinct tuples이다. (이게 중요!!)

• 앞서 원래 100개의 튜플이 있었다면 "기본적으로는" 결과 relation도 100개의 튜플을 가진다고 했다.
• 그러나 중복이 발생하면 하나만 표시하기 때문에 실제로는 tuple 개수가 줄어들 수 있다.

 

Examples

왼쪽 표의 튜플: 8개, 오른쪽 표의 튜플: 7개(중복으로 하나가 줄어들었다고 해석할 수 있음)

 

---

Relational Algebra Expressions

Sequence of relational algebra operations

Complex queries can be represented

• 연속적인 적용이 가능한 이유: relational algebra operation을 적용한 결과 역시 relation이기 때문

Examples

자연어로 된 query: 5번 department에서 일하는 사람들의 first name, last name, salary 정보 좀 찾아줘!

• $\pi _{Fname,Lname,Salary}\left ( \sigma _{Dno=5}\left ( EMPLOYEE \right ) \right )$

중간결과를 별도의 table name을 줘서 처리할 수도 있다.

• $DEP5\_EMPS ← \sigma _{Dno=5}\left ( EMPLOYEE \right )$
• $RESULT ← \pi _{Fname,Lname,Salary}\left ( DEP5\_EMPS \right )$

각 attribute의 이름도 rename할 수 있다.

• $TEMP ← \sigma _{Dno=5}\left ( EMPLOYEE \right )$
• $R\left ( First\_name, Last\_name, Salary \right ) ← \pi _{Fname,Lname,Salary}\left ( TEMP \right )$

---

Set Operations 집합 연산

tuple이 set이기 때문에, set operation이 빠질 수 없다.

• UNION operation
  • $R_{1}\cup R_{2}$
• INTERSECTION operation
  • $R_{1}\cap R_{2}$
• SET_DIFFERENCE(MINUS) operation
  • $R_{1}-R_{2}$
• CARTESIAN PRODUCT(CROSS PRODUCT) operation
  • $R_{1}\times R_{2}$

Example

RESULT1: 5번 부서에서 일하는 사람들, RESULT2: supervisor들의 ssn

RESULT2를 보면 333445555는 RESULT1에도 포함되는 걸로 보아 5번부서에서 일하는 동시에 누군가의 supervisor이다.

또, 88866555는 RESULT1에 없으므로 5번부서에서 일하는 것은 아니지만 5번 부서에서 일하는 누군가의 supervisor이다.

 

Union compatibility [ type compatibility ]

한글로하면 합집합 호환성. 즉 아무때나 다 합집합을 할 수 있는 건 아니다. 

의미있는 union이 되기 위한 조건이 있다. 두 가지 조건은 다음과 같다.

• attribute 개수가 같아야 한다.
• 대응되는 attribute 쌍은 도메인이 같아야 한다.
  • attribute 이름까지 똑같아야 하는 것은 아니다. 
  • R1은 domain이 1~100인데, R2가 domain이 1~101인 것도 가능하다.

Examples

이 두 relation은 union compatible하다.

• attribute개수가 2개로 같다.
• Fn-Fname, Ln-Lname의 도메인이 같다.

STUDENT ∪ INSTRUCTOR

STUDENT의 tuple 개수는 7개, INSTRUCTOR의 튜플 개수는 5개 였는데 합집합 하니까 8개로 줄어들었다.

이유는? 중복이 발생했기 때문(Susan Yao, Ramesh Shah)

 

STUDENT ∩ INSTRUCTOR

 

 

STUDENT - INSTRUCTOR / INSTRUCTOR - STUDENT

---

CARTESIAN PRODUCT Operation

Format $$R\times S$$

$$or$$

$$R\left ( A_{1},A_{2},...,A_{n} \right )\times S\left ( B_{1},B_{2},...,B_{m} \right )$$

→ $k*l$ 개의 tuple

 

Meaning

두 relation 사이의 가능한 모든 조합을 만드는 것

$Q\left ( A_{1},A_{2},...,A_{n},B_{1},B_{2},...,B_{m} \right )$

• Number of attributes: $n+m$
• number of tuples: $n_{R} * n_{S}$

이 연산을 언제 쓰냐?

cartesian product 자체로는 큰 의미가 없고 이후에 selection을 할 때 큰 의미가 있다.

 

Example

각 여성 근로자의 dependents들의 이름 리스트를 찾아줘!

• $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,Dependent\_name}(ACTUAL\_DEPENDENTS)$

$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,Dependent\_name}(ACTUAL\_DEPENDENTS)$

---

JOIN Operation

Necessity

cartesian product + select를 한 번에 할 수 있는 operation을 만들 순 없어? 해서 나온 operation

Example

각 부서의 매니저의 이름을 알려줘!

 

Using CARTESIAN PRODUCT

$ALL\_PRODUCT ← DEPARTMENT \times EMPLOYEE$

$DEPT\_MGR ← \sigma_{Mgr\_ssn=Ssn}ALL\_PRODUCT$

$RESULT ← \pi_{Dname,Lname,Fname}(DEPT\_MGR)$

 

Using JOIN

$DEPT\_MGR ← DEPARTMENT \bowtie_{Mgr\_ssn=Ssn}EMPLOYEE$

$RESULT ← \pi_{Dname, Lname, Fname}(DEPT\_MGR)$

• 이점 1) query 작성자도 편함(한 번에 쓸 수 있음)
• 이점 2) 처리속도 향상 
  • cartesian product: 모든 쌍을 디스크에 저장 후 select ↔ join: Mgr_ssn = Ssn 인 쌍만 찾아서 처리

 

THETA JOIN Operation

Format $$R\ \bowtie_{<join\ condition>}S$$

Meaning

이제는 모든 가능한 조합이 아니라, join condition을 만족하는 조합만.

CARTESIAN PRODUCT + SELECT와 같은 의미

Join condition c

• <condition> AND <condition> AND ... AND <condition>
• <condition> = $A_{i}\ \theta\ B_{j}$
• $\theta = {=,<,\leq ,>,\geq ,\neq } $
  • 다양한 관계 연산자를 쓸 수 있다는 점에서 theta join이라고 함.

EQUIJOIN Operation

Meaning

theta join의 특수한 케이스로, theth가 = 일 때를 의미.

equijoin의 결과는 항상 동일한 값의 attribute쌍을 가짐. 

ex) Mgr_ssn = ssn 를 찾으면 항상 두 값은 동일 → 중복!

 

NATURAL JOIN Operation

Format $$R*S$$

Meaning

EQUIJOIN에서 동일한 값의 attribute 쌍이 생기는 중복 현상이 unnatural하다!

둘 중에 하나는 지워버리자!(두번째 attribute)

natural join을 하기 전에 join할 두 attribute는 같은 이름이어야 한다.

Example

각 PROJECT 튜플을 그 프로젝트를 관리하고 있는 DEPARTMENT 튜플과 결합해줘 

즉, 각 프로젝트가 어느 부서에서 관리되고 있는지 알려줘!

 

$DEPT \leftarrow \rho_{(Dname, Dnum, Mgr\_ssn, Mgr\_start\_date)}(DEPARTMENT)$

• DEPARTMENT가 갖고있는 attribute 중 PROJECT attribute 구성(개수, 이름)과 동일하게 전처리

$PROJ\_DEPT \leftarrow PROJECT * DEPT$

Dnumber, Dnum이 하나로 합쳐진 모습

 

각 DEPARTMENT의 위치들을 알려줘!

$DEPT\_LOCS ← DEPARTMENT * DEPT\_LOCSATIONS$

• 이미 Dnumber라는 attribute을 둘 다 갖고 있음

이렇게 join함으로써 Location에 위치하는 Dname을 알 수 있게 됨

 

두 relation 사이에 join 될 수 있는 방법은 여러 개가 있으며, 그 결과는 각각 다른 의미를 갖는다.

Examples

$DEPARTMENT\bowtie_{Mgr\_ssn=Ssn}EMPLOYEE$

$EMPLOYEE\bowtie_{Dno=Dnumber}DEPARTMENT$

• DEPARTMENT, EMPLOYEE간의 join case

한 relation이 JOIN operation의 양 쪽에 올 수도 있다.

이 경우는 renaming이 아주 유용하다.

Examples

각 EMPLOYEE의 이름과 그 사람의 supervisor 이름을 찾아줘!

$SUPERVISOR(Super\_ssn, Sfname,Slname) ←\pi_{Ssn,Fname,Lname}(EMPLOYEE)$

$TEMP ← EMPLOYEE * SUPERVISOR$

$RESULT ← \pi_{Fname,Lname,Sfname,Slname}(TEMP)$

---

A Complete Set of Relational Algebra Operations

Complete set

어떤 relational algebra expression도 complete set내의 operation만 이용하면 그것들의 sequence로 표현 가능하다.

Complete set of relational algebra

{SELECT, PROJECT, UNION, SET DIFFERENCE, CARTESIAN PRODUCT}

• JOIN은? 
  • CARTESIAN PRODUCT와 SELECT의 조합으로 표현될 수 있다.
• INTERSECTION은?
  • $R\cap S = R - (R-S)$ 이렇게 표현할 수 있다.

Relationally complete languages

어떤 새로운 query language를 만들었을 때 relational algebra operation의 complete set을 표현할 수 있으면, relationally complete하다고 한다.