관계 데이타 모델 (Relational Data Model) 경북대학교 전자 전기 컴퓨터 학부 박영철

Fundamentals of Database Systems 관계 모델 (The relational model) E.F. Codd, “A Realtional Model for Large Shared Data Banks,” CACM, 13:6, June 1970. 수학적 릴레이션(mathematical relation)의 개념을 이용 형태 : Table; 이론적 기반 : Set theory, First order predicate logic {데이타베이스 구조, 제약조건들, 연산들의 집합} 연산 : 추출(retrieval) 연산, 갱신(update) 연산 갱신 연산 : 삽입 (insert), 삭제 (delete), 갱신(update) 관계 데이타베이스 스키마 S = {R1, R2, ..., Rn} + IC {R1, R2, ..., Rn} : 릴레이션 스키마(relation schema)들의 집합. IC : 무결성 제약조건(integrity constraint)들의 집합. 예, 관계 데이타베이스 스키마 COMPANY COMPANY = {EMPLOYEE, DEPARTMENT, DEPT_LOCATIONS, ROJECT, WORKS_ON, DEPENDENT} 관계 데이타베이스 인스턴스 DB = {r1, r2, ..., rn} {r1, r2, ..., rn} : 릴레이션 인스턴스들의 집합 {r1, r2, ..., rn}. 각 ri는 Ri의 인스턴스이며 IC에 명시된 무결성 제약조건들을 만족한다. 무결성 제약조건은 모든 릴레이션 인스턴스들이 만족해야 하는 조건이다. 다섯 가지 주요 제약조건 1. 도메인 제약조건 (domain constraints),  각 칼럼은 그 칼럼의 data type, domain을 만족 2. NULL / NOT NULL 제약조건 3. 키 제약조건 (key constraints)  primary key, unique 칼럼: 유일성(uniqueness property) 4. 엔티티 무결성 제약조건 (entity integrity constraints)  primary key 칼럼: NOT NULL 5. 참조 무결성 제약조건 (referential integrity constraints)  foreign key 칼럼: 허상 참조를 방지 2006-03-15 Fundamentals of Database Systems

STUDENT 릴레이션의 애트리뷰트와 투플들 관계 모델 릴레이션의 이름 STUDENT Name SSN HomePhone Address OfficePhone Age GPA Benjamin Bayer Katherine Ashly Dick Davidson Charles Cooper Barbara Benson 305-61-2435 381-62-1245 422-11-2420 489-22-1100 533-69-1238 373-1616 375-4409 null 376-9821 839-8461 2918 BlueBonnet Lane 125 Kirby Road 3452 Elgin Road 265 Lark Lane 7384 Fontana Lane null 749-1253 19 18 25 28 3.21 2.89 3.53 3.93 3.25 투플 STUDENT 릴레이션의 애트리뷰트와 투플들 관계 모델 데이타베이스 = {릴레이션} 릴레이션 = <{<Attribute, Domain>}, {투플}> 2006-03-15 Fundamentals of Database Systems

Fundamentals of Database Systems 릴레이션 스키마 R(A1, A2, … An) R : 릴레이션 이름 Ai : 애트리뷰트(Attribute)  각 애트리뷰트 Ai 는 도메인 dom(Ai)를 가진다.  도메인(domain) : 원자 값들(atomic values)의 집합. <이름, 자료 형(data type), 포맷(format), 단위> n : the degree (차수) of the relation: the number of attributes 예: STUDENT(Name, SSN, BirthDate, Addr) 정의 1 투플 t: 값들의 순서 리스트 t = <v1, v2, ..., vn>, 값 vi는 dom(Ai)의 한 원소임. n-투플이라고도 함. 정의 2 릴레이션 스키마 R = {A1, A2, … An} 투플 t: R에서 D로의 사상(mapping), D = dom(A1) U dom(A2) U … U dom(An) 릴레이션 인스턴스 r(R) 또는 r : 투플들의 집합. r(R) = {t1, t2, ..., tm} 또는 r(R) ⊆ dom(A1) × dom(A2) × ... × dom(An) 하나의 릴레이션의 투플들은 그들 간의 순서를 가지지 않는다. R(A1, A2, ..., An)의 애트리뷰트들과 t = <v1, v2, ..., vn>의 애트리뷰트 값들은 순서를 가지지 않는다. 2006-03-15 Fundamentals of Database Systems

