관계 해석

관계 해석 Relational calculus

Predicate calculus에 기반
Predicate = 실행 결과가 반드시 참(true)이나 거짓(false)인 함수

튜플 관계 해석

튜플 해석식의 구성요소

1. 투플 변수(tuple variable) 또는 범위 변수(range variable): t

• 범위식(range formula) : R(t)

  R은 t의 범위 릴레이션

2. 한정 애트리뷰트(qualified attribute) : t.A 또는 t[A]

• 튜플 변수 t가 나타내는 튜플의 애트리뷰트 A의 값

  student (s)
  s.Sno

3. 원자식(atomic formula)
   3-1) 범위식R(t)

   t : 튜플변수
   R: t의 범위 릴레이션

3-2) 조건식 t.A θ u.B

A, B : 애트리뷰트
θ : 비교 연산자(=, ≠, <, ≤, >,≥)
t.A = s.B 참 거짓 판별
원자식의 실행 결과는 반드시 참(True) 또는 거짓(False)

4. 정형식(WFF, well-formed formula)

• 원자식, 불리언 연산자(∧,∨, ¬ ), 정량자 자 (∀,∃)가 다음규칙에 따라 결합된 식

불리언 연산자(∧,∨, ¬)
∧ - AND
∨ - OR
¬ - NOT

∀ - 전체정량자
For every
∀x – 모든 x에 대해서 ~한 조건을 만족하면 참, 아니면 거짓
∃ - 존재정량자
For some
∃x – ~한 조건을 만족하는 것이 하나라도 있다면 참, 없으면 거짓

정형식의 규칙

1. 모든 원자식은 정형식
2. F가 정형식이면 (F)와¬F도 WFF
3. F와 G가 WFF이면, F∧G와 F∨G도 WFF
4. 투플 변수 t가 자유변수로 사용된 F(t)가 WFF이면, ∀t(F(t))와∃t(F(t))도 WFF
5. 위의 규칙만을 적용해서 만들어진 식은 WFF

예시

s.Sno = 100 원자식
c.Cno ≠ e.Cno 원자식
s.Sno = e.Sno ∧ e.Cno ≠ c.Cno 원자식간의 불리언 연산자
(∃e)(e.Sno = s.Sno ∧ e.Cno = 'C413') 원자식간의 불리언 연산자의 존재정량자

자유변수, 속박변수

자유변수 :

• 정량자(quantifier)로 한정되지 않는 투플 변수
  • t.Sno = 100 조건을 붙이지 않음
    이러한 튜플변수를 자유변수라 부름

속박변수 :

• 정량자(∀t ,∃t )로 한정된 투플 변수
  • (∀t)t.Sno = 100 과 같은 자유변수 수식에 정량자를 붙이면 정량자로 한정된 속박변수가 되어버림

튜플해석식의 형식

{ t1.A1, t2.A2, …, tn.An｜F(t1, … tn, tn+1, …, tn+m) } 조건제시법

• ti : 투플 변수
• F(t1,…, tn, tn+1,…, tn+m): ti가 연관된 정형식으로 조건을 명세
• 막대 (｜) 왼편에 명세된 한정 애트리뷰트들은
  목표 리스트 (target list)로서 막대(｜) 오른편에 명세된 조건을 만족하는 투플로부터 추출됨

예제

{s.Sname｜STUDENT(s) }
s는 student의 어떠한 변수를 가르킴. 이중에서 s.name을 꺼내라

{s.Sname｜STUDENT(s) ∧ s.Dept=‘컴퓨터’ }
S 변수가 학생 릴리이션에 어떠한 것을 가르킴. 이 때 dept가 컴퓨터인 경우 결과가 참임. s.Sname에 참인 결과값들이 들어감

{s.Sname, s.Dept｜STUDENT(s) ∧(∃e)(ENROL(e) ∧ s.Sno=e.Sno ∧ e.Grade='A')}

S 변수가 학생 릴리이션에 어떠한 것을 가르킴
어떠한 e에 대해서(Enroll을 가르키는 e 중에서) S.Sno와 e.Sno 를 만족하고, e.grade가 A이냐
두개 다 만족하면 ok 둘중 하나라도 만족하는 (정량자 존재) 경우를 가지고 옴
s.Sno=e.Sno ∧ e.Grade='A')} -> join 한 효과

튜플 관계 해석 예제

1. 과목 C413에서 성적이 A인 학생의 학번을 모두 검색하라

답) {e.Sno｜ENROL(e) ∧ e.Cno='C413'∧ e.Grade='A' }

풀이) 3개가 다 있는 릴레이션은 등록 릴레이션
e 가 등록을 가르키고 e.Cno='C413'∧ e.Grade='A' c413과 성적 a를 확인하고 있다면 학번을 결과로 보냄

2. 과목 C413을 등록한 학생의 이름과 학과를 모두 검색하라

답) { s.Sname, s.Dept｜STUDENT(s) ∧ ∃e(ENROL(e) ∧ s.Sno=e.Sno ∧ e.Cno='C413’) }

풀이) 이름학과정보가 있는 학생과 과목정보가 있는 등록을 join해서 검색해야함. 따라서 s.Sno=e.Sno ∧ e.Cno='C413’ 를 통해 조인하고 c413을 듣는 경우를 찾음. 맞으면 이름 학과 출력

학생과 등록을 join해서 검색해야함
따라서 ∧ s.Sno=e.Sno ∧ e.Cno='C413’) 를 통해 조인하고 c413을 듣는 경우를 찾음
맞으면 이름 학과 출력

3. 모든 과목에 등록한 학생의 이름을 전부 검색하라.

답) { s.Sname｜STUDENT(s) ∧ (∀c)(∃e)(COURSE(c) ∧ENROL(e)∧ e.Sno=s.Sno ∧ e.Cno=c.Cno) }

