관계대수

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

관계 대수는 에드거 F. 코드가 제안한 관계형 모델에 기반한 데이터베이스 언어의 기초로, 데이터베이스 질의 언어의 한 종류이다. 관계 대수는 집합론과 일계 술어 논리에 기반하며, 관계 모델의 개념을 사용하여 테이블 형태의 데이터를 연산한다.

관계 대수는 역사적으로 IBM의 ISBL, Tutorial D 등의 데이터베이스 언어에 영향을 미쳤으며, SQL에도 부분적으로 영향을 주었지만, SQL은 관계 대수를 완전하게 구현하지는 않는다.

관계 대수는 기본적인 연산자로 집합 연산(합집합, 차집합, 교집합, 데카르트 곱)과 관계 대수 특유의 연산자(제한, 투영, 결합, 나눗셈)를 사용한다. 또한, 속성 이름 변경, 확장, 요약 등의 응용적인 연산자를 통해 기능을 확장한다.

관계 대수식은 트리 구조로 표현되며, 질의 최적화를 통해 연산 순서를 변경하여 질의 처리 효율을 높인다. 제한 연산의 이동, 복합 제한 연산의 분할 및 결합, 결합 연산과 제한 연산의 조합 등을 통해 질의의 성능을 향상시킨다.

2. 역사

코드가 1969년에 관계형 모델을 고안하기 전까지 관계대수는 거의 주목받지 못했다.^[7] 코드는 관계대수를 데이터베이스 언어 (질의 언어)의 기초로 제안했다. 코드의 관계대수에 기초하여 구현된 최초의 데이터베이스 언어는 IBM의 ISBL (Information Systems Base Language)이었다.^[7] ISBL은 PRTV (Peterlee Relational Test Vehicle)라는 관계형 데이터베이스 관리 시스템 (RDBMS, 관계형 데이터베이스)의 데이터베이스 언어였다. ISBL은 데이터베이스 분야의 권위자들로부터 코드의 구상을 사용하기 쉬운 언어로 구현하는 길을 열었다고 평가받았다. 이후 ISBL을 계승한 IBM Business System 12라는 RDBMS는 업계에 단기간 영향을 미쳤다. 1998년에 크리스 데이트와 휴 다윈은 Tutorial D라는 데이터베이스 언어를 제창했다.^[8] Tutorial D는 관계형 데이터베이스 이론 학습을 위해 사용되었으며, ISBL의 기본적인 사고방식을 이용했다. Rel이라는 RDBMS는 Tutorial D를 구현했다. SQL은 관계대수에 어느 정도 기반을 두고 있지만, 완전하지는 않다. SQL의 연산 대상인 표 (테이블)는 엄밀하게 관계라고 할 수 없으며, 관계대수의 몇 가지 편리한 법칙도 SQL에서는 활용할 수 없다. 이 때문에 관계대수식의 최적화, 옵티마이저 및 데이터베이스 이용자에게 큰 손실을 주고 있다.^[10]

3. 관계 모델

관계 대수는 관계 모델에 기반한 관계 데이터베이스의 데이터베이스 언어 (질의 언어)이므로, 먼저 관계 모델을 간단히 정의한다. 관계 모델의 기본적인 구성 요소는 정의역, 즉 데이터 타입이다. 튜플은 순서가 없는 속성의 집합이다. 속성은 정의역과 값의 쌍이다. 관계 변수는 특정 관계형의 이름이 붙은 변수이며, 순서가 없는 속성 이름과 속성의 정의역의 쌍의 집합이다. 관계 변수는 관계의 머리글을 제공한다. 관계는 머리글과 튜플 집합으로 구성된다.^[1] 이러한 관계 모델의 개념은 수학적으로 정의되지만, 기존 데이터베이스의 구현은 이러한 정의에 엄격하게 준수하지 않는다. 테이블은 관계의 시각적 표현으로 받아들여지고 있다. 튜플은 행의 개념과 유사하다.

4. 관계 논리와의 관계

관계 대수와 관계 논리(관계 계산)는 서로 동등하다. 즉, 관계 대수로 표현된 식은 그에 상응하는 관계 논리의 식으로 표현할 수 있으며, 그 반대로도 가능하다. 이러한 동등성은 집합론과 일계 술어 논리에 기반을 둔 관계 대수의 기본 개념에서 비롯된다.

