이산수학 () n-항관계 (n-ary Relations) 2011년봄학기 강원대학교컴퓨터과학전공문양세
n-ary Relations (n-항관계 ) An n-ary relation R on sets A 1,,A n, written R:A 1,,A n, is a subset R A 1 A n. (A 1,,A n 에대한 n- 항관계 R 은 A 1 A n 의부분집합이다.) The sets A i are called the domains of R. (A i 를 R 의정의역이라한다.) The degree of R is n. ( 관계 R 의차수는 n 이다.) Page 2
Relational Databases ( 관계형 DB) A relational database is essentially an n-ary relation R. ( 관계형데이터베이스란 n- 항관계 R 을의미한다.) A domain A i is a primary key for the database if the relation R contains at most one n-tuple (, a i, ) for any value a i within A i. ( 만일 R 이 ( 정의역 A i 에포함된 ) a i 에대해서기껏해야하나의 n- 항튜플 (, a i, ) 를포함하면, A i 는기본키라한다.) ( 다시말해서, a i 값을가지는 n- 항튜플이유일하면 A i 를키본키라한다.) A composite key for the database is a set of domains {A i, A j, } such that R contains at most 1 n-tuple (,a i,,a j, ) for each composite value (a i, a j, ) A i A j Page 3
Primary Key 예제 예제 : ( 새로운튜플이추가되지않는다고할때,) 다음테이블에서어떤 정의역이기본키인가? 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 Student_name 은키본키이다. ( 유일하게구분짓는다.) 마찬가지로, ID_ number 또한기본키이다. 반면에, Major 나 GPA 는기본키가아니다. Page 4
Composite Key 예제 예제 : ( 새로운튜플이추가되지않는다고할때,) 다음테이블에서 {Major, GPA} 는합성키인가? 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 Major와 GPA를조합하여사용하면튜플을유일하게구분지을수있으므로, {Major, GPA} 는상기테이블의합성키이다. Page 5
Selection Operator ( ) Let A be any n-ary domain A=A 1 A n, 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 P. ( 셀렉션연산자 p 은관계 R 의 n- 튜플중에서술어 P 를만족하는튜플들의관계 로정의한다.) I.e., R A, p (R) = R {a A P(a) = T} Page 6
Selection Example 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, UpperLevel is the selection operator that takes any relation R on A (database of students) t and produces a relation consisting of just the upper-level classes (juniors and seniors). Student_namename 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 That is, (level = junior) (level = senior) (R) Rao 678543 Mathematics 390 3.90 Stevens 786576 Psychology 2.99 Page 7
Projection Operator ( ) Let A = A 1 A n be any n-ary domain, and let {i k }=(i 1,,ii m ) be a sequence of indexes, That is, where 1 i k n for all 1 k m. Then the projection operator on n-tuples is defined by: { i } : A Ai Ai k 1 m 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 ( a,..., a ) ( a,..., a ) { i } 1 n i i k 1 m Page 8
Projection Example Suppose we have a ternary (3-ary) domain Cars = Model Year Color. l (note n=3). Consider the index sequence {i k }= 13 1,3. (m=2) Then the projection simply maps each tuple (a 1,a 2,a 3 ) = (model,year,color) to its image: ( ai, a ) ( a1, a3 ) ( model dl, color ) 1 i 2 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 Page 9
(Natural) Join Operator ( ) Puts two relations together to form a sort of combined relation. ( 관계를합성하는한가지방법 ) If the tuple (A,B) appears in R 1, and the tuple (B,C) appears in R 2, then the tuple (A,B,C) appears in the join R 1 R 2. A, B, C can also be sequences of elements rather than single elements. Page 10
(Natural) Join Example Suppose R 1 is a teaching assignment table, relating Professors to Courses. ((Professor, Courses) 로구성된관계 ) Suppose R 2 is a room assignment table relating Courses to Rooms,Times. ((Courses, Rooms, Times) 로구성된관계 ) Then R 1 R 2 is like your class schedule, listing (professor,course,room,time). room Page 11