관계 대수

데이터베이스 이론에서 관계 대수학은 데이터를 모델링하고 그것에 대한 질의를 정의하기 위해 충분한 근거가 있는 의미론들을 가진 대수학적 구조를 사용하는 이론이다. 그 이론은 에드가 F에 의해 소개되었다. Codd.

관계 대수학의 주요 적용은 관계형 데이터베이스에 대한 이론적 기반을 제공하는 것이며, 특히 그러한 데이터베이스에 대한 질의 언어 중 주로 SQL이다. 관계형 데이터베이스는 관계로 표현된 표 형식의 데이터를 저장한다. 관계형 데이터베이스에 대한 질의도 마찬가지로 관계형 데이터베이스로 대표되는 표 형식의 데이터를 반환하는 경우가 많다.

관계 대수학의 주요 전제는 하나 이상의 입력 관계를 출력 관계로 변환하는 연산자를 정의하는 것이다. 이러한 운영자들이 관계를 입력으로 받아들이고 관계를 산출하는 것을 감안한다면, 그것들은 결합되어 사용되어 잠재적으로 많은 입력 관계(데이터가 데이터베이스에 저장되는 것)를 단일 출력 관계(쿼리 결과)로 변환하는 잠재적으로 복잡한 질의를 표현하는데 사용될 수 있다.

단항 연산자는 단일 관계를 입력으로 받아들인다. 예로는 입력 관계에서 특정 속성(열) 또는 튜플(열)을 필터링하는 연산자를 포함한다.

이진 연산자는 입력 2 관계로 받아들인다. 예를 들어, 그러한 연산자는 두 입력 관계를 하나의 출력 관계로 결합한다. 예를 들어, 두 번째 관계에서 발견된 첫 번째 관계에서 튜플을 제거하고, 두 번째 관계에서 튜플을 특정 관계와 일치하는 두 번째 관계에서 튜플을 사용하여 첫 번째 관계의 튜플을 확장한다. 조건 등

특정 운영자를 포함하거나 제외할 경우 알제브라 계열을 발생시키는 다른 보다 발전된 운영자도 포함될 수 있다.

소개

관계 대수학은 E.F.가 출판되기 전까지 순수 수학 외의 다른 분야에서는 거의 주목을 받지 못했다. Codd의 1970년 데이터 관계 모델 Codd는 데이터베이스 질의 언어의 기초로 그러한 대수학을 제안했다. (실행 섹션 참조)

Codd 대수의 5개의 원시 연산자는 선택, 투영, 카르테시안 제품(크로스 제품 또는 크로스 조인이라고도 함), 세트 유니언, 세트 차이 등이다.

연산자 설정

관계 대수학에서는 세트 이론으로부터 세트 유니언, 세트 차이, 데카르트 제품을 사용하지만, 이들 연산자에 추가적인 제약조건을 부가한다.

설정된 결합과 설정 차이를 위해 관련되는 두 관계는 조합과 호환되어야 한다. 즉, 두 관계는 동일한 속성 집합을 가져야 한다. 집합교차는 집합조합과 설정차이의 관점에서 정의되기 때문에 집합교차로와 관련된 두 관계도 조합과 호환되어야 한다.

데카르트 제품을 정의하려면 관련된 두 관계가 분리 헤더, 즉 공통 속성 이름을 가지고 있지 않아야 한다.

또한, 카르트 제품은 튜플이 조작 목적상 "허용"으로 간주된다는 점에서 세트 이론의 제품과 다르게 정의된다. 즉, m-tuples 세트가 있는 n-tuples 세트의 데카르트 제품은 "flattened"(n + m)-tuple 세트를 산출한다(여기서 기본 세트 이론은 각각 n-tuple과 m-tuple을 포함하는 2-tuple 세트를 규정했을 것이다). 보다 형식적으로 R × S는 다음과 같이 정의된다.

