8.4 Relational algebra

Operations and expressions 연산 및 표현식

E. F. Codd는 관계형 모델에 대한 원래 논문에서 테이블을 조작하기 위한 형식적인 연산을 소개했다. 이러한 연산은 관계 대수(Relational Algebra)라고 불리며, 이후 정제되어 SQL의 이론적 기반이 되었다. 관계 대수는 주로 이론적인 관심의 대상이지만, SQL 쿼리의 컴파일에 실질적인 응용을 가지고 있다.
 
관계 대수에는 9개의 연산이 있다. 각 연산은 주로 그리스 문자의 특수 기호로 표시된다. 연산 기호는 숫자에 대해 사용되는 +, -, ×, /처럼 테이블과 결합하여 표현식으로 사용할 수 있다. 각 관계 대수 표현식은 SQL 쿼리와 동등하며 단일 결과 테이블을 정의한다.
Table 8.4.1: 관계대수 연산

Operation	Symbol	Greek letter	Derivation
Select	σ	sigma	corresponds to Latin letter s, for Select
Project	Π	Pi	corresponds to Latin letter P, for Project
Product	×		multiplication symbol
Join	⋈		multiplication symbol with vertical bars
Union	∪		set theory
Intersect	∩		set theory
Difference	−		set theory
Rename	ρ	rho	corresponds to Latin letter r, for Rename
Aggregate	γ	gamma	corresponds to Latin letter g, for group

 

추가 연산 관계 대수(Relational Algebra)는 표준화되어 있지 않다. 일부 저자는 할당(assign) 및 나눗셈(divide)과 같은 추가 연산을 포함시키기도 한다. 또한 조인(join) 연산의 변형인 내부 조인(inner join), 전체 조인(full join), 등가 조인(equijoin) 등을 개별적인 연산으로 간주하기도 한다.

---

Select and project

선택(Select) 연산
선택 연산은 논리적 표현식에 기반하여 테이블의 행을 선택한다. 선택 연산은 다음과 같이 표현되며:

이는 SQL의 SELECT * FROM Table WHERE expression 과 동일하다.
 
투영(Project) 연산
투영 연산은 테이블의 열을 선택한다. 투영 연산은 다음과 같이 표현되며:

이는 SQL의 SELECT Column1, Column2, ... FROM Table 과 동일하다.

1. 연산은 표현식에서 결합될 수 있다.
2. 선택 연산은 급여가 $50,000 이상인 직원을 선택한다.
3. 투영 연산은 결과에서 Name과 Salary 열을 선택한다.

---

False
첫 번째 표현식은 유효하지만 두 번째 표현식은 유효하지 않다.  
두 번째 표현식에서 내부 투영 연산이 결과에서 Name을 제거하므로, 외부 투영에서 Name을 선택하는 것은 유효하지 않다.

---

Product and join

곱(Product) 연산
곱 연산은 두 테이블을 결합하여 하나의 결과를 만든다. 결과에는 두 테이블의 모든 열과 모든 행 조합이 포함된다. 곱 연산은 다음과 같이 표현된다:

Table1 × Table2

이는 SQL의 SELECT * FROM Table1 CROSS JOIN Table2와 동일하다.
만약 Table1에  n1개의 행이 있고 Table2에 n2개의 행이 있다면, 결과는 n1×n2개의 행을 가진다.
 
조인(Join) 연산
조인 연산은 "보타이(bowtie)" 기호로 표시되며 다음과 같이 표현된다:

이는 곱 연산 후 선택(select) 연산과 동일하다:

조인 연산은 SQL의 SELECT * FROM Table1 INNER JOIN Table2 ON expression 과 동일하다.
조인 표현식은 Table1과 Table2의 열에 대한 조건을 나타내며, 종종 그리스 문자 θ(theta)로 표시된다:

이러한 θ 표기법 때문에 조인 연산은 가끔 "θ 조인(theta join)"이라고도 불린다.
조인 기호

• Left Join: ⟕
• Right Join: ⟖
• Full Join: ⟗
  조인하는 방향으로 연결을 받아들이려는 상태

---

▼See result

위의 두 표현식은 동일하다.
▼See result

▼See result

---

Q1. What is the result of the following expression?

▼View solution

Q2. How many course names are selected by the following expression?

▼View answer

2

---

합집합(Union), 교집합(Intersect), 차집합(Difference)

호환되는 테이블은 동일한 데이터 유형을 가진 동일한 수의 열을 가진다. 열 이름은 다를 수 있다. 합집합, 교집합, 차집합은 호환되는 테이블에서 작동하며, 이를 통틀어 집합 연산이라고 한다.

합집합 연산은 두 개의 호환 테이블의 모든 행을 단일 테이블로 결합한다. 중복된 행은 결과 테이블에서 제외된다. 합집합 연산은 다음과 같이 작성된다:  

