이산수학(Discrete Mathematics) 수학적 귀납법 (Mathematical Induction)

Presentation on theme: "이산수학(Discrete Mathematics) 수학적 귀납법 (Mathematical Induction)"— Presentation transcript:

1 이산수학(Discrete Mathematics) 수학적 귀납법 (Mathematical Induction)
강원대학교 컴퓨터과학전공 문양세

2 n-ary Relations (n-항 관계)
An n-ary relation R on sets A1,…,An, written R:A1,…,An, is a subset R  A1× … × An. (A1,…,An에 대한 n-항 관계 R은 A1× … × An의 부분집합이다.) The sets Ai are called the domains of R. (Ai를 R의 정의역이라 한다.) The degree of R is n. (관계 R의 차수는 n이다.)

3 Relational Databases (관계형 DB)
7.2 n-ary Relations A relational database is essentially an n-ary relation R. (관계형 데이터베이스란 n-항 관계 R을 의미한다.) A domain Ai is a primary key for the database if the relation R contains at most one n-tuple (…, ai, …) for any value ai within Ai. (만일 R이 (정의역 Ai에 포함된) ai에 대해서 기껏해야 하나의 n-항 튜플 (…, ai, …)를 포함하면, Ai는 기본 키라 한다.) (다시 말해서, ai 값을 가지는 n-항 튜플이 유일하면 Ai를 키본 키라 한다.) A composite key for the database is a set of domains {Ai, Aj, …} such that R contains at most 1 n-tuple (…,ai,…,aj,…) for each composite value (ai, aj,…)Ai×Aj×…

4 Primary Key 예제 예제 3: (새로운 튜플이 추가되지 않는다고 할 때,) 다음 테이블에서 어떤 정의역이 기본 키인가?
7.2 n-ary Relations 예제 3: (새로운 튜플이 추가되지 않는다고 할 때,) 다음 테이블에서 어떤 정의역이 기본 키인가? Student_name ID_number Major GPA Ackermann 231455 Computer Science 3.88 Adams 888323 Physics 3.45 Chou 102147 3.49 Goodfriend 453876 Mathematics Rao 678543 3.90 Stevens 786576 Psychology 2.99 Student_name은 키본 키이다. (유일하게 구분 짓는다.) 마찬가지로, ID_number 또한 기본 키이다. 반면에, Major나 GPA는 기본 키가 아니다.

5 Composite Key 예제 7.2 n-ary Relations 예제 4: (새로운 튜플이 추가되지 않는다고 할 때,) 다음 테이블에서 {Major, GPA}는 합성 키인가? Student_name ID_number Major GPA Ackermann 231455 Computer Science 3.88 Adams 888323 Physics 3.45 Chou 102147 3.49 Goodfriend 453876 Mathematics Rao 678543 3.90 Stevens 786576 Psychology 2.99 Major와 GPA를 조합하여 사용하면 튜플을 유일하게 구분 지을 수 있으므로, {Major, GPA}는 상기 테이블의 합성 키이다.

6 Selection Operator ()
7.2 n-ary Relations Let A be any n-ary domain A=A1×…×An, and let P:A→{T,F} be any predicate on elements of A. (A를 n-항 관계의 정의역이라 하고, P를 A에서 {T,F}로의 술어라 하자.) Then, the selection operator p is the operator that maps any (n-ary) relation R on A to the n-ary relation of all n-tuples from R that satisfy C. (셀렉션 연산자 p 은 관계 R의 n-튜플 중에서 술어 P를 만족하는 튜플들의 관계로 정의한다.) I.e., RA, p(R) = R{aA | P(a) = T}

7 Suppose we have a domain A = StudentName × Level × SocSecNos
Selection Example 7.2 n-ary Relations Suppose we have a domain A = StudentName × Level × SocSecNos Suppose we define a certain predicate on A, UpperLevel(name, level, ssn) :≡ [(level = junior)  (level = senior)] Then, sUpperLevel is the selection operator that takes any relation R on A (database of students) and produces a relation consisting of just the upper-level classes (juniors and seniors). That is, (level = junior)  (level = senior)(R)

8 Projection Operator ()
7.2 n-ary Relations Let A = A1×…×An be any n-ary domain, and let {ik}=(i1,…,im) be a sequence of indexes, That is, where 1 ≤ ik ≤ n for all 1 ≤ k ≤ m. Then the projection operator  on n-tuples is defined by:

9 Consider the index sequence {ik}= 1,3. (m=2)
Projection Example 7.2 n-ary Relations Suppose we have a ternary (3-ary) domain Cars = Model×Year×Color. (note n=3). Consider the index sequence {ik}= 1,3. (m=2) Then the projection  simply maps each tuple (a1,a2,a3) = (model,year,color) to its image:

10 (Natural) Join Operator ( )
7.2 n-ary Relations Puts two relations together to form a sort of combined relation. (관계를 합성하는 한 가지 방법) If the tuple (A,B) appears in R1, and the tuple (B,C) appears in R2, then the tuple (A,B,C) appears in the join R1 R2. A, B, C can also be sequences of elements rather than single elements.

11 (Natural) Join Example
7.2 n-ary Relations Suppose R1 is a teaching assignment table, relating Professors to Courses. ((Professor, Courses)로 구성된 관계) Suppose R2 is a room assignment table relating Courses to Rooms,Times. ((Courses, Rooms, Times)로 구성된 관계) Then R1 R2 is like your class schedule, listing (professor,course,room,time).