${\displaystyle 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의 산물이다.

투영(π)

투영은 $\pi {\displaystyle {\mathrm{}}_{}}$ ${\displaystyle {a{}_{}}_{}}$ ${\displaystyle 1{{}_{}}_{}}$,${\displaystyle {}_{}}$…${\displaystyle {n_{}}_{}}$ (${\displaystyle {{}_{}}_{}}$R )${\displaystyle \Pi _{a_{1},\ldots,a_{n}}(R)$로 작성된 단항 작업이며, ${\displaystyle {여기}_{}}$서, 1 ${\displaystyle \dots ,}$ ${\$는 속성$$ 이름의 집합이다. 그러한 투영의 결과는 R의 모든 튜플이 세트$1$},${\displaystyle n_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle \{a_{1},\ldots ,a_{n}\}}$로 제한될 때 얻을 수 있는 세트로 정의된다$.$

참고: SQL 표준에서 구현했을 때 "기본 투영"은 세트 대신 멀티셋을 반환하며, 중복 데이터를 제거하기 위한 π 투영법은 키워드를 추가하여 얻는다.

선택(선택)

A generalized selection is a unary operation written as ${\displaystyle \sigma _{\varphi }(R)}$ where φ is a propositional formula that consists of atoms as allowed in the normal selection and the logical operators ${\displaystyle \wedge }$ (and), ${\displaystyle \lor }$ (or) and ${\displaystyle \neg }$ (부정 이 선택은 φ이 지탱하는 R의 모든 튜플을 선택한다.

주소록에 있는 모든 친구 또는 비즈니스 관계자의 목록을 얻으려면 $selection{\displaystyle {}_{}}$ ${\displaystyle {\text{isFriend}}_{}}$= ${\displaystyle {\text{true}\text{is}}_{}}$ isBusinessContact = ${\displaystyle {\text{true}(}_{}\text{주소록})}$ ${\displaystyle \sigma _{\text{isFriend$= $true}\,\lor \,$ {\$is BusinessContact$= $true}}({text{dressBook})$로 선택될 수 있다$.$ 결과는 isFriend가 참이거나 BusinessContact가 참인 모든 고유 레코드의 모든 속성을 포함하는 관계가 될 것이다.

이름 바꾸기(이름 변경)

이름 변경은 $\rho {\displaystyle {}_{}}$ ${\displaystyle a_{}}$/ ${\displaystyle b{}_{}}$( ${\displaystyle R_{}}$) ${\displaystyle \rho _{a/b}(R)}$로 작성된 단항 작업이며, 여기서$$ 모든 튜플의 b 속성이 속성으로 이름이 바뀐 것을 제외하고 결과는 R과 동일하다. 이것은 단순히 관계의 속성이나 관계 그 자체의 이름을 바꾸는 데 사용된다.

관계에서 'isFriend' 속성의 이름을 'isBusinessContact'로 바꾸려면, ${\displaystyle {\text{is}}_{}}$ isBusinessContact / ${\displaystyle {\text{isFriend}}_{}}$(${\displaystyle \text{주소록}}$)$${\$displaystyle \rho _{\isBusinessContact$/ $isFriend}}({\text{Book})}$가 사용될 수 있다$$.

There is also the ${\displaystyle \rho _{x(A_{1},\ldots ,A_{n})}(R)}$ notation, where R is renamed to x and the attributes ${\displaystyle \{a_{1},\ldots ,a_{n}\}}$ are renamed to ${\displaystyle \{A_{1},\ldots ,A_{n}\}}$.^[1]

결합 및 결합 유사 연산자

내추럴 조인( (⋈)

자연 결합(Natural join)은 R과 S가 관계인 (R ⋈ S)로 표기된 이진 연산자다.^[2] 자연 결합의 결과는 공통 속성 이름에 동일한 R과 S의 모든 튜플 조합의 집합이다. 예를 들어, 직원 및 부서와 이들의 자연 결합 표를 고려하십시오.

메리라는 직원이나 인사과 직원도 결과에 나타나지 않는다는 점에 유의하십시오.

이것은 관계의 구성을 정의하는 데도 사용될 수 있다. 예를 들어, 종업원과 뎁트의 구성은 공통 속성인 DeptName을 제외한 모든 것에 투영된 위에서 표시한 대로 이들의 결합이다. 카테고리 이론에서 결합은 정확하게 섬유 제품이다.

자연 결합은 논리 AND 연산자의 관계적 상대이기 때문에 거의 틀림없이 가장 중요한 연산자 중 하나이다. AND로 연결된 두 술어 각각에 동일한 변수가 나타나는 경우, 그 변수는 동일한 것을 나타내며 두 가지 모양 모두 항상 동일한 값으로 대체되어야 한다는 점에 유의하십시오(이는 논리적 AND의 특유성의 결과임). 특히 자연 결합은 외국 키와 연관된 관계의 결합을 가능하게 한다. 예를 들어 위의 예에서 외래 키는 아마도 직원으로부터 보관될 것이다.DeptName에서 Dept.뎁트이름 그리고 나서 직원과 뎁트의 자연적인 가입은 모든 직원을 그들의 부서와 결합시킨다. 이것은 외래 키가 같은 이름의 속성 사이에 있기 때문에 작동한다. 만약 뎁트의 외래 키와 같은 경우가 아니라면.관리자와 직원 연결.이름을 지정한 다음 이 열 이름을 변경하고 자연 결합하십시오. 이러한 결합을 에퀴조인이라고도 한다(θ조인 참조).

보다 공식적으로 자연 결합의 의미론은 다음과 같이 정의된다.

${\displaystyle R\bowtie S=\좌측\{r\cup s\\\\\vert \r\in R\\\land\s\in S\\\land\\{\mathit{Fun}(r\cup s)\right\}}}}$

(1)

여기서 fun(t)은 if t가 함수인 경우 관계 t(수학적 의미에서는)에 대해 참인 술어다. 보통 R과 S는 적어도 하나의 공통속성이 있어야 하지만, 이 제약조건이 생략되고, R과 S가 공통속성이 없다면, 자연 결합은 정확하게 카르테시안 제품이 된다.

자연 결합은 다음과 같이 Codd의 원시성으로 시뮬레이션할 수 있다. c₁, ...,c는_m R과 S에 공통되는 속성 이름, r,...,r은_1n R과 s에₁ 고유한 속성 이름, ...s는_k S에 고유한 속성 이름이라고 가정해 보자. 또한 속성 이름 x₁, ...,x가_m R이나 S에 있지 않다고 가정하십시오. 첫 번째 단계에서 S의 공통 속성 이름을 렌더링할 수 있다.

${\displaystyle T=\rho _{x_{1}/c_{1},\ldots ,x_{m}/c_{m}}(S)=\rho _{x_{1}/c_{1}}(\rho _{x_{2}/c_{2}}(\ldots \rho _{x_{m}/c_{m}}(S)\ldots ))}$

(2)

그런 다음 데카르트 제품을 사용하여 결합할 튜플을 선택하십시오.

${\displaystyle P=\sigma _{c_{1}=x_{1},\ldots ,c_{m}=x_{m}}(R\times T)=\sigma _{c_{1}=x_{1}}(\sigma _{c_{2}=x_{2}}(\ldots \sigma _{c_{m}=x_{m}}(R\times T)\ldots ))}$

(3)

마지막으로, 우리는 다음과 같이 이름이 바뀐 속성을 제거하기 위해 투영한다.

${\displaystyle U=\Pi _{r_{1},\ldots,r_{n},c_{n},c_{m},s_{1},\ldots,s_{k}(P)}$

(4)

θ-join과 에퀴조인

차와 보트의 모델과 각각의 가격을 나열하는 표를 생각해 보십시오. 고객이 차와 보트를 사고 싶어하지만, 차보다 보트에 더 많은 돈을 쓰고 싶지 않다고 가정해보자. CarPrice pred BoatPrice라는 술어의 θ-join (⋈)_θ은 술어를 만족시키는 평평한 행 쌍을 생산한다. 속성이 동일한 조건(예: Price)을 사용할 경우 해당 조건을 Price=Price 또는 (Price) 자체로 지정할 수 있다.

결합 조건이 단순히 공유 속성의 동일성이 아닌 두 관계에서 나오는 튜플을 결합하기 위해서는 보다 일반적인 형태의 조인 연산자, 즉 in조인(또는 teta-join)을 갖는 것이 편리하다. R⋈ S는 θ b{\displaystyle{R\ \bowtie)S\atop a\ \theta)b}}또는 R⋈ S가 a와 b은 특성 이름,{<>, ≤, 음, ≠,>, ≥}에 θ는 2항 관계 연산자, υ은 값이 θ v{\displaystyle{R\ \bowtie)S\atop a\ \theta)v}}로 기록되어 있는 θ-join는 2항 연산자이다.장단점탄트, 그리고 R과 S는 관계다. 이 연산의 결과는 θ을 만족시키는 R과 S의 튜플의 모든 조합으로 구성된다. θ-join의 결과는 S와 R의 헤더가 분리되는 경우, 즉 공통 속성을 포함하지 않는 경우에만 정의된다.

그러므로 기본 운전에서 이 운전의 시뮬레이션은 다음과 같다.

R ⋈_θ S = σ_θ(R × S)

연산자 θ이 동일 연산자(=)인 경우, 이 결합을 동일 연산자(=)라고도 한다.

단, 자연 조인 및 선택 연산자를 지원하는 컴퓨터 언어는 자연 조인 결과(공유 속성이 없을 때 데카르트 제품으로 전락하는 것)의 선택으로 얻을 수 있기 때문에 θ조인도 필요하지 않다는 점에 유의한다.

SQL 구현에서 술어에 가입하는 것을 보통 내부 조인이라고 하며, on 키워드는 행을 필터링하는 데 사용되는 술어를 지정할 수 있다. 주목해야 할 것은 평평한 데카르트 제품을 형성한 다음 행을 필터링하는 것은 개념적으로는 맞지만 구현 시 조인 쿼리를 가속화하기 위해 보다 정교한 데이터 구조를 사용할 수 있다는 점이다.

세미조인(⋉)

왼쪽 세미조인은 자연 결합과 유사한 결합이며 R과 S가 관계인 R ⋉ S로 표기된다.^[3] 결과는 공통 속성 이름에 동일한 S에 튜플이 있는 R의 모든 튜플 집합이다. 자연 결합과 다른 점은 S의 다른 열이 나타나지 않는다는 것이다. 예를 들어, 직원 및 부서와 해당 세미조인 표를 고려하십시오.

좀 더 공식적으로 세미조인의 의미론은 다음과 같이 정의될 수 있다.

R ⋉ S = { t : t ∈ R ∧s ∈ S(Fun (t ∪ s)) }

여기서 재미(r)는 자연 결합의 정의와 같다.

세미 조인은 다음과 같은 자연 조인을 사용하여 시뮬레이션할 수 있다. a₁, ...가_n R의 속성 이름인 경우

R ⋉ S = $\pi {\displaystyle \mathrm{}}$ ${\displaystyle \Pi$ $\}($_a1,..,anR ⋈ S)

기본 연산자와의 자연 결합을 시뮬레이션할 수 있기 때문에 세미조인에도 이 기능이 적용된다.

Codd의 1970년 논문에서 세미조인은 제한이라고 불린다.^[4]

안티조인(▷)

R과 S가 관계인 경우 R ▷ S로 표기된 반조인은 반조인과 유사하지만, 반조인의 결과는 공통 속성 이름에 동일한 S에 튜플이 없는 R의 튜플에 불과하다.^[5]

예를 들어, 직원 및 부서와 해당 부서에 대한 안티조인 표를 고려하십시오.

안티조인은 공식적으로 다음과 같이 정의된다.

R ▷ S = { t : t ∈ R ∧ ¬s ∈ S(Fun (t ∪ s)) }

또는

R ▷ S = { t : t ∈ R, Fun (t ∪ s)을 만족시키는 S의 튜플 s가 없다. }

여기서 재미(t ∪ s)는 자연 결합의 정의와 같다.

안티조인은 다음과 같이 세미조인의 보완으로도 정의할 수 있다.

R ▷ S = R − R ⋉ S

(5)

이에 따라 반조인(反朝人)은 반조인(反朝人)이라고도 하고, 반조인(反朝人) 연산자는 ▷가 아니라 그 위에 막대가 있는 반조인(半朝in) 기호로 표기하기도 한다.

분할(÷)

분할은 R ÷ S 디비전이 SQL에서 직접 실행되지 않는 이진 연산이다. 결과는 R에 고유한 속성 이름에 대한 R의 튜플 제한으로 구성된다. 즉, R의 헤더에는 있지만 S의 헤더에는 없는 R의 속성 이름에 대한 R의 튜플 제한으로 구성되며, S의 튜플과의 모든 조합은 R에 존재한다고 한다. 예를 들어 Completed, DBProject 및 해당 분할 표를 참조하십시오.

DBProject가 데이터베이스 프로젝트의 모든 태스크를 포함하는 경우, 위의 분할 결과에 데이터베이스 프로젝트의 두 태스크를 모두 완료한 학생이 정확히 포함된다. 보다 공식적으로 분단의 의미론은 다음과 같이 정의된다.

R ÷ S = { t[a1, ...,an] : t ∈ R ∧s ∀s ∈ S (t[a1,...,an] ∪ R) } } } R) }

