관계 해석(Relational Calculus)

Presentation on theme: "관계 해석(Relational Calculus)"— Presentation transcript:

1 관계 해석(Relational Calculus)
데이터베이스 (Databases) 관계 대수와 관계 해석 관계 해석(Relational Calculus) 문양세 강원대학교 IT대학 컴퓨터과학전공

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

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

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

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

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

7 {t.FNAME, t.LNAME | EMPLOYEE(t) and t.SALARY > 50000}
투플 관계 해석의 표현과 식 (1/2) 관계 대수와 관계 해석 투플 관계해석의 일반식 형태 {t1.A1, t2.A2, ..., tn.An | COND(t1, t2, ..., tn, tn+1, tn+2, ..., tn+m)} t1, t2, ..., tn, tn+1, tn+2, ..., tn+m은 투플 변수 각 Ai는 ti가 범위로 하는 릴레이션의 애트리뷰트 COND는 조건 또는 투플 관계 해석의 식(formula) 식(formula)은 다음과 같은 원자(atom)들로 이루어짐 Ri(ti)는 ti의 범위가 Ri임을 명시 (예: EMPLOYEE(t)) (ti.A op tj.B), op는 비교 연산자 (=, <, ≤, ...) (예: t1.FNAME = t1.SNAME) (ti.A op c) 또는 (c op tj.B), c는 상수 (예: t.SALARY > 50000) 각 원자는 특정한 투플들의 조합에 대해서 참(true) 또는 거짓(false)으로 계산되며, 계산된 결과값을 원자의 진리값이라 부름 {t.FNAME, t.LNAME | EMPLOYEE(t) and t.SALARY > 50000}

8 투플 관계 해석의 표현과 식 (2/2) 식(formula): and, or, not으로 연결된 원자들 모든 원자들은 식이다.
관계 대수와 관계 해석 식(formula): and, or, not으로 연결된 원자들 모든 원자들은 식이다. F1과 F2가 식이면 (F1 and F2), (F1 or F2), not(F1), not(F2)도 식이다. 예: EMPLOYEE(t) and t.SALARY > 50000

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

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

11 존재 정량자를 이용한 질의 예 (1/4) 질의 1: ‘Research’ 부서에서 일하는 모든 사원의 이름과 주소를 검색하라.
관계 대수와 관계 해석 질의 1: ‘Research’ 부서에서 일하는 모든 사원의 이름과 주소를 검색하라. Q1: {t.FNAME, 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과 유사한 목적으로 사용됨)

12 존재 정량자를 이용한 질의 예 (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, e.LNAME, s.FNAME, s.LNAME | EMPLOYEE(e) and EMPLOYEE(s) and e.SUPERSSN = s.SSN}

13 존재 정량자를 이용한 질의 예 (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))}

14 존재 정량자를 이용한 질의 예 (4/4) AND/OR/NOT 관계 대수의 UNION은 관계 해석의 or 연결자에 대응함
관계 대수와 관계 해석 AND/OR/NOT 관계 대수의 UNION은 관계 해석의 or 연결자에 대응함 INTERSECTION은 and 연결자에 대응함 not 연결자는 전체 정량자와 존재 정량자를 동등한 식으로 변환하는 데에 사용될 수 있음

15 전체 정량자와 존재 정량자 사이의 변환 -- 생략
관계 대수와 관계 해석 수학적 논리로부터 유래된 잘 알려진 변환법 (∀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))

16 전체 정량자의 사용 (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) and w.ESSN = e.SSN and x.PNUMBER = w.PNO)

17 전체 정량자의 사용 (2/3) -- 생략 Q3에서 사용한 규칙 설명
관계 대수와 관계 해석 Q3에서 사용한 규칙 설명 1. Q3의 결과로 구해지는 사원 e는 5 번 부서에서 관리하는 모든 프로젝트에 근무해야 한다. 이러한 투플을 찾기 위하여 관심 없는 모든 투플들을 전체 정량자로부터 제외시켜야 한다. 2. F’에서, not(PROJECT(x))는 관심있는 릴레이션 “PROJECT”에 없는 모든 투플들에 대해 x를 참으로 만든다. 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)

18 전체 정량자의 사용 (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))}

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

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

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

22 도메인 관계 해석 개념 (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)}

23 도메인 관계 해석 질의 예제 (1/2) 질의 1: ‘Research’ 부서에서 일하는 모든 사원들의 이름과 주소를 검색하라.
관계 대수와 관계 해석 질의 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’)))}

24 도메인 관계 해석 질의 예제 (2/2) -- 생략 질의 6: 부양가족이 없는 사원들의 이름을 찾아라.
관계 대수와 관계 해석 질의 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)))))}

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

26 Homework #3 관계 대수와 관계 해석