데이터베이스및설계 Chap 5. 관계대수와관계해석 #1. Relational lgebra 2014.03.18. 오병우 컴퓨터공학과
관계데이터연산 데이터모델 (D) D = <S, O, C> S: 구조, O: 연산, C: 제약조건연산과데이터언어 연산 : 시스템입장 데이터언어 : 사용자입장관계데이터언어 ⅰ. 관계대수 (relational algebra) 절차언어 : how ⅱ. 관계해석 (relational calculus) 비절차언어 : what 투플관계해석 도메인관계해석관계해석과관계대수는표현이나기능면에서동등 Department of Computer Engineering 2
Relational lgebra & Calculus Relational lgebra ( 관계대수 ) lgebra is a type of mathematics in which letters are used to represent possible quantities. Procedural language ( 절차언어 ) : How Relational Calculus ( 관계해석 ) Calculus is a branch of advanced mathematics which deals with variable quantities. Nonprocedural language ( 비절차언어 ) : What 뭘원하는지만기술하면되므로사용편이 Department of Computer Engineering 3
Relationally Complete 관계해석으로표현할수있는것은모두관계대수로도표현가능 a language: relationally complete ( 완전성 ) at least as powerful as the relation algebra i.e., its expressions permit the definition of every relation that can be defined by means of expressions of the algebra 어떤데이터언어가 relational calculus 가표현할수있는모든질의를표현할수있을때 relationally complete 하다고함 ( 또는 relational completeness) Department of Computer Engineering 4
Relational lgebra Department of Computer Engineering 5
Introduction of Relational lgebra Manipulative part of the relational model Relational algebra: a set of operators ssignment operation: named relation := expression of the algebra Relational algebra (8 operators) collection of high-level operators that operate on relations 릴레이션 : 투플의집합 One or two relations (input) a new relation (output) Traditional set operations ( 집합연산 ) Union, intersection, difference, and Cartesian product Special relational operations Restrict (select), project, join, and divide 수학의 Closure property ( 정수의덧셈결과는정수 ) Relations are closed under the algebra 피연산자와연산결과가모두릴레이션 Nested relational expressions 가능 Expressions in which the operands are themselves represented by expressions (not names) Department of Computer Engineering 6
lgebra expression What is the lgebra for? a high-level and symbolic representation of the user s intent basis for query optimization (ex) (( S JOIN SP ) WHERE P#= P2 ) [SNME] (S JOIN (SP WHERE P#= P2 )) [SNME] 줄여놓은다음에 Join 하여질의처리시간을줄일수있음 pplications of algebraic expression defining a scope for retrieval defining a scope for update (insert, modify, delete) defining virtual data (i.e., view) defining snapshot data defining access rights (authorization) defining stability requirement (concurrency control) defining integrity constraints Department of Computer Engineering 7
Traditional Set Operations Two relations: union compatibility ( 합병가능 ) They have identical ( 동일한 ) headings ( 스키마 ) 1. They each have the same set of attribute names (same degree) 2. Corresponding attributes are defined on the same domain Traditional set operations: two operands, B union( ) : Union-compatible UNION B = {t t t B} intersection( ) : Union-compatible INTERSECT B = {t t t B} difference ( - ) : Union-compatible MINUS B = {t t t B} extended Cartesian product (X) Concatenation ( ) TIMES B = {t s t s B} Department of Computer Engineering 8
ⅰ. 합집합 (union, ) R S = { t t R t S } R S R + S ⅱ. 교집합 (intersect, ) R S = { t t R t S } R S min{ R, S } ⅲ. 차집합 (difference,-) R - S = { t t R t S } R - S R 일반집합연산자 Cardinality ( 투플의개수 ) ⅳ. 카티션프로덕트 (cartesian product, ) R S = { r s r R s S } Concatenation of t=(1:a1, 2:a2,,m:am), s=(b1:, B2:b2,,Bn:bn) t s = (1:a1, 2:a2,, m:am, B1:, B2:b2,, Bn:bn) (m+n)-th attribute R S = R S 차수 (degree) = R 의차수 + S 의차수 Department of Computer Engineering 9
ssociative and Commutative Operations UNION, INTERSECT, TIMES (not MINUS) associative ( UNION B) UNION C = UNION (B UNION C) = UNION B UNION C,, 연산은결합적 (associative) 임 R S T = (R S) T = R (S T) R S T = (R S) T = R (S T) R S T = (R S) T = R (S T) commutative UNION B = B UNION,, 연산은교환적 (commutative) 임 R S = S R R S = S R R S = S R 순서에상관없이결과가동일한 Department of Computer Engineering 10
Examples Union, intersection, difference and Cartesian product Department of Computer Engineering 11
표기법 릴레이션 : R(X) = R( 1,..., n ) R 의투플 : r = <a 1,..., a n > R 은 r 의집합 R={ r } R={r r = <a 1,..., a n > } 근데, r 은애트리뷰트값들로구성됨 ttribute Degree (# of ttribute) a tuple Value of the n-th ttribute 투플 r 에대한애트리뷰트 i 의값 r. i 또는 a i r. i = r[ i ] = a i 다음관계가성립 <r. 1, r. 2,, r. n > = < r[ 1 ], r[ 2 ],, r[ n ] > = r[ 1, 2, n ] = r[x] Department of Computer Engineering 12
Restriction (select) : (sigma) Restriction (theta-selection) R(U): a relation, B U: attribute defined on the same domain θ (theta) {<,, >,, =, } v : literal value v (R) = { r r R r. θ v } B (R) = { r r R r. θ r.b } horizontal subset of R 선택조건을만족하는릴레이션의수평적부분집합 Boolean combination of simple comparisons R WHERE C1 ND C2 (R WHERE C1) INTERSECT (R WHERE C2) R WHERE C1 OR C2 (R WHERE C1) UNION (R WHERE C2) R WHERE NOT C R MINUS (R WHERE C) 조건식 (predicate) 중간성적 > 30 조건식 (predicate) 중간성적 < 기말성적 데이터언어식표현 Department of Computer Engineering 13
Restriction (select) Example 학과 = ' 컴퓨터 ' ( 학생 ) 학번 = 300 과목번호 ='C312' ( 등록 ) 중간성적 < 기말성적 ( 등록 ) 데이터언어식표현 R WHERE 조건식 조건 2 ( 조건 1 (R)) = 조건 1 ( 조건 2 (R)) = 조건 1 조건 2 (R) 선택도 (selectivity) : 선택조건에의해선택된투플의비율 Query optimization: 선택도가적은것부터수행 Department of Computer Engineering 14
데이터언어식표현 학생 WHERE 학과 = 컴퓨터 예제 σ 학과 =' 컴퓨터 ' ( 학생 ) 학번이름학년학과 100 300 나수영정기태송병길 σ 학번 =300 과목번호 ='C312' ( 등록 ) 4 1 4 컴퓨터컴퓨터컴퓨터 교재 p.86 또는슬라이드 pp.16-17 참조 등록 WHERE 학번 =300 ND 과목번호 = C312 등록 WHERE 중간성적 < 기말성적 학번과목번호성적중간성적기말성적 300 C312 90 σ 중간성적 < 기말성적 ( 등록 ) 학번과목번호성적중간성적기말성적 100 300 C413 C312 C312 C413 E412 B C 90 90 90 80 65 85 75 Department of Computer Engineering 15
example 대학 (University) 관계데이터베이스 학생 (STUDENT) 학번 (Sno) 이름 (Sname) 학년 (Year) 학과 (Dept) 100 나수영 4 컴퓨터 200 이찬수 3 전기 300 정기태 1 컴퓨터 송병길 4 컴퓨터 500 박종화 2 산공 과목 (COURSE) 과목번호 (Cno) 과목이름 (Cname) 학점 (Credit) 학과 (Dept) C123 프로그래밍 3 컴퓨터 C312 자료구조 3 컴퓨터 C324 화일구조 3 컴퓨터 C413 데이터베이스 3 컴퓨터 E412 반도체 3 전자 담당교수 (PRname) 김성국 황수관 이규찬 이일로 홍봉진 Department of Computer Engineering 16
example 대학 (University) 관계데이터베이스 (cont d) 등록 (ENROL) 학번 (Sno) 100 과목번호 (Cno) C413 성적 (Grade) 중간성적 (Midterm) 90 기말성적 (Final) 100 E412 200 C123 B 85 80 300 C312 90 300 C324 C 75 75 300 C413 90 C312 90 C324 90 C413 B 80 85 E412 C 65 75 500 C312 B 85 80 Department of Computer Engineering 17
Projection : (pi) Projection 릴레이션 R(X) 에서 Y X 이고 Y={B 1,B 2,,B m } 이면, Y (R)={ <r.b 1,..., r.b m > r R } vertical subset of R 릴레이션의수직적부분집합 duplicate tuples are eliminated 생성된중복투플은제거 Example 학생 ( 학번, 이름, 학년 ) 에서 이름 ( 학생 ) 데이터언어식표현 R [B 1,B 2,,B m ] e.g., (S WHERE CITY = Paris ) [ S#, SNME ] Y ( X (R)) = Y (R) Department of Computer Engineering 18
데이터언어식표현 이름, 학과 ( 학생 ) 예제 학생 [ 이름, 학과 ] 과목 [ 과목이름, 담당교수 ] 이름 나수영이찬수정기태송병길박종화 과목이름, 담당교수 ( 과목 ) 과목이름 프로그래밍자료구조화일구조데이터베이스반도체 학과 컴퓨터전기컴퓨터컴퓨터산공 담당교수 김성국황수관이규찬이일로홍봉진 Department of Computer Engineering 19
데이터언어식표현 Theta-join : θb Theta-join : not primitive operation R(U), S(V): relations X, Y: X U and Y V and defined on the same domain θ {<,, >,, =, } R.X theta-join S.Y = {r s: r R s S r[x] θ s[y]} R[X θ Y]S = (R TIMES S) WHRER X theta Y 예제 ) ((S RENME CITY S SCITY) TIMES (P RENMES CITY S PCITY)) WHERE SCITY>PCITY 학생 학번 = 학번등록의결과릴레이션에서학생. 학번, 학생. 이름, 학생. 학년, 학생. 학과, 등록. 과목번호, 등록. 성적, 등록. 중간성적, 등록. 기말성적 Equijoin theta(θ): equals (=) two attributes have identical ( 동일한 ) values R =B S = { r s r R s S ( r.=s.b ) } Department of Computer Engineering 20
Equijoin 예제 cf.) Natural Join 은 1 개 ( 중복제거 ) 학번이 2 개 학생 학번 = 학번등록 학생. 학번이름학년학과등록. 학번과목번호성적중간성적기말성적 100 100 200 300 300 300 500 나수영나수영이찬수정기태정기태정기태송병길송병길송병길송병길박종화 4 4 3 1 1 1 4 4 4 4 2 컴퓨터컴퓨터전기컴퓨터컴퓨터컴퓨터컴퓨터컴퓨터컴퓨터컴퓨터산공 100 100 200 300 300 300 500 C413 E412 C123 C312 C324 C413 C312 C324 C413 E412 C312 B C B C B 90 85 90 75 90 80 65 85 80 75 90 85 75 80 Department of Computer Engineering 21
일반적인 조인 Natural Join : ( 또는 N ) 데이터언어식표현 Natural join R(X, Y) = R(X1, X2,, Xm, Y1, Y2,, Yn) S(Y, Z) = S(Y1, Y2,, Yn, Z1, Z2,, Zp) R S R JOIN S = {x y z r R s S r[x]=x r[y] = s[y] = y s[z] = z} X Y Y Z X Y Z Y: 중복되는애트리뷰트 ssociative and commutative R and S: no common attribute names R JOIN S R TIMES S Department of Computer Engineering 22
Natural Join ( 교재 ) Natural join: N R(X), S(Y) 의조인애트리뷰트를 Z(=X Y) 라하면 R NS = {<r s>[x Y] r R s S r[z]=s[z] } = X Y ( Z=Z (R S)) = X Y (R Z=ZS) thetajoin 즉 equijoin 의결과릴레이션에서애트리뷰트의중복을제거함 예제 ) Equijoin: 학생. 학번, 등록. 학번 (2 개 ) Natural Join: 학번 (1 개 ) Department of Computer Engineering 23
Natural join 예제 학번이 1 개 cf.) EquiJoin 은 2 개 ( 중복 ) 학생 N 등록 학번이름학년학과과목번호성적중간성적기말성적 100 100 200 300 300 300 500 나수영나수영이찬수정기태정기태정기태송병길송병길송병길송병길박종화 4 4 3 1 1 1 4 4 4 4 2 컴퓨터컴퓨터전기컴퓨터컴퓨터컴퓨터컴퓨터컴퓨터컴퓨터컴퓨터산공 C413 E412 C123 C312 C324 C413 C312 C324 C413 E412 C312 B C B C B 90 85 90 75 90 80 65 85 80 75 90 85 75 80 Department of Computer Engineering 24
Division Division : R(X, Y) = R(X1, X2,, Xm, Y1, Y2,, Yn) S(Y) = S(Y1, Y2,, Yn) 데이터언어식표현 R DIVIDEDBY S = {r[x]: r R r[x] s R for all s S} 교재 : 릴레이션 R(X), S(Y) 에대하여 Y X 이고 Z =X-Y 이면 R(X)=R(Z,Y) R S ={ t t Z (R) t s R for all s S } Note : (R S) S R Department of Computer Engineering 25
Examples of Division 학과목 (SC) 과목 1(C1) 과목 2(C2) 과목 3(C3) 학번 (Sno) 과목번호 (Cno) 100 C413 100 E412 200 C123 300 C312 300 C324 300 C413 C312 C324 C413 E412 500 C312 과목번호 (Cno) C413 학번 (Sno) 100 300 과목번호 (Cno) C312 C413 학번 (Sno) 300 과목번호 (Cno) C312 C413 E412 SC C1 SC C2 SC C3 학번 (Sno) Department of Computer Engineering 26
RENME: ρ (Rho) 중간결과릴레이션에이름을지정 ( 예제 1) 하거나애트리뷰트이름을변경 ( 예제 2) 할때사용 1 2 3 ρ S (E) 관계대수식 E 의결과릴레이션의이름을 S 로지정 ρ S(B1,B 2,,B m )(E) 관계대수식 E 의결과릴레이션의이름을 S 로지정하면서 애트리뷰트이름을각각 B 1,B 2,,B m 으로변경 ρ (B1,B 2,,B m )(R) 릴레이션 R 의애트리뷰트이름을각각 B 1,B 2,,B m 으로변경 예제 1: 학생중에서컴퓨터학과학생의이름선택 이름 (σ 학과 =' 컴퓨터 ' ( 학생 )) Temp σ 학과 =' 컴퓨터 ' ( 학생 ) 컴학생 이름 (Temp) 예제 2: 이름애트리뷰트를성명으로변경 컴학생 ( 성명 ) 이름 (Temp) Department of Computer Engineering 27
Relational ssignment Relational assignment operation to remember the value of some algebraic expression to change the database state insert S := S UNION { (S# : S6, SNME: Baker, STTUS: 50, CITY: Madrid ) } delete SP := SP MINUS { (S# : S1, P# : P1, QTY : 300) } 데이터언어식표현 데이터언어식표현 Department of Computer Engineering 28
Primitive and Composite Operations Primitive operations ( 근원연산 ) can not be defined in terms of the others 하나의논리적기능을수행, 다른연산을이용하여표현할수없음 restriction, projection, product, union, difference Composite operations ( 복합연산 ) 근원연산을이용하여표현할수있음 (intersection, join, division) R S = R - (R - S) = S - (S - R) = (R S) - ( (R - S) (S - R) ) R θb S = θb (R S) R(Z,Y) S(Y)= R[Z] - ((R[Z] S) - R)[Z] 연산력보다는표현력증대 간단하게표현가능 Department of Computer Engineering 29
Relational lgebra 의확장 Semijoin Outerjoin Outer-union 수학적인집계연산 SUM VG MX, MIN COUNT GROUP Department of Computer Engineering 30
Semijoin: R(X), S(Y) 의조인애트리뷰트를 Z=X Y 라하면 R S = R N( Z (S)) = X(R NS) S 와 natural join 할수있는 R 의투플만을선택 특징 R S S R R NS = (R S) NS = (S R) NR 처리해야할데이터의양이다름 Query Optimization Department of Computer Engineering 31
Natural Join vs. Semijoin R B C S B C D X Y (S) a1 a2 a3 a4 X b2 c2 c3 b2 Y c3 d1 d2 d3 B b2 C c3 N R N S R S B C D B C a1 d1 a1 a1 d2 N a2 a2 d1 a4 b2 c3 a2 d2 a4 b2 c3 d3 Semijoin Natural Join N R N S 에서 D 제거 R S = R N( Z (S)) = X(R NS) Z=X Y Department of Computer Engineering 32
Equijoin, Natural Join and Semijoin R B C a1 a2 a3 a4 R.B S.B R.C S.C D a1 a1 a2 a2 a4 b2 b2 b2 c2 c3 Equijoin c3 S c3 B C D b2 c3 d1 d2 d1 d2 d3 d1 d2 d3 중복제거 Natural Join B C D a1 a1 a2 a2 a4 Semijoin b2 c3 B C a1 a2 a4 b2 D 제거 c3 d1 d2 d1 d2 d3 Department of Computer Engineering 33
Outerjoin: + 한릴레이션에있는투플이조인할상대릴레이션에대응되는투플이없을경우, 상대를널 (null) 투플로만들어결과릴레이션에포함 두조인릴레이션의모든투플들이결과릴레이션에포함됨 Department of Computer Engineering 34
Natural Join vs. Outerjoin R B C S B C D a1 a2 a3 a4 b2 c2 c3 b2 b3 c3 c3 d1 d2 d3 d3 + R + S N outerjoin B C D a1 a1 a2 a2 a3 a4 b2 b3 c2 c3 c3 d1 d2 d1 d2 d3 d3 R N S B C D a1 a1 a2 a2 a4 b2 c3 d1 d2 d1 d2 d3 Natural join Department of Computer Engineering 35
PHP 예제 Event 를평가한점수를기반으로아이돌순위별정렬 $query = "SELECT event.userid, avg(rating.userrating) as rating, IFNULL(COUNT(rating.userid), 0) as ratingcount, COUNT(distinct rating.userid) as usercount, ( 생략 ) user.memo FROM user, idol, event LEFT OUTER JOIN rating ON rating.eventid=event.eventid WHERE user.userid=event.userid ND user.userid=idol.userid ND ( 생략 ) GROUP BY event.userid ORDER BY VG(rating.userrating) DESC, ( 생략 ), IFNULL(COUNT(rating.userid), 0) DESC LIMIT $since,$max"; Department of Computer Engineering 36
외부합집합 Outer-union, + 합병가능하지않은 ( 부분적으로합병가능한 ) 두릴레이션을 degree( 차수 ) 를확장시켜합집합생성 R(U): degree n, S(V): degree m, RS = R JOIN S R OJOIN S = RS ((R - RS[U]) (null,, null)m-1) ((null,, null)n-1 (S - RS[V])) 문제점 : nulls in the primary key position + B C D R B C a1 a2 a3 a4 b2 c2 c3 S B C D b2 c2 d1 d2 d3 a1 a2 a3 a4 b2 b2 c2 c3 c2 d1 d2 d3 Department of Computer Engineering 37
집계연산 집계연산 SUM : 합계, VG: 평균값, MX: 최대값, MIN: 최소값 COUNT: 집합내에속한값의개수 GROUP: 지정된애트리뷰트값에따라투플들을그룹핑 SUMMRIZE SP GROUPBY (P#) DD SUM (QTY) S TOTQTY VG 성적 ( 등록 ) 등록릴레이션에있는성적애트리뷰트값들에대해평균값계산 GROUP 학년 ( 학생 ) 학생릴레이션의투플들을학년값에따라그룹짓게함 GROUP 과목번호 VG 성적 ( 등록 ) 과목별그룹에대한평균성적 일반형식 : G F B (E) G : 그룹함수 GROUP (GROUPBY) : 그룹함수가적용할애트리뷰트 F : 집단함수 ( SUM, VG, MX, MIN, COUNT) B : 집단함수의적용대상애트리뷰트 E : Relational lgebra Expression ( 관계대수식 ) 데이터언어식표현 Department of Computer Engineering 38
Relational lgebra 질의 교재 p.111, p.86 참조 시험문제 : 다음질의를 (1) Relational lgebra, (2) 데이터언어식표현으로바꾸고 (3) 결과릴레이션을구하시오. 모든학생의이름과학과를검색하라. 과목번호가 C413 인과목에등록한학생의이름과성적은무엇인가? ' 화일구조 ' 과목을가르치는교수의이름을검색하라. 모든과목에수강하고있는학생의학번과이름을검색하라. 학번이 600, 이름이 ' 김영호 ', 학년이 4, 학과가컴퓨터인학생을삽 입하라. 과목 ' 데이터베이스 ' 를삭제하라. Department of Computer Engineering 39