(6)

여기서 {a₁,...,a_n}은(는) R에 고유한 속성 이름의 집합이며 t[a₁,...,a_n]는 이 집합에 대한 t의 제한 사항이다. 그렇지 않으면 작업 결과가 항상 비어 있기 때문에 일반적으로 S 헤더에 있는 속성 이름은 R의 속성 이름의 하위 집합이어야 한다.

기본 운영으로 분업 시뮬레이션은 다음과 같다. 우리는₁ a,...a가_n R과 b₁, ...b가_m S의 속성 이름이라고 가정한다. 첫 번째 단계에서 우리는 R을 그것의 고유한 속성 이름에 투영하고 모든 조합을 S:에서 튜플로 구성한다.

T := π_a1,...,an(R) × S

앞의 예에서, T는 모든 학생이 주어진 모든 과제와 결합되는 표를 대표할 것이다. 그래서 유진은 예를 들면 T에 유진→데이터베이스1과 유진→데이터베이스2라는 두 개의 행이 있을 것이다.

EG: 먼저, "완료"가 "등급"이라는 세 번째 속성을 가지고 있다고 가정해 봅시다. 여기는 원치 않는 수하물이니, 우리는 항상 투영해야 한다. 사실 이 단계에서 우리는 R에서도 '태스크'를 떨어뜨릴 수 있다; 곱셈은 그것을 다시 붙인다.

