제 6 장 관계 대수와 관계 해석 Fundamentals of Database Systems 제 6 장 관계 대수와 관계 해석 Fundamentals of Database Systems R. A. Elmasri and S. B. Navathe

Fundamentals of Database Systems 내 용 6.1 단항 관계 연산: 실렉트와 프로젝트 6.2 집합 이론과 관계 대수 연산 6.3 이항관계 연산 : 조인과 디비전 연산 6.4 추가적인 관계 연산 6.5 관계 대수 질의의 예 6.6 투플 관계 해석 6.7 도메인 관계 해석 Ch6 Fundamentals of Database Systems

Fundamentals of Database Systems 6.1 단항 관계 연산 관계 대수란 릴레이션들을 다루는 연산들 검색 요구(질의)를 기술하는 데에 사용함 질의 결과도 릴레이션임 이 절의 구성 6.1.1 실렉트(SELECT) 연산 6.1.2 프로젝트(PROJECT) 연산 6.1.3 연산의 순서와 이름 변경 연산 Ch6 Fundamentals of Database Systems

Fundamentals of Database Systems 6.1.1 실렉트(SELECT) 연산 SELECT 연산 (σ로 표기) 릴레이션 R에서 어떤 선택조건 c를 만족하는 투플들을 선택함 연산 형식: σc(R) 조건 c는 R의 애트리뷰트들에 대한 임의의 불리언 식임 결과 릴레이션은 R과 동일한 애트리뷰트들을 가짐 결과 릴레이션은 r(R)의 투플 중 애트리뷰트 값들이 조건 c를 만족하는 투플들로 구성됨 예제: σDNO=4 (EMPLOYEE) σSALARY>30000 (EMPLOYEE) σ(DNO=4 AND SALARY>25000) OR DNO=5 (EMPLOYEE) Ch6 Fundamentals of Database Systems

Fundamentals of Database Systems 6.1.2 프로젝트(PROJECT) 연산 PROJECT 연산 (Π로 표기) 릴레이션 R에서 애트리뷰트 리스트 L에 명시된 애트리뷰트들만 선택함 연산 형식: ΠL(R) 결과 릴레이션은 L에 명시된 R의 애트리뷰트들만 가짐 예제: ΠFNAME,LNAME,SALARY (EMPLOYEE) PROJECT 연산은 결과 릴레이션이 수학적 집합이므로 중복된 투플들을 제거함 예제: ΠSEX,SALARY (EMPLOYEE) 봉급이 1,000,000원인 남자 사원들이 여러명 이더라도 결과 릴레이션에는 단지 하나의 <M, 1000000> 투플만이 포함되며, 나머지는 제거됨 Ch6 Fundamentals of Database Systems

Fundamentals of Database Systems 6.1.3 연산의 순서와 이름 변경 연산 다수의 연산을 결합하여 관계 대수식(질의)을 형성할 수 있음 예제: 부서 4에서 일하는 사원들의 이름과 봉급을 검색하라. ΠFNAME,LNAME,SALARY (σDNO=4 (EMPLOYEE)) 각 중간 단계의 임시 릴레이션에 이름을 부여할 수도 있음 DEPT4_EMPS ←σDNO=4 (EMPLOYEE) R ←ΠFNAME,LNAME,SALARY (DEPT4_EMPS) 결과 릴레이션의 애트리뷰트 이름은 재명명 할 수도 있음 R(FIRSTNAME, LASTNAME, SALARY) ← ΠFNAME,LNAME,SALARY(DEPT4_EMPS) Ch6 Fundamentals of Database Systems

Fundamentals of Database Systems 6.2 집합 이론과 관계 대수 연산 수학적 집합 이론에서의 이진 연산 합집합: R1∪ R2 교집합: R1∩ R2 차집합: R1 – R2 카티션 곱: R1× R2 연산 ∪,∩,－에서의 호환성 피연산자 릴레이션 R1(A1,A2,...,An)과 R2(B1,B2,...,Bn)는 애트리뷰트들의 갯수가 동일하고, 대응되는 애트리뷰트들의 도메인이 호환성을 가져야 함; 즉, i=1,2,...,n에 대하여 dom(Ai) = dom(Bi)이어야 함 이 조건을 합집합 호환성(union compatibility)이라 부름 연산 ∪,∩,－의 결과 릴레이션은 피연산자 릴레이션 R1과 동일한 애트리뷰트 이름들을 가짐 (관례적으로) Ch6 Fundamentals of Database Systems

