Microsoft PowerPoint 관계 대수 및 관계 해석(Part 2)

Size: px

Start display at page:

Download "Microsoft PowerPoint 관계 대수 및 관계 해석(Part 2)"

현우 왕
6 years ago
Views:

1 데이터베이스 (Database) (Part 2) 문양세강원대학교 IT특성화대학컴퓨터과학전공

2 관계대수및관계해석강의요약 단항관계연산 : 실렉트와프로젝트 집합이론과관계대수연산 이항관계연산 : 조인과디비전연산 추가적인관계연산 관계대수질의의예 투플관계해석 도메인관계해석 Page 2

3 관계대수질의의예 (1/7) 질의 1 : Research 부서에서일하는모든사원의이름과주소를검색하라. Page 3

4 관계대수질의의예 (2/7) 질의 2 : Stafford 에위치한모든프로젝트에대하여프로젝트번호와관리부서 번호, 부서관리자의성, 주소, 생년월일을나열하라. Page 4

5 관계대수질의의예 (3/7) 질의 3 : 번호 5 인부서가관리하는모든프로젝트에서근무하는사원들의이름을찾아라. Page 5

6 관계대수질의의예 (4/7) 질의 4: 성이 Smith 인사원이직원 (worker) 이나관리자 (manager) 로근무하는부서가관리하는프로젝트의프로젝트번호들을나열하라. Page 6

7 관계대수질의의예 (5/7) 질의 5: 두명이상의부양가족을가진사원의이름을나열하라. ( 집단함수 COUNT 를사용하여질의를표현한다.) Page 7

8 관계대수질의의예 (6/7) 질의 6: 부양가족이없는사원의이름을나열하라. Page 8

9 관계대수질의의예 (7/7) 질의 7: 부양가족이적어도한명이상인관리자 (manager) 들의이름을나열하라. Page 9

10 관계대수및관계해석강의요약 단항관계연산 : 실렉트와프로젝트 집합이론과관계대수연산 이항관계연산 : 조인과디비전연산 추가적인관계연산 관계대수질의의예 투플관계해석 (tuple relational calculus) 도메인관계해석 Page 10

11 관계해석개요 (1/2) 관계해석 (Relational Calculus) 어떻게검색할것인가 보다 무엇을검색할것인가 만을기술하는선언적표현법을사 용하는비절차적질의어 SQL 을포함한많은상업용관계언어들이관계해석에기반을두고있음 투플관계해석 (tuple relational calculus) 와도메인관계해석 (domain relational calculus) 으로구분됨 관계대수와의차이점 관계해석은하나의선언적 (declarative) 해석식으로검색질의를명시하며, 비절차적인 언어임 관계대수에서는연산들을순차적으로사용하므로절차적인성질을가짐 두언어의표현력 (expressive power) 은동등함 Page 11

12 관계해석개요 (2/2) 관계적완전성 (relationally completeness) 어떤관계질의어 L 이있을때, L 이관계해석 ( 또는관계대수 ) 으로표현가능한어떤질의 도표현할수있으면 L 은 관계적으로완전 (relationally complete) 하다 라고한다. 대부분의관계질의어들은관계적으로완전 ( 해야 ) 하며, 집단함수 (aggregate functions), 그룹화 (grouping), 순서화 (ordering) 등의연산들을제공하므로관계해석보다표현력이 강해진다. Page 12

13 투플변수와범위릴레이션 (1/2) 투플변수 릴레이션의투플들을범위 (range) 로가지는변수이다. 예제 : 봉급이 $50,000 를넘는모든사원을검색하라. {t EMPLOYEE(t) () and t.salary > 50000} 여기서, EMPLOYEE(t) 는투플변수 t 가릴레이션 EMPLOYEE 의투플들을범위로함을 나타낸다. 투플 t 에대하여 t.salary > 을만족하는투플만이검색된다. 투플 t 의모든애트리뷰트값들이리턴된다. Page 13

14 투플변수와범위릴레이션 (2/2) 프로젝션의표현 t 의일부애트리뷰트만을검색하려면다음과같이작성한다. {t.fname, t.lname EMPLOYEE(t) and t.salary > 50000} 이는다음 SQL 질의와동일한의미를가진다. ( 표현력이동일하다 ) SELECT FROM T.FNAME, T.LNAME EMPLOYEE T WHERE T.SALARY > 50000; Page 14