Fundamentals of Database Systems 앞으로 다음과 같은 표기법을 사용한다. 차수가 n인 릴레이션 스키마 R(A1, A2, …, An) 릴레이션 r(R)의 n-투플 t = <v1, v2, …, vn> t[Ai]와 t.Ai 는 투플 t에 대한 애트리뷰트 Ai의 값을 나타낸다. t[Au, Aw, ..., Az]와 t.(Au, Aw, ..., Az)는 애트리뷰트 Au, Aw, ..., Az 의 값을 포함하는 서브투플 <vu, vw, ..., vz> 를 가리킨다. 대문자 Q, R, S 등은 릴레이션 이름 소문자 q, r, s 등은 릴레이션 상태 소문자 t, u, v 등은 투플 STUDENT 처름 릴레이션 스키마의 이름 : 릴레이션의 현재 투플들의 집합 즉, 현재의 릴레이션 상태도 가리킨다. STUDENT(Name, SSN, …)은 릴레이션 스키마만을 가리킨다. R.A로 표기할 수 있다. 예, STUDENT.Name, STUDENT.Age 2006-03-15 Fundamentals of Database Systems

Fundamentals of Database Systems 수퍼키(superkey): R의 애트리뷰트 집합 SK에 대하여, 모든 유효한 릴레이션 인스턴스 r(R)의 어떠한 두 투플도 동일한 SK 값을 갖지 않는다. 즉, r(R) 내의 임의의 서로 다른 두 투플 t1과 t2에 대해 t1[SK] ≠t2[SK]이다. 키(key): “최소” 수퍼키. 수퍼키들 중에서 수퍼키 K를 구성하는 어느 한 애트리뷰트라도 빠지면 수퍼키가 될 수 없는 수퍼키 K를 의미한다. 예제: CAR 릴레이션 스키마 CAR(State, RegNumber, SerialNo, Make, Model, Year)는 두개의 키 Key1 = {State, RegNumber}, Key2 = {SerialNo}를 가지며, 이들은 동시에 수퍼키이다. {SerialNo, Make}는 수퍼키이지만 키는 아니다. 릴레이션이 여러 개의 후보키(candidate key)를 가지면 이들 중 하나를 임의로 선택하여 기본키(primary key)로 한다. 널(NULL) 값 해당사항 없음(not applicable) 예: 단독주택에 사는 사람의 아파트 주소, 대학학위 2. 모름(unknown) : 존재하지만 누락되었음(value exists but is missing) 예: 사람의 키 존재하는지조차 모름(it is not known whether the attribute value exists) 예: 전화번호 2006-03-15 Fundamentals of Database Systems

관계대수 (Relational Algebra) 경북대학교 전자 전기 컴퓨터 학부 박영철

Fundamentals of Database Systems 관계 대수 : 관계 모델 연산들의 기본 집합. 릴레이션들에 대한 검색 요구(질의)를 기술하는 데에 사용 질의 결과도 릴레이션이다. 1. SELECT 연산 (σ로 표기): 연산 형식: σc(R) 릴레이션 R에서 선택조건 c를 만족하는 투플들을 선택한다. 조건 c는 R의 애트리뷰트들에 대한 임의의 불리언 식(boolean expression)이다. 결과 릴레이션은 R과 동일한 애트리뷰트들을 가진다. 결과 릴레이션은 r(R)의 투플들 중 애트리뷰트 값들이 조건 c를 만족하는 투플들을 포함한다. 선택 조건 c <애트리뷰트 이름> <비교 연산자> <상수값>, 또는 <애트리뷰트 이름> <비교 연산자> <애트리뷰트 이름> <비교 연산자> : { =, <, <=, >, >=, != } AND, OR, NOT 예: σDNO=4 (EMPLOYEE) σSALARY>30000 (EMPLOYEE) σ(DNO=4 AND SALARY>25000) OR DNO=5 (EMPLOYEE) σ(DNO=4 AND SALARY>25000) OR (DNO=5 AND SALARY>30000) (EMPLOYEE) 선택률(selectivity) : 선택 조건에 의해 선택된 투플 수의 비율 실렉트 연산은 교환적(commutative)이다. σ<조건1> (σ<조건2> (R)) = σ<조건2> (σ<조건1> (R)) 실렉트 연산들의 연속은 항상 AND 조건을 가진 하나의 실렉트 연산으로 결합할 수 있다. σ<조건1> (σ<조건2> (… σ<조건n> (R))…)) = σ<조건1> AND<조건2>AND …AND<조건n> (R) 2006-03-15 Fundamentals of Database Systems

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

