DB02 - relational algebra (관계 대수)

목차

- 관계 대수

- 선택

- 프로젝션

- 데카르트 곱

- 조인

- 이름 바꾸기

- 합집합

- 집합 교차

- 집합 차집합

대수(Algebra)

1. 수학 시스템은 다음과 같이 구성된다.

• 피연산자(Operands) : 새로운 값을 구성하는 데 사용되는(be constructed) 변수 또는 값

  • 숫자, 변수

• 연산자(Operators) : 주어진 피연산자에서 새로운 값을 구성하는 절차를 나타내는(denoting) 기호(symbol)

  • add , sub, multi, divide

관계 대수(Relational ALgebra)

0. Relation Algebra

• Operands : relations / tables

• Operators : ()

1. 하나 또는 두 개의 관계를 입력으로 받아, 새로운 관계를 출력하는 일련의 연산으로 구성된 절차적 언어(procedural language)

2. 기본 연산자

• 선택(select) : σ

• 프로젝션(project) : ∏

• 데카르트 곱(Cartesian product) : ×

• 조인(join) : ⋈

• 이름 바꾸기(rename) : ρ

• 합집합(union) : ∪

• 집합 교차(set-intersection) : ∩

• 집합 차집합(set-difference) : –

두 개의 예시 관계

1. 이 모듈에서는 개념을 설명하기 위해 다음 두 개의 예시 관계를 사용할 것임

: 강사(instructor) 관계 / 가르치는 과목(teaches) 관계

• instructor relation : 4 cols, 12 records

• teaches relation : 5 cols, 15 records

Select Operation 선택 연산 - (1)

1. 선택(select) 연산은 주어진 술어(predicate)를 만족하는(satisfy) 튜플을 선택함

2. 표기법: σp(r)

• p는 선택 술어(selection predicate)라고 함

• r : releation

• p : predicate

3. 예시: "Comp. Sci." 학과에 속하는 강사 튜플 선택

1) 쿼리: σdept_name=“Comp. Sci.”(instructor)

- Query = expression in relational algebra

(검색 전)

(결과)

선택 연산 - (2)

1. 선택 술어(selection predicates)에서 =, ≠, >, ≥, <, ≤를 사용한 비교가 허용됨(Comparison)

2. 여러 술어를 결합하여 더 큰 술어를 생성할 수 있음: ∧ (and), ∨ (or), ¬ (not)

3. 예시: Comp. Sci.에서 연봉이 $70,000보다 높은 강사 찾기

1) 쿼리: σdept_name=“Comp. Sci.” ∧ salary > 70,000(instructor)

(검색 전)

(결과)

프로젝션 연산

1. 특정(certain) 속성을 제외하고(left out) 인수 관계를 반환하는 단항 연산(unary operation)

1) 표기법: ΠA1,A2,A3,…,Ak(r)

(1) A1, A2, A3,…, Ak는 속성 이름이고 r은 관계 이름

2) 결과는 k개의 열을 가진 관계로 정의됨

(1) A1, A2, A3,…, Ak에 나열되지 않은(not listed among) 열은 결과에서 제거됨

(2) 결과에서 중복 행이 제거됨 (결과 관계는 집합이므로)

2. 예시: instructor의 ID와 dept_name 속성 제거

1) 쿼리: Πname, salary(instructor)

2) 결과:

결과 : ID, dept_name 속성을 제거한 결과 (Projected relation)

3) 만약 Original relation에 3333 Kim Music 80000이 추가된다면?

: name, salary가 같아서 괜찮다.

관계 연산의 조합(Composition)

1. 관계 대수 연산은 함께 조합되어 관계 대수 표현식으로 구성될 수 있음(can be composed)

1) 관계 대수의 결과는 관계임을 기억할 것

2) 프로젝션 연산의 인수로 관계의 이름 대신 평가하여 결과가 관계가 되는 표현식을 제공할 수 있음

2. 아래의 쿼리를 고려하자 : Comp. Sci. 학과의 모든 강사 이름 찾기

1) 쿼리: Πname(σ dept_name=“Comp. Sci.”(instructor))

데카르트 곱 연산 (Cartesian-Product Operation)

1. 데카르트 곱 연산(× 기호 사용)은 두 관계의 정보를 결합함

1) 가능한 모든 튜플 쌍의 결과 관계를 구성함

2. 예시: instructor와 teaches 관계의 데카르트 곱

1) 쿼리: instructor × teaches

2) 결과 (총 180 튜플 = 12 강사 × 15 강의)