15 투플관계해석의표현과식 (1/2) 투플관계해석의일반식형태 {t 1.A 1, t 2.A 2,..., t n.a n COND(t 1, t 2,..., t n, t n+1, t n+2,..., t n+m )} t 1, t 2,..., t n, t n+1, t n+2,..., t n+m 은투플변수 각 A i 는 t i 가범위로하는릴레이션의애트리뷰트 COND 는조건또는투플관계해석의식 (formula) 식 (formula) 은다음과같은원자 (atom) 들로이루어짐 R i (t i ) 는 t i 의범위가 R i 임을명시 ( 예 : EMPLOYEE(t)) (t i.a op t j.b), op 는비교연산자 (=, <,,...) ( 예 : t 1.FNAME = t 1.SNAME) (t i.a op c) 또는 (c op t j.b), c 는상수 ( 예 : t.salary > 50000) 각원자는특정한투플들의조합에대해서참 (true) 또는거짓 (false) 으로 계산되며, 계산된결과값을원자의진리값이라부름 Page 15

16 투플관계해석의표현과식 (2/2) 식 (formula): and, or, not 으로연결된원자들 모든원자들은식이다. F 1 과 F 2 가식이면 (F 1 and F 2 ), (F 1 or F 2 ), not(f 1 ), not(f 2 ) 도식이다. 예 : EMPLOYEE(t) and t.salary > Page 16

존재정량자와전체정량자 정량자 (quantifiers) 가식에사용될수있음 전체정량자 (universal

) (their exists 라읽음 ) 자유 (free) 투플변수와속박 (bound) 투플변수 ( 간단히설명해서 )

정형적정의는교재 p. 186 참조 ( 강의에서는생략 ) 예제 : F1: d.

17 존재정량자와전체정량자 정량자 (quantifiers) 가식에사용될수있음 전체정량자 (universal quantifier) ( ) (for all 이라읽음 ) 존재정량자 (existential quantifier) ( ) (their exists 라읽음 ) 자유 (free) 투플변수와속박 (bound) 투플변수 ( 간단히설명해서 ) 투플변수 t 가 ( t) 나 ( t) 절에나타나면, t 는속박되는것을의미하며, 그렇지않으면자유롭다는것을의미한다. 정형적정의는교재 p. 186 참조 ( 강의에서는생략 ) 예제 : F1: d.dname = Research F2: ( t)(d.dnumber = t.dno) 변수 d 는 F1 과 F2 모두에서자유롭다 변수 t 는 F2 에서 정량자에속박된다 Page 17

18 정량자가포함된식의진리값계산 F 가식이면, ( t)(f) 도식이다. F 내의 t 의자유어커런스들에할당된 적어도하나의투플 에대해서 F 가참으로 계산되면, 식 ( t)(f) 는참이고, 그렇지않으면거짓이다. F 가식이면, ( t)(f) 도식이다. F 내의 t 의자유어커런스들에할당된 모든투플 에대해서 F 가참으로계산되면 식 ( t)(f) 는참이고, 그렇지않으면거짓이다. F 가참이되게하는어떤투플 t 가 존재 하면 ( t)(f) 가참이므로, 를존재정량 자라부른다. 모든 투플들이 F 를참이되도록해야 ( t)(f) 가참이므로, 를전체정량자라부 른다. Page 18

19 존재정량자를이용한질의예 (1/4) 질의 1: Research 부서에서일하는모든사원의이름과주소를검색하라. Q1: {t.fname, tlname t.lname, t.address EMPLOYEE(t) and ( d) (DEPARTMENT(d) and d.dname = Research and d.dnumber = t.dno)} 관계해석식에서자유투플변수들만막대 ( ) 왼쪽에나타낸다. 막대 ( ) 는 such that 이라읽는다 EMPLOYEE(t), DEPARTMENT(d) 는 t 와 d 의범위릴레이션을명시한다. d.dname= Research 는선택조건 (selection condition) 임 ( 관계대수의 SELECT 에해당함 ) d.dnumber = t.dno 는조인조건 (join condition) 임 ( 관계대수의 EQUI JOIN 과유사한목적으로사용됨 ) Page 19

20 존재정량자를이용한질의예 (2/4) 질의 2: Stafford 에위치한모든프로젝트에대하여, 프로젝트번호, 관리부서의 번호와부서관리자의성, 생일, 그리고주소를나열하라. Q2: {p.pnumber, p.dnum, m.lname, m.bdate, m.address PROJECT(p) and EMPLOYEE(m) and p.plocation = Staffordʹ and (( d)(department(d) and p.dnum = d.dnumber and d.mgrssn = m.ssn))} 질의 8: 각사원에대하여, 그사원의이름과성, 그리고직속상사의이름과성을검 색하라. Q8: {e.fname, elname e.lname, sfname s.fname, slname s.lname EMPLOYEE(e) and EMPLOYEE(s) and e.superssn = s.ssn} Page 20