T := π_Student(R) × S // 이것은 R에 실제로 존재하지 않는 조합을 포함하여 다른 조합을 제외한 모든 가능한 원하는 조합을 제공한다(예: Fred 컴파일러1은 원하는 조합이 아니다).

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

관계:

U := T − R

U에서 우리는 R에 있을 수 있는 가능한 조합들을 가지고 있지만, 그렇지 않았다.

EG: 다시 투영 — T와 R은 동일한 속성 이름/헤더를 가져야 한다.

U :=T - π_Student,Task(R) // 이것은 우리에게 " 빠진 것" 목록을 준다.

이제 R에 고유한 속성 이름에 대한 투영법을 사용한다면

그 다음에 우리는 S에서 튜플을 가진 모든 조합이 R:에 존재하지 않았던 R에서 튜플의 제약을 받는다.

V := π_a1,...,an(U)

EG: 문제의 속성(Student)에 대한 프로젝트 U

V := π_Student(U)

따라서 앞으로 해야 할 일은 R의 고유한 속성 이름에 대한 투영법을 취하고 V의 속성 이름을 빼는 것이다.

W := π_a1,...,an(R) − V

EG: W := π_Student(R) − V.

공통 확장자

실제로 위에서 설명한 고전적 관계 대수학은 외부 결합, 집계 함수, 심지어 전이적 폐쇄와 같은 다양한 연산을 통해 확장된다.^[6]

외부 결합

조인(또는 내부 조인)의 결과는 두 피연산자의 일치하는 튜플을 결합하여 형성된 튜플로 구성되는 반면, 외부 조인은 다른 피연산자의 각 속성에 대해 "채우기" 값으로 피연산자 중 한 명에서 일치하지 않는 튜플을 확장하여 형성된 튜플과 일부 튜플을 포함한다. 외부 결합은 지금까지 논의된 고전적 관계 대수학의 일부로 간주되지 않는다.^[7]

이 절에 정의된 연산자는 채우기 값에 사용할 null 값 Ω이 존재한다고 가정한다. 실제로 이는 SQL의 NULL에 해당한다. 결과표상의 후속 선택 연산을 의미 있게 하기 위해서는 의미적 의미가 null에 할당될 필요가 있다; Codd의 접근법에서는 우리가 이 글에서 그러한 세부사항들을 익히기는 하지만, 그 선택에 의해 사용되는 명제적 논리는 3가지 가치 논리로 확장된다.