Fundamentals of Database Systems 3. 연산의 순서와 이름 변경(rename) 연산 몇개의 연산들이 결합되어 관계대수식(질의)을 형성한다. 예: 부서 4에서 일하는 사원들의 이름과 봉급을 검색하라. ΠFNAME,LNAME,SALARY (σDNO=4 (EMPLOYEE)) 각 중간 단계의 릴레이션들에 이름을 부여할 수 있다. DEPT4_EMPS ←σDNO=4 (EMPLOYEE) R ←ΠFNAME,LNAME,SALARY (DEPT4_EMPS) 결과 릴레이션에 나타나는 애트리뷰트들의 이름을 재명명(rename)할 수 있다. R(FIRSTNAME, LASTNAME, SALARY) ← ΠFNAME,LNAME,SALARY(DEPT4_EMPS) 릴레이션의 이름과 애트리뷰트 이름의 변경 즉, 이름변경 연산 ρS(B1, B2, …, Bn)(R) 또는 ρS(R) 또는 ρ(B1, B2, …, Bn)(R) 2006-03-15 Fundamentals of Database Systems

Fundamentals of Database Systems 4. 집합연산 수학적 집합 이론에서의 이진 연산 (1) 합집합: R1∪R2 (2) 교집합: R1∩ R2 (3) 차집합: R1 - R2 (4) 카티션 곱: R1× R2 연산 ∪,∩,－에 대하여, 피연산자 릴레이션 R1(A1,A2,...,An)과 R2(B1,B2,...,Bn)는 애트리뷰트들의 갯수가 같고 대응되는 애트리뷰트들의 도메인이 호환성을 가져야 한다. 즉, i=1,2,...,n에 대하여 dom(Ai) = dom(Bi)이다. 이 조건을 합집합 호환성(union compatibility)이라 한다. 연산 ∪,∩,－의 결과 릴레이션은 피연산자 릴레이션 R1과 같은 애트리뷰트 이름들을 갖는다 (관례적으로). 카티션 프로덕트 (CARTESIAN PRODUCT) 크로스 프로덕트(cross product) 또는 크로스 조인(cross join) 라고도 함. R(A1,A2,...,Am,B1,B2,...,Bn) ← R1(A1,A2,...,Am)×R2 (B1,B2,...,Bn) R1의 투플 t1과 R2의 투플 t2의 모든 조합에 대하여 다음을 만족하는 투플 t가 R에 존재한다. 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) 2006-03-15 Fundamentals of Database Systems

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

Fundamentals of Database Systems 5. 조인(JOIN) 연산 세타 조인(THETAJOIN): SELECT가 따라오는 카티션 프로덕트. 조건 c를 조인 조건(join condition)이라 한다. R(A1,A2,...,Am,B1,B2,...,Bn) ← R1(A1,A2,...,Am) ▷◁c R2 (B1,B2,...,Bn) 동등 조인(EQUIJOIN): 조인 조건 c가 R1과 R2의 애트리뷰트들에 대한 하나 이상의 동등 비교(equality comparison)를 포함한다. 즉, c는 다음과 같은 형태이다: (Ai=Bj) AND ... AND (Ah=Bk); 1≤i, h≤m, 1≤j, k≤n EQUIJOIN 연산에서 Ai,...,Ah는 R1의 조인 애트리뷰트(join attributes)이고, Bh,...,Bk는 R2의 조인 애트리뷰트(join attributes)이다. 예: 모든 DEPARTMENT의 이름과 그 관리자의 이름을 검색하라: RESULT← ΠDNAME,FNAME,LNAME( DEPARTMENT ▷◁MGRSSN=SSN EMPLOYEE) R1 ▷◁c R2 의 결과 투플의 수 0 과 nR * nS 의 사이 조인 선택률(join selectivity) : 조인 결과의 예상 투플 수를 nR * nS 로 나눈 비율. 조인 조건이 없으면 : 카티션 프로덕트가 된다. n-원 (n-way)조인 예: 3-원 조인 ((PROJECT ▷◁DNUM=DNUMBER DEPARTMENT) ▷◁MGRSSN=SSN EMPLOYEE) 2006-03-15 Fundamentals of Database Systems