21 존재정량자를이용한질의예 (3/4) 질의 3 : 부서 5 에의해관리되는프로젝트에참여하는모든사원의이름을찾아라. Q3ʹ: {e.lname, e.fname EMPLOYEE(e) and (( x) ( w) (PROJECT(x) and WORKS_ON(w) and x.dnum = 5 and w.essn = e.ssn and x.pnumber = w.pno))} Page 21

22 존재정량자를이용한질의예 (4/4) 질의 4: Smith 라는성을가진사원이직원이나관리자로서관여된프로젝트들을 나열하라. Q4: {p.pname PROJECT(p) and ((( e)( w)(employee(e) ( ) and WORKS_ON(w) and w.pno = p.pnumber and e.lname = Smith and e.ssn = w.essn)) or (( m)( d)(employee(m) and DEPARTMENT(d) and p.dnum = d.dnumber and d.mgrssn = m.ssn and mlname= m.lname Smith )))} AND/OR/NOT 관계대수의 UNION 은관계해석의 or 연결자에대응함 INTERSECTION 은 and 연결자에대응함 not 연결자는전체정량자와존재정량자를동등한식으로변환하는데에사용될수있음 Page 22

23 전체정량자와존재정량자사이의변환 수학적논리로부터유래된잘알려진변환법 ( x) (P(x)) (not x) (not(p(x))) ( x) (P(x)) not( x) (not(p(x))) ( x) (P(x) and Q(x)) (not x) (not(p(x)) or not(q(x))) ( x) (P(x) or Q(x)) (not x) (not(p(x)) and not(q(x))) ( x) (P(x) or Q(x)) not( x) (not(p(x)) and not(q(x))) ( x) (P(x) and Q(x)) not( x) (not(p(x)) or not(q(x))) 다음식들이성립함 ( 는내포 (implies) 를나타냄 ) ( x) (P(x)) ( x) (P(x)) (not x) (P(x)) not( x) (P(x)) 그러나, 다음은성립하지않음 not( x) (P(x)) (not x) (P(x)) Page 23

24 전체정량자의사용 (1/3) 전체정량자사용시, 식이의미를갖도록하기위하여몇가지규칙을따라야함 다음질의 3 을통해규칙을살펴보자 질의 3: 5 번부서에의해관리되는모든프로젝트들에참여하는사원들의 이름을찾아라. Q3: {e.lname, e.fname EMPLOYEE(e) and (( x) (not (PROJECT(x)) or (not (x.dnum = 5) or (( w) (WORKS_ON(w) and w.essn = e.ssn and x.pnumber = w.pno)))))} Q3의기본구성요소들 Q3: {e.lname, e.fname EMPLOYEE(e) and F } F = ( x) (not(project(x)) or F1) F1 = (not(x.dnum = 5) or F2) F2 = ( w) (WORKS_ON(w) ON(w) and w.essn = e.ssn and x.pnumber = w.pno) Page 24

25 전체정량자의사용 (2/3) Q3 에서사용한규칙설명 1. Q3 의결과로구해지는사원 e 는 5 번부서에서관리하는모든프로젝트에근무해야한다. 이러한투플을찾기위하여관심없는모든투플들을전체정량자로부터제외시켜야한다. 2. F 에서, not(project(x)) 는관심있는릴레이션 PROJECT 에없는모든투플들에대해 x 에서 ( J ( )) 는관심있는릴레이션 J 에없는든투플들에대해 를참으로만든다. 3. F1 에서, not(x.dnum = 5) 는관심없는 PROJECT 투플들, 즉 DNUM 이 5 가아닌투플들 에대해 x 를참으로만든다. 4. F2 는나머지에대해만족되어야할조건, 즉 5 번부서에의해관리되는모든 PROJECT 투 플들 을명시한다. Q3: {e.lname, e.fname EMPLOYEE(e) and F } F = ( x) (not(project(x)) or F1) F1 = (not(x.dnum = 5) or F2) F2 = ( w) (WORKS_ON(w) and w.essn = e.ssn and x.pnumber = w.pno) Page 25

26 전체정량자의사용 (3/3) 추가적인예제들 질의 6: 부양가족이없는사원들의이름을찾아라. Q6: {e.fname, e.lname EMPLOYEE(e) and (not( d) (DEPENDENT(d) and e.ssn = d.essn))} 전체정량자를사용하기위하여 Q6 를 Q6 으로변환하면 Q6 : {e.fname, e.lname EMPLOYEE(e) and (( d) (not(dependent(d)) or not(e.ssn = d.essn)))} 질의 7: 부양가족이적어도한명있는관리자들의이름을나열하라. Q7: {e.fname, e.lname EMPLOYEE(e) and (( d) ( p) (DEPARTMENT(d) and DEPENDENT(p) and e.ssn = e.mgrssn and p.essn = e.ssn))} Page 26