3개의 외부 조인 연산자가 정의된다: 왼쪽 외부 조인, 오른쪽 외부 조인, 전체 외부 조인. (혹시 '외'라는 말이 생략되기도 한다.)

좌측 외측 조인(⟕)

왼쪽 바깥쪽 조인은 R과 S가 관계인 R ⟕ S로 쓰여 있다.^[8] 왼쪽 외부 조인의 결과는 공통 속성 이름에 동일한 R과 S의 튜플의 모든 조합의 집합이며, S에 일치하는 튜플이 없는 R의 튜플에 추가(느리게 말하기)한다.

예를 들어, 직원 및 부서 및 왼쪽 외부 조인 표를 고려하십시오.

결과 관계에서 R에 튜플이 있는 공통 속성 이름에 공통 값이 없는 S의 튜플은 null 값 Ω을 취한다.

재무 또는 경영진의 뎁트명이 있는 뎁트에는 튜플이 없기 때문에, Ω은 직원의 뎁트명이 재무 또는 경영자를 갖는 결과 관계에서 발생한다.

r₁, r₂, ..., r을_n 관계 R의 속성으로 하고 {(Ω, ..., Ω)}을 관계 S(R의 속성이 아닌 속성)에 고유한 속성에 대한 단일톤 관계가 되게 한다. 그런 다음 왼쪽 외부 조인은 다음과 같이 자연 조인(따라서 기본 연산자를 사용)의 관점에서 설명할 수 있다.