관계 대수를 구현한 대표적인 데이터베이스 언어로는 SQL과 Tutorial D가 있다. SQL은 관계 대수와 관계 논리를 구현한 것으로 널리 알려져 있다. 그러나 크리스 데이트와 휴 다웬을 비롯한 일부 연구자들은 SQL이 코드가 제안한 관계 대수를 완벽하게 구현하지 못한다고 비판하며, 완전한 구현체로 D (Tutorial D)를 제안했다.

관계는 특정 술어의 외연으로 해석될 수 있으며, 관계 대수의 각 연산자는 술어 계산의 해당 연산으로 해석할 수 있다. 예를 들어, 자연 결합은 논리곱 AND ( $\land$ )에 해당한다. 관계 ''R''과 관계 ''S''가 각각 술어 ''p1''과 술어 ''p2''의 외연을 나타낸다면, ''R''과 ''S''의 자연 결합 (''R'' $\bowtie$ ''S'')은 술어 ''p1'' $\land$ ''p2''의 외연을 나타낸다.

5. 관계의 형 적합성

집합론에 기반한 관계 연산자 (합집합, 차집합, 교집합)에서는 두 개의 형(type)이 적합(compatible)한 관계를 대상으로 연산을 수행한다. 형 적합은 합집합 호환(union-compatibility)이라고도 한다. 이러한 관계 연산에서는 형이 적합하지 않은 두 관계를 대상으로 연산을 수행할 수 없다.

관계의 형 적합이란, 두 관계가 잘 조합될 수 있다는 것을 의미한다. 구체적으로, 관계 R과 관계 S가 형 적합성을 가지려면 다음 조건을 만족해야 한다.

R과 S가 같은 수의 속성을 가지고 있을 것.
R과 S가 가진 속성의 이름이 같을 것.
R과 S가 가진 같은 이름의 속성의 정의역이 같을 것.

6. 기본적인 연산자

관계 대수의 연산자는 크게 집합론에 기반한 연산자와 관계 대수에 특유한 연산자로 분류할 수 있다.^[1]

집합론에 기반한 연산자로는 합집합, 차집합, 교집합, 데카르트 곱이 있다. 관계 대수 특유의 연산자로는 제한(선택), 투영, 결합, 제어가 있다.^[1] 나눗셈은 SQL에서 직접 구현되지 않는 특수한 연산자이다.

이러한 연산자들은 관계에 대해 연산을 수행하며, 그 결과 역시 관계이다. 따라서 관계 대수 연산은 중첩되어 사용될 수 있다.

6. 1. 집합 연산자

관계 대수는 집합론의 집합의 합집합, 집합의 차집합, 집합의 교집합, 데카르트 곱 연산을 사용한다. 합집합, 차집합, 교집합 연산은 두 관계가 형 적합성을 가져야 한다. 형 적합성은 합집합 호환이라고도 불리며, 두 관계의 속성 수, 이름, 정의역이 같아야 함을 의미한다.^[1] 데카르트 곱은 두 관계가 서로소 헤더, 즉 공통된 속성 이름을 가지지 않아야 정의될 수 있다.^[1]

6. 1. 1. 합집합 (Union)

집합론에 기반한 관계 연산자 중 하나인 합집합(union) 연산 R ∪ S는 R과 S의 모든 튜플(tuple, 행)로 구성된 하나의 관계를 반환한다.^[1] 이 연산은 R과 S가 타입 적합성, 즉 합집합 호환성을 갖는다는 것을 전제로 하며, 연산 결과 중복되는 튜플은 제거된다.^[1]

관계 R과 S가 타입 적합성을 갖는다는 것은 다음을 의미한다.

R과 S는 같은 수의 속성을 가진다.
R과 S는 같은 이름의 속성을 가진다.
R과 S에서 같은 이름을 가진 속성의 정의역이 같다.

6. 1. 2. 차집합 (Difference)

두 관계 R과 S의 차집합은 R에서 S에 속하는 튜플을 제거한 관계를 반환한다.^[1] R과 S는 합집합 호환이 되어야 한다. 즉, 두 관계는 동일한 속성 집합을 가져야 한다.^[1]