(a) (b) (c) (d) (e) [그림 6.4] 집합연산 합집합, 교집합, 차집합 : (a) 합집합 호환적인 두 릴레이션 STUDENT FN Susan Ramesh Johnny Barbara Amy Jimmy Ernest LN Yao Shah Kohler Jones Ford Wang Gilbert INSTRUCTOR FNANE John Ricardo Francis LNAME Smith Browne Johnson FN Susan Ramesh Johnny Barbara Amy Jimmy Ernest John Ricardo Francis LN Yao Shah Kohler Jones Ford Wang Gilbert Smith Browne Johnson (b) (c) (d) (e) [그림 6.4] 집합연산 합집합, 교집합, 차집합 : (a) 합집합 호환적인 두 릴레이션 (b) STUDENT ∪ INSTRUCTOR (c) STUDENT ∩ INSTRUCTOR (d) STUDENT － INSTRUCTOR (e) INSTRUCTOR － STUDENT Ch6 Fundamentals of Database Systems

Fundamentals of Database Systems 6.2 집합 이론과 관계 대수 연산(cont.) 카티션 프로덕트 (CARTESIAN PRODUCT) R(A1,A2,...,Am,B1,B2,...,Bn) ← R1(A1,A2,...,Am)×R2 (B1,B2,...,Bn) R의 투플 t는 R1의 투플 t1과 R2의 투플 t2 분리됨; 즉, t[A1,A2,...,Am] = t1 그리고 t[B1,B2,...,Bn] = t2 R1이 n1개의 투플을, R2가 n2개의 투플을 갖는다면, R은 n1*n2 개의 투플을 가지게 됨 카티션 프로덕트은 그 자체로는 큰 의미가 없는 연산이지만 적절한 SELECT 연산과 함께 사용되면 두 릴레이션에서 서로 관련이 있는 투플들을 생성하는데 사용됙 수 있음 예제: 모든 DEPARTMENT 투플과 그 부서장의 EMPLOYEE 투플을 조합하라. DEP_EMP ← DEPARTMENT×EMPLOYEE DEPT_MANAGER ← σMGRSSN=SSN(DEP_EMP) (다음 Slide 참고) Ch6 Fundamentals of Database Systems