${\displaystyle (R\bowti S)\cup (R-\pi _{1}r_{1}{2},\dots,r_{n}(R\bowti S)\time \{{{(\omega ,\dotes \otesomega )\}}}}$

우측 외측 조인(⟖)

오른쪽 바깥쪽 조인은 왼쪽 바깥쪽 조인과 거의 동일하게 동작하지만 테이블의 역할은 전환된다.

R과 S 관계의 오른쪽 바깥쪽 결합은 R ⟖ S로 쓰여 있다.^[9] 오른쪽 외부 조인의 결과는 R에 일치하는 튜플이 없는 S의 튜플 외에 공통 속성 이름에 동일한 R과 S의 튜플의 모든 조합의 집합이다.

예를 들어, 직원 및 부서 및 오른쪽 외부 조인 표를 고려하십시오.

결과 관계에서 S에 튜플이 있는 공통 속성 이름에 공통 값이 없는 R의 튜플은 null 값 Ω을 취한다.

DeptName of Production을 가진 직원에는 튜플이 없기 때문에 Ω은 Dept의 튜플이 DeptName of Production을 가졌던 결과 관계의 Name 및 EmpId 속성에서 발생한다.

s₁, s₂, ...s는_n 관계 S의 속성이 되고 {(Ω, ..., Ω)}은 관계 R(S의 속성이 아닌 속성)에 고유한 속성의 단톤 관계가 된다. 그런 다음 왼쪽 외부 조인과 마찬가지로 오른쪽 외부 조인은 다음과 같이 자연 조인을 사용하여 시뮬레이션할 수 있다.

${\displaystyle (R\bowtie S)\cup (\{{s_{1}, s_{2},\dots ,s_{n}(R\bowtie S))}}}$

전체 외부 조인( ()

외부 결합 또는 전체 외부 결합은 사실상 왼쪽과 오른쪽 외부 결합의 결과를 결합한다.

완전한 외부 결합은 R과 S가 관계인 R ⟗ S로 쓰여 있다.^[10] 전체 외부 조인 결과는 공통 속성 이름에 일치하는 튜플이 없는 S와 공통 속성 이름에 일치하는 튜플이 없는 R과 S의 모든 튜플 조합의 집합이다.

예를 들어, 직원 및 부서와 전체 외부 조인 표를 고려하십시오.

결과 관계에서 S에 튜플이 있는 공통 속성 이름에 공통 값이 없는 R의 튜플은 null 값 Ω을 취한다. R에 튜플이 있는 공통 속성 이름에 공통 값이 없는 S의 튜플도 null 값 Ω을 취한다.

전체 외부 결합은 다음과 같이 왼쪽과 오른쪽 외부 결합(따라서 자연 결합 및 세트 결합)을 사용하여 시뮬레이션할 수 있다.

R ⟗ S = (R ⟕ S) ∪ (R ⟖ S)

도메인 계산 작업

지금까지 도입된 관계 대수학에는 (평등을 포함하는 명제적 표현에 대한 평가 외에는) 데이터 영역에서 연산을 허용하는 것은 없다. 예를 들어, 총가격을 얻기 위해 단가를 수량으로 단가와 같이 두 개의 컬럼의 숫자를 곱하는 표현을 쓰는 것은 지금까지 소개된 대수학만을 사용하는 것은 불가능하다. 실용적인 쿼리 언어는 그러한 기능을 가지고 있다. 예를 들어, SQL SELECT를 사용하면 산술 연산이 결과에서 새로운 열을 정의할 수 있다. SELECT unit_price * quantity AS total_price FROM t자습서 D에 의해 유사한 시설이 보다 명확하게 제공됨 EXTEND 키워드^[11] 데이터베이스 이론에서 이것을 확장 투영이라고 한다.^{[12]: 213}

집계

더욱이 그 원소의 합계처럼 열에 다양한 기능을 계산하는 것도 지금까지 소개된 관계 대수학으로는 불가능하다. 대부분의 관계형 데이터베이스 시스템에 포함되는 5가지 집계 기능이 있다. 이러한 작업은 합계, 카운트, 평균, 최대 및 최소 작업이다. 관계 대수에서 스키마에 대한 집계 연산(A₁, A₂, ...) A_n)는 다음과 같이 쓰여 있다.

${\displaystyle G_{1},G_{2},\ldots,G_{m}\g_{f_{1}{1}({A_{1}:{2}}'),\ldots ,f_{k}({A_{k}}}}}}}\(r)}$

여기서 각 A_j'는 1 ≤ j ≤ k이며, 원래 속성_i A의 하나, 1 i i n n이다.

g 앞에 있는 속성은 그룹화 속성으로, SQL의 "group by" 절처럼 기능한다. 그러면 개별 속성에 적용되는 임의의 집계 함수의 수가 있다. 연산은 임의의 관계 r에 적용된다. 그룹화 속성은 선택사항이며, 이러한 속성이 제공되지 않을 경우, 연산이 적용되는 전체 관계에 걸쳐 집계 함수가 적용된다.

이름 붙여진 테이블이 있다고 가정해 봅시다. Account_Number, Branch_Name 및 Balance라는 세 개의 열이 있는 계정. 우리는 각 지점의 최대 잔액을 찾기를 바란다. 이것은_Max(Balance) G(계정)에 의해 달성된다. 지점과 상관없이 모든 계좌의 최고 잔액을 찾기 위해 우리는 간단히 G_Max(Balance)(계정)를 쓸 수 있었다.

그룹화는 대신 ɣ_Max(Balance)(계정)으로 표기하는 경우가 많다.^[13]

전이성폐쇄

관계 대수학은 대부분의 실용적인 목적을 위해 충분히 강력해 보이지만, 관계 대수로는 표현할 수 없는 관계에 대한 단순하고 자연스러운 운영자가 있다. 그 중 하나는 이항 관계의 전이적 폐쇄다. 도메인 D를 지정하면, 이진 관계 R을 D×D의 하위 집합으로 한다. R의 Transitive closure R은⁺ R을 포함하고 다음 조건을 만족하는 D×D의 가장 작은 부분집합이다.

${\displaystyle \forall x\forally z\left(x,y)\in R^{+}\wedge(y,z)\in R^{+}\R^{+}\R^{+}\righrow(x,z)\in R^{}\in)}$

R을 생성하는⁺ 변수 인수로 간주하는 관계 대수식 E(R)는 없다. 이는 E(R) = R⁺, 여기서 R이 변수라고 주장하는 관계식 E를 고려할 때 E(r) ≠ r과⁺ 같은 R(및 해당 도메인 d)의 인스턴스 r을 항상 찾을 수 있다는 사실을 사용하여 증명할 수 있다.^[14]

그러나 SQL은 1999년 이후 공식적으로 그러한 픽스포인트 쿼리를 지원했고 그 이전에도 이 방향으로 벤더별 확장을 가지고 있었다.

쿼리 최적화를 위한 대수적 속성 사용

이 절은 출처를 인용하지 않는다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 섹션을 개선할 수 있도록 도와주십시오. 공급되지 않은 재료는 도전하여 제거할 수 있다. (2013년 6월) (이 템플릿 메시지를 제거하는 방법과 시기 알아보기)

쿼리를 트리로 나타낼 수 있는 위치

• 내부 노드는 연산자,
• 나뭇잎은 관계다.
• 하위 트리는 하위 표현이다.

주요 목표는 표현 트리를 등가 표현 트리로 변환하는 것인데, 여기서 트리 내 하위 표현에 의해 산출되는 관계의 평균 크기는 최적화 이전보다 작다. 두 번째 목표는 단일 쿼리 내에서 또는 동시에 평가되는 쿼리가 둘 이상일 경우 모든 쿼리에서 공통 하위 익스프레션을 형성하는 것이다. 두 번째 목표의 근거는 일반적인 하위 표현을 한 번 계산하면 충분하며, 그 하위 표현을 포함하는 모든 쿼리에 결과를 사용할 수 있다는 것이다.

이러한 변환에 사용될 수 있는 일련의 규칙들이 여기에 있다.

선택

선택 연산자에 대한 규칙은 질의 최적화에 가장 중요한 역할을 한다. 선택이란 피연산자의 행 수를 매우 효과적으로 감소시키는 연산자여서, 표현 트리의 선택이 잎을 향해 움직이면 내적 관계(하위표현에 의한 결과)가 위축될 가능성이 높다.

기본 선택 속성

선택은 idempotent(동일한 선택의 다중 적용은 첫 번째 적용 이상의 추가 효과가 없음)와 대응(순서 선택이 적용되어 최종 결과에 영향을 미치지 않음)이다.

1. ${\displaystyle \sigma _{A}(R)=\sigma _{A}\sigma _{A}(R)\,\!}$
2. ${\displaystyle \sigma _{A}\sigma _{B}(R)=\sigma _{B}\sigma _{A}(R)\,\!}$

복잡한 조건으로 선택 항목 분리

조건이 단순한 조건의 결합인 선택은 동일한 개별 조건을 가진 일련의 선택과 같으며, 조건이 분리된 선택은 선택 조합과 같다. 이러한 ID는 선택 항목을 병합하여 더 적은 수의 선택 항목을 평가하거나 구성 요소 선택 항목을 별도로 이동하거나 최적화하도록 분할하는 데 사용할 수 있다.

1. ${\displaystyle \sigma _{A\land B}(R)=\sigma _{B}(R)=\sigma _{B}(\sigma _{A})(R)}$
2. $\displaystyle \sigma _{A\lor B}(R)=\sigma _{A}(R)\cup \sigma _{B}(R)}$

선택 및 교차 제품

교차 제품은 평가하기에 가장 비용이 많이 드는 연산자다. 입력 관계에 N 및 M 행이 있는 경우 결과에는 ${\displaystyle N}$ M ${\displaystyle NM}$ 행이$$ 포함된다. 따라서 교차 제품 연산자를 적용하기 전에 두 피연산자의 크기를 줄이는 것이 중요하다.

이는 $\sigma {\displaystyle {}_{}}$ ${\displaystyle A_{}R}$ ${\displaystyle \times }$ P${\displaystyle }$)와 같은 선택 연산자가 크로스 제품을 따를 경우 효과적으로 이루어질 수 있다$.$ $\displaystyle \sigma _{A}(R\times P)}.$ 가입의 정의를 고려할 때 가장 가능성이 높은 경우다. 크로스 제품을 선택 연산자가 따르지 않을 경우 다른 선택 규칙을 사용하여 더 높은 수준의 표현 트리에서 선택 항목을 아래로 밀어넣을 수 있다.

