5. 관계대수와 관계해석 관계자료 연산(operation)

Presentation on theme: "5. 관계대수와 관계해석 관계자료 연산(operation)"— Presentation transcript:

1 5. 관계대수와 관계해석 관계자료 연산(operation)

2  관계 자료 연산 연산과 자료 언어 관계 자료 언어 관계 해석과 관계 대수는 표현이나 기능면에서 동등 연산 : 시스템 입장
자료 언어 : 사용자 입장 관계 자료 언어 ⅰ. 관계 대수(relational algebra) 절차언어 : how, what ⅱ. 관계해석(relational calculus) 비절차언어 : what(대상) (1) 투플 관계해석 (2) 도메인 관계해석 관계 해석과 관계 대수는 표현이나 기능면에서 동등

3  5.1 관계대수(Relational Algebra) p96
릴레이션을 처리하기 위한 연산의 집합 릴레이션 : 투플의 집합 기본 연산 일반 집합 연산자 : 합집합 교집합 차집합 카티션 프로덕트 순수 관계 연산자 : 실렉트 프로젝트 조인 디비전 폐쇄속성(closure property) 피연산자와 연산 결과가 모두 릴레이션 중첩(nested)된 수식의 표현이 가능

4 ▶ 5.1.1 일반 집합 연산자(1) p97 (1). 합집합 (union, ∪) (2). 교집합 (intersect, ∩)
R∪S ＝ { t | t∈R ∨ t∈S } |R∪S| ≤ |R| + |S| (2). 교집합 (intersect, ∩) R∩S ＝ { t | t∈R ∧ t∈S } |R∩S| ≤ min{ |R|, |S| } (3). 차집합 (difference, -) R­S ＝ { t | t∈R ∧ t  S } |R­S| ≤ |R| (4). 카티션 프로덕트 (cartesian product, ×) R×S ＝ { r·s | r∈R ∧ s∈S } · : 접속(concatenation) |R×S| = |R|×|S| 차수(degree) ＝ R의 차수 + S의 차수

5 ▶ 일반 집합 연산자(2) tip 합병가능(union-compatible)한 릴레이션
∪, ∩, - 연산의 피연산자들은 ⅰ. 차수가 같아야 함 ⅱ. 대응 애트리뷰트 별로 도메인이 같아야 함 ∪, ∩, × 연산은 결합적(associative)임 A∪B∪C ＝ (A∪B)∪C ＝ A∪(B∪C) ∪, ∩, × 연산은 교환적(commutative)임 A∪B ＝ B∪A

6 ▶ 5.1.2 순수 관계 연산자 p99 릴레이션 : R(X) ＝ R(A1, ... , An)
R의 투플 : r ＝ <a1, ... , an> R={r | r ＝ <a1, ... , an> } 투플 r에 대한 애트리뷰트 Ai의 값 r.Ai 또는 ai r.Ai ＝ r[Ai] ＝ ai

7 (1) 실렉트(SELECT, ) (1) p100 A, B가 릴레이션 R의 애트리뷰트일 때,
Av(R) ＝ { r | r∈R ∧ r.Aθv } AB(R) ＝ { r | r∈R ∧ r.Aθr.B } 조건식(predicate) 단, θ(theta) ＝ { <, >, ≤, ≥, ＝, ≠ } v : 상수 선택 조건을 만족하는 릴레이션의 수평적 부분집합 (horizontal subset)

8 실렉트 (2) 예 자료 언어식 표현 R WHERE 조건식 조건2(조건1(R)) = 조건1(조건2(R))
학과 = '전산학' (학생) 학번 = 300  과목번호='C312'(등록) 중간성적<기말성적 (등록) 자료 언어식 표현 R WHERE 조건식 조건2(조건1(R)) = 조건1(조건2(R)) = 조건1  조건2 (R) 선택도(selectivity) : 선택 조건에 의해 선택된 투플의 비율