Fundamentals of Database Systems 자연 조인 (NATURAL JOIN) (*): EQUIJOIN R ← R1 ▷◁c R2에서는, R2의 조인 애트리뷰트들이 중복되어 결과 릴레이션 R에 나타난다. 자연 조인에서는 R2의 중복되는 조인 애트리뷰트들은 R에서 삭제된다. 동등 조건이 내재되어 있다. 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) 2006-03-15 Fundamentals of Database Systems

Fundamentals of Database Systems 주의: 자연 조인(NATURAL JOIN)의 본래의 정의에서는 조인 애트리뷰트들이 양쪽의 릴레이션에서 같은 이름을 가져야 한다. 같은 두 릴레이션 간에 하나 이상의 조인 애트리뷰트들의 집합이 존재하여 다른 의미를 가질 수 있다. 예를 들어: 예제: 모든 EMPLOYEE의 이름과 그가 일하는 DEPARTMENT의 이름을 검색하라: T ← EMPLOYEE ▷◁DNO=DNUMBER DEPARTMENT RESULT ← ΠFNAME,LNAME,DNAME(T) 2006-03-15 Fundamentals of Database Systems

Fundamentals of Database Systems 하나의 릴레이션은 자기 자신과 조인하기 위한 조인 애트리뷰트들의 집합을 가질 수 있다. 실제로 하나의 릴레이션만 존재하지만, 한 릴레이션의 서로 다른 두 사본을 조인하는 것으로 생각할 수 있다. 이 경우, 재명명(renaming)이 유용하다. 예제: 모든 EMPLOYEE의 이름과 그의 SUPERVISOR의 이름을 검색하라: SUPERVISOR(SSSN,SFN,SLN) ← ΠSSN,FNAME,LNAME(EMPLOYEE) T ← EMPLOYEE ▷◁SUPERSSN=SSSN SUPERVISOR RESULT ← ΠFNAME,LNAME,SFN,SLN(T) 2006-03-15 Fundamentals of Database Systems

Fundamentals of Database Systems 관계대수 연산의 완전집합 지금까지의 모든 연산자는 선택(SELECT), 프로젝트(PROJECT), 합집합(UNION), 차집합(SET DIFFERNECE), 카티션 프로덕트(CARTESIAN PRODUCT) 연산들 만의 조합으로 표현할 수 있다. R∩ S = (R∪S) – ((R – S) U (S – R)) R ▷◁c S = σc(R X S) 따라서, {σ,Π, ∪,－,×} 집합을 관계대수 연산자의 완전 집합(complete set)이라 부른다. 이 연산들과 동등한 모든 질의 언어들은 관계적으로 완전하다(relationally complete)라고 한다. 데이타베이스 응용에 있어서 본래 관계대수의 일부분이 아닌 다음의 추가적인 연산들이 필요하다. 1. 집단 함수(aggregate functions)와 그룹화(grouping) 2. 외부 조인(OUTER JOIN)과 외부 합집합(OUTER UNION) 2006-03-15 Fundamentals of Database Systems

Fundamentals of Database Systems division (÷) 연산 Let S  R. Consider two relations r(R) and s(R). r ÷ s = R-S (r) - R-S ((R-S (r) x s) - r) r ÷ s is a relation on scheme R - S. A tuple t is in r ÷ s if for every tuple ts in S, there is a tuple tr in r satisfying both of the following: tr[S] = ts[S] tr[R - S] = t [R - S] r(A,B,C,D) = {abcd, abef, abde, bcef, edcd, edef}, s = {cd, ef} r ÷ s = temp{A,B} = {ab, ed} 2006-03-15 Fundamentals of Database Systems

Fundamentals of Database Systems 집단함수 (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)라 한다. 2006-03-15 Fundamentals of Database Systems

... ... [그림 7.4] GROUP BY와 HAVING의 결과 (a) DNO 값으로 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 333445555 888665555 987654321 null DNO 5 4 1 DNO 5 4 1 COUNT(*) 4 3 1 AVG(SALARY) 33250 31000 55000 ... [그림 7.4] GROUP BY와 HAVING의 결과 (a) DNO 값으로 EMPLOYEE 투플들의 그룹화 2006-03-15 Fundamentals of Database Systems