In the above case the condition A is broken up in to conditions B, C and D using the split rules about complex selection conditions, so that ${\displaystyle A=B\wedge C\wedge D}$ and B contains attributes only from R, C contains attributes only from P, and D contains the part of A that contains attributes from both R and P. B, C 또는 D가 비어 있을 수 있다는 점에 유의하십시오. 그 다음이 유지된다.

$\displaystyle \sigma _{A}(R\times P)=\sigma _{B}(R)=\sigma _{B}(R)\time \sigma _{C}(P)}$

연산자 선택 및 설정

선택은 설정된 차이, 교차점, 조합 운영자에 대해 분배된다. 다음 세 가지 규칙을 사용하여 표현식 트리의 설정 작업 아래의 선택을 푸시한다. 설정 차이와 교차로 연산자의 경우 변환 후 피연산자 중 한 명에만 선택 연산자를 적용할 수 있다. 이것은 피연산자 중 한 명이 작을 때 유익할 수 있으며, 선택적 운영자를 평가하는 데 드는 오버헤드는 피연산자로서 더 작은 관계를 사용하는 것의 이점을 능가한다.

1. $\displaystyle \sigma _{A}(R\setminus P)=\sigma \{A}(R)\setminus \sigma \{A}(P)=\sigma _{A}(R)\setminus P}$
2. ${\displaystyle \sigma _{A}(R\cupp P)=\sigma _{A}(R)\cuppose \sigma _{A}(P)}$
3. $\displaystyle \sigma _{A}(R\cap P)=\sigma _{A}(P)=\sigma _{A}(R)\cap P=R\cap \sigma _{A}(P)}$

선택 및 투영

선택 조건에서 참조되는 필드가 투영에서 필드의 하위 집합인 경우에만 선택 영역이 투영과 통근된다. 피연산자가 교차 제품 또는 결합인 경우 투영 전에 선택을 수행하는 것이 유용할 수 있다. 다른 경우에 선택 조건이 계산에 상대적으로 비용이 많이 드는 경우, 투영 밖에서 선택을 이동하면 시험해야 하는 튜플의 수가 감소할 수 있다(투영에서 누락된 중복이 제거되어 더 적은 튜플이 생성될 수 있기 때문이다).

${\displaystyle \pi _{a_{1},\ldots ,a_{n}(\sigma _{A}(R)=\sigma _{A}(\pi _{a_{1},\ldots,a_{n})(R)){\text{{}}A\subseteq \{1},\ldots,a_{n}\}}}의 필드$

투영

기본 투영 특성

투영은 IDempotent이므로 일련의 (유효한) 투영이 가장 바깥쪽 투영과 동일하다.

${\displaystyle \pi _{a_{1},\ldots,a_{n}(\pi _{b_{1},\ldots,b_{m})(R)=\pi _{a_{1},\ldots,a_{n}(R){\text{{}{{1},\ldots,a_{n}\}\subseteq \{b_{1},\ldots,b_{m}\}\}}}}}}}}}$

투영 및 설정 연산자

투영은 세트 유니온에 대해 분배된다.