9 (2) 프로젝트 (PROJECT, ) 릴레이션 R(X)에서 Y⊆X 이고 Y={B1,B2, … ,Bm} 이면,
Y(R)＝{ <r.B1, ... , r.Bm> | r∈R } 예 학생(학번,이름,학년)에서 이름(학생) 릴레이션의 수직적 부분집합(vertical subset) 생성된 중복 투플은 제거 Y(X(R)) = Y(R)

10 (3) 조인(JOIN, )(1) 세타조인 (theta-join) 예 동일조인 (equi-join)
R(X), S(Y), A∈X, B∈Y 에 대하여 R AθB S ＝ { r · s | r∈R ∧ s∈S ∧ ( r.Aθs.B) } A, B : joining attribute 결과 차수 = R의 차수 + S의 차수 예 학생 학번=학번 등록 동일조인 (equi-join) 세타조인에서 θ가 "＝"인 경우 R A=BS ＝ { r·s | r∈R ∧ s∈S ∧ ( r.A＝s.B ) }

11 조인 (2) 자연조인 (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(R Z=ZS) = X∪Y(Z=Z(R×S)) 즉 동일조인의 결과 릴레이션에서 애트리뷰트의 중복을 제거함

12 (4) 디비전 (DIVISION, ÷) (1) p104 릴레이션 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

13 디비전(2) 예 학과목(SC) 과목1(C1) 과목2(C2) 과목3(C3) 학번 (SNO) 과목번호 (CNO) 과목번호
100 C413 C413 C312 C312 100 E412 C413 C413 200 C123 E412 300 C312 300 C324 300 C413 SC ÷ C1 SC ÷ C2 SC ÷ C3 400 C312 400 C324 학번 (SNO) 학번 (SNO) 학번 (SNO) 400 C413 400 E412 100 300 400 500 C312 300 400 400

14 (5) 개명 연산 (RENAME, ρ) 중간 결과 릴레이션에 이름을 지정하거나 애트리뷰트 이름을 변경할 때 사용 ρS(E)
ρS(B1,B2, … ,Bm )(E) 관계 대수식 E의 결과 릴레이션의 이름을 S로 지정하면서 애트리뷰트 이름을 각각 B1,B2, … ,Bm 으로 변경 ρ(B1,B2, … ,Bm )(E) 애트리뷰트 이름만 각각 B1,B2, … ,Bm 으로 변경

15 ▶ 5.1.3 기본(원시) 연산과 복합 연산 p106 기본(원시)연산 (primitive operations)
합집합, 차집합, 카티션 프로덕트, 프로젝트, 실렉트 복합연산 (composite operations) 교집합, 조인, 디비전 R∩S ＝ R­ (R­S) ＝ S ­ (S­R) ＝ (R∪S) ­ ( (R­S) ∪ (S­R) ) R AθB S ＝ AθB (R×S) R(Z,Y)÷S(Y)＝ R[Z] - ((R[Z]×S) - R)[Z] 연산력 보다는 표현력 증대

16 ▶ 5.1.4 관계 대수의 확장(1) p107 ⅰ. 세미조인 (Semijoin, )
R(X), S(Y)의 조인 애트리뷰트를 Z=X∩Y라 하면 R S ＝ R N(Z(S)) ＝  X(R NS) S와 자연조인을 할 수 있는 R의 투플 특징 R S ≠ S R R NS ＝ (R S) NS ＝ (S R) NR  처리해야 될 자료의 양이 다름

17  자연조인과 세미조인 p108 R S X∩Y(S) A B C B C D B C a1 b1 c1 b1 c1 d1 b1 c1
N R S N N R S A B C D A B C a1 b1 c1 d1 N a1 b1 c1 a1 b1 c1 d2 a2 b1 c1 a2 b1 c1 d1 a4 b2 c3 a2 b1 c1 d2 (세미조인) a4 b2 c3 d3 (자연조인)

18 ▶ 관계대수의 확장(2) ⅱ. 외부조인 (Outerjoin, +)
한 릴레이션에 있는 투플이 조인할 상대 릴레이션에 대응되는 투플이 없을 경우, 상대를 널(null) 투플로 만들어 결과 릴레이션에 포함 두 조인 릴레이션의 모든 투플들이 결과 릴레이션에 포함됨

19  자연조인과 외부조인 R S A B C B C D a1 b1 c1 b1 c1 d1 a2 b1 c1 b1 c1 d2 a3 b1
+ R S + N A B C D R S N a1 b1 c1 d1 A B C D a1 b1 c1 d2 a1 b1 c1 d1 a2 b1 c1 d1 a1 b1 c1 d2 a2 b1 c1 d2 a2 b1 c1 d1 a3 b1 c2 a2 b1 c1 d2 a4 b2 c3 d3 a4 b2 c3 d3 b3 c3 d3 (자연조인) (외부조인)

20 ▶ 관계대수의 확장(3) ⅲ. 외부 합집합 (Outer-union, ∪+)
합병가능하지 않은(부분적으로 합병 가능한) 두 릴레이션을 차수를 확장시켜 합집합으로 만듬

21  외부 합집합 R S A B C B C D a1 b1 c1 b1 c1 d1 a2 b1 c1 b1 c1 d2 a3 b1 c2
+ U A B C D a1 b1 c1 a2 b1 c1 a3 b1 c2 a4 b2 c3 b1 c1 d1 b1 c1 d2 b2 c2 d3

22 ▶ 관계대수의 확장(4) ⅳ. 집합 연산 AVG성적(등록) GROUP학년(학생) GROUP과목번호AVG성적(등록)
등록 릴레이션에 있는 성적 애트리뷰트 값들에 대해 평균값 계산 GROUP학년(학생) 학생 릴레이션의 투플들을 학년 값에 따라 그룹 짓게 함 GROUP과목번호AVG성적(등록) 과목별 그룹에 대한 평균성적 일반 형식 : GAFB(E) E : 관계 대수식 F : 집단 함수 ( SUM, AVG, MAX, MIN, COUNT) B : 집단 함수의 적용 대상 애트리뷰트 G : 그룹 함수 GROUP A : 그룹 함수가 적용할 애트리뷰트

23 ▶ 5.1.5 관계대수의 질의문 표현(1) p111 모든 학생의 이름과 학과를 보여라.
사용자의 요구를 관계 대수식으로 표현 모든 학생의 이름과 학과를 보여라. 이름,학과 (학생) 과목번호가 C413인 과목에 등록한 학생의 이름과 성적은 무엇인가? 이름,성적(과목번호='C413' (학생 N등록)) ‘파일처리' 과목을 가르치는 교수의 이름은? 담당교수(과목이름=‘파일처리'(과목))

