관계 대수와 관계 해석

제 6 장

관계 대수와 관계 해석

Fundamentals of Database Systems

R. A. Elmasri and S. B. Navathe

6.1 단항 관계 연산: 실렉트와 프로젝트 6.2 집합 이론과 관계 대수 연산

6.3 이항 관계 연산

내 용

6.3 이항 관계 연산

6.4 추가적인 관계 연산 6.5 관계 대수 질의 요약 6.6 튜플 관계 해석

6.7 도메인 관계 해석

관계 대수란

– 릴레이션들을 다루는 연산들

– 검색 요구(질의)를 기술하는데 사용함 – 관계 대수 연산의 결과도 릴레이션 임

이 절의 구성

6.1 기본 관계대수

이 절의 구성

6.1.1 실렉트(SELECT) 연산 6.1.2 프로젝트(PROJECT) 연산

6.1.3 연산의 순서와 이름 변경 연산

• SELECT 연산 (σ로 표기)

– 릴레이션 R에서 어떤 선택조건 c를 만족하는 투플들을 선택함 – 연산 형식: σ _c (R)

– 조건 c는 R의 애트리뷰트들에 대한 임의의 불리언 식임 – 결과 릴레이션은 R과 동일한 애트리뷰트들을 가짐

6.1.1 실렉트(SELECT) 연산

– 결과 릴레이션은 R과 동일한 애트리뷰트들을 가짐

– 결과 릴레이션은 r(R)의 투플 중 애트리뷰트 값들이 조건 c를 만족하는 투플들로 구성됨

– 예제:

σ _DNO=4 (EMPLOYEE)

σ SALARY>30000 (EMPLOYEE)

σ (DNO=4 AND SALARY>25000) OR DNO=5 (EMPLOYEE)

SQL과의 비교

6.1.1 실렉트(SELECT) 연산

σ

_DNO=4

σ

SALARY>30000

σ

(DNO=4 AND SALARY>25000) OR DNO=5

Where Dno = 4;

Select *

From EMPLOYEE Where Salary > 30000;

From EMPLOYEE

Where (Dno = 4 And Salary > 25000 ) OR Dno = 5 ;

PROJECT 연산 (Π로 표기)

– 릴레이션 R에서 애트리뷰트 리스트 L에 명시된 애트리뷰트들만 선택함 – 연산 형식: Π

_L

– 결과 릴레이션은 L에 명시된 R의 애트리뷰트들만 가짐 – 예제: Π (EMPLOYEE)

6.1.2 프로젝트(PROJECT) 연산

– 예제: Π

FNAME,LNAME,SALARY

– PROJECT 연산은 결과 릴레이션이 수학적 집합이므로 중복된 투플들을 제거함

– 예제: Π

SEX,SALARY

봉급이 1,000,000원인 남자 사원들이 여러명 이더라도

결과 릴레이션에는 단지 하나의 <M, 1000000> 투플만이 포함되며, 중복된 나머지는 제거됨

다수의 연산을 결합=> 관계 대수식(질의)을 형성 가능

예제: 부서 4에서 일하는 사원들의 이름과 봉급을 검색하라.

Π FNAME,LNAME,SALARY (σ _DNO=4 (EMPLOYEE))

중간 단계의 임시 릴레이션에 이름을 부여할 수도 있음

6.1.3 연산의 순서와 이름 변경 연산

DEPT4_EMPS ←σ _DNO=4 (EMPLOYEE) R ←Π FNAME,LNAME,SALARY (DEPT4_EMPS)

결과 릴레이션의 속성 이름은 재명명할 수 있음

DEPT4_EMPS ←σ

_DNO=4

R(FIRSTNAME, LASTNAME, SALARY) ← Π

FNAME,LNAME,SALARY

6.2.1 합집합, 교집합, 차집합 연산

– 합집합: R ₁ ∪ R ₂ – 교집합: R ₁ ∩ R ₂ – 차집합: R ₁ – R ₂

6.2 집합 이론과 관계 대수 연산

– 차집합: R ₁ – R ₂

6.2.2 카테션 곱 (또는, 크로스 프로덕트) 연산

– 카티션 곱: R ₁ × R ₂