풀이) 학생이름 출력을 위해 학생 릴레이션 가르키는 s
과목을 가르키는 변수 c가 있음
등록을 가르키는 변수 e가 있음
c변수가 모든 변수에 만족해야함.
e.Sno=s.Sno ∧ e.Cno=c.Cno 해당 식을 통해서 조인을 한다. 모든 과목에 대해 등록에 하나라도 있고, 모든 결과가 조인에 있다면 반환한다.

4. 과목 ‘C413’에 등록하지 않은 학생의 이름을 전부 검색하라.

답) {s.Sname｜STUDENT(s) ∧ (┐∃e)(ENROL(e) ∧ s.Sno=e.Sno ∧ e.Cno=‘C413’) }

풀이) e에서 s.Sno=e.Sno이고 e.Cno=‘C413’ 인것이 하나라도 있으면 참을 반환하지만 앞에 not 이라 부정으로 돌림. 따라서 등록되지 않은 학생들을 전부 가지고 옴. 결과에 따라 이름 출력

도메인 해석

도메인 해석식의 구성요소

1. 도메인 변수(domain variable)

• 지정된 애트리뷰트 도메인의 한 원소만을 취하는 변수

ex) xSno, xSname, xDept, xYear, …

• 범위식
  • 도메인 변수 선언 식
  • STUDENT(xSno, xSname, xDept, xYear)

2. 원자식

① 범위 식, R(x1,x2,…,xn)
xi : 도메인 변수
R : xi의 범위 릴레이션
<x1,x2,…,xn>에 대응하는 값의 리스트는 릴레이션 R의 투플

② 조건 식, x θ y
x, y : 도메인 변수
θ: 비교 연산자(=, ≠, <, ≤, >,≥)

③ 조건 식, x θ c
x : 도메인 변수
c : x가 정의된 도메인 값의 상수
 원자 식의 실행 결과는 반드시 참(True) 또는 거짓(False)

3. 정형식(WFF, Well-formed formula)

• 원자식, 불리언 연산자(∧,∨, ¬ ), 정량자 자 (∀,∃)가 다음규칙에 따라 결합된 식

불리언 연산자(∧,∨, ¬)
∧ - AND
∨ - OR
¬ - NOT

∀ - 전체정량자
For every
∀x – 모든 x에 대해서 ~한 조건을 만족하면 참, 아니면 거짓
∃ - 존재정량자
For some
∃x – ~한 조건을 만족하는 것이 하나라도 있다면 참, 없으면 거짓

정형식의 규칙

상동

도메인 해석식의 형식

{ x1,x2,…,xn｜F(x1,…,xn,xn+1,…,xn+m) }
xi: 도메인변수
F(x1,…,xn,xn+1,…,xn+m) : xi가 관련된 정형식
막대 (｜) 왼편에 명세된 n 도메인 변수들은 목표 리스트로서막대 (｜) 오른편에 명세된 조건(정형식)을 만족하는 도메인값으로 만들어지는 투플을 표현

도메인 관계 해석 예제

1. 컴퓨터학과 3,4 학년(Year)의 이름(Sname)을 검색하라.

답 ) {xSname｜(∃xYear)(∃xDept) (STUDENT(xSno, xSname, xYear, xDept) ∧ xYear ≥ 3∧ xDept='컴퓨터' ) }

해석) 학생 릴레이션에서 각각의 4개가 도메인 변수 (xSno, xSname, xYear, xDept)를 선언, xYear가 3이상이고 xDept가 컴퓨터인것을 찾는다. 그런것이 한 개라도 있다면 (∃) 이름 출력

2. 과목번호(Cno) C413에서 성적(Grade)이 A인 학생의 학번(Sno)을 모두 검색하라

답) { xSno｜(∃xCno)(∃xGrade) (ENROL(xSno, xCno, xGrade, xMidterm, xFinal) ∧ xCno= ‘C413’ ∧ xGrade=‘A’) }

풀이) 등록 릴레이션의 각 도메인 변수에서 과목 c413과 성적 a가 둘다 존재하면 (and 연산) 학번 출력한다

3. 기말 성적(Final)이 90점 이상인 학생의 학번(Sno)과 이름(Sname)을 검색하라.

답) {xSno,xSname｜(STUDENT(xSno,xSname,xYear,xDept) ∧ (∃xFinal)(∃xxSno) (ENROL(xxSno, xCno, xGrade, xMidterm, xFinal)∧xSno=xxSno ∧ xFinal ≥ 90) }

Student 릴레이션의 각각의 도메인 지칭. Enrol의 각각의 도메인 지칭. 그 후 두 릴레이션간의 학번이 같으면서(동일인물) 기말성적이 90점 이상인 조건에 맞는 경우 이름, 학번

4. 과목번호(Cno) C324에 등록하지 않은 학생의 이름(Sname)을 검색하라.

답) { xSname｜(∃xSno) ((STUDENT(xSname, xSno, xYear, xDept) ∧ (┐∃xxSno) (∃xCno) (ENROL(xxSno, xCno, xGrade, xMidterm, xFinal) ∧ xSno=xxSno ∧ xCno='C324')) }

Student 릴레이션의 각각의 도메인 지칭. Enrol의 각각의 도메인 지칭. 그 후 두 릴레이션의 학생넘버가 같은 경우 중, 과목번호가 C324인 경우 반환을 하나, not이 붙어서 반전해서 없는 경우를 반환함