27 관계해석에서안전식 (Safe Expression) 결과로서유한 (finite) 개투플들을생성하는것이보장된식 불안전식은무한 (infinite) 개투플들을생성할수있고, 투플들의타입이 서로다를수있음 불안전한식의예제 : {t not(employee(t))} 가능한모든투플들중에서 EMPLOYEE 가아닌모든투플들을생성함 이러한투플들은무한개투플들로구성되며, 투플의타입이상이할수있음 따라서위의식은불안전한식이됨 Page 27

28 관계대수및관계해석강의요약 단항관계연산 : 실렉트와프로젝트 집합이론과관계대수연산 이항관계연산 : 조인과디비전연산 추가적인관계연산 관계대수질의의예 투플관계해석 도메인관계해석 Page 28

29 도메인관계해석개념 (1/2) 투플변수대신도메인변수 (domain variables) 를사용하는관계해석 도메인변수는한애트리뷰트의도메인을범위로가짐 투플관계해석에서는? 투플의도메인을범위로가졌음 투플관계해석에서는투플이중심인반면, 도메인관계해석에서는 애트리뷰트가중심임 차수가 n 인릴레이션의경우 n 개의도메인변수를사용함 Page 29

30 도메인관계해석개념 (2/2) 예제 : 질의 0: 이름이 John B. Smith 인사원의생일과주소를검색하라. Q0: {uv ( q) ( r) ( s) (EMPLOYEE(qrstuvwxyz) and q = John and r = B and s = Smith )} EMPLOYEE 의각애트리뷰트들을위한열개의도메인변수들 : qrstuvwxyz BDATE 를위한변수 u, ADDRESS 를위한 v 조건에참여하는변수들 q(fname), r(minit), s(lname) 조건에참여하는변수들 (q, r, s) 만존재정량자로속박함 또다른표기법 (QBE 에서사용 ): Q0 : {uv EMPLOYEE( John, B, Smith,t,u,v,w,x,y,z)} Page 30

31 도메인관계해석질의예제 (1/2) 질의 1: Research 부서에서일하는모든사원들의이름과주소를검색하라. Q1: {qsv ( z) (EMPLOYEE(qrstuvwxyz) and ( l) ( m) (DEPARTMENT(lmno) and l = Research and m = z))} (m = z) 는조인조건 (l = Research ) 는선택조건 질의 2: Stafford 에위치한모든프로젝트에대해서프로젝트번호와부서번호, 그리고부서관리자의성, 생일, 주소를나열하라. Q2: {iksuv ( j) (PROJECT(hijk) and ( t) (EMPLOYEE(qrstuvwxyz) and ( m) ( n) (DEPARTMENT(lmno) and k = m and n = t and j = Stafford )))} Page 31

32 도메인관계해석질의예제 (2/2) 질의 6: 부양가족이없는사원들의이름을찾아라. Q6: {qs ( t) (EMPLOYEE(qrstuvwxyz) and (not ( l) (DEPENDENT(lmno) and t = l)))} 질의 7: 적어도한명의부양가족이있는관리자들의이름을나열하라. Q7: {sq ( t) (EMPLOYEE(qrstuvwxyz) and (( j) (DEPARTMENT(hijk) ( and (( l) (DEPENDENT(lmno) and t = j and l = t)))))} Page 32

33 요약 기본관계대수연산 선택 (SELECT), 프로젝트 (PROJECT), 합집합 (UNION), 차집합 (SET DIFFERNECE), 카티션프로덕트 (Cartesion product) 추가적인관계연산 집계함수, 그루핑연산, 외부조인연산 관계대수질의의예 투플 관계해석 투플변수와정량자 ( 존재정량자와전체정량자 ) 안전식 도메인관계해석 Page 33

Microsoft PowerPoint - 6 [호환 모드]

Microsoft PowerPoint - 6 [호환 모드] 제 6 장 관계대수와관계해석 Fundamentals of Database Systems R. A. Elmasri and S. B. Navathe 내용 6.1 단항관계연산 : 실렉트와프로젝트 6.2 집합이론과관계대수연산 6.3 이항관계연산 : 조인과디비전연산 6.4 추가적인관계연산 6.5 관계대수질의의예 6.6 투플관계해석 6.7 도메인관계해석 2 6.1 단항관계연산