조인 연산

1. 데카르트 곱은 instructor의 모든 튜플을 teaches의 모든 튜플과 연결함

1) 이전 예시에서 결과로 나온 행 대부분은 특정 과목을 가르치지 않은 강사에 대한 정보임

2. 예시: 강사가 가르친 과목과 관련된 “instructor × teaches”의 튜플만 가져오기

1) 쿼리: σ instructor.id=teaches.id(instructor × teaches)

2) 결과

3. 조인 연산은 선택 연산(select operation)과 데카르트 곱 연산을 하나의 연산으로 결합함(combines)

4. 관계 r(R)와 s(S)에 대해(Consider)

1) ?는 R “합집합(union)” S의 속성에 대한 술어임

2) 조인 연산 r ⋈θ는 다음과 같이 정의됨 : ? ⋈θ ? = ?θ ? × ?

- ⋈θ : predicate(condition)

3) 예시: ? instructor.id=teaches.id(instructor × teaches)는 instructor ⋈ Instructor.id=teaches.id teaches와 동등함

- If oustred(?) natural join, makes JOIN based on column names

5. 결과

집합 합집합 연산

1. 합집합 연산(union operation)은 두 관계를 결합하여 두 관계의 슈퍼셋을 생성함

1) 표기법: r ∪ s

- r, s : Binary Operation (이항 연산, 두 개의 관계를 입력으로 받는 연산)

2. r ∪ s가 유효하려면:

1) r, s는 같은 수의 속성(같은 차수(airty))을 가져야 함

(1) 예를 들어, r(A, B, C)와 s(A, B, C)는 합집합이 가능하지만, s(A, B)는 속성 개수가 다르므로 합집합을 수행할 수 없음.

2) 속성의 도메인이 호환되어야 함

(1) 예: r의 두 번째 열은 s의 두 번째 열과 동일한 유형의 값을 다룰 수 있어야 함

(2) 예를 들어, r(A: INT, B: STRING, C: FLOAT)와 s(A: INT, B: STRING, C: FLOAT)는 합집합 가능하지만, s(A: STRING, B: STRING, C: FLOAT)처럼 도메인이 다르면 합집합을 수행할 수 없음.

3) 예시: 2017년 가을 학기 또는 2018년 봄 학기 또는 두 학기에 가르친 모든 과목 찾기 (이 쿼리는 2017년 가을 학기(Fall 2017) 또는 2018년 봄 학기(Spring 2018)에 개설된 모든 과목(course_id)을 찾는 연산이다.)

(1) 쿼리

Πcourse_id (σsemester=“ Fall” ∧ year=2017 (teaches)) ∪

Πcourse_id (σsemester=“ Spring” ∧ year=2018 (teaches))

(2) 결과

- set이기 때문에, 중복된 행이 없다.

집합 교집합 연산

1. 집합 교차 연산(set intersection operation) 은 두 입력 관계 모두에 존재하는 튜플을 찾음

1) 표기법: r ∩ s

2) 가정:

(1) r, s는 같은 차수를 가짐

(2) r과 s의 속성이 호환됨

2. 예시: 2017년 가을 학기와 2018년 봄 학기 모두에 가르친 과목의 집합 찾기

1) 쿼리

Πcourse_id (σsemester=“ Fall” ∧ year=2017 (teaches)) ∩

Πcourse_id (σsemester=“ Spring” ∧ year=2018 (teaches))

2) 결과

집합 차집합 연산

1. 집합 차집합 연산(set-difference operation)은 한 관계에 존재하지만 다른 관계에는 존재하지 않는 튜플을 찾음

1) 표기법: r - s

2) 가정:

(1) r, s는 같은 차수를 가짐

(2) r과 s의 속성이 호환됨

2. 예시: 2017년 가을 학기에 가르친 과목 중 2018년 봄 학기에 가르치지 않은 과목 찾기

1) 쿼리

Πcourse_id (σsemester=“ Fall” ∧ year=2017 (teaches)) -

Πcourse_id (σsemester=“ Spring” ∧ year=2018 (teaches))

2) 결과

: 왼쪽 행에서 우측 행에 없는 행만 보여준다.

할당 연산 (Assignment Opeartion)

1. 관계 대수 표현식(relation-algebra expression)을 임시 관계 변수(temporary relation variables) 에 할당하여 쓰는 것이 편리할 때가 있음

1) 표기법: ←

2) 할당은 프로그래밍 언어의 할당과 유사하게 작동함

