ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 9 관계relation 2
    Discrete mathmatics and Problem Solving/9 관계 Relations 2016. 10. 17. 10:45

    n진 관계 n-ary relations

    두 집합 이상의 엘리먼트들의 연관성은 자주 발생합니다. 학생의 이름과 그/그녀의 전공, 학점의 연관을 예로 들 수 있습니다. 이와 비슷한, 항공기와 항공번호, 출발지, 도착지, 도착시간, 출발시간과 같은 연관도 있습니다. 수학에서의 연관성의 예로, 정수 세 개를 들 수 있습니다. 첫 째 정수는 둘 째 정수보다 크며, 둘 째 정수는 셋 째 정수보다 큽니다. 다른 예는, 한 선 위의 점들을 살펴볼 수 있습니다. 두 번째 점이 첫 째점과 셋 째점 사이에 위치하고 있을 때 이 세 점은 연관되어 있습니다.

    이 섹션에서는 두 집합 이상에의 엘리먼트들이 연관이 있을 때에 대해 학습할 것입니다. 이런 연관성들은 n진(항) 관계n-ary relations라고 합니다. 이 관계들은 컴퓨터 데이터베이스를 표현하기 위해 사용됩니다. 이런 표현들은 데이터베이스 내에 저장된 정보들에 관해 쿼리를 질의할 때 도움이 됩니다. 예로: 3 A.M. 과 4 A.M. 사이에 O'Hare 공항에 착륙하는 여객편들은 무엇인가요? 2학년 학생 중에서 수학이나 컴퓨터 사이언스를 전공하고 평점이 3.0이 넘는 학생들은 누구입니까? 회사 내의 근로자 중에서 이 회사에서 5년 이하로 근무했고 50,000불 이상을 번 근로자들은 누구입니까?

    n진 관계n-ary Relations

    정의1

    A1, A2, A3 ... , An을 집합이라고하자. 이 집합들 자신으로의 n진 관계n-ary relations는 A1 x A2 x ... x An 의 부분집합입니다. A1, A2, ... An은 관계의 정의역들domains이라고 부르며, n은 관계의 급degree이라고 합니다.

    예제 1

    R을 N x N x N에서 자신으로의 관계라고 합시다. N x N x N은 정렬된-세쌍 (a,b,c)로 이루어져있습니다. 여기서 a, b, c는 자연수이며 a < b < c 입니다. 그러므로 (1,2,3) ∈ R이고 (2,4,3) ∉ R 입니다. 이 관계의 급degree는 3입니다. 이 관계의 정의역들은 모두 자연수들의 집합과 같습니다.

    예제 2

    R을 Z x Z x Z에서 자신으로의 관계라고 합시다. Z x Z x Z는 정렬된-세쌍 (a,b,c)로 이루어져있습니다. 여기서 a,b,c는 등차수열입니다. (연속된 항의 차이가 모두 일정) 즉, (a,b,c) ∈ R는 정수 k에 대하여 b = a+k이고 c = a+2k에 대해 필요충분조건입니다. 같은 의미로 b-a = k와 c-b = k를 만족해야합니다. (1,3,5) ∈ R 입니다. 왜냐하면 등차이기때문입니다. 그렇지만 (2,5,9) ∉ R 입니다. 5-2 = 3 이고 9-5 = 4이며 3≠4문입니다.

    예제 3

    R을 Z x Z x Z+에서 자신으로의 관계라고 합시다. 이 정렬된-세쌍 (a,b,m)은 a, b, m이 모두 정수이고 m ≥ 1 이며 a≡b(mod m)입니다. (8,2,3), (-1,9,5), (14,10,7)은 관계 R의 원소입니다. 그러나 (7,2,3),(-2,-8,-5),(11,0,6)은 R에 속하지않습니다.

    예제 4

    R을 5-튜플로 이루어진 관계라고 합시다. 5-튜플 (A, N, S, D, T)는 항공사A, 항공편명N, 출발지S, 도착지D, 출발시간T를 표현합니다. 예로, Nadir Express Airlines는 편명 963이 Newark에서 Bangor까지 15:00에 출발합니다. 이때 (Nadir, 963, Newark, Bangor, 15:00) 이 R의 원소가됩니다. 관계의 급degree는 5이고 정의역들은 모든 항공사의 집합, 항공편명들의 집합, 도시들의 집합, 도시들의 집합, 시간들의 집합 입니다.

    데이터베이스와 관계 Databases and Relations

    데이터베이스 내에 위치한 정보를 이용하는데 요구되는 시간은 정보가 어떤방식으로 저장되어 있는가에 영향을 받습니다. 레코드를 지우거나 더하기, 레코드 업데이트, 레코드 탐색, 중복되는 데이터베이스에서 레코드 병합하는 작업들은 대형 데이터베이스내에서 하루에만해도 수백만번 수행됩니다. 이 작업들의 중요도 때문에, 데이터베이스를 표현하는 여러가지 방법들이 개발되었습니다. 이런 메서드들 중 하나에 대해서 이야기 해볼 것입니다. 이는 관계형 데이터 모델이며, 관계의 개념에 기초하고 있습니다.
     데이터베이스는 레코드들로 이루어져있고, 레코드들은 n-튜플이고 필드들로 구성되어있습니다. 필드들은 n-튜플의 엔트리들입니다. 예로, 학생 레코드들의 데이터베이스는 필드들로 구성되어있습니다. 필드들은 이름과 학생번호, 전공, 평점을 담고있습니다. 관계형 데이터 모델은 레코드들의 데이터베이스를 n-ary 관계로 표현합니다. 즉, 학생 레코드들은 다음과 같은 4-튜플 형식으로 표현됩니다. (student_name, ID_number, Major, GPA).
    이런 여섯개의 레코드들로 이루어진 샘플 데이터베이스는 다음과 같습니다.
    (Ackermann, 231455, Computer Science, 3.88)
    (Adams, 888323, Physics, 3.45)
    (Chou, 102147, Computer Science, 3.49)
    (Goodfriend, 453876, Mathematics, 3.45)
    (Rao, 678543, Mathematics, 3.90)
    (Stevens, 786576, Psychology, 2.99)

    데이터베이스를 포현하기위한 관계들은 테이블tables라고도 불립니다. 관계들은 테이블과 같이 보여줄 수도 있기때문입니다.

     테이블의 각 열은 데이터베이스의 어트리뷰트(속성)attribute와 대응됩니다. 예로, 위 학생들의 데이터베이스는 아래의 테이블과 같습니다. 이 데이터베이스의 어트리뷰트attribute는 studnet_name, ID_number, Major, GPA 입니다.

    n-진 관계n-ary relations의 정의역domain은 주요 키primary key가 될 수 있습니다. 이 정의역의 n-튜플 값을 통해 n-튜플을 판단하는데 주요 키primary key가 사용될 수 있습니다. 즉, 관계 내에서 이 정의역의 값을 두개 이상 가지는 n-튜플들이(레코드가) 없을 때 주요 키가 됩니다.

    ** 쉽게 말해서, ID_number가 n-튜플(레코드)을 판단하는데 주요 키가 될 수 있습니다. 이름과 평점, 전공은 중복될 수 있으니까요.

     데이터베이스에서 레코드들은 추가되거나 삭제될 수 있습니다. 이런 유 때문에, 정의역이 주요 키라는 속성은 시간 의존적time-dependent입니다. 결과적으로, 주 키는 데이터베이스가 변화할 때마다 선택되어야합니다. 관계 내의 현재의 n-튜플들의 컬렉션은 관계의 확장extension라고 부릅니다. (**공백의 관계에서 n-튜플들이 하나라도 더해져있기 떄문이라고 생각합시다. ) 데이터베이스의 더욱 영구적permanent인 것은, 데이터베이스의 이름과 어트리뷰트를 포함하는, 강화intension 입니다. 주 키를 선택할 때, 이 주 키는 모든 데이터베이스의 확장extension 가능성에 대해 주 키로 작동할 수 있게끔 대응가능해야합니다. 이렇게 하기 위해서, 데이터베이스의 강화intension를 검사하는 것은 매우 중요합니다. 이는 데이터베이스 확장extension에서 n-튜플들의 모든 가능성에 대해 알 수 있습니다.

    (즉, database의 extension은 각 레코드n-tuple들이 해당 어트리뷰트에서 가지는 값을 의미하고, intension은 데이터베이스 내에서 각 값들이 가질 수 있는 크기를 정의합니다. intension의 예는

    Employee(EmpNo Number(4) Not NULL, EName Char(20), Age Number(2), Dept Char(4) ) 가 있습니다.)

    예제 5

    위 예에서 어느 것이 주 키primary key가 될 수 있습니까? 단, 미래에도 어떤 n-튜플들이 추가되지 않는다고 가정합니다.

    *** 테이블 내에서 각 학생 이름에 대해 단 하나의 4-튜플이 존재하기 때문에, 학생 이름의 정의역이 주 키가 될 수 있습니다. 비슷하게, 학생 번호의 정의역이 주 키가 될 수 있습니다. 그러나 학생 번호는 주 키primary key가 될 수 없습니다. 왜냐하면 전공에 대해 여러개의 4-튜플이 존재하기 때문입니다. 유사하게, GPA 또한 같습니다.

    정의역의 조합은 n-진 관계에서 고유한 n-튜플을 인지하는데 사용됩니다. 이는 관계내에서 n-튜플을 판단할 때 정의역의 집합의 값이 사용될 때, 이 정의역의 카테시안 곱Cartesian product 은 복합 키composite key이라고 불립니다. 

    예제 6

    전공의 정의역과 GPA의 정의역의 카테시안 곱이 위 테이블의 n-ary 관계에 대해 복합 키composite key가 될 수 있습니까? 단, 추가되는 n-튜플들이 없다고 가정합니다.

    *** 전공과 학점을 동일하게 가진 4-튜플이 하나 이상 존재하지 않기 때문에, 전공과 학점을 복합 키로 사용할 수 있습니다.


    데이터베이스 내에서 고유한 레코드들을 판별하기위해 주 키primary key와 복합 키composite key가 사용 되기 때문에, 데이터베이스에 레코드가 나중에 추가되더라도 키가 사용 가능하다는게 확실해야합니다. 따라서, 모든 새로운 레코드들에 대해 해당 필드 또는 다수의 필드들(복합 키인 경우)이 고유해야합니다. 예로, 학생 번호는 모든 학생들에 대해 고유하므로 키로 사용할 수 있다고 예측가능합니다. 그러나 학생 이름은 주요 키로 사용해서는 안됩니다. 왜냐하면 혹시나 동일한 이름의 학생이 대학교에 등록할 수 있기 때문입니다.


    n-진 관계에서의 연산Operations on n-ary Relations

    n-진 관계에서의 다양한 연산 행위들이 새로운 n-진 관계를 형성하기위해 사용될 수 있습니다. 모두 응용해서, 이 연산 행위들은 데이터베이스 내에 존재하는 모든 n-튜플들에 대해 특정 조건들을 만족하는 것에 한해서 탐색할 수 있습니다.  

    n-진 관계에서 할 수 있는 가장 기본적인 연산은 n-진 관계에서 해당 조건을 만족하는 모든 n-튜플들을 검사하는 것입니다. 예로, 데이터 베이스내에 존재하는 컴퓨터 사이언스 전공인 학생들의 레코드들을 찾고 싶을 수 있습니다. 평점이 3.5 이상인 학생들을 찾고 싶어할 수 도 있습니다. 평점이 3.5이상인 컴퓨터 사이언스 전공인 학생을 찾고 싶어 할 수도 있습니다. 이런 작업을 수행하기 위해서, selection 연사자를 이용합니다.

    정의 2

    R을 n-진 관계라 하고, C를 관계 R의 엘리먼트가 만족할 수도 있는 조건이라고 하자. 그러면 선택 연산자selection operator s(C)는 n-진 관계 R에서 모든 n-튜플들에 대해 조건 C를 만족하는 n-튜플들을 탐색합니다. 

    예제 7 

    위 테이블에서 컴퓨터 전공자를 찾아봅시다. 이때 연산자 s(C1)를 사용합니다. 여기서 조건 C1는 전공 조건 = "컴퓨터 사이언스"입니다. 결과는 4-튜플들 2개입니다.  (Ackerman, ..., Computer Science, ..), (chou, ... , Computer Science, ...) 비슷하게, 데이터베이스에서 평점 3.5 이상인 레코드들을 찾기 위해서는, 연산자 s(C2)를 사용합니다. 여기서 C2는 조건 GPA > 3.5 입니다. 결과는 4-튜플들 2개입니다. (Ackermann, ... , 3.88), (Rao, ... , 3.90). 마지막으로, 컴퓨터 사이언스 전공이면서 평점이 3.5 이상인 학생을 찾습니다. 이 조건은 연산자 s(C3)를 사용합니다. 여기서 C3는 조건 (전공 ="컴퓨터 사이언스" ∧ GPA > 3.5) 입니다. 결과는 하나의 4-튜플들 입니다. (Ackermann, ..., COmputer Science, 3.88)

    정의 3

    프로젝션 P(i1i2,...,im)은 n-튜플(a1,a2,....an)에서 m-튜플(a1,a2, ..., am)을 탐색합니다. 여기서 i1<a2<...<im 이고, m<= n 입니다.

    예제 8

    프로젝션 P1,3이 4 -튜플 (2,3,0,4), (Jane Doe, 234111001, Geography, 3.14), (a1,a2,a3,a4)에 적용되면 결과는 어떻습니까?

    ** 프로젝션 P1,3은 각각의 4튜플들을 (2,0), (Jane Doe, Geography), (a1,a3)으로 반환합니다.

    예제 9

    프로젝션 P1,4가 위 테이블에 적용되면 결과는 무엇입니까?

    *** 프로젝션 P1,4는 테이블의 두 번째와 세 번째 열을 지우고, 학생 이름과 평점을 얻어냅니다. 결과는 아래의 표(표2)와 같습니다.
     

    관계에 대한 테이블에서 프로젝션이 적용되었을 때 결과물은 적은 열column이기도 합니다. 이는 관계 내의 n-튜플들의 몇몇 튜플들이 m 구성의 프로젝션에서 고유한 값을 가지고, 불일치한 컴퍼넌트가 있을 때만 표시하기 때문입니다.예로 아래의 예를 살펴봅시다.

    예제 10 

    아래의 표(표3)에서, 프로젝션 P(1,2)가 적용되면 어떤 테이블 결과가 나옵니까?

    *** 표3에 대해 프로젝션 P(1,2)가 적용된 결과는 아래 표(표4)처럼 보입니다. 이 프로젝션이 적용된 뒤에는 적은 열만이 있는 것을 확인합시다.

    join 연산자는 두 테이블을 결합하는데 사용합니다. 이때 테이블은 동일한 필드를 공유하고 있습니다. 예로, 한 테이블이 항공사, 항공편명, 게이트 필드들을 가지고 있고, 다른 테이블의 필드는 항공편명, 게이트, 출발시간을 가지고 있습니다. 이 두 테이블을 결합시키면 필드는 항공사, 항공편명, 게이트, 출발시간 필드들을 가지고 있습니다.

    정의 4

    R을 m 급degree의 관계이고 S는 n degree의 관계라고 하자. join Jp(R,S)는 m+n-p 급의 관계입니다. 여기서 p≤m 이고 p≤n이며 (m+n-p)-튜플들 (a1,a2,...,am-p,c1,c2,...,cp,b1,b2,...,bn-p)로 이루어져있습니다. 여기서 R에 속한 m-튜플은 (a1,a2,....,am-p,c1,c2,...,cp)이고 S에 속한 n-튜플은 (c1,c2,...,cp,b1,b2,..,bn-p)입니다.

    다른 표현으로는, join 연산자 Jp는 첫 번째 관계의 m-튜플들과 두 번째 관계의 n-튜플들을 결합하여 새로운 관계를 제공합니다. 여기서 m-튜플들의 마지막 p 컴퍼넌트는 n-튜플들의 p 컴퍼넌트와 일치합니다.  

    예제 11

    아래에 제시된 표5와 표6에 대한 join 연산자 J2의 결과는 무엇입니까? 

    *** 다음과 같은 테이블이 도출됩니다.


    'Discrete mathmatics and Problem Solving > 9 관계 Relations' 카테고리의 다른 글

    9 관계 Relations 4  (0) 2016.10.20
    9 관계Relations 3  (0) 2016.10.18
    9 관계relation 2  (0) 2016.10.17
    9 관계 Relations 1  (0) 2016.10.13

    댓글 0

Designed by Tistory.