Table1 ∪ Table2

 
이는 SQL의 SELECT * FROM Table1 UNION SELECT * FROM Table2 와 동일하다.

교집합 연산은 두 개의 호환 테이블에서 작동하며, 두 테이블 모두에 나타나는 행만 반환한다. 교집합 연산은 다음과 같이 작성된다:  
 

Table1 ∩ Table2

 
이는 SQL의 SELECT * FROM Table1 INTERSECT SELECT * FROM Table2 와 동일하다.

차집합 연산은 첫 번째 테이블에서 두 번째 호환 테이블에 나타나는 모든 행을 제거한다. 차집합 연산은 다음과 같이 작성된다:  

Table1 - Table2

이는 SQL의 SELECT * FROM Table1 MINUS SELECT * FROM Table2 와 동일하다.

세 가지 집합 연산 모두에서 결과 열 이름은 Table1의 열 이름이 된다.

EXCEPT 키워드는 MINUS 키워드와 동일하다.    EXCEPT와 MINUS에 대한 지원은 데이터베이스에 따라 다르다.   MySQL은 EXCEPT를 지원하지만 MINUS는 지원하지 않는다.

---

Rename and aggregate

rename 연산은 새로운 테이블 이름과 열 이름을 지정한다. 이름 변경 연산은 다음과 같이 작성된다:

TableName이 생략되면 열 이름만 변경된다.
(ColumnName1, ColumnName2, ...)가 생략되면 테이블 이름만 변경된다.
 
aggregate 연산은 SUM(), AVG(), MIN(), MAX()와 같은 집계 함수를 적용한다. 집계 연산은 다음과 같이 작성된다:

 
이는 SQL의 SELECT GroupColumn, Function(Column) FROM Table GROUP BY GroupColumn과 동일하다.
GroupColumn이 생략되면, 연산은 SQL의 SELECT Function(Column) FROM Table과 동일하며, 모든 행에 대해 단일 집계 값을 계산한다.

표기법 집계 연산의 표기법은 다양하다. 본 자료에서는 집계 연산을 그리스 문자 γ(감마)로 나타낸다.   일부 출판물에서는 라틴 문자 G, 스크립트 F(ℱ), 또는 스크립트 A(𝒜)를 사용하여 나타내기도 한다.

---

Query optimization 쿼리 최적화

관계 대수 표현식은 동일한 테이블에서 작업하고 동일한 결과를 생성하면 동등하다. Ex:

은 다음과 동등하다.

연산 순서는 다르지만, 두 표현식 모두 Employee 테이블에서 작업하며 동일한 결과 테이블을 정의한다.
 
쿼리 옵티마이저(Query Optimizer)는 SQL 쿼리를 저수준 데이터베이스 작업의 순서로 변환하며, 이를 쿼리 실행 계획(Query Execution Plan)이라 한다. 쿼리 실행 계획은 SQL 문을 처리하는 정확한 방법을 지정한다. 쿼리 옵티마이저는 프로그래밍 언어 컴파일러와 유사하다.
 
쿼리 옵티마이저는 동등한 표현식을 사용하여 쿼리 실행을 최적화한다. 옵티마이저의 작업은 다음과 같다:

1. 쿼리를 관계 대수 표현식으로 변환한다.
2. 동등한 표현식을 생성한다.
3. 각 표현식의 각 연산에 대한 '비용(cost)'을 추정한다.
4. 총 비용이 가장 낮은 최적의 표현식을 결정한다.
5. 최적의 표현식을 쿼리 실행 계획으로 변환한다.

연산의 비용(Cost)은 처리 시간을 수치로 추정한 값이다. 비용 추정은 보통 저장 매체 접근 시간과 계산 시간을 결합한 단일 척도를 사용한다. 실제로, 쿼리 옵티마이저는 더 정교한 비용 측정 방법을 사용한다.

1. 쿼리는 Lisa Ellison이 관리하는 부서를 선택한다.  
2. 관계 대수에서는 이 쿼리가 조인 연산 후 선택 연산으로 표현된다.  
3. 조인 연산은 곱 연산 후 선택 연산과 동등하다.  
4. 곱 연산은 4개의 Department 행과 3개의 Employee 행을 읽는다. 첫 번째 선택 연산은 12개의 행을 읽고, 두 번째 선택 연산은 3개의 행을 읽는다.  
5. 동등한 표현식은 먼저 Employee에서 Lisa Ellison을 선택한다.  
6. 첫 번째 선택 연산은 3개의 행을 읽는다. 곱 연산은 4개의 Department 행과 1개의 Employee 행을 읽는다. 두 번째 선택 연산은 4개의 행을 읽는다.  
7. 두 번째 표현식의 비용이 첫 번째 표현식보다 낮으므로 쿼리 실행 계획에서 사용된다.