[기초데이터베이스] 04. Relational Algebra

 

관계대수

 

관계대수 (Relational Algebra)

- 질의어 : 데이터베이스에 들어있는 데이터에 대한 질문(=질의, query)를 하기위한 특수 언어
- 관계대수 : 관계 모델과 관련한 형식 질의어

* 관계대수에서는 릴레이션들이 투플들의 집합이 되도록 중복 제거가 항상 수행된다고 가정함

Relational Algebra

Example Instances

 

셀렉션과 프로젝션

- 셀렉션 연산자 σ
 : 행들을 선택 (유지할 투플들을 명시)
   애트리뷰트 op 상수 또는 애트리뷰트1 op 애트리뷰트2 라는 형태의 항들을 불리언(논리 연산자)으로 조합한 것

- 프로젝션 연산자 π
 : 열들을 추출

중복 제거됨

 

집합 연산

* 합병가능 (union-compatible)
 : 두 릴레이션 인스턴스들의 필드 수가 같아야 하고,
   왼쪽에서부터 오른쪽으로 차례대로, 대응하는 필드들이 동일한 도메인(타입)을 가지고 있어야 함.

- 합집합 R ∪ S
: R이나 S에 나타나는 모든 투플들을 포함하는 릴레이션 인스턴스를 반환함.
  R과 S는 서로 합병가능해야함.

- 교집합 R ∩ S
: R과 S에 모두 속하는 투플들을 포함하는 릴레이션 인스턴스를 반환함.
  R과 S는 서로 합병가능해야함.

- 차집합 RㅡS
 : R에는 속하고 S에는 속하지 않는 투플들로 구성된 릴레이션 인스턴스를 반환함.
   R과 S는 서로 합병가능해야함.

- 크로스 프로덕트 R X S (=카티션 프로덕트, Cartesian product)
 : 그 스키마가 R의 모든 필드 다음에 S의 모든 필드들을 순서대로 포함하는 릴레이션 인스턴스를 반환함.

  R X S의 필드들은 R과 S의 대응하는 필드로부터 이름을 상속함.
  R과 S가 동일한 이름을 갖는 하나 이상의 필드들을 포함하여 이름 충돌(naming conflict)가 발생한다면
  해당 필드들은 R X S에서 이름이 만들어지지 않고 그 위치로만 언급됨. 

 

이름 바꾸기

- 개명 연산자 ρ
 : 관계대수식에 의해 정의되는 릴레이션 인스턴스의 필드에 이름을 명시적으로 부여.
   
   ρ(R(F), E)는 임의의 관계대수식 E를 취하여 R이라고 하는 새로운 릴레이션의 인스턴스를 반환함.
   릴레이션 이름을 R이라고 변경, F는 필드의 이름을 변경하는 리스트.

 

조인 ▷◁

크로스프로덕트를 한 후에 셀렉션과 프로젝션을 바로 적용하는 것으로 정의될 수 있음.

- 조건조인 (Condition Join)
 : 크로스 프로덕트 후에 조건 c로 셀렉션을 하는 것

- 동등조인 (Equi-Join)
 : 조건조인이 R.sid=S.sid의 형태(R과 S의 두 필드간에 등호가 들어가는 형태)의
   (^으로 연결된) 등식들만으로 구성되는 것.
   이 경우, 결과에 두 애트리뷰트를 모두 유지하기 때문에 중복이 있게됨. -> S.sid를 제거(정제 작업 수행)

   R과 S로 부터 같은 이름을 상속하는 두 필드를 포함하면, 결과 릴레이션에서 그 두 필드에는 이름이 붙여지지 않음.

sid 필드는 오직 한번만 결과에 나타남

- 자연조인 (Natural Join)
 : 동등조건이 R과 S에서 동일한 이름을 가지고 있는 모든 필드에 대해 명시되는 동등조인. (조건 조인 생략 가능)
   묵시적으로 조인 조건은 모든 공통 필드에 대한 동등조건들로 구성됨.
   결과가 동일한 이름을 가진 두 필드를 갖지 않도록 보장됨. (중복 없음)

 

디비전

디비전 연산 A/B는 B(의 투플)에 있는 모든 y값에 대해서 A에 투플 <x,y>가 존재하는
(단항 투플 형태의) 모든 x값들의  집합으로 정의됨.

* A/B를 기본 대수 연산자로 풀어 표현한다면?

A에서 자격이 없는 모든 x값

 

 

---

대수 질의의 예제들

Q1) 배 103을 예약한 뱃사람의 이름을 구하시오.

개선

sol3보다 sol1,2가 더 좋음.
(중간 결과의 릴레이션 크가기 더 작기 때문에 계산비용 더 적게 듦)


Q2) 적색 배를 예약한 뱃사람의 이름을 구하시오.

개선

두번째 식이 필드 수가 더 적은 중간 릴레이션들을 생성하므로
더 적은 수의 투플들을 가지는 중간 릴레이션 인스턴스들이 됨.


Q5) 적색 배나 녹색 배를 예약한 뱃사람의 이름을 구하시오.

using union

Q6) 적색 배와 녹색 배를 예약한 뱃사람의 이름을 구하시오.

마지막줄 교집합을 합집합으로 바꾸면 Q5)의 정답임.

키(key)로 프로젝션하지 않으면 의도치 않은 결과 나옴!
만약 여기서 sid가 아니라 sname으로 프로젝션했었다면
각각 적색과 녹색의 배를 예약한 동명이인이 있는 경우 그 사람이 포함됨.


Q9) 모든 배를 예약한 뱃사람들의 이름을 구하시오.

디비전은 두번째 릴레이션의 모든 bid에 대해서
첫번째 릴레이션에 투플 <sid,bid>가 존재하는 sid값 모두를 반환함.


Q10) Interlake라고 하는 배를 모두 예약한 뱃사람들의 이름을 구하시오.

Q7) 적어도 두 척의 배를 예약한 뱃사람의 이름을 구하시오.