${\displaystyle \pi _{a_{1},\ldots,a_{n}}(R\cup P)=\pi _{a_{1}, {n}(R)\cup \pi _{a_{1},\ldots,a_{n}(P).\,}$

투영은 교차점 및 설정 차이를 통해 분포되지 않는다. 백배수는 다음과 같이 주어진다.

${\displaystyle \pi _{{\langle A=a,B=b\rangle \}\cap \{\langle A=a,B=b'\rangle \}}\empt }$

${\displaystyle \pi \{\langle A=a,B=b\angle \}\cap \pi _{A}(\\\langle A=a,B=b'\angle \}=\\langle A=a\angle \}}}}}}}$

그리고

${\displaystyle \pi \{\langle A=a,B=b\rangle \}\setminus \{\langle A=a,B=b'\rangle \}=\{\langle A=a\rangle \}}}}$

${\displaystyle \pi \{\langle A=a,B=b\angle \}\setminus \pi \{\langle A=a,B=b'\angle \}\empt \}$

여기서 b는 와 구별되는 것으로 가정한다. b'.

이름 바꾸기

기본 이름 바꾸기 속성

변수의 연속적인 이름은 단일 이름 변경으로 축소될 수 있다. 공통 변수가 없는 이름 바꾸기 작업은 서로에 대해 임의로 순서를 변경할 수 있으며, 이를 이용하여 연속적인 이름을 인접하게 만들어 축소할 수 있다.

1. ${\displaystyle \rho _{a/b}(\rho _{b/c}(R))=\rho _{a/c}(R)\,\!}$
2. ${\displaystyle \rho _{a/b}(\rho _{c/d}(R))=\rho _{c/d}(\rho _{a/b}(R)\,\!}$

연산자 이름 변경 및 설정

이름 변경은 설정 차이, 결합 및 교차로에 대한 분배다.

1. ${\displaystyle \rho_{a/b}(R\setminus P)=\rho_{a/b}(R)\setminus \rho _{a/b}(P)}$
2. ${\displaystyle \rho_{a/b}(R\cup P)=\rho_{a/b}(R)\cup \rho_{a/b}(P)}$
3. ${\displaystyle \rho_{a/b}(R\cap P)=\rho_{a/b}(R)\cap \rho_{a/b}(P)}$

제품 및 조합

데카르트 제품은 유니온보다 분배적이다.

1. $(A\displaystyle (A\time B)\컵 (A\time C)=A\time (B\컵 C)}$

구현

Codd의 대수학을 기반으로 한 최초의 질의어는 Codd 박사가 직접 개발한 알파였다. 그 뒤 ISBL이 만들어졌고, 이 선구적인 작품은 Codd의 사상을 유용한 언어로 만드는 방법을 보여주었다는 점에서 많은 당국으로부터^[15] 호평을 받았다. 비즈니스 시스템 12는 ISBL의 예를 따르는 단명 산업 강도의 관계형 DBMS였다.

1998년에 Chris Date와 Hugh Darwen은 관계형 데이터베이스 이론을 가르칠 목적으로 Tutorial D라는 언어를 제안했고, 그것의 질의 언어도 ISBL의 아이디어에 의존한다. Rel은 자습서 D의 구현이다.

SQL(테이블)의 피연산자는 정확히 관계가 아니며 관계대수에 대한 몇 가지 유용한 이론이 SQL 상대방에 있지 않지만(추천적 및/또는 사용자의 손상에 대한 주장으로) SQL의 질의 언어조차도 관계대수에 느슨하게 기초하고 있다. SQL 테이블 모델은 세트가 아닌 가방(멀티셋)이다. For example, the expression ${\displaystyle (R\cup S)\setminus T=(R\setminus T)\cup (S\setminus T)}$ is a theorem for relational algebra on sets, but not for relational algebra on bags; for a treatment of relational algebra on bags see chapter 5 of the "Complete" textbook by Garcia-Molina, Ullman and Wid옴^[12]

참고 항목

참조

추가 읽기

실제로 데이터베이스에 관한 모든 학술 교과서는 고전적인 관계 대수학을 상세히 다루고 있다.

• Imieliński, T.; Lipski, W. (1984). "The relational model of data and cylindric algebras". Journal of Computer and System Sciences. 28: 80–102. doi:10.1016/0022-0000(84)90077-1. (원통형 알헤브라스와의 관계용).

외부 링크

이 기사의 외부 링크 사용은 위키피디아의 정책이나 지침을 따르지 않을 수 있다. 너무 많거나 부적절한 외부 링크를 제거하고 적절한 경우 유용한 링크를 각주 참조로 변환하여 이 문서를 개선하십시오. (2017년 1월) (이 템플릿 메시지를 제거하는 방법과 시기 알아보기)

• RAT. SQL로 소프트웨어 관계 대수 변환기
• 강의 비디오: 관계 대수 처리 - 데이터베이스 시스템이 관계 대수학을 처리하는 방법에 대한 소개
• 강의 노트: 관계 대수 – SQL 질의를 관계 대수학으로 적용하기 위한 간단한 자습서
• 관계 – 관계 대수 그래픽 구현
• 쿼리 최적화(페이지 삭제, 가장 가까운 대안: 스탠포드 쿼리 최적화 2, 관계형 시스템의 마이크로소프트 리서치 쿼리 최적화, 스탠포드 논문: 쿼리 최적화)이 논문은 질의 최적화에 관계 대수학의 사용에 대한 소개로, 보다 심층적인 연구를 위한 수많은 인용구를 포함하고 있다.
• Oracle 및 Microsoft SQL Server 관계 대수 시스템
• 피레알 – 관계 대수학을 이용한 실험 교육 도구
• DES – 관계 대수 및 기타 공식 언어로 작업하기 위한 교육 도구
• RelaX - 관계 대수 계산기(등록 없이 온라인 서비스로 제공되는 오픈 소스 소프트웨어)
• RA: 관계 대수 해석기
• SQL을 관계 대수로 변환