[DB] Chap 8. The Relational Algebra

 

개떡같은 쿼리를 DBMS가 찰떡같이 처리할 '수학적인' 근거

 

Unary Relational Operations: SELECT AND PROJECT

Relation algebra: 관계형 모델의 operation들의 기본 집합.

사용자가 기본 검색 요청(쿼리)을 지정하게 한다.

operation의 결과는 새로운 relation-하나 이상의 입력된 relation으로 구성된.

-closed함.(닫혀있음)

relation algebra operation의 단계는 relational algebra expression으로 구성된다.

algebra를 query로 매핑.

 

변수 계산을 al-jabr라고 했는데 이것이 Algebra로 번역.

변수를 shay라고 했는데 원 뜻은 thing임. 이것이 xay로 변하고, x로 나타내게 됨.

 

Unary Relational Operation

-SELECT(sigma 심볼)

-PROJECT(pi 심볼)

-RENAME(rho 심볼)

 

Set theory관련 

-UNION/INTERSECTION/DIFFERENCE/CARTESIAN PRODUCT

 

Binary Relational Operation

-Join/DIVISION

 

Additional Relational Operations

-OUTER JOIN, OUTER UNION

-AGGREGATE FUNCTIONS

 

SELECT 연산은 relation안의 튜플들의 부분집합을 선택 조건에 기반하여 선택하는데에 사용

-선택조건(selection condition)은 필터처럼 기능

-자격을 만족한 튜플만 유지

 

sigma_<selection condition>(R)

조건은 boolean 형태. true인 튜플만 선택됨.

-교환법칙 먹힘.(commutative)

-여러개 조건은 AND로 한번에 묶을 수 있음.

 

PROJECT 연산은 확실한 columns(attribute)dmf dbwl.

pie_<attribute list>(R) 형태

-중복을 제거함

-결과의 튜플 수는 R의 튜플과 같거나 더 적음

-교환법칙 X

 

연산을 nested operations 와 같이 하나의 relational algebra로 나타내거나(streaming/on the fly) 중간 결과값(intermediate result)을 만드는 경우 느려진다.(DISK IO)

 

RENAME

속성 이름을 다시 지음

rho_S(B1, B2...)(R)

-relation 이름을 S로, 속성들을 B1, B2...로 변경

rho_S(R)

-relation 이름을 S로 변경.

rho_(B1, B2...)(R)

-속성 이름을 B1, B2...로 변경

 

UNION

U 기호로 나타냄.

RUS면 R과 S에 있는 모든 튜플이 포함됨.

중복은 제거

type compatible(Union competible)

-R과 S의 속성의 수가 같아야함.

-corresponding attribute는 type compatible해야함.

 

Relational Algebra Operations from Set Theory

binary 집합 operation(union, intersection, set difference)에 피연산자의 Type compatibility(타입 호환성)이 필요.

R1(A1, A2, A3,.. An)와 R2(B1, B2, ...Bn)은 type compatible이다.

조건

-같은 수의 속성.

-상응하는 속성의 domain이 type compatible

R1과 R2의 set operation 결과 relation은 처음 R1과 같은 속성 이름을 가진다.(또한 반대로도)

 

R INTERSECTION S는 R와 S 양쪽에 모두 존재하는 튜플들을 포함하는 relation이다.

-속성의 이름은 R과 동일

R과 S의 operand relation은 항상 type compatible이다.

 

Difference(=MINUS = EXCEPT)는 -로 표시

R-S는 R에는 있으나 S에는 없는 튜플들을 포함하는 relation을 결과로 한다.

 

UNION과 INTERSECTION은 commutative operation(교환법칙 성립), associative operations(결합법칙 성립)

MINUS는 commutative하지 않음.

 

CARTESIAN (or CROSS) PRODUCT

-combinatorial fashio에 있는 두 relation에서 두 튜플 결합

-x로 표현

-n+m개의 속성을 가진 Q relation을 결과로함.

Q(A1,A2...An,B1,B2...Bm)

-결과인 relation 상태는 튜플의 각 combination당 하나의 튜플(하나는 R, 하나는 S에서)