• 연산 ∪,∩,－에서의 호환성

–

피연산자 릴레이션 R ₁ (A ₁ ,A ₂ ,...,A _n )과 R ₂ (B ₁ ,B ₂ ,...,B _n )는

• 애트리뷰트들의 갯수가 동일하고,

• 대응되는 애트리뷰트들의 도메인이 호환성을 가져야 함

6.2.1 합집합, 교집합, 차집합 연산

– 이 조건을 합집합 호환성(union compatibility)이라 부름

• 연산 ∪,∩,－의 결과 릴레이션은 피연산자 릴레이션

R

과 동일한 애트리뷰트 이름들을 가짐 (관례적으로)

[그림 5.4] 집합연산 합집합, 교집합, 차집합 : (a) 대상이 되는 두 릴레이션 (b) STUDENT ∪ INSTRUCTOR (c) STUDENT ∩ INSTRUCTOR

• 카티션 프로덕트 (CARTESIAN PRODUCT)

– R(A

₁

₂

_m

₁

₂

_n

₁

₁

₂

_m

₂

₁

₂

_n

₁

₁

₂

₂

t[A₁,A₂,...,A_m] = t₁ 그리고 t[B₁,B₂,...,B_n] = t₂

– R

₁

₁

₂

₂

₁

₂

6.2.2 카티션 곱 (또는, 크로스 프로덕트) 연산

– R

₁

₁

₂

₂

₁

₂

– 카티션 프로덕트은 그 자체로는 큰 의미가 없는 연산이지만 적절한 SELECT 연산과 함께 사용되면 두 릴레이션에서 서로 관련이 있는 투플들을 생성하는데 사용됙 수 있음

– 예제: 모든 DEPARTMENT 투플과 그 부서장의 EMPLOYEE 투플을 조합하라.

DEP_EMP ← DEPARTMENT× EMPLOYEE DEPT_MANAGER ← σ

_MGRSSN=SSN

카티션 프로덕트

a b c d

a1 b1 c1 d1

a1 b1 c2 d2

a1 b1 c3 d3

a2 b2 c1 d1

6.2.2 카티션 곱 (또는, 크로스 프로덕트) 연산

× =

a2 b2 c1 d1

a2 b2 c2 d2

a2 b2 c3 d3

a3 b3 c1 d1

a3 b3 c2 d2

a3 b3 c3 d3

a4 b4 c1 d1

a4 b4 c2 d2

a4 b4 c3 d3

EMPLOYEE FNAME John Franklin

MINIT B T

LNAME Smith Wong

SSN 123456789 333445555

BDATE 09-JAN-55 08-DEC-45

ADDRESS

731 Fondren, Houston, TX 638 Voss, Houston, TX

SEX M M

SALARY 30000 40000

SUPERSSN 333445555 888665555

DNO 5 5

DEPARTMENT DNAME

Research Administration Headquarters

DNUMBER 5 4 1

MGRSSN 333445555 987654321 888665555

MGRSTARTDATE 22-MAY-78

01-JAN-85 19-JUN-71

6.2.2 카티션 곱 (또는, 크로스 프로덕트) 연산

Alicia Jennifer Ramesh Joyce Ahmad James

J S K A V E

Zelaya Wallace

Narayn English Jabbar Borg

999887777 987654321 666884444 453453453 987987987 888665555

19-JUL-58 20-JUN-31 15-SEP-52 31-JUL-62 29-MAR-59 10-NOV-27

3321 Castle, Spring, TX 291 Berry, Bellaire, TX 975 Fire Oak, Humble, TX 5631 Rice, Houston, TX 980 Dallas, Houston, TX 450 Stone, Houston, TX

F F M F M M

25000 43000 38000 25000 25000 55000

987654321 888665555 333445555 333445555 987654321

null

4 4 5 5 4 1

DEP_EMP ← DEPARTMENT×EMPLOYEE / 3 * 8 = 24 tuples 생성 DEPT_MANAGER ← σ

_MGRSSN=SSN

< 카티젼 프로덕트와 셀렉션 연산의 조합 예 >

6.3.1 조인 연산

6.3.2 동등 조인과 자연 조인

6.3 이항 관계 연산

6.3.2 동등 조인과 자연 조인

6.3.3 관계 대수 연산의 완전 집합

6.3.4 디비전 연산

Join 연산

– 두 릴레이션으로부터 관련있는 투플을 결합하여 하나의 투플로 생성함 – 관련성의 여부를 조건으로 표시하며, 이를 조인 조건이라고 함

6.3.1 조인(JOIN) 연산

T ← DEPARTMENT

_MGRSSN=SSN

DNAME,FNAME,LNAME

DEPARTMENT DNAME

DNUMBER 5

MGRSSN 333445555

MGRSTARTDATE 22-MAY-78

RESULT

Research Franklin Wong

EMPLOYEE FNAME John Franklin Alicia Jennifer Ramesh Joyce Ahmad James

MINIT B T J S K A V E

LNAME Smith Wong Zelaya Wallace

Narayn English Jabbar Borg

SSN 123456789 333445555 999887777 987654321 666884444 453453453 987987987 888665555

BDATE 09-JAN-55 08-DEC-45 19-JUL-58 20-JUN-31 15-SEP-52 31-JUL-62 29-MAR-59 10-NOV-27

ADDRESS

731 Fondren, Houston, TX 638 Voss, Houston, TX 3321 Castle, Spring, TX 291 Berry, Bellaire, TX 975 Fire Oak, Humble, TX 5631 Rice, Houston, TX 980 Dallas, Houston, TX 450 Stone, Houston, TX

SEX M M F F M F M M

SALARY 30000 40000 25000 43000 38000 25000 25000 55000

SUPERSSN 333445555 888665555 987654321 888665555 333445555 333445555 987654321

null

DNO 5 5 4 4 5 5 4 1 Research

Administration Headquarters

5 4 1

333445555 987654321 888665555

22-MAY-78 01-JAN-85 19-JUN-71

Research Franklin Wong

Administration Jennifer Wallace

Headquarters James Borg

조인 조건

– <조건> AND <조건> AND … AND <조건>

– 각 조건의 형태는 A

_i

_j

_i

_j

– 조인 조건에 사용된 속성 (A

_i

_j

Theta Join

6.3.2 동등 조인과 자연 조인

Theta Join

– 일반적인 조인 조건(>, =, < 등)을 가진 조인 연산

EQUIJOIN

– 조인 조건에서 동등 비교(equality comparison) 만을 사용하는 조인 – EQUIJOIN 사용 예제: 모든 DEPARTMENT의 이름과 그 관리자의 이름을

검색하라:

T ← DEPARTMENT

_MGRSSN=SSN

DNAME,FNAME,LNAME

• 자연 조인 (NATURAL JOIN) (*):

– EQUIJOIN의 결과에는 두 조인속성의 값이 중복되어 나타남

– 조인 결과에서 조인 속성 하나를 제거하여 중복된 값이 나타나지 않도록 한 조인을 자연조인이라고 함

– 표시법 : R ← R

₁

(R1의 조인 애트리뷰트들),(R2의 조인 애트리뷰트들)

₂

– 예제: 모든 EMPLOYEE의 이름과 그의 DEPARTMENT 이름을 검색하라

6.3.2 동등 조인과 자연 조인 (cont.)

T ← EMPLOYEE *

(DNO),(DNUMBER)

FNAME,LNAME,DNAME

– 두 조인 속성이 동일한 이름을 갖는다면 간단히 R ← R

₁

₂

– 예제: 모든 EMPLOYEE의 이름과 그 상급자의 이름을 검색하라:

SUPERVISOR(SUPERSSN,SFN,SLN) // 속성 이름의 변경

←Π

SSN,FNAME,LNAME

T ← EMPLOYEE * SUPERVISOR // 자연조인 RESULT ← Π

FNAME,LNAME,SFN,SLN

주의

– 자연 조인에서는 조인 애트리뷰트들이 양쪽의 릴레이션에서 동일한 이름을 가져야 하며, 그렇지 않는 경우 조인 속성의 이름을 먼저 동일하게 변경해야 함

– 두 릴레이션에서 하나 이상의 조인 애트리뷰트 쌍이 존재하는 경우 주의가 요망됨

조인 애트리뷰트들 관 계

6.3.2 동등 조인과 자연 조인 (cont.)

에 대한 자연 조인은 다음과 같이 작성함

DEPT(DNAME, DNUM, MGRSSN, MGRSTARTDATE) ← DEPARTMENT PROJ_DEPT ← PROJECT * DEPT // DUNM이 조인속성임;

조인 애트리뷰트들 관 계

EMPLOYEE.SSN =

DEPARTMENT.MGRSSN

EMPLOYEE가

DEPARTMENT를 관리.

EMPLOYEE.DNO =

DEPARTMENT.DNUMBER

EMPLOYEE가

DEPARTMENT에서 일함.

Self Join

– 하나의 릴레이션에 대한 조인

– Self join은 한 릴레이션의 서로 다른 두 사본을 조인하는 것으로 간주함

– 이 경우, 사본 릴레이션에서는 원본 애트리뷰트 이름을

6.3.2 동등 조인과 자연 조인 (cont.)

재명명(renaming)하는 것이 유용함

– 예제: “모든 EMPLOYEE의 이름과 그의 SUPERVISOR의 이름을 검색하라”

SUPERVISOR(SSSN,SFN,SLN) ← Π

SSN,FNAME,LNAME

SUPERSSN=SSSN

RESULT ← Π

FNAME,LNAME,SFN,SLN

최소한의 연산자 집합

– 지금까지 소개한 모든 연산자는 선택(SELECT), 프로젝트(PROJECT),

합집합(UNION), 차집합(SET DIFFERNECE), 카티션 프로덕트 (CARTESIAN PRODUCT) 연산들 만의 조합으로 표현할 수 있음

– 연산자 집합 {σ,Π, ∪,－,×}를 관계대수 연산자의 완전 집합(complete set)이라 부름

6.3.3 관계대수 연산의 완전집합

부름

– 이 연산자 집합과 동등한 모든 질의 언어들은 관계적으로 완전하다(relationally complete)라고 정의함

추가적으로 유용한 연산자들

1. 디비젼(division) 연산

2. 집단 함수(aggregate functions)와 그룹화(grouping) 연산 2. 외부 조인(OUTER JOIN)과 외부 합집합(OUTER UNION)

R(Z) ÷ S(X)은 다음과 같이 정의됨 (X ⊆ Z 이고, Y = Z – X임)

– T1 = Π

_Y

– T2 = Π

_Y

예

6.3.4 디비젼 연산

R A B S A T B

R A B S A T B

a1 b1 a1 b1

a2 b1 a2 b4

a3 b1 a3

a4 b1

a1 b2

a3 b2

a2 b3

a3 b3

a4 b3

a1 b4

a2 b4

a3 b4

÷ =

T1 = Π

_B

T2 = Π

_B

6.4.1 집계 함수와 그룹화

6.4.2 순환적 폐포 (recursive closure) 연산

6.4 추가적인 관계 연산

6.4.3 외부 조인 연산

6.4.4 외부 합집합 연산

집계함수 (aggregate functions)

– SUM, COUNT, AVERAGE, MIN, MAX 함수를 의미함

– 이들은 데이터베이스 응용에서 값들의 집합 또는 투플들의 집합에 적용되며, 표준 관계 대수로 표현할 수 없음

– 다음과 같이 표현하며, 그룹화 애트리뷰트들은 선택적임

<그룹화 애트리뷰트들>

<함수 리스트>

6.4.1 집계 함수와 그룹화 연산

<그룹화 애트리뷰트들>

<함수 리스트>

– 예제 1: 모든 사원의 평균 봉급을 검색하라(그룹화 불필요) R(AVGSAL) ← Ｆ _AVERAGE

_SALARY

– 예제 2: 각 부서에 대하여, 부서 번호와 부서별 사원 수와 평균 봉급을 검색하라 R(DNO,NUMEMPS,AVGSAL) ←

DNO

SSN, AVERAGE SALARY

– 위의 예제에서 DNO를 그룹화 애트리뷰트(grouping attribute)라고 부름

EMPLOYEE FNAME John Franklin Ramesh Joyce Alicia Jennifer

MINIT B T J S K A

LNAME Smith Wong Narayn English Zelaya Wallace

SSN 123456789 333445555 666884444 453453453 999887777 987654321

SALARY 30000 40000 38000 25000 25000 43000

SUPERSSN 333445555 888665555 333445555 333445555 987654321 888665555

DNO 5 5 5 5 4 4

...

...

DNO 5 4 1

COUNT(*) 4 3 1

AVG(SALARY) 33250 31000 55000

6.4.1 집계 함수와 그룹화 연산 (cont.)

GROUP BY와 HAVING의 결과

(a) DNO 값으로 EMPLOYEE 투플들의 그룹화

Jennifer Ahmad James

A V E

Wallace Jabbar

Borg

987654321 987987987 888665555

43000 25000 55000

888665555 987654321

null

4

4

1

동일한 테이블에서 투플들 간의 순환적 관계 (recursive relationship)를 질의하는데 사용됨

관계 대수로서는 표현할 수 없음

예: Employee 테이블에서 사원과 상사간의 관계에 대하여 특정

6.4.2 순환적 폐포 (recursive closure) 연산

사원의 모든 상사 (직간접 상사관계)에 있는 직원을 모두 리턴하시오 ?

이러한 질의는 루핑을 사용하여 한단계 윗 상사들의 집합을

구하고, 이를 바탕으로 2단계 위 상사를 구하며, 이러한 과정을 더

이상의 상사 집합이 없을때까지 (사장이 나올때까지) 구해나가야

하므로 루핑 처리가 필요하게 된다 .

외부 조인(OUTER JOIN)

– 정규 EQUIJOIN이나 자연 조인(NATURAL JOIN) 연산에서 조인 조건을 만족하지 않은 투플들은 결과 릴레이션에도 나타나지 않음

– 조인에 참여하는 릴레이션의 모든 투플들이 조인의 여부와 관계없이 결과 릴레이션에 나타내고 싶은 경우 외부조인을 사용함

– 외부 조인에서는 상대방 릴레이션에 대응되는 투플이 없으면 빈 애트리뷰트들에 NULL 값을 채워서 결과에 포함시킴

6.4.3 외부 조인 연산

애트리뷰트들에 NULL 값을 채워서 결과에 포함시킴

외부 조인의 종류

– 왼쪽 외부 조인(LEFT OUTER JOIN): R

₁

₂

₁

– 오른쪽 외부 조인(RIGHT OUTER JOIN): R

₁

₂

₂

– 완전 외부 조인(FULL OUTER JOIN): R

₁

₂

₁

₂

TEMP <- (EMPLOYEE

_SSN=MGRSSN

FNAME, MINI, LNAME, DNAME

EMPLOYEE FNAME John Franklin Ramesh Joyce Alicia Jennifer Ahmad James

MINIT B T J S K A V E

LNAME Smith Wong Narayn English Zelaya Wallace

Jabbar Borg

SSN 123456789 333445555 666884444 453453453 999887777 987654321 987987987 888665555

SALARY 30000 40000 38000 25000 25000 43000 25000 55000

SUPERSSN 333445555 888665555 333445555 333445555 987654321 888665555 987654321

null

DNO 5 5 5 5 4 4 4 1

...

...

James E Borg 888665555 55000 null 1

DEPARTMENT DNAME Research Administration Headquarters

DNUMBER 5 4 1

MGRSSN 333445555 987654321 888665555

MGRSTARTDATE 22-MAY-78 01-JAN-85 19-JUN-71

John B Smith null

Franklin T Wong Research

Alicia J Zelaya null

Jennifer S Wallace Administration

Joyce A English null

Ahmad V Jabber null

James E Borg Headquarters

외부 합집합 (outer union)

– 호환성이 없는 두 릴레이션을 합집합하는데 사용됨 – 예

STUDENT(Name, SSN, Department, Advisor)와

FACULTY(Name, SSN, Department, Rank)의 outer union은 RESULT(Name, SSN, Department, Advisor, Rank) 임;

6.4.4 외부 합집합 연산

RESULT(Name, SSN, Department, Advisor, Rank) 임;

RESULT 에서 STUDENT 투플은 Rank 속성의 값이 null이고, FACULTY 투플은 Advisor 속성의 값이 null이다

기본 관계대수 연산

– 선택(SELECT), 프로젝트(PROJECT), 합집합(UNION), 차집합(SET DIFFERNECE), 카티션 프로덕트(Cartesion product)

추가적인 관계연산

6.5 관계 대수 질의 요약

추가적인 관계연산

– 집계함수, 그루핑 연산, 외부조인 연산

관계 대수 질의의 예

6.6.1 튜플 변수와 범위 릴레이션 6.6.2 튜플 관계 해석의 표현식과 식 6.6.3 존재 정량자와 전체 정량자

6.6 투플 관계해석

6.6.4 존재 정량자를 이용한 질의 예

6.6.5 전체 정량자와 존재 정량자 사이의 변환 6.6.6 전체 정량자의 사용

6.6.7 안전식 (safe expression)

6.6 투플 관계해석

관계 해석

− “어떻게 검색할 것인가” 보다 “무엇을 검색할 것인가” 만을 기술하는 선언적 표현법을 사용하는 비절차적 질의어

− SQL을 포함한 많은 상업용 관계 언어들이 관계 해석에 기반을 두고 있음

− 투플 관계 해석(tuple relational calculus)와 도메인 관계 해석

− 투플 관계 해석(tuple relational calculus)와 도메인 관계 해석 (domain relational calculus)으로 구분됨

관계 대수와의 차이점

– 관계 해석은 하나의 선언적(declarative) 해석식으로 검색 질의를 명시하며, 비절차적인 언어임

– 관계 대수에서는 연산들을 순차적으로 사용하므로 절차적인 성질을 가짐

– 두 언어의 표현력(expressive power)은 동등함

•

– 어떤 관계 질의어 L이 관계 해석 또는 관계 대수로 표현 가능한 어떤 질의도 표현할 수 있으면 L은 “관계적으로

완전(relationally complete)하다”라고 한다.

6.6 투플 관계해석 (cont.)

– 대부분의 관계 질의어들은 관계적으로 완전하며, 집단

함수(aggregate functions), 그룹화(grouping), 순서화(ordering) 등의 연산들을 제공하므로 관계 해석보다 표현력이 강해진다.

투플 변수

– 릴레이션의 투플들을 범위(range)로 가지는 변수이다.

예제: 봉급이 $50,000를 넘는 모든 사원을 검색하라.

{t | EMPLOYEE(t) and t.SALARY > 50000}

여기서, EMPLOYEE(t)는 투플 변수 t가 릴레이션 EMPLOYEE의 투플들을 범위로 함을 나타낸다.

6.6.1 투플 변수와 범위 릴레이션

투플들을 범위로 함을 나타낸다.

– 투플 t에 대하여 t.SALARY > 50000을 만족하는 투플 만이 검색된다.

– 투플 t의 모든 애트리뷰트 값들이 리턴된다.

프로잭션의 표현

– t의 일부 애트리뷰트 만을 검색하려면 다음과 같이 작성한다.

{t.FNAME, t.LNAME | EMPLOYEE(t) and t.SALARY > 50000}

SELECT T.FNAME, T.LNAME FROM EMPLOYEE T

WHERE T.SALARY > 50000;

{t

₁

₁

₂

₂

_n

_n

₁

₂

_n

_n+1

_n+2

_n+m

– t

₁

₂

_n

_n+1

_n+2

_n+m

_i

_i

6.6.2 투플 관계해석의 표현과 식

– R

_i

_i

_i

_i

– (t

_i

_j

_i

_j

거짓(false)으로 계산되며, 계산된 결과값을 원자의 진리값이라 부름

– 모든 원자들은 식이다.

– F

₁

₂

₁

₂

₁

₂

₁

₂

• 정량자(quantifiers)가 식에 사용될 수 있음

– 전체 정량자(universal quantifier) (∀) (for all이라 읽음) – 존재 정량자(existential quantifier) (∃) (their exists라 읽음)

• 자유 (free) 투플 변수와 속박 (bound) 투플 변수

– 어떤 식 F가 원자인 경우, 여기에 나타난 투플 변수의

어커런스(occurrence)는 F에서 자유롭다 (자유투플 변수)

6.6.3 존재 정량자와 전체 정량자

– 식 (F

₁

₂

₁

₂

₁

₂

₁

₂

– F 내의 투플 변수 t의 모든 자유 어커런스들은 F’ = (∃t)(F)나 F’ = (∀t)(F) 형태의 식에서 정량자에 속박된다

• 예제:

F1: d.DNAME = ‘Research’

F2: (∃t)(d.DNUMBER = t.DNO) – d는 F1과 F2 모두에서 자유롭다 – t는 F2에서 ∃정량자에 속박된다

– F가 식이면, (∃t)(F)도 식이다.

– F 내의 t의 자유 어커런스들에 할당된 “적어도 하나의 투플”에 대해서 F가 참으로 계산되면 식 (∃t)(F)는 참이고, 그렇지 않으면 거짓이다.

– F가 식이면, (∀t)(F)도 식이다.

6.6.3 존재 정량자와 전체 정량자 (cont.)

– F 내의 t의 자유 어커런스들에 할당된 “모든 투플”에 대해서 F가 참으로 계산되면 식 (∀t)(F)는 참이고, 그렇지 않으면 거짓이다.

– F가 참이 되게 하는 어떤 투플 t가 “존재”하면 (∃t)(F)가 참이므로,

∃를 존재 정량자라 부른다.

– “모든” 투플들이 F를 참이 되도록 해야 (∀t)(F)가 참이므로, ∀를 전체 정량자라 부른다.

질의 1: ‘Research’ 부서에서 일하는 모든 사원의 이름과 주소를 검색하라.

Q1: {t.FNAME, t.LNAME, t.ADDRESS | EMPLOYEE(t) and (∃d) (DEPARTMENT(d) and d.DNAME = ‘Research’ and d.DNUMBER = t.DNO)}

6.6.4 존재 정량자를 이용한 질의 예

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과 유사한 목적으로 사용됨)

6.6.4 존재 정량자를 이용한 질의 예(cont.)

• 질의 2: ‘Stafford’에 위치한 모든 프로젝트에 대하여, 프로젝트 번호, 관리 부서의 번호와 부서 관리자의 성, 생일, 그리고 주소를

나열하라.

Q2: {p.PNUMBER, p.DNUM, m.LNAME, m.BDATE, m.ADDRESS | PROJECT(p) and EMPLOYEE(m) and p.PLOCATION = ‘Stafford' and

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’: 부서 5에 의해 관리되는 프로젝트에 참여하는 모든 사원의 이름을 찾아라.

6.6.4 존재 정량자를 이용한 질의 예(cont.)

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: ‘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

6.6.4 존재 정량자를 이용한 질의 예(cont.)

(( m)( d)(EMPLOYEE(m) and DEPARTMENT(d) and p.DNUM = d.DNUMBER and d.MGRSSN = m.SSN and m.LNAME = ‘Smith’)))}

•

–

–

–

• 수학적 논리로부터 유래된 잘 알려진 변환법

(

∀

≡

∃

∃

≡

∀

(

∀

≡

∃

∀

≡

∃

∃

≡

∀

6.6.5 전체 정량자와 존재 정량자 사이의 변환

(

∃

≡

∀

∃

≡

∀

• 다음 식들이 성립함 (⇒는 내포(implies)를 나타냄) (∀x) (P(x)) ⇒ (∃x) (P(x)) (not∃x) (P(x)) ⇒ not(∀x) (P(x))

• 그러나, 다음은 성립하지 않음

not(∀x) (P(x)) ⇒ (not∃x) (P(x))

• 전체 정량자를 사용할 때 식이 의미를 갖도록 하기 위하여 몇가지 규칙을 따라야 함

• 다음의 질의 3을 통하여 규칙을 살펴보자

질의 3: 5번 부서에 의해 관리되는 모든 프로젝트들에 참여하는 사원들의 이름을 찾아라.

Q3: {e.LNAME, e.FNAME | EMPLOYEE(e) and

6.6.6 전체 정량자의 사용

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)

• ^{Q3의 설명}

– Q3의 결과로 구해지는 사원 e는 5 번 부서에서 관리하는 모든 프로젝트에서 근무해야 한다.

– 이러한 푸플을 찾기 위하여 관심없는 모든 투플들을 전체 정량자로부터 제외시켜야 한다.

– F’에서, not(PROJECT(x))는 관심있는 릴레이션 “PROJECT”에 없는 모든 투플들에 대해 x를 참으로 만든다.

6.6.6 전체 정량자의 사용 (cont.)

모든 투플들에 대해 x를 참으로 만든다.

– F1에서, not(x.DNUM = 5)는 관심없는 PROJECT 투플들, 즉

“DNUM이 5가 아닌 투플들”에 대해 x를 참으로 만든다.

– F2는 나머지에 대해 만족되어야 할 조건, 즉 “5번 부서에 의해 관리되는 모든 PROJECT 투플들”을 명시한다.

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)

Q3’: {e.LNAME, e.FNAME | EMPLOYEE(e) and (not(∃x)

(PROJECT(x) and (x.DNUM = 5) and (not(∃w) (WORKS_ON(w) and w.ESSN = e.SSN and x.PNUMBER = w.PNO))))}

– 질의 6: 부양가족이 없는 사원들의 이름을 찾아라.

6.6.6 전체 정량자의 사용 (cont.)

• 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))}

• 관계 해석에서의 안전식

– 결과로서 유한개의 투플들을 생성하는 것이 보장된 식

– 불안전식은 무한개의 투플들을 생성할 수 있고, 투플들의 타입이 서로 다를 수 있음

– 불안전한 식의 예제:

6.6.7 안전식(safe expression)

– 불안전한 식의 예제:

{t | not(EMPLOYEE(t))}

• 가능한 모든 투플들 중에서 EMPLOYEE가 아닌 모든 투플들을 생성함

• 이러한 투플들은 무한개의 투플들로 구성되며, 투플의 타입이 상이할 수 있음

• 따라서 위의 식은 불안전한 식이 됨

• 투플 변수 대신 도메인 변수(domain variables)를 사용하는 관계 해석

• 도메인 변수는 한 애트리뷰트의 도메인을 범위로 가짐

• 차수가 n인 릴레이션의 경우 n 개의 도메인 변수를 사용함 예제:

– 질의 0: 이름이 ‘John B. Smith’인 사원의 생일과 주소를 검색하라.

Q0: {uv | (∃q) (∃r) (∃s) (EMPLOYEE(qrstuvwxyz) and q = ‘John’ and r = ‘B’ and s = ‘Smith’)}

• EMPLOYEE의 각 애트리뷰트들을 위한 열 개의 도메인 변수들: qrstuvwxyz

6.7 도메인 관계해석

• 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: ‘Research’ 부서에서 일하는 모든 사원들의 이름과 주소를 검색하라.

Q1: {qsv | (∃z) (EMPLOYEE(qrstuvwxyz) and (∃l) (∃m) (DEPARTMENT(lmno) and l = ‘Research’ and m = z))}

(m = z)는 조인 조건

(l = ‘Research’)는 선택 조건

– 질의 2: ‘Stafford’에 위치한 모든 프로젝트에 대해서 프로젝트 번호와 부서 번호, 그리고 부서 관리자의 성, 생일, 주소를 나열하라.

6.7 도메인 관계해석(cont.)

번호, 그리고 부서 관리자의 성, 생일, 주소를 나열하라.

Q2: {iksuv | (∃j) (PROJECT(hijk) and (∃t) (EMPLOYEE(qrstuvwxyz) and (∃m) (∃n)

(DEPARTMENT(lmno) and k = m and n = t and j = ‘Stafford’)))}

– 질의 6: 부양가족이 없는 사원들의 이름을 찾아라.

Q6: {qs | (∃t) (EMPLOYEE(qrstuvwxyz) and

(not (∃l) (DEPENDENT(lmno) and t = l)))}

– 질의 7: 적어도 한명의 부양가족이 있는 관리자들의 이름을

6.7 도메인 관계해석(cont.)

– 질의 7: 적어도 한명의 부양가족이 있는 관리자들의 이름을 나열하라.

Q7: {sq | (∃t) (EMPLOYEE(qrstuvwxyz) and ((∃j) (DEPARTMENT(hijk) and

((∃l) (DEPENDENT(lmno) and t = j and l = t)))))}