R
A	B	C
1	2	3
4	5	6

S
A	B	C
4	5	6
7	8	9

R - S
A	B	C
1	2	3

6. 1. 3. 교집합 (Intersection)

집합론에 기반한 관계 연산자 중 하나로, 두 관계 R과 S 모두에 속하는 튜플로 구성된 관계를 반환한다. 집합의 교집합은 집합의 합집합과 집합의 차집합을 사용하여 정의되므로, 교집합 연산에 관련된 두 관계 역시 합집합 호환되어야 한다.^[1] 즉, 두 관계는 동일한 속성 집합을 가져야 한다.^[1] 교집합 연산은 차집합 연산을 사용하여 표현할 수 있다. (R ∩ S = R - (R - S))^[1]

6. 1. 4. 데카르트 곱 (Cartesian Product)

관계 R과 S의 데카르트 곱은 R의 모든 튜플과 S의 모든 튜플을 조합한 모든 튜플로 구성된 관계를 반환하며, R과 S는 형 적합성을 가질 필요가 없다.^[1]

데카르트 곱이 정의되려면 관련된 두 관계는 서로소 헤더를 가져야 한다. 즉, 공통된 속성 이름을 가져서는 안 된다.^[1]

데카르트 곱은 집합 이론에서의 데카르트 곱과는 다르게 정의된다. 튜플이 연산의 목적에 따라 "얕게" 간주된다. 즉, ''n''-튜플 집합과 ''m''-튜플 집합의 데카르트 곱은 "평평해진" (''n'' + ''m'')-튜플 집합을 생성한다. 반면, 기본적인 집합 이론은 각각 ''n''-튜플과 ''m''-튜플을 포함하는 2-튜플 집합을 규정했을 것이다.^[1] 더 형식적으로, ''R'' × ''S''는 다음과 같이 정의된다.^[1]

:

R\times S:=\{(r_1,r_2,\dots,r_n,s_1,s_2,\dots,s_m)|(r_1,r_2,\dots,r_n)\in R, (s_1,s_2,\dots,s_m)\in S\}

데카르트 곱의 기수는 그 인수의 기수의 곱이다. 즉, |''R'' × ''S''| = |''R''| × |''S''|이다.^[1]

6. 2. 관계 대수 특유 연산자

관계 대수는 집합론에 기반한 연산자와 관계 대수 특유의 연산자로 분류할 수 있다. 관계 대수 특유의 연산자에는 제한(선택), 투영, 조인, 나눗셈이 있다.^[1]

제한(Selection): 주어진 조건을 만족하는 튜플들을 선택한다.
투영(Projection): 주어진 속성들만 남기고 나머지 속성들은 제거한다.
조인(Join): 두 관계에서 공통 속성을 기준으로 튜플들을 결합한다.
나눗셈(Division): 특정 조건을 만족하는 튜플들을 포함하는 관계를 반환한다. SQL에서는 직접 구현되지 않는다.

6. 2. 1. 제한 (Selection)

'''일반화된 선택'''(σ)은

\sigma_\varphi(R)

로 표기되는 단항 연산이며, 여기서 φ는 명제 공식으로, 일반 선택에 허용된 원자 공식과 논리곱(and), 논리합(or),

\neg

(부정) 논리 연산자로 구성된다. 이 선택은 ''R''의 모든 튜플 중에서 φ가 참인 튜플을 선택한다.^[1]

예를 들어 주소록에서 모든 친구 또는 비즈니스 파트너의 목록을 얻기 위해 선택을

\sigma_{\text{isFriend = true} \,\lor\, \text{isBusinessContact = true}}( \text{addressBook} )

로 작성할 수 있다. 결과는 isFriend가 참이거나 isBusinessContact가 참인 모든 고유 레코드의 모든 속성을 포함하는 관계가 된다.^[1]

6. 2. 2. 투영 (Projection)

'''프로젝션'''은

\Pi_{a_1, \ldots,a_n}( R )

와 같이 작성되는 단항 연산이며, 여기서

a_1,\ldots,a_n

