관계 해석(Relational Calculus)

Slides:



Advertisements
Similar presentations
Ⅰ. 연산자 Ⅱ. 제어 구조. 연산자 : 할당 연산자 - 사용자가 정의한 변수에 임의의 값을 저장하는 기능 strvar = strVar1+ “ Hello ”
Advertisements

1. 2 차원 배열  배열은 동일한 데이터 유형으로 여러 개의 변수를 사용할 경우 같은 이 름으로 지정하여 간편하게 사용할 수 있도록 하는 것으로서 앞에서 1 차원 배열을 공부하였습니다.  2 차원 배열은 바둑판을 생각하면 되며, 1 차원 배열에서 사용하는 첨자를 2.
2장. 프로그램의 기본 구성. 2장. 프로그램의 기본 구성 2-1"Hello, World!" 들여다 보기 /* Hello.c */ #include int main(void) { printf("Hello, World! \n"); return 0;
(생각열기) 멘델레예프의 주기율표와 모즐리의 주기율표 에서 원소를 나열하는 기준은? ( )
4.2 SQL 개요 SQL 개요 SQL은 현재 DBMS 시장에서 관계 DBMS가 압도적인 우위를 차지하는데 중요한 요인의 하나
Chapter 7. 조건문.
8장 서브 쿼리.
관계 데이타 모델 (Relational Data Model)
MySQL 및 Workbench 설치 데이터 베이스.
6 장. ER-관계 사상에 의한 관계 데이터베이스 설계
제 6 장 관계 대수와 관계 해석 Fundamentals of Database Systems
10장 함수.
6장 그룹 함수.
07 그룹 함수 그룹 함수의 개념 그룹 함수의 종류 데이터 그룹 생성 HAVING 절.
3.2 SQL Server 설치 및 수행(계속) 시스템 데이터베이스 master
컴퓨터 프로그래밍 기초 #02 : printf(), scanf()
Error Detection and Correction
4장. 관계 대수와 SQL SQL 관계 데이터 모델에서 지원되는 두 가지 정형적인 언어 어느것을 기본으로 만들것인가
관계 대수.
5장. 관계대수와 관계 해석 관계 대수 릴레이션들을 다루는 연산들의 집합 검색 요구(질의)를 기술하는 데에 사용
23장. 구조체와 사용자 정의 자료형 2.
1. 관계 데이터 언어 관계 대수 1) 관계대수 정의 ① 원하는 정보와 그 정보를 어떻게 유도하는가를 기술하는 절차적 인 방법 ② 주어진 관계로 부터 원하는 관계를 얻기 위해 연산자와 연산 규칙을 제공하는 언어 ③ 릴레이션 조작을 위한 연산의 집합으로 피연산자와 결과가.
5. 관계대수와 관계해석 ( Relational Operations: 관계연산)- 9장

2주차: 변수, 수식, Control Flow.
Tail-recursive Function, High-order Function
행렬 기본 개념 행렬의 연산 여러가지 행렬 행렬식 역행렬 연립 일차 방정식 부울행렬.
관계 해석(Relational Calculus)
Ⅲ. 이 차 방 정 식 1. 이차방정식과 그 풀이 2. 근 의 공 식.
1.4 중첩된 한정기호 (Nested Quantifiers) 이산수학 (Discrete Mathematics)
환경 설정 예제 데이터베이스 생성 - 그림 3.34의 SQL Server 관리 스튜디오 창의 왼쪽 영역의 데이터베
JA A V W. 03.
어서와 C언어는 처음이지 제14장.
술어명제의 해석  ∧ ∨ → ↔  =.
13. 포인터와 배열! 함께 이해하기 IT응용시스템공학과 김 형 진 교수.
자료구조: CHAP 7 트리 –review 순천향대학교 컴퓨터공학과 하 상 호.
27장. 모듈화 프로그래밍.
ER-관계 사상에 의한 관계 데이터베이스 설계
데이터베이스 (Database) SQL-99: 스키마 정의, 기본 제약조건, 질의어 문양세 강원대학교 IT대학 컴퓨터과학전공.
Term Projects 다음에 주어진 2개중에서 한 개를 선택하여 문제를 해결하시오. 기한: 중간 보고서: 5/30 (5)
연산자 (Operator).
관계 해석(Relational Calculus)
컴퓨터 프로그래밍 기초 - 10th : 포인터 및 구조체 -
2장. 변수와 타입.
05. Relational DBMS 명지대학교 ICT 융합대학 김정호.
이산수학(Discrete Mathematics)  명제의 동치 (Propositional Equivalence)
컴퓨터 프로그래밍 기초 - 5th : 조건문(if, else if, else, switch-case) -
3강. 컴퓨터와의 기본적인 소통수단 - I 연산자란? 컴퓨터와 소통하기 위한 다양한 방법들
문성우 SQL 실습 Part Ⅰ 문성우.
에어 PHP 입문.
2장 PHP 기초 PHP의 시작과 끝을 이해한다. 주석문에 대하여 이해한다. echo 문을 이용하여 화면에 출력하
제 8 장 ER-관계 사상에 의한 관계 데이타베이스 설계
Part 2 개념적 데이터 모델 Copyright © 2006 by Ehan Publishing Co. All rights reserved.
쉽게 배우는 알고리즘 2장. 점화식과 점근적 복잡도 분석
Chapter 10 데이터 검색1.
11장 배열 1. 배열이란? 1.1 배열의 개요 1.2 배열의 선언과 사용.
ER-관계 사상에 의한 관계데이터베이스 설계 충북대학교 구조시스템공학과 시스템공학연구실
제 22 강 논리식 및 논리 값 shcho.pe.kr.
Numerical Analysis Programming using NRs
이산수학(Discrete Mathematics)  술어와 한정기호 (Predicates and Quantifiers)
07. DB 설계 명지대학교 ICT 융합대학 김정호.
Chapter 2: Intro to Relational Model
9장. spss statistics 20의 데이터 변수계산
ER-관계 사상에 의한 관계 데이터베이스 설계
 6장. SQL 쿼리.
                              데이터베이스 설계 및 실습 #6 - SQL 실습 한국외국어대학교 DaPS 연구실                              
(Permutations and Combinations)
13. 포인터와 배열! 함께 이해하기.
7 생성자 함수.
6 객체.
Presentation transcript:

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

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

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

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

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

투플 변수와 범위 릴레이션 (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;

{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}

투플 관계 해석의 표현과 식 (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

존재 정량자와 전체 정량자 정량자(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에서 ∃정량자에 속박된다

정량자가 포함된 식의 진리값 계산 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)가 참이므로, ∀를 전체 정량자라 부른다.

존재 정량자를 이용한 질의 예 (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과 유사한 목적으로 사용됨)

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

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

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

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

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

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

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

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

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

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

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

도메인 관계 해석 질의 예제 (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’)))}

도메인 관계 해석 질의 예제 (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)))))}

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

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