Fundamentals of Database Systems 순환적 폐포(recursive closure) 연산 이행적 폐포 (transitive closure) 연산 2006-03-15 Fundamentals of Database Systems

Fundamentals of Database Systems 외부 조인과 외부 합집합 연산 외부 조인(OUTER JOIN) 연산 EQUIJOIN이나 자연 조인(NATURAL JOIN) 연산에서는, R1 또는 R2에서 대응되는 상대방 투플이 없는 투플들은 결과 릴레이션에 나타나지 않는다. R1(또는 R2 또는 둘 다)의 모든 투플들이 결과 릴레이션에 나타나기를 요구하는 경우 상대방 릴레이션에 대응되는 투플이 없으면 빈 애트리뷰트들에는 NULL 값이 들어간다. 왼쪽 외부 조인(LEFT OUTER JOIN): R1 R2는 R1의 모든 투플들이 결과 릴레이션에 나타나도록 한다. 오른쪽 외부 조인(RIGHT OUTER JOIN): R1 R2는 R2의 모든 투플들이 결과 릴레이션에 나타나도록 한다. 완전 외부 조인(FULL OUTER JOIN): R1 R2는 R1과 R2의 모든 투플들이 결과 릴레이션에 나타나도록 한다. 외부 합집합(OUTER UNION) 연산 합집합 호환성이 없는 두 릴레이션에 대한 합집합을 수행 2006-03-15 Fundamentals of Database Systems

Fundamentals of Database Systems 조인 알고리즘을 수정하여 구현 : 조인에 참여하지 못하는 투플의 해당 칼럼 값들을 NULL 값으로 채움. 외부 조인을 위하여 조인 알고리즘의 수정이 아닌 별개의 알고리즘을 개발할 수도 있으나 이의 효율성은 낮음. Outer join (1) left outer join, (2) right outer join, (3) full outer join SELECT lname, fname, dname FROM (employee LEFT OUTER JOIN department ON dno = dnumber); E.g., employee department result =========== =========== ============ <kim, a, 1> < 1, cs> <kim, a, cs> <park, b, 2> < 2, ce> <park, b, ce> <lee, c, NULL> <3, ee> <lee, c, NULL> Note: every tuple in the left must appear in the result. Algorithm extend the join algorithms. E.g., use the left relation as the outer loop or single-loop. If there are matching tuples in the other relation, the joined tuples are produced and saved in the result. However, if no matching tuple is found, the tuple is still included in the result but is padded with null value(s). The sort-merge and hash-join algorithms can also be extended to compute outer joins. 2006-03-15 Fundamentals of Database Systems

Fundamentals of Database Systems Union of tuples from two relations if the relations are not union compatible. Tuples from the component relations with the same key are represented only once in the result and have values for all attributes in the result. E.g., STUDENT FACULTY result (Name, SSN, Dept, Advisor) (Name, SSN, Dept, Rank) (Name, SSN, Dept, Advisor, Rank) ==================== ==================== ========================== <kim, 333, a, choi> < choi, 777, c, 1> <kim, 333, a, choi, NULL> <park, 444, b, lee> < hwang, 999, a, 2> <park, 444, b, lce, NULL> <lee, 555, c, NULL> <peter, 666, b, 3> <lee, 555, c, NULL, NULL> <choi, 777, c, NULL, 1> <hwang, 999, a, NULL, 2> <peter, 666, b, NULL, 3> Notice that OUTER UNION is equivalent to a FULL OUTER JOIN if the join attributes are all the common attributes of the two relations. 2006-03-15 Fundamentals of Database Systems

Fundamentals of Database Systems 관계 대수 질의의 예 ‘Research’ 부서에서 일하는 모든 사원의 이름과 주소를 검색하라. ‘Stafford’에 위치한 모든 프로젝트에 대하여 프로젝트 번호와 관리 부서 번호, 부서 관리자의 성, 주소, 생년 월일을 나열하라. 번호 2인 부서가 관리하는 모든 프로젝트에서 근무하는 사원들의 이름을 찾아라. 2006-03-15 Fundamentals of Database Systems

관계해석 (Relational Calculus) 경북대학교 전자 전기 컴퓨터 학부 박영철