DEP_EMP ← DEPARTMENT×EMPLOYEE /* 3 * 8 = 24 tuples 생성 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 F SALARY 30000 40000 25000 43000 38000 55000 SUPERSSN null DNO 5 4 1 DEPARTMENT DNAME Research Administration Headquarters DNUMBER MGRSSN MGRSTARTDATE 22-MAY-78 01-JAN-85 19-JUN-71 DEP_EMP ← DEPARTMENT×EMPLOYEE /* 3 * 8 = 24 tuples 생성 DEPT_MANAGER ← σMGRSSN=SSN(DEP_EMP) /* 3 개의 tuples 만 선택 < 카티젼 프로덕트와 셀렉션 연산의 조합 예 > Ch6 Fundamentals of Database Systems

Fundamentals of Database Systems 6.3 이항 관계 연산: 조인과 디비전 연산 Join 연산 두 릴레이션으로부터 관련있는 투플을 결합하여 하나의 투플로 생성함 관련성의 여부를 조건으로 표시하며, 이를 조인 조건이라고 함 T ← DEPARTMENT MGRSSN=SSN EMPLOYEE RESULT ← ΠDNAME,FNAME,LNAME(T) RESULT Research Franklin Wong Administration Jennifer Wallace Headquarters James Borg 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 F SALARY 30000 40000 25000 43000 38000 55000 SUPERSSN null DNO 5 4 1 DEPARTMENT DNAME Research Administration Headquarters DNUMBER MGRSSN MGRSTARTDATE 22-MAY-78 01-JAN-85 19-JUN-71 Ch6 Fundamentals of Database Systems

Fundamentals of Database Systems 6.3 이항 관계 연산 (계속) 조인 조건 <조건> AND <조건> AND … AND <조건> 각 조건의 형태는 Ai θ Bj 이며, Ai 는 R의 애트리뷰트, Bj 는 S의 애트리뷰트임 조인 조건에 사용된 속성 (Ai 와 Bj 를 조인 속성이라고 부름) Theta Join 일반적인 조인 조건(>, =, < 등)을 가진 조인 연산 EQUIJOIN 조인 조건에서 동등 비교(equality comparison) 만을 사용하는 조인 EQUIJOIN 사용 예제: 모든 DEPARTMENT의 이름과 그 관리자의 이름을 검색하라: T ← DEPARTMENT MGRSSN=SSN EMPLOYEE RESULT ← ΠDNAME,FNAME,LNAME(T) Ch6 Fundamentals of Database Systems

Fundamentals of Database Systems 6.3 이항 관계 연산 (cont.) 자연 조인 (NATURAL JOIN) (*): EQUIJOIN의 결과에는 두 조인속성의 값이 중복되어 나타남 조인 결과에서 조인 속성 하나를 제거하여 중복된 값이 나타나지 않도록 한 조인을 자연조인이라고 함 표시법 : R ← R1*(R1의 조인 애트리뷰트들),(R2의 조인 애트리뷰트들) R2 예제: 모든 EMPLOYEE의 이름과 그의 DEPARTMENT 이름을 검색하라 T ← EMPLOYEE *(DNO),(DNUMBER) DEPARTMENT RESULT ← ΠFNAME,LNAME,DNAME(T) 두 조인 속성이 동일한 이름을 갖는다면 간단히 R ← R1* R2라고 표시함 예제: 모든 EMPLOYEE의 이름과 그 상급자의 이름을 검색하라: SUPERVISOR(SUPERSSN,SFN,SLN) // 속성 이름의 변경 ←ΠSSN,FNAME,LNAME(EMPLOYEE) T ← EMPLOYEE * SUPERVISOR // 자연조인 RESULT ← ΠFNAME,LNAME,SFN,SLN(T) Ch6 Fundamentals of Database Systems

Fundamentals of Database Systems 6.3 이항 관계 연산(cont.) 주의 자연 조인에서는 조인 애트리뷰트들이 양쪽의 릴레이션에서 동일한 이름을 가져야 하며, 그렇지 않는 경우 조인 속성의 이름을 먼저 동일하게 변경해야 함 두 릴레이션에서 하나 이상의 조인 애트리뷰트 쌍이 존재하는 경우 주의가 요망됨 예제: “모든 EMPLOYEE의 이름과 그가 일하는 DEPARTMENT의 이름을 검색하라” 에 대한 자연 조인은 다음과 같이 작성함 DEPT(DNAME, DNUM, MGRSSN, MGRSTARTDATE) ← DEPARTMENT PROJ_DEPT ← PROJECT * DEPT // DUNM이 조인속성임; // MGRSSN은 조인속성이 아님 Ch6 Fundamentals of Database Systems

Fundamentals of Database Systems 6.3 이항 관계 연산(cont.) Self Join 하나의 릴레이션에 대한 조인 Self join은 한 릴레이션의 서로 다른 두 사본을 조인하는 것으로 간주함 이 경우, 사본 릴레이션에서는 원본 애트리뷰트 이름을 재명명(renaming)하는 것이 유용함 예제: “모든 EMPLOYEE의 이름과 그의 SUPERVISOR의 이름을 검색하라” SUPERVISOR(SSSN,SFN,SLN) ← ΠSSN,FNAME,LNAME(EMPLOYEE) T ← EMPLOYEE SUPERSSN=SSSN SUPERVISOR RESULT ← ΠFNAME,LNAME,SFN,SLN(T) Ch6 Fundamentals of Database Systems

Fundamentals of Database Systems 6.3 이항 관계 연산 (cont.) 관계 대수 연산의 완전 집합 지금까지 소개한 모든 연산자는 선택(SELECT), 프로젝트(PROJECT), 합집합(UNION), 차집합(SET DIFFERNECE), 카티션 프로덕트 (CARTESIAN PRODUCT) 연산들 만의 조합으로 표현할 수 있음 연산자 집합 {σ,Π, ∪,－,×}를 관계대수 연산자의 완전 집합(complete set)이라 부름 이 연산자 집합과 동등한 모든 질의 언어들은 관계적으로 완전하다(relationally complete)라고 정의함 추가적으로 유용한 연산자들 디비젼(division) 연산 집단 함수(aggregate functions)와 그룹화(grouping) 연산 2. 외부 조인(OUTER JOIN)과 외부 합집합(OUTER UNION) Ch6 Fundamentals of Database Systems

Fundamentals of Database Systems 6.3 이항 관계 연산 (cont.) 디비전 연산 : R(Z)  S(X)은 다음과 같이 정의됨 (X  Z 이고, Y = Z – X임) T1 = ΠY(R) T2 = ΠY(( S × T1) – R) T = T1 – T2 예 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(R) T2 = ΠB(( S × T1) – R) T = T1 – T2 Ch6 Fundamentals of Database Systems

Fundamentals of Database Systems 6.4 추가적인 관계연산 집단함수 (aggregate functions) SUM, COUNT, AVERAGE, MIN, MAX 함수를 의미함 이들은 데이타베이스 응용에서 값들의 집합 또는 투플들의 집합에 적용되며, 표준 관계 대수로 표현할 수 없음 다음과 같이 표현하며, 그룹화 애트리뷰트들은 선택적임 <그룹화 애트리뷰트들> Ｆ <함수 리스트> (R) 예제 1: 모든 사원의 평균 봉급을 검색하라(그룹화 불필요) R(AVGSAL) ← Ｆ AVERAGE SALARY (EMPLOYEE) 예제 2: 각 부서에 대하여, 부서 번호와 부서별 사원 수와 평균 봉급을 검색하라 R(DNO,NUMEMPS,AVGSAL) ← DNO Ｆ COUNT SSN, AVERAGE SALARY (EMPLOYEE) 위의 예제에서 DNO를 그룹화 애트리뷰트(grouping attribute)라고 부름 Ch6 Fundamentals of Database Systems

6.4 추가적인 관계연산 (cont.) ... (a) DNO 값으로 EMPLOYEE 투플들의 그룹화 Ch6 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 43000 55000 SUPERSSN null DNO 5 4 1 ... COUNT(*) 3 AVG(SALARY) 33250 31000 (a) DNO 값으로 EMPLOYEE 투플들의 그룹화 Ch6 Fundamentals of Database Systems

Fundamentals of Database Systems 6.4 추가적인 관계연산 (cont.) 순환적 폐포 (recursive closure) 연산 동일한 테이블에서 투플들 간의 순환적 관계 (recursive relationship)를 질의하는데 사용됨 관계 대수로서는 표현할 수 없음 예: Employee 테이블에서 사원과 상사간의 관계에 대하여 특정 사원의 모든 상사 (직간접 상사관계)에 있는 직원을 모두 리턴하시오 ? 이러한 질의는 루핑을 사용하여 한단계 윗 상사들의 집합을 구하고, 이를 바탕으로 2단계 위 상사를 구하며, 이러한 과정을 더 이상의 상사 집합이 없을때까지 (사장이 나올때까지) 구해나가야 하므로 루핑 처리가 필요하게 된다. Ch6 Fundamentals of Database Systems

Fundamentals of Database Systems 6.4 추가적인 관계연산(cont.) 외부 조인(OUTER JOIN) 정규 EQUIJOIN이나 자연 조인(NATURAL JOIN) 연산에서 조인 조건을 만족하지 않은 투플들은 결과 릴레이션에도 나타나지 않음 조인에 참여하는 릴레이션의 모든 투플들이 조인의 여부와 관계없이 결과 릴레이션에 나타내고 싶은 경우 외부조인을 사용함 외부 조인에서는 상대방 릴레이션에 대응되는 투플이 없으면 빈 애트리뷰트들에 NULL 값을 채워서 결과에 포함시킴 외부 조인의 종류 왼쪽 외부 조인(LEFT OUTER JOIN): R1 R2는 R1의 모든 투플들이 결과 릴레이션이 나타나도록 한다. 오른쪽 외부 조인(RIGHT OUTER JOIN): R1 R2는 R2의 모든 투플들이 결과 릴레이션이 나타나도록 한다. 완전 외부 조인(FULL OUTER JOIN): R1 R2는 R1과 R2의 모든 투플들이 결과 릴레이션이 나타나도록 한다. Ch6 Fundamentals of Database Systems

Fundamentals of Database Systems TEMP <- (EMPLOYEE SSN=MGRSSN DEPARTMENT ) RESULT <= Π FNAME, MINI, LNAME, DNAME (TEMP) 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 43000 55000 SUPERSSN null DNO 5 4 1 ... DEPARTMENT DNAME Research Administration Headquarters DNUMBER 5 4 1 MGRSSN 333445555 987654321 888665555 MGRSTARTDATE 22-MAY-78 01-JAN-85 19-JUN-71 RESULT FNAME MINIT LNAME DNAME John B Smith null Franklin T Wong Research Alicia J Zelaya null Jennifer S Wallace Administration Ramesh K Narayan null Joyce A English null Ahmad V Jabber null James E Borg Headquarters Ch6 Fundamentals of Database Systems

Fundamentals of Database Systems 6.4 추가적인 관계연산(cont.) 외부 유니온 (outer union) 호환성이 없는 두 릴레이션을 유니온하는데 사용됨 예 STUDENT(Name, SSN, Department, Advisor)와 FACULTY(Name, SSN, Department, Rank)의 outer union은 RESULT(Name, SSN, Department, Advisor, Rank) 임; RESULT 에서 STUDENT 투플은 Rank 속성의 값이 null이고, FACULTY 투플은 Advisor 속성의 값이 null이다 Ch6 Fundamentals of Database Systems

Fundamentals of Database Systems 6.5 관계 대수 질의의 예 질의 1 : ‘Research’ 부서에서 일하는 모든 사원의 이름과 주소를 검색하라. RESEARCH_DEPT ← σDNAME = ‘Research’ (DEPARTMENT) RESEARCH_EMPS ← RESEARCH_DEPT DNUMBER=DNO EMPLOYEE RESULT ← ΠFNAME,LNAME,SFN,SLN(T) 질의 2 : ‘Stafford’ 에 위치한 모든 프로젝트에 대하여 프로젝트 번호와 관리 부서 번호, 부서 관리자의 성, 주소, 생년월일을 나열하라. STAFFORD_PROJS ← σDLOCATION = ‘Stafford’ (PROJECT) CONTR_DEPT ← STAFFORD_PROJS DNUM=DNUMBER DEPARTMENT PROJ_DEPT_MGR ← CONTR_DEPT MGRSSN=SSN EMPLOYEE RESULT ← ΠPNUMBER,DNUM,LNAME,ADDRESS,BDATE(PROJ_DEPT_MGR) Ch6 Fundamentals of Database Systems

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

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

Fundamentals of Database Systems 6.6.1 투플 변수와 범위 릴레이션 투플 변수 릴레이션의 투플들을 범위(range)로 가지는 변수이다. 예제: 봉급이 $50,000를 넘는 모든 사원을 검색하라. {t | EMPLOYEE(t) and t.SALARY > 50000} 여기서, EMPLOYEE(t)는 투플 변수 t가 릴레이션 EMPLOYEE의 투플들을 범위로 함을 나타낸다. 투플 t에 대하여 t.SALARY > 50000을 만족하는 투플 만이 검색된다. 투플 t의 모든 애트리뷰트 값들이 리턴된다. 프로잭션의 표현 t의 일부 애트리뷰트 만을 검색하려면 다음과 같이 작성한다. {t.FNAME, t.LNAME | EMPLOYEE(t) and t.SALARY > 50000} 이는 다음 SQL 질의와 동일한 의미를 가진다. SELECT T.FNAME, T.LNAME FROM EMPLOYEE T WHERE T.SALARY > 50000; Ch6 Fundamentals of Database Systems

Fundamentals of Database Systems 6.6.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)은 다음과 같은 원자(atoms)들로 이루어짐 Ri(ti)는 ti의 범위가 Ri임을 명시 (ti.A op tj.B), op는 비교 연산자 (=, <, ≤, ...) (ti.A op c) 또는 (c op tj.B), c는 상수 각 원자는 특정한 투플들의 조합에 대해서 참(true) 또는 거짓(false)으로 계산되며, 계산된 결과값을 원자의 진리값이라 부름 식(formula): and, or, not으로 연결된 원자들 모든 원자들은 식이다. F1과 F2가 식이면 (F1 and F2), (F1 or F2), not(F1), not(F2)도 식이다. Ch6 Fundamentals of Database Systems

Fundamentals of Database Systems 6.6.3 존재 정량자와 전체 정량자 정량자(quantifiers)가 식에 사용될 수 있음 전체 정량자(universal quantifier) (∀) (for all이라 읽음) 존재 정량자(existential quantifier) (∃) (their exists라 읽음) 자유 (free) 투플 변수와 속박 (bound) 투플 변수 어떤 식 F가 원자인 경우, 여기에 나타난 투플 변수의 어커런스(occurrence)는 F에서 자유롭다 (자유투플 변수) 식 (F1 and F2), (F1 or F2), not(F1), not(F2)에 나타난 투플 변수 t가 자유로운가 여부는 F1이나 F2에서 자유로운가에 달려있다 F 내의 투플 변수 t의 모든 자유 어커런스들은 F’ = (∃t)(F)나 F’ = (∀t)(F) 형태의 식에서 정량자에 속박된다 예제: F1: d.DNAME = ‘Research’ F2: (∃t)(d.DNUMBER = t.DNO) d는 F1과 F2 모두에서 자유롭다 t는 F2에서 ∃정량자에 속박된다 Ch6 Fundamentals of Database Systems

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

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

Fundamentals of Database Systems 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 ((∃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} Ch6 Fundamentals of Database Systems

Fundamentals of Database Systems 6.6.4 존재 정량자를 이용한 질의 예(cont.) 질의 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))} Ch6 Fundamentals of Database Systems

Fundamentals of Database Systems 6.6.4 존재 정량자를 이용한 질의 예(cont.) 질의 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 m.LNAME = ‘Smith’)))} AND/OR/NOT 관계 대수의 UNION은 관계 해석의 or 연결자에 대응함 INTERSECTION은 and 연결자에 대응함 not 연결자는 전체 정량자와 존재 정량자를 동등한 식으로 변환하는 데에 사용될 수 있음 Ch6 Fundamentals of Database Systems

6.6.6 전체 정량자와 존재 정량자 사이의 변환 수학적 논리로부터 유래된 잘 알려진 변환법 (∀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)) Ch6 Fundamentals of Database Systems

Fundamentals of Database Systems 6.6.7 전체 정량자의 사용 전체 정량자를 사용할 때 식이 의미를 갖도록 하기 위하여 몇가지 규칙을 따라야 함 다음의 질의 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) Ch6 Fundamentals of Database Systems

Fundamentals of Database Systems 6.6.7 전체 정량자의 사용 Q3의 설명 Q3의 결과로 구해지는 사원 e는 5 번 부서에서 관리하는 모든 프로젝트에서 근무해야 한다. 이러한 푸플을 찾기 위하여 관심없는 모든 투플들을 전체 정량자로부터 제외시켜야 한다. F’에서, not(PROJECT(x))는 관심있는 릴레이션 “PROJECT”에 없는 모든 투플들에 대해 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) Ch6 Fundamentals of Database Systems

Fundamentals of Database Systems 6.6.7 전체 정량자의 사용 전체 정량자로부터 존재 정량자로의 변환 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: 부양가족이 없는 사원들의 이름을 찾아라. 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))} Ch6 Fundamentals of Database Systems

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

Fundamentals of Database Systems 6.7 도메인 관계해석 투플 변수 대신 도메인 변수(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 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)} Ch6 Fundamentals of Database Systems

Fundamentals of Database Systems 6.7 도메인 관계해석(cont.) 질의 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’)))} Ch6 Fundamentals of Database Systems

Fundamentals of Database Systems 6.7 도메인 관계해석(cont.) 질의 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)))))} Ch6 Fundamentals of Database Systems

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