Microsoft PowerPoint - 27.pptx

Size: px

Start display at page:

Download "Microsoft PowerPoint - 27.pptx"

이현 엽
6 years ago
Views:

1 이산수학 () n-항관계 (n-ary Relations) 2011년봄학기 강원대학교컴퓨터과학전공문양세

2 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

3 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

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

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

6 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

7 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 Computer Science 3.88 Adams Physics 3.45 Chou Computer Science 3.49 Goodfriend Mathematics 3.45 That is, (level = junior) (level = senior) (R) Rao Mathematics Stevens Psychology 2.99 Page 7

8 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 Computer Science 3.88 Adams Physics 3.45 Chou Computer Science 3.49 Goodfriend Mathematics 3.45 Rao Mathematics 3.90 Stevens Psychology 2.99 ( a,..., a ) ( a,..., a ) { i } 1 n i i k 1 m Page 8

9 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 Computer Science 3.88 Adams Physics 3.45 Chou Computer Science 3.49 Goodfriend Mathematics 3.45 Rao Mathematics 3.90 Stevens Psychology 2.99 Page 9

10 (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

11 (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

Microsoft PowerPoint Relations.pptx

Microsoft PowerPoint Relations.pptx 이산수학 () 관계와그특성 (Relations and Its Properties) 2010년봄학기강원대학교컴퓨터과학전공문양세 Binary Relations ( 이진관계 ) Let A, B be any two sets. A binary relation R from A to B, written R:A B, is a subset of A B. (A 에서 B 로의이진관계