은 속성 이름의 집합이다. 이러한 프로젝션의 결과는 ''R''의 모든 튜플이 집합

\{a_1,\ldots,a_n\}

으로 제한될 때 얻어지는 집합으로 정의된다.^[1]

SQL 표준에서 구현될 때 "기본 프로젝션"은 집합 대신 멀티셋을 반환하며, 중복 데이터를 제거하는 프로젝션은 DISTINCT 키워드를 추가하여 얻는다.^[1]

6. 2. 3. 결합 (Join)

관계 대수에서 결합(Join)은 두 관계에서 공통 속성을 기반으로 튜플을 결합하여 새로운 관계를 반환하는 연산이다. 예를 들어, 서적 데이터베이스에서 특정 서명을 가진 서적을 재고로 보유한 서점의 점포명과 전화번호를 조회하는 절차는 다음과 같다.

1. 서적 관계와 서명 관계를 서점 ID로 결합한다.

2. 결합하여 생성된 관계를 지정된 서명으로 제한한다.

3. 제한하여 생성된 관계를 점포명과 전화번호로 사영한다.

이러한 조회는 관계 논리(관계 계산)에서 다음과 같이 표현할 수 있다.

관계 대수의 연산자는 집합론 기반 연산자(합집합, 차집합, 교집합, 데카르트 곱)와 관계 대수 특유의 연산자(제한(선택), 투영, 조인, 나눗셈)로 분류할 수 있다.^[1]

6. 2. 4. 나눗셈 (Division)

나눗셈(÷)은 이항 연산으로, ''R'' ÷ ''S''와 같이 표기한다. 나눗셈은 SQL에서 직접 구현되지 않는다. 결과는 ''R''에만 있고 ''S''에는 없는 속성(즉, ''R''의 헤더에는 있지만 ''S''의 헤더에는 없는 속성)으로 제한된 ''R''의 튜플 집합으로 구성된다. 이 튜플들은 ''S''의 모든 튜플과의 조합이 ''R''에 존재한다.

''완료됨''
학생	과제
프레드	데이터베이스1
프레드	데이터베이스2
프레드	컴파일러1
유진	데이터베이스1
유진	컴파일러1
사라	데이터베이스1
사라	데이터베이스2

''DB프로젝트''
과제
데이터베이스1
데이터베이스2

''완료됨'' ÷ ''DB프로젝트''
학생
프레드
사라

만약 ''DB프로젝트''가 데이터베이스 프로젝트의 모든 과제를 포함한다면, 위의 나눗셈 결과는 데이터베이스 프로젝트의 두 과제를 모두 완료한 학생만 정확하게 포함한다.

더욱 형식적으로 나눗셈의 의미는 다음과 같이 정의된다.

: ''R'' ÷ ''S'' = { ''t''[''a''₁,...,''a''_''n''] : ''t'' ∈ ''R'' ∧ ∀''s'' ∈ ''S'' ( (''t''[''a''₁,...,''a''_''n''] ∪ ''s'') ∈ ''R'') }

여기서 {''a''₁,...,''a''_''n''}은 ''R''에 고유한 속성 이름의 집합이고, ''t''[''a''₁,...,''a''_''n'']은 이 집합에 대한 ''t''의 제한이다. 일반적으로 ''S''의 헤더에 있는 속성 이름은 ''R''의 부분 집합이어야 한다. 그렇지 않으면 연산의 결과는 항상 비어 있게 된다.

기본 연산을 사용하여 나눗셈을 시뮬레이션하는 방법은 다음과 같다. ''a''₁,...,''a''_''n''은 ''R''에 고유한 속성 이름이고, ''b''₁,...,''b''_''m''은 ''S''의 속성 이름이라고 가정한다.

1. 먼저 ''R''을 고유한 속성 이름에 투영하고, ''S''의 튜플과 모든 조합을 구성한다.

: ''T'' := π_{''a''₁,...,''a''_''n''}(''R'') × ''S''

이전 예제에서, T는 모든 학생(학생이 완료됨 테이블의 고유 키/속성이기 때문에)이 주어진 모든 과제와 결합된 테이블을 나타낸다. 예를 들어, 유진은 T에 유진 → 데이터베이스1과 유진 → 데이터베이스2의 두 행을 갖게 된다.

