관계 대수(Relation Algebra)

Library/Database 2008.04.14 23:50 posted by Celdee
데이터 무결성 제약 조건은 반드시 현실 세계를 반영해야 한다. 데이터 무결성을 위배하는 인스턴스는 존재할 수 없으며, 반대로 인스턴스만으로 데이터 무결성을 판단할 수 없다. 즉, 데이터 무결성은 귀납적인 방법으로 결정할 수 없다는 이야기다. 예를 들어, 상속 관계는 어떤 방식으로 데이터베이스에 저장되어야 하는가? 상속 관계는 슈퍼 클래스만 아니라, 서브 클래스까지 관계 집합의 속성(attribute)으로 간주하여 표현할 수 있다. 하지만, 이것은 항상 좋은 방법은 아니다. 현실에서는 하나의 개체가 여러 속성을 가질 수 있으며, 데이터베이스에서 이 관계를 그대로 표현한다면 하나의 튜플이 동일한 속성값을 중복적으로 저장할 수 있기 때문이다.


관계 대수에서 정의되는 연산자는 5개이다. Selection(δ), Projection(π), Cross-Product(×), Set-Difference(-), Union(∪)이 그것이다. 모든 연산은 이 5개의 기본연산으로 표현할 수 있다.

Selection(δ)은, 주어진 관계에서, 몇개의 row subset을 골라내는 작업을 뜻한다. Selection의 결과는 관계 집합이다.

Projection(π)은 관계 집합에서 원하지 않는 성분을 제거한다. 수학적인, 다른 dimension으로 mapping 한다는 것과 동일하다. Projection의 결과는 관계 집합이다.

Cross-Product(×)는, 해당 스키마가 각 Tuple의 모든 필드 다음에 피연산 Tuple의 모든 필드가 순서대로 나열되는 것을 말한다. 이 연산의 결과도 관계 집합이다. 다시 말해서, R × S의 결과는, r ∈ R, s ∈ S의 각 쌍에 대하여 < r, s >를 포함하게 된다. 즉, 이 연산의 결과는 Cartesian Product다. 그리고, Cross-Product의 경우, 중복되는 필드가 존재한다면, 중복되는 스키마의 이름을 바꿔주어야 한다. 이때 필요한 연산자가 rename이다. rename 연산자는 ρ로 표현한다.

Set-Difference(-)는 차집합을 의미한다. 튜플(tuple) 집합에서 튜플 집합을 제거하는 것을 의미하는데, 이 연산을 적용하기 위해서는 대상이 되는 관계 R과 S는 서로 합병 가능해야 하며, 이 결과의 스키마는 R의 스키마와 동일해야 한다. Union(∪) 역시 마찬가지이다. 대상이 되는 관계 R과 S도 합병 가능해야 하며, 이 결과는 R의 스키마와 동일해야 한다. 그렇다면, 합병가능하다는 의미는 무엇인가? 이것은, 해당 관계의 필드가 같아야 하며, 왼쪽에서부터 오른쪽까지 차례대로, 대응하는 필드들이 동일한 도메인을 가지고 있어야 한다는 의미이다. 즉, 스키마가 동일해야 한다. (최소한 Type이라도 동일해야 한다)

Intersection은 어떤 경우에 가능한가? R ∩ S가 주어졌다고 하면, R과 S에 모두 속하는 Tuple을 포함하는 관계 인스턴스를 반환한다. 관계 R과 S는 서로 합병 가능해야 하며, 이 결과의 스키마는 R의 스키마와 동일하다. 하지만, Intersection은 기본 연산자가 아닌데, 왜냐하면 이것은 (A ∩ B) = A - (A - B)의 형태로 표현할 수 있기 때문이다. 이런 종류의 연산으로는 join이 있다. join은 한쌍의 관계 인스턴스를 받아들여 하나의 관계 인스턴스를 반환하는 것인데, 이것 역시 기본 연산으로 표현할 수 있다. join은, 두 개 이상의 관계로부터 정보를 조합하기 위해 가장 일반적으로 사용되는 방법이다. join은 Cross-Product 후에 Selection과 Projection 하는 것으로 정의될 수 있지만, Cross-Product는 모든 Tuple에 대해서 작용하기 때문에 효율성이 문제가 될 수 있다.

pojection은 duplication이 발생 할 수 있지만, selection은 duplication이 발생하지 않는다. join의 경우, 이것은 기본 연산자로 표현할 수 있다. 즉, cross-product 후에 selection, projection 연산자를 적용하면 동일한 결과를 얻을 수 있다. 연산 과정에서, 반드시 이들은 서로 연산 가능한 집합이어야 한다. 다시 말해서, 피연산자끼리 common attribute가 존재해야 하며, 연산자에서 요구하는 정의하는 정의도 만족해야 한다.

특히, Equi-join은 join 조건에 equal만 허용되어 있는 것을 말한다. natural-join은, 합쳐지는 대상이 되는 R과 S에서 동일한 이름을 가지고 있는 모든 필드에 대해서 명시되는 조건이다. natural-join에 의미가 있는 것은, 이미 존재하는 같은 개체의 다른 정보를 합치는 것이라면 이것이 자연스러운 형태이기 때문이다. 즉, 서로 동질의 튜플 을 합친다면, 동일한 스키마를 보유하고 있다는 말이 된다.

Division은 무엇인가? 두 관계 인스턴스 A, B가 존재한다고 했을 때, A에는 정확하게 두 필드 x, y가 있고, B에는 하나의 필드 y가 있으며, A에 있는 y의 도메인과 동일하다. Division A / B는, B의 모든 튜플에 있는 y에 대해서, A의 튜플< x, y >가 존재하는, 단항 형태의 x 값들의 집합으로 정의된다. 여기서, < x, y >의 각 요소는 집합이 될 수도 있다. 즉, < x, < u, v > >의 형태도 될 수 있으며, 이런 경우 < x, u >, < x, v >는 원래의 집합 A에 존재하는 쌍이어야 한다.

정수 나눗셈과의 유사성을 생각해보자. 정수 A와 B에 대해서, A / B는, Q × B ⊆ A를 만족하는 가장 큰 정수는 Q다. 관계 인스턴스 A와 B에 대해서, A / B는 Q × B ⊆ A를 만족하는 가장 큰 관계 인스턴스는 Q다. 즉, 인스턴스 Q와 B의 Cross-Product 결과는 A의 부분집합의 원소가 된다. Division 역시 기본 연산을 사용하여 표현할 수 있다.

그렇다면, Division의 직관적인 표현은 어떤 것인가? 튜플의 집합 A와 B가 있다고 했을 때, A / B는 A에 포함되는 B의 값의 집합을 의미한다.

신고