Fundamentals of Database Systems 관계해석 제 1 차 프레디키트 해석(first-order predicate calculus)에 기반을 둔 형식적 언어 관계 대수와의 차이점: 관계 해석  SQL, OQL의 기반 선언적(비절차적) : 무엇(what)을 검색할 것인가를 기술 관계 대수 절차적(procedural) : 어떻게(how) 검색할 것인가를 기술 두 언어의 표현력(expressive power)은 동등함. 관계적 완전성(Relational Completeness): 어떤 관계 질의어 L이 관계 해석 또는 관계 대수로 표현 가능한 어떤 질의도 표현할 수 있으면 L은 관계적으로 완전(relationally complete)하다고 한다. 대부분의 관계 질의어들은 관계적으로 완전하다. 집단 함수(aggregate functions), 그룹화(grouping), 순서화(ordering) 등의 연산들을 사용하면 관계 해석보다 표현력이 강해진다. 투플 관계해석, 도메인 관계해석 2006-03-15 Fundamentals of Database Systems

Fundamentals of Database Systems 투플 관계 해석(Tuple Relational Calculus): 투플 변수와 범위 릴레이션 하나의 투플 변수(tuple variable)는 특정 릴레이션의 투플들을 범위(range)로 가진다. 예: 봉급이 $50,000를 넘는 모든 사원을 검색하라. {t | EMPLOYEE(t) and t.SALARY > 50000} EMPLOYEE(t)는 투플 변수 t가 릴레이션 EMPLOYEE를 범위로 함을 나타낸다. 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 2006-03-15 Fundamentals of Database Systems

Fundamentals of Database Systems 투플 관계해석의 형식적 명세 투플 관계해석식의 형태: {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)으로 계산된다. 그 값을 원자의 진리값(truth value)이라 부른다. 식(formula): and, or, not으로 연결된 원자들 모든 원자들은 식이다. F1과 F2가 식이면 (F1 and F2), (F1 or F2), not(F1), not(F2)도 식이다. 정량자(quantifiers): 전체 정량자(universal quantifier) (∀) (for all이라 읽음) 존재 정량자(existential quantifier) (∃) (their exists라 읽음) 자유 (free) 투플 변수와 속박 (bound) 투플 변수: 어떤 식 F가 원자인 경우, 여기에 나타나는 투플 변수는 F에서 자유롭다 식 (F1 and F2), (F1 or F2), not(F1), not(F2)에 나타난 투플 변수 t가 자유로운가 여부는 F1이나 F2에서 자유로운가에 달려있다 F 내의 투플 변수 t의 모든 자유 어커런스들은 F’ = (∃t)(F)나 F’ = (∀t)(F) 형태의 식에서 정량자에 속박된다. 2006-03-15 Fundamentals of Database Systems

Fundamentals of Database Systems 예제: 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)도 식이다. F 내의 t의 자유 어커런스들에 할달된 모든 투플들에 대해서 F가 참으로 계산되면 식 (∀t)(F)는 참이고, 그렇지 않으면 거짓이다. F가 참이 되게 하는 어떤 투플 t가 “존재”하면 (∃t)(F)가 참이므로, ∃를 존재 정량자라 부른다. “모든” 투플들이 F를 참이 되도록 해야 (∀t)(F)가 참이므로, ∀를 전체 정량자라 부른다. 2006-03-15 Fundamentals of Database Systems

Fundamentals of Database Systems 질의 1: ‘Research’ 부서에서 일하는 모든 사원의 이름과 주소를 검색하라. Q1: {t.FNAME, t.LNAME, t.ADDRESS | EMPLOYEE(t) and (∃d) (DEPARTMENT(d) and d.DNAME = ‘Research’ and d.DNUMBER = t.DNO)} 관계 해석 식에서 자유 투플 변수들만 막대 (|) 왼쪽에 나타낸다. EMPLOYEE(t), DEPARTMENT(d)는 t와 d의 범위 릴레이션을 명시한다. d.DNAME = ‘Research’는 선택 조건(selection condition)임 (관계 대수의 SELECT에 대응) d.DNUMBER = t.DNO는 조인 조건(join condition)임 (관계 대수의 EQUIJOIN과 유사한 목적으로 사용됨) select e.fname, e.lname, e.address from EMPLOYEE e, DEPARTMENT d where e.DNO = d.DNUMBER AND d.DNAME = ‘Research’; 2006-03-15 Fundamentals of Database Systems

Fundamentals of Database Systems 질의 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’: 부서 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))} 2006-03-15 Fundamentals of Database Systems