2. 다음 단계에서는 ''T''에서 ''R''을 뺀다.

: ''U'' := ''T'' − ''R''

''U''에는 ''R''에 "있을 수 있었지만" 없었던 가능한 조합이 있다.

3. 이제 ''R''에 고유한 속성 이름에 대한 투영을 수행하면 ''S''의 튜플과 모든 조합이 ''R''에 존재하지 않았던 튜플의 제한을 얻게 된다.

: ''V'' := π_{''a''₁,...,''a''_''n''}(''U'')

4. 마지막으로, ''R''을 고유 속성 이름으로 투영하고 ''V''를 뺀다.

: ''W'' := π_{''a''₁,...,''a''_''n''}(''R'') − ''V''

7. 응용적인 연산자

관계 대수는 외부 조인, 집계 함수, 전이적 폐쇄 등 다양한 연산으로 확장된다.^[3]

Codd의 대수를 기반으로 한 최초의 쿼리 언어는 Codd 박사가 직접 개발한 Alpha였다. 그 후 ISBL이 만들어졌으며, 많은 권위자들^[7]은 ISBL이 Codd의 아이디어를 유용한 언어로 만드는 방법을 제시했다고 평가했다. Business System 12는 ISBL의 예를 따른, 수명이 짧았던 산업용 관계형 DBMS였다.

1998년 크리스 데이트와 휴 다윈은 관계형 데이터베이스 이론 교육용 언어인 '''튜토리얼 D'''를 제안했으며, 이 언어 또한 ISBL의 아이디어를 활용한다.^[8] Rel은 '''튜토리얼 D'''의 구현체이다. Bmg는 '''튜토리얼 D'''와 ''The Third Manifesto''의 원칙을 엄격히 따르는, Ruby로 구현된 관계 대수이다.^[9]

SQL은 관계 대수를 느슨하게 기반으로 하지만, SQL의 피연산자(테이블)는 관계가 아니며, 관계 대수의 몇 가지 유용한 정리들은 SQL에서 성립하지 않는다. (이는 최적화 프로그램 및/또는 사용자에게 불이익을 줄 수 있다.) SQL 테이블 모델은 집합이 아닌 백(bag) (멀티셋)이다. 예를 들어, 집합에 대한 관계 대수의 정리인 $(R \cup S) \setminus T = (R \setminus T) \cup (S \setminus T)$ 는 백에 대한 관계 대수에는 적용되지 않는다.^[10]

{| class="wikitable"

|+ 예시

|-

|

R:
A	B	C
1	2	3
4	5	6

||

S:
A	B	C
7	8	9
4	5	6

||

R ∩ S:
A	B	C
4	5	6

|}

7. 1. 속성 이름 변경 (Rename)

이름 바꾸기(ρ, rename)는 단항 연산이며,

\rho_{a / b}(R)

로 표기한다. 그 결과는 모든 튜플에서 ''b'' 속성이 ''a'' 속성으로 이름이 변경된 것을 제외하고는 ''R''과 동일하다. 이는 일반적으로 관계의 속성을 조인을 위해 이름을 변경하는 데 사용된다.^[1]

예를 들어 "isFriend" 속성을 관계에서 "isBusinessContact"로 변경하려면

\rho_{\text{isBusinessContact / isFriend} } ( \text{addressBook} )

을 사용할 수 있다.^[1]

또한

\rho_{x(A_1, \ldots,A_n)}(R)

표기법을 사용하여 ''R''의 이름을 ''x''로 바꾸고 속성

\{a_1,\ldots,a_n\}

의 이름을

\{A_1,\ldots,A_n\}

로 바꿀 수도 있다.^[1]

7. 2. 확장 (Extend)

데이터베이스 이론에서 '''확장된 투영'''은 어떤 식에 기초하여 산출되는 새로운 속성이 관계에 추가되어 반환되는 것을 의미한다.^[10] 예를 들어 단가에 수량을 곱하여 총 가격을 얻는 식과 같이, 두 열의 숫자를 곱하는 식을 작성할 수 있다. 실제 쿼리 언어는 이러한 기능을 갖추고 있는데, 예를 들어 SQL의 SELECT는 산술 연산을 사용하여 결과에 새로운 열을 정의할 수 있다.^[5] 튜토리얼 D의 `EXTEND` 키워드에서도 유사한 기능을 명시적으로 제공한다.^[5]