24 ▶ 관계대수의 질의문 표현(2) 모든 과목에 수강하고 있는 학생의 학번, 이름은?
학번,이름((학번,과목번호(등록) ÷ 과목번호(과목)) N학생) 학번이 600, 이름이 '김현일', 학년이 4, 학과가 컴정학과인 학생을 삽입하라. 학생∪{<600, ‘윤현준', 4, ‘컴정학과’>} 과목 '데이터베이스'를 삭제하라. 과목 - (과목이름='데이터베이스'(과목))

25  5.2 관계 해석 (Relational Calculus) p112
predicate calculus에 기반 Predicate(서술어) : a function whose value is true or false 관계 자료 모델의 연산 표현 방법 비절차적(non-procedural) 원하는 정보가 무엇이라는 것만 선언 투플 관계 해석(tuple relational calculus) 도메인 관계 해석(domain relational calculus)

26 ▶ 5.2.1 투플 관계해석(1) p112 투플 해석식의 구성 요소
원하는 릴레이션을 투플해석식 (tuple calculus expression) 으로 명세 투플 해석식의 구성 요소 ⅰ. 투플변수(tuple variable) 또는 범위변수(range variable): t 범위식(range formula) : R(t) R : t의 범위 릴레이션(range relation) ⅱ. 한정(qualified) 애트리뷰트 : t.A 또는 t[A] 투플 변수 t가 나타내는 투플의 어떤 애트리뷰트 A의 값 – Students(S) S.SNO

27 ▶ 투플 관계해석(2) 투플 해석식의 구성 요소(con’t) ⅲ. 원자(atom)
R(t) t : 투플변수 R : t의 범위 릴레이션 t.Aθu.B t, u : 투플변수 A, B : t와 u에 대한 한정 애트리뷰트 θ : 비교 연산자(=, ≠, <, ≤, >,≥) t.Aθc A : 투플변수 t에 대한 한정 애트리뷰트 c : 상수 원자의 실행 결과는 반드시 참(True) 또는 거짓(False)

28 ▶ 투플 관계해석(3) 투플 해석식의 구성 요소(con’t) ⅳ. 정형식(WFF, Well-formed formula)
원자, 불리언 연산자(∧,∨,  ), 정량자 (∀,∃)가 다음 규칙에 따라 결합된 식 ① 모든 원자는 WFF ② F가 WFF이면, (F)와 F도 WFF ③ F와 G가 WFF이면, F∧G와 F∨G도 WFF ④ F가 WFF이고 t가 자유변수이면, ∀t(F)와 ∃t(F)도 WFF ⑤ 위의 규칙만을 반복 적용해서 만들어진 식은 WFF 정형식의 예 s.SNO = 100 c.CNO≠e.CNO s.SNO = e.SNO ∧ e.CNO ≠ c.CNO (∃e)(e.SNO = s.SNO ∧ e.CNO = 'C413')

29 tip 자유변수(free variable) 속박변수(bound variable) 정량자로 한정되지 않는 투플 변수
∀ : 전칭 정량자(Universal quantifier) – “for all” ∃ : 존재 정량자(Existential quantifier) – “there exists” 속박변수(bound variable) 정량자로 한정된 투플 변수 –∀t, ∃t

30 투플 해석식 형식 예 { t1.A1, t2.A2, …, tn.An｜F(t1, … tn, tn+1, …, tn+m) }
ti : 투플 변수 F(t1,…, tn, tn+1,…, tn+m): ti가 연관된 정형식 막대 (｜) 왼편에 나온 한정 애트리뷰트들은 목표리스트로서 막대(｜) 오른편에 명세된 조건을 만족하는 결과로 추출 됨 예 {s.SNAME｜STUDENT(s) } {s.SNAME｜STUDENT(s)∧s.DEPT=‘전산학’ }

31 ▶ 투플 해석식의 질의문 표현(1) 과목 C413에서 성적이 A인 모든 학생의 학번은?
{e.SNO｜ENROL(e) ∧ e.CNO='C413'∧ e.GRADE='A' } 과목 C413을 등록한 모든 학생의 이름과 학과는? { s.SNAME, s.DEPT｜STUDENT(s) ∧∃e(ENROL(e) ∧ s.SNO=e.SNO ∧ e.CNO='C413') }

32 ▶ 투플 해석식의 질의문 표현(2) 모든 과목에 등록한 학생의 이름을 전부 기술하라.
{ s.SNAME｜STUDENT(s) ∧ (∀c)(∃e)(COURSE(c) ∧ENROL(e)∧ e.SNO=s.SNO ∧ e.CNO=c.CNO) } 과목 C413에 등록하지 않은 학생의 이름 전부를 기술하라. {s.SNAME｜STUDENT(s) ∧ (∃e)(ENROL(e) ∧ s.SNO=e.SNO ∧ e.CNO=‘C413’) }

33 ▶ 5.2.3 도메인 관계해석 (1) p117 도메인 해석식의 구성요소
원하는 릴레이션을 도메인 해석식 (domain calculus expression) 으로 명세 도메인 해석식의 구성요소 ⅰ. 도메인 변수(domain variable) dSNO, dSNAME, … 범위식 STUDENT(dSNO, dSNAME, dDEPT, dYEAR)

34 ▶ 도메인 관계해석 (2) 도메인 해석식의 구성요소(con’t) ⅱ. 원자(atom)
① R(x1,x2,…,xn) xi : 도메인 변수 R : xi의 범위 릴레이션 <x1,x2,…xn>에 해당하는 값의 리스트는 릴레이션 R의 투플 ② xθ y x, y : 도메인 변수 θ: 비교 연산자(=, ≠, <, ≤, >,≥) ③ xθ c x : 도메인 변수 θ: 비교 연산자 c : x가 정의된 도메인 값의 상수 원자의 실행 결과는 반드시 참(True) 또는 거짓(False)

35 ▶ 도메인 관계해석 (3) 도메인 해석식의 구성요소(con’t) iii. 정형식(WFF, Well-formed formula)
원자, 불리언 연산자(∧,∨,  ), 정량자(∀,∃)가 다음 규칙에 따라 결합되어 표현된 식 ① 모든 원자는 WFF ② F가 WFF이면, (F)와  F도 WFF ③ F와 G가 WFF이면, F∧G와 F∨G도 WFF ④ F가 WFF이고 x가 자유변수이면, (∀x)(F)와 (∃x)(F)도 WFF ⑤ 위의 규칙만을 반복 적용해서 만들어진 식은 WFF

36 도메인 해석식 형식 { x1,x2,…,xn｜F(x1,…,xn,xn+1,…,xn+m) }
xi: 도메인변수 F(x1,…,xn,xn+1,…,xn+m) : xi에 대한 정형식 막대 (｜) 왼편에 나온 도메인 변수들은 목표리스트로서 막대 (｜) 오른편에 명세된 조건을 만족하는 도메인 값으로 만들어지는 투플 예 ① { dSNAME｜STUDENT(dSNO, dSNAME, dYEAR, dDEPT)} ② { dSNAME｜(∃dDEPT)(STUDENT(dSNO, dSNAME, dYEAR, dDEPT)∧ dDEPT=‘컴정학’) } ③ { dSNO, dDEPT｜STUDENT(dSNO, dSNAME, dYEAR, dDEPT)∧(∃ddSNO)(∃dGRADE)(ENROL(ddSNO, dCNO, dGRADE, dMIDTERM, dFINAL)∧ dSNO=ddSNO∧dGRADE='A‘) }

37 ▶ 5.2.4 도메인 해석식의 질의문 표현(1) 컴정학과 3,4 학년의 이름을 보여라. p177
{dSNAME｜(∃dYEAR)(∃dDEPT)(STUDENT(dSNO, dSNAME, dYEAR, dDEPT)∧ dYEAR ≥ 3∧ dDEPT=‘컴정학' ) } 과목 C413에서 성적이 A인 모든 학생의 학번은? { dSNO｜(∃dCNO)(∃dGRADE)(ENROL(dSNO, dCNO, dGRADE, dMIDTERM, dFINAL) ∧ dCNO= ‘C413’ ∧ dGRADE=‘A’) }

38 ▶ 도메인 해석식의 질의문 표현(2) 기말 성적이 90점 이상인 학생의 학번과 이름을 보여라.
{dSNO,dSNAME｜(STUDENT(dSNO,dSNAME,dYEAR,dDEPT) ∧ (∃dFINAL)(∃ddSNO) (ENROL(ddSNO, dCNO, dGRADE, dMIDTERM, dFINAL)∧dSNO=ddSNO ∧ dFINAL ≥ 90) } 과목 C324에 등록하지 않은 학생의 이름은? { dSNAME｜(∃dSNO)((STUDENT(dSNAME, dSNO, dYEAR, dDEPT) ∧ (∃ddSNO) (∃dCNO) (ENROL(ddSNO, dCNO, dGRADE, dMIDTERM, dFINAL) ∧ dSNO=ddSNO ∧ dCNO='C324')) }

39  5.3 QBE p120 QBE (Query By Example) 생성 : 1975, IBM 도메인 관계 해석 사용
그래픽 디스플레이 단말기 사용 이차원 구문(two-dimensional syntax) 언어 테이블 형태 : "Skeleton" 예(example)를 질의문 명세에 사용 예제 원소(example element) : 도메인 변수 STUDENT SNO SNAME YEAR DEPT _STX 3

40 ▶ 5.3.1 자료 검색(1) p121 단순 조건 검색 테이블 전체의 검색 컴정학과 4학년 학생의 학번과 이름을 검색하라
중복되는 것은 자동적으로 제거됨 'ALL'을 삽입하면 중복을 허용 테이블 전체의 검색 STUDENT SNO SNAME YEAR DEPT P. 4 컴퓨터 STUDENT SNO SNAME YEAR DEPT P.

41 ▶ 자료 검색(2) 복수 조건 검색 'OR' 조건 : 두 개의 행, 다른 예제 원소
기말성적이 85점 이상이거나 과목번호 ‘C413’에 등록한 학생의 학번을 검색하라 'AND' 조건 : 하나의 행, 같은 예제 원소 과목번호가 ‘C413’이고 기말성적이 85점 이상인 학생의 학번 ENROL SNO CNO FINAL MIDTERM 85 P._STX P._STY C413 ENROL SNO CNO FINAL MIDTERM P. C413 85

42 ▶ 자료 검색(3) 복수 조건 검색(con’t) 조건 상자(condition box)의 사용 ENROL SNO CNO
FINAL MIDTERM P. _EC _EF CONDITIONS _EC=C413 AND _EF 85

43 ▶ 자료 검색(4) 복수 테이블에서 검색 기말성적이 85점 이상이거나 과목 ‘C413’을 등록한 학생의 이름 ENROL SNO
CNO FINAL MIDTERM 85 _STX _STY C413 STUDENT SNO SNAME YEAR DEPT _STX _STY P.

44 ▶ 5.3.2 자료의 삽입 p123 단순 레코드의 삽입 투플 검색을 이용한 삽입
학번이 100이고 과목번호가 ‘C413’인 투플 삽입 Note : 기본키가 null이어서는 안됨 투플 검색을 이용한 삽입 4학년 학생의 학번을 학생테이블로부터 검색해서 SENIOR 테이블에 삽입하라. ENROL SNO CNO GRADE MIDTERM I. 100 C413 FINAL STUDENT SNO SNAME YEAR DEPT _STX 4 SENIOR I.

45 ▶ 5.3.3 자료의 삭제 p123 한 테이블에서의 삭제 복수 테이블에서의 레코드 삭제
학번이 100인 학생을 학생 테이블에서 삭제 복수 테이블에서의 레코드 삭제 기말성적이 60점 미만인 학생을 등록 테이블과 학생테이블에서 삭제 STUDENT SNO SNAME YEAR DEPT D. 100 ENROL SNO CNO GRADE MIDTERM FINAL _STX <60 D. STUDENT SNO SNAME YEAR DEPT D. _STX

46 ▶ 5.3.4 자료의 갱신 p124 필드값의 단순 갱신 산술식을 이용한 갱신 학번이 300인 학생의 학년을 2로 변경
과목 ‘C413’에 등록한 학생의 기말 성적(FINAL)에 5점을 가산 STUDENT SNO SNAME YEAR DEPT 300 U.2 U. 2 ENROL SNO CNO FINAL MIDTERM U. _G+5 _G C413