Fundamentals of Database Systems 질의 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’)))} 일반적으로, 관계 대수의 UNION이 관계 해석의 or 연결자에 대응된다. INTERSECTION은 and 연결자에 대응된다. not 연결자는 전체 정량자와 존재 정량자를 동등한 식으로 변환하는 데에 사용될 수 있다. 2006-03-15 Fundamentals of Database Systems

다음 식들이 성립한다 (⇒는 내포(implies)를 나타냄) (∀x) (P(x)) ⇒ (∃x) (P(x)) 수학적 논리로부터 유래된 잘 알려진 변환법 (∀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)) 2006-03-15 Fundamentals of Database Systems

Fundamentals of Database Systems 전체 정량자를 사용할 때에는 안전식(safe expression)이 되도록 주의해야 한다. 식이 의미를 갖도록 하기 위해 규칙을 따라야 한다. 그렇지 않으면, 불안전식(unsafe expressions)이 될 수 있다. 질의 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의 기본 구성요소들: 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) 2006-03-15 Fundamentals of Database Systems

Fundamentals of Database Systems 관심없는 모든 투플들에 대해서 조건이 참이 되도록 함으로써 그러한 투플들을 전체 정량자로부터 제외시켜야 한다. 전체 정량자로 속박된 변수 x는 모든 가능한 투플들에 대해서 참이 되어야 한다. F’에서, not(PROJECT(x))는 관심있는 릴레이션 “PROJECT”에 없는 모든 투플들에 대해 x를 참으로 만든다. F1에서, not(x.DNUM = 5)는 관심없는 PROJECT 투플들, 즉 “DNUM이 5가 아닌 투플들”에 대해 x를 참으로 만든다. F2는 나머지에 대해 만족되어야 할 조건, 즉 “5번 부서에 의해 관리되는 모든 PROJECT 투플들”을 명시한다. 관계 해석에서의 안전식들: 결과로서 유한개의 투플들을 생성하는 것이 보장된 식. 불안전식은 무한개의 투플들을 생성할 수 있고, 투플들의 타입이 서로 다를 수 있다. 예제: {t | not(EMPLOYEE(t))} 가능한 모든 투플들 중에서 EMPLOYEE가 아닌 모든 투플들을 생성한다. 전체 정량자를 사용할 때에는 Q3에 사용된 규칙을 따르면 안전식이 보장된다. 전체 정량자를 존재 정량자로 변환하는 규칙을 사용하면 Q3를 Q3’으로 재구성할 수 있다: 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))))} 2006-03-15 Fundamentals of Database Systems

Fundamentals of Database Systems 추가적인 예제들: 질의 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 = d.MGRSSN and p.ESSN = e.SSN))} 2006-03-15 Fundamentals of Database Systems

Fundamentals of Database Systems 도메인 관계해석(Domain Relational Calculus) 투플 변수 대신 도메인 변수(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의 각 애트리뷰트들을 위한 열 개의 도메인 변수들 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)} 2006-03-15 Fundamentals of Database Systems

Fundamentals of Database Systems 질의 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’)))} 질의 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)))))} 2006-03-15 Fundamentals of Database Systems

Fundamentals of Database Systems Homework-2 Homework-1의 테이블들에 대하여 아래 물음에 답하시오. 각 부서에 근무하는 직원들에 대하여 “이름” 칼럼의 값이 “성공” 보다는 크거나 같고 “차두리” 보다는 작거나 같으며 “생일”이 1980년 12월 31일 이후에 출생한 직원들의 “부서명”, “이름”, “주민등록번호”, 참여하는 hobby_club의 “클럽명”을 “부서명”, “이름”, 그리고 “클럽명”의 오름차순(nondecreasing order)으로 보고자 한다. 1. 이를 하나의 관계대수식(relational algebraic expression)으로 표현하시오. 단, 필요하다면 새로운 연산자를 가정하고 사용하여도 좋다. 2. 이를 하나의 투플 관계해석식(tuple relational claculus expression)으로 표현하시오. 단, 필요하다면 새로운 연산자를 가정하고 사용하여도 좋다. 3. 이를 하나의 도메인 관계해석식(domain relational claculus expression)으로 표현하시오. 단, 필요하다면 새로운 연산자를 가정하고 사용하여도 좋다. 2006-03-15 Fundamentals of Database Systems