2. 예시: 물리학과와 음악과의 모든 강사 찾기

1) 쿼리

Physics ← σdept_name=“ Physics”(instructor)

Music ← σdept_name=“ Music” (instructor)

Physics ∪ Music

3. 할당 연산을 통해 쿼리를 순차적인(sequential) 프로그램 형태로 작성할 수 있음

1) 순차 프로그램은 일련의 할당과 쿼리 결과로 표시될 표현식으로 구성됨

이름 바꾸기 연산

1. 관계 대수 표현식의 결과에는 참조할 수 있는 이름이 없음

2. 이름 바꾸기 연산자, ρ는 관계 대수 표현식에 이름을 설정함

1) 표기법: ρnew_name(E)

(1) 표현식 E의 결과를 “new_name”이라는 이름으로 반환함

2) 예시

: ρ teacher(instructor)

: p code (instructor.id)

동치 쿼리 (Equivalent Queires)

1. 관계 대수에서는 쿼리를 작성하는 방법이 여러 가지가 있음

2. 예시: 급여가 50,000 이상인 컴퓨터 과학부 강사가 가르친 과목에 대한 정보 찾기

1) 쿼리 1 : σ dept_name=“ Comp. Sci.” ∧ salary > 50,000 (instructor)

- 한 번의 σ 연산으로 모든 조건 적용

- 12 * 2 = 24 (모든 행을 한 번씩 검사하며 두 조건을 동시에 적용)

2) 쿼리 2 : σ dept_name=“ Comp. Sci.”(σ salary > 50,000 (instructor))

- 두 번의 σ 연산으로 순차적으로 필터링

- 12 + 7 = 19 (첫 연산으로 12개 검사, 이후 남은 데이터에 대해 7개만 검사)

3) 두 쿼리는 동일하지 않지만 동치이며, 모든 데이터베이스에서 동일한 결과를 제공함

4) 쿼리 3 : σ salary > 50,000 (σ dept_name = " Comp. Sci" (instructor))

- 12 + 3 = 15 (첫 연산으로 12개 검사, 이후 남은 데이터에 대해 3개만 검사)

3. 표로 보는 위의 예시 차이

EOF

1. 다음 내용:

- MySQL

- 구조적 쿼리 언어 (SQL)

? 관계 대수(Relational Algebra) 요약

? 기본 연산자

? 선택 연산 σ

• 형식: σ 조건(테이블)

• 조건 결합: ∧(AND), ∨(OR), ¬(NOT)

• 예시:σ dept_name="Comp. Sci." ∧ salary>70000 (instructor)

? 프로젝션 연산 π

• 형식: π 열1, 열2,... (테이블)

• 중복 제거

• 예시:π name, salary (instructor)

➗ 데카르트 곱 ×

• 모든 튜플 간의 조합

• 예시:instructor × teaches

? 조인 연산 ⋈

• 일반 조인: r ⋈ 조건 s = σ조건(r × s)

• 예시:instructor ⋈ instructor.id = teaches.id teaches

➕ 합집합 ∪

• 두 테이블의 모든 튜플 + 중복 제거

• 조건: 동일한 차수 + 속성 도메인 호환

• 예시:π course_id (σ semester="Fall" ∧ year=2017 (teaches)) ∪ π course_id (σ semester="Spring" ∧ year=2018 (teaches))

☯️ 교집합 ∩

• 두 테이블 모두에 존재하는 튜플만 추출

• 예시: 위 쿼리에서 ∪를 ∩로 변경하면 교집합 연산

➖ 차집합 –

• A에는 있지만 B에는 없는 튜플만 추출

• 예시:π course_id (σ semester="Fall" ∧ year=2017 (teaches)) - π course_id (σ semester="Spring" ∧ year=2018 (teaches))

? 이름 바꾸기 ρ

• 형식: ρ 새이름(식)

• 예시:ρ teacher(instructor) → instructor 테이블을 teacher로 이름 변경

? 할당 연산 ←

• 결과를 변수로 저장하여 복합 쿼리에 사용

• 예시:

• Physics ← σ dept_name="Physics" (instructor) Music ← σ dept_name="Music" (instructor) Physics ∪ Music

? 동치 쿼리 (Equivalent Queries)

• 여러 방식으로 같은 결과 가능

• 필터 순서에 따라 성능 차이 있음

• 쿼리1: σ dept="CS" ∧ salary>50000 쿼리2: σ dept="CS" (σ salary>50000) 쿼리3: σ salary>50000 (σ dept="CS")