-RxS는 n_R * n_S개의 튜플을 가진다.

-type compatible이 아니다!

 

Generally, Cross Product는 meaningful operation이 아님.

 

Binary Relational Operations JOIN and DIVISION

JOIN 연산자

- SELECT에 이어지는 CARTESIAN PRODUCT의 시퀸스는 두개의 relation에서 식별하고 관련된 튜플을 선택하는데에 일반적으로 사용된다.

-JOIN은 이 시퀸스를 하나의 연산자로 결합

- RDB에 굉장히 중요한 연산자. 다양한 relation에서 관련 tuple들을 결합할 수 있게 함.

R JOIN_<Join condition> S 형태(나비형태 연산기호)

 

R(A1,A2...An) JOIN_R.Ai = S.Bj S(B1,B2..Bm)

결과는 n+m개 속성을 가진 realtion Q

-각 튜플의 결합당 하나의 state

-n_R*n_S 개보다 적은 튜플 수

 

일반적인 JOIN은 보통 Theta-join이라고 한다.

join condition을 Theta라고 함.

theta는 일반적인 boolean 연산.

theta는 하나 이상의 AND로 결합시킬 수 있음.

 

EQUIJOIN 연산

-오직 = 비교연산자만 사용하는 join을 EQUIJOIN이라고 함.

-하나 이상의 속성의 짝을 결과로 한다.

-각 튜플에서 식별되는 값이다.

 

Natural JOIN 연산

- *로 표현함.

- second (superflous) 속성을 EQUIJOIN에서 제거한 것.

-두개의 join 속성이나 각 상응하는 join 속성의 짝이 필요-얘들은 양 relation에서 같은 이름을 가짐.

-다르면 renaming 필요

 

Complete Set

연산의 집합(SELECT, PROJECT, UNION, DIFFERENCE, RENAME, CARTESIAN PRODUCT)를 complete set이라고 함.

이 5개 연산으로 어떤 다른 relational algebra를 가능하게 하기 때문.

 

Division

-이항 연산

-  R(Z) / S(X) (X subset Z)는 Y=Z-X (왜냐하면 Z=X U Y)로 정의됨.

여기서 Y는 R에는 있으나, S에는 없는 속성

T(Y)는 튜플 t를 가진다- 튜플 t_R이 t_R[Y]=t와 t_R[X] = t_S를 S안의 모든 튜플 t_S에 대해 만족할 때.

-T의 Division결과로 나타나는 튜플 t에 대해  t의 값은 S의 모든 튜플과 결합한 R에서 나타난다.

 

Query Tree Notation

-쿼리를 나타내는 자료구조

-쿼리 실행을 추론하기 위한 기본적 기술

-leaf는 base relation을 나타냄

-쿼리의 복잡성을 보기 좋게 나타냄.

 

 

Additional Relational Operations

aggregate functions and grouping

DB에서 값들을 모으는 데에 수학적 집합 함수를 지정

검색(retrieving)

Imaginary Part 기호.

MAX/MIN/SUM/COUNT

 

Grouping

-Aggregation 함수와 결합될 수 있음.

-심볼의 왼쪽에 위치(aggregation은 오른쪽)

 

Recursive Closure Operation

재귀 호출

재귀 관계에 적용됨.

 

OUTER JOIN

-Natural JOIN이나 EQUIJOIN은 매칭이 되지 않는 튜플은 결과에서 삭제.

-한쪽 relation의 tuple을 모두 유지하기 원할 때 사용.

 

left outer join은 왼쪽을 유지(나비모양에서 왼쪽이 길어짐)

right outer join은 오른쪽을 유지(나비모양에서 오른쪽이 길어짐)

매칭되지 않는 부분의 빈것은 죄다 null 값으로 padding

full outer join은 양쪽 모두 유지.

 

OUTER UNION

type compatible이 아닌 두개의 relation을 UNION하는데에 사용.

두 relation R(X, Y)와 S(X, Z)에 사용-둘은 partially compatible. X의 attribute부분만 type compatible

겹치는 부분(type compatible)은 결과에 한번만 나옴.

T(X, Y, Z)형태.

 

 

Examples of Queries in Relational Algebra