7. 3. 요약 (Summarize)

관계 대수는 외부 조인, 집계 함수, 전이적 폐쇄와 같은 다양한 연산으로 확장된다.^[3]

열에 대한 다양한 함수 (예: 해당 요소들의 합 계산)는 기존 관계 대수로는 불가능하다. 대부분의 관계형 데이터베이스 시스템에는 합계, 개수, 평균, 최대값, 최소값의 5가지 집계 함수가 포함되어 있다. 관계 대수에서 스키마 (''A''₁, ''A''₂, ... ''A''_''n'')에 대한 집계 연산은 다음과 같이 작성한다.

: G₁, G₂, ..., G_m g_{f₁(A₁'), f₂(A₂'), ..., f_k(A_k')} (r)

여기서 각 A_j', 1 ≤ j ≤ k는 원래 속성 A_i, 1 ≤ i ≤ n 중 하나이다.

''g'' 앞에 오는 속성은 그룹화 속성으로, SQL의 "group by" 절과 같은 기능을 한다. 그 후 개별 속성에 적용되는 임의의 수의 집계 함수가 온다. 이 연산은 임의의 관계 ''r''에 적용된다. 그룹화 속성은 선택 사항이며, 생략시 집계 함수는 연산이 적용되는 전체 관계에 걸쳐 적용된다.

Account^영어라는 이름의 테이블에 Account_Number|계좌 번호^영어, Branch_Name|지점명^영어, Balance|잔액^영어이라는 세 개의 열이 있다고 가정해 보자. 각 지점의 최대 잔액을 찾으려면 _{Branch_Name|지점명^영어}''G''_{Max(Balance|잔액^영어)}(Account|계정^영어)으로 표현할 수 있다. 지점에 관계없이 모든 계정의 최고 잔액을 찾으려면 ''G''_{Max(Balance|잔액^영어)}(Account|계정^영어)라고 쓸 수 있다.

그룹화는 _{Branch_Name^영어}''ɣ''_{Max(Balance^영어)}(Account^영어) 대신에 자주 쓰인다.^[10]

8. 질의 최적화

관계 대수식은 트리 구조로 표현될 수 있으며, 최적화는 이 트리 구조를 변환하여 수행된다. 관계 대수는 관계 데이터베이스 관리 시스템(RDBMS)의 데이터베이스 언어(질의 언어)의 기초가 된다.

8. 1. 최적화의 목표

관계대수는 관계 데이터베이스 관리 시스템(RDBMS, 관계형 데이터베이스) 데이터베이스 언어(질의 언어)의 기초가 된다. 관계대수와 관계 논리(관계 계산)는 서로 동일하여, 관계대수로 표현된 식은 동일한 관계 논리 식으로 표현 가능하며, 그 반대도 가능하다.

관계대수를 구현한 데이터베이스 언어로는 SQL이나 Tutorial D 등이 있다. SQL은 관계대수와 관계 논리를 구현한 것으로 여겨지지만, 크리스 데이트와 휴 다웬 등은 SQL이 에드거 F. 코드의 관계대수를 완전하게 구현하지 못한다고 비판하며, 완전한 구현으로 D(Tutorial D)를 제안했다.

관계는 술어의 외연으로 해석될 수 있으며, 관계대수의 각 연산자는 술어 계산에 해당하는 것으로 해석할 수 있다. 예를 들어, 자연 결합은 논리곱 AND (

\land

)에 해당한다. 관계 ''R''과 관계 ''S''가 각각 술어 ''p1''과 술어 ''p2''의 외연을 표현한다면, ''R''과 ''S''의 자연 결합 (''R''

\bowtie

''S'')은 술어 ''p1''

\land

''p2''의 외연을 표현한다.

코드의 관계대수는 일계 술어 논리에 대해 완전하지 않은데, 이는 컴퓨터 구현상의 어려움 때문이다. 코드는 관계대수의 연산 대상을 유한한 관계로 한정하고, 부정(NOT)과 선언(OR)을 제한적으로 지원하여 이 문제를 해결했다. 코드의 관계대수는 혼 절에서 재귀와 부정이 없는 일계 술어 논리의 서브셋이다.

코드는 관계 데이터베이스 언어의 표현 능력에 대해 '''관계 완비'''라는 용어를 정의했는데, 이는 코드가 제안한 제한 하에서 일계 술어 논리에 대해 완전한 언어임을 의미한다. 관계대수는 관계 완비이며, 관계대수와 동등하거나 그 이상의 표현 능력을 가진 관계 데이터베이스 언어는 관계 완비라고 할 수 있다. 관계 논리는 관계대수와 동등한 표현 능력을 가지므로 관계 완비이다.

어떤 대수든, 기본적인(프리미티브) 연산자와 그렇지 않은 연산자로 나눌 수 있다. 관계대수에서 기본적인 연산자의 선택은 논리학에서의 기본적인 연산자 선택과 유사하다. 코드는 관계대수에서 다음 6개의 기본적인 연산자를 정했다.

제한(선택)
투영
데카르트 곱(데카르트 곱)
합(합집합)
차(차집합)
속성 이름 변경

이 6개의 연산자는 관계대수의 기반을 이루며, 이들 중 어느 하나라도 제외하면 표현 능력이 손상된다. 이 6개의 연산자를 기반으로 다른 많은 연산자들이 정의되었으며, 그 중 중요한 것은 교집합(교차, 교집합), 제어, 자연 결합이다.

직적(積, 데카르트 곱, cartesian product) 연산 R × S는 R과 S의 튜플(組, tuple)의 모든 조합의 관계(데카르트 곱)를 반환한다. 즉, R이 가진 모든 튜플이 S가 가진 모든 튜플과 조합된다. 직적 연산에서 R과 S가 타입 적합(型適合)일 필요는 없다. 직적 연산 R × S의 튜플의 수는 R의 튜플의 수와 S의 튜플의 수를 곱한 수가 되며, 직적 연산 R × S의 속성의 수는 R의 속성의 수와 S의 속성의 수를 더한 수가 된다.^[1]

데카르트 곱에서 관계 R과 S에 공통된 속성 이름이 없어야 한다.^[1]

8. 2. 최적화 규칙

집합론과 일계 술어 논리를 기반으로 하는 관계대수는 관계 데이터베이스 관리 시스템(RDBMS)에서 데이터베이스 언어(질의 언어)의 기초가 된다. 관계대수 최적화 규칙은 다음과 같다.

제한 연산의 이동: 제한(selection) 연산은 질의 트리 구조의 잎(leaf) 방향으로 이동시켜 연산 대상 관계의 카디널리티(cardinality)를 최대한 줄인다.
복합 제한 연산의 처리: 복합 제한 연산은 분할하거나 결합할 수 있다.
직접곱 연산의 최적화: 직접곱(cartesian product) 연산 전에 연산 대상 관계의 크기를 최대한 줄인다.
제한 연산과 집합 연산의 순서 조정: 제한 연산과 집합 연산(차집합, 합집합, 교집합)의 순서를 조정한다.

참조

_[1] 논문 A Relational Model of Data for Large Shared Data Banks 1970
_[2] 서적 Database system concepts 2020
_[3] 서적 Principles of Distributed Database Systems https://books.google[...] Springer
_[4] 서적 Database: Principles, Programming, and Performance, Second Edition https://books.google[...] Morgan Kaufmann
_[5] 서적 SQL and Relational Theory: How to Write Accurate SQL Code https://books.google[...] O'Reilly Media, Inc.
_[6] 논문 Universality of data retrieval languages
_[7] 웹사이트 Edgar F. Codd - A.M. Turing Award Laureate https://amturing.acm[...] 2020-12-27
_[8] 웹사이트 Databases, Types, and the Relational model: The Third Manifesto https://www.dcs.warw[...] 2024-07-04
_[9] 웹사이트 Bmg documentation https://www.relation[...] 2024-07-04
_[10] 서적 Database systems: the complete book Pearson Prentice Hall
_[11] 간행물

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com