관계 대수 Chapter 4, Part A The slides for this text are organized into chapters. This lecture covers relational algebra from Chapter 4. The relational calculus.

Presentation on theme: "관계 대수 Chapter 4, Part A The slides for this text are organized into chapters. This lecture covers relational algebra from Chapter 4. The relational calculus."— Presentation transcript:

1 관계 대수 Chapter 4, Part A The slides for this text are organized into chapters. This lecture covers relational algebra from Chapter 4. The relational calculus part can be found in Chapter 4, Part B. Chapter 1: Introduction to Database Systems Chapter 2: The Entity-Relationship Model Chapter 3: The Relational Model Chapter 4 (Part A): Relational Algebra Chapter 4 (Part B): Relational Calculus Chapter 5: SQL: Queries, Programming, Triggers Chapter 6: Query-by-Example (QBE) Chapter 7: Storing Data: Disks and Files Chapter 8: File Organizations and Indexing Chapter 9: Tree-Structured Indexing Chapter 10: Hash-Based Indexing Chapter 11: External Sorting Chapter 12 (Part A): Evaluation of Relational Operators Chapter 12 (Part B): Evaluation of Relational Operators: Other Techniques Chapter 13: Introduction to Query Optimization Chapter 14: A Typical Relational Optimizer Chapter 15: Schema Refinement and Normal Forms Chapter 16 (Part A): Physical Database Design Chapter 16 (Part B): Database Tuning Chapter 17: Security Chapter 18: Transaction Management Overview Chapter 19: Concurrency Control Chapter 20: Crash Recovery Chapter 21: Parallel and Distributed Databases Chapter 22: Internet Databases Chapter 23: Decision Support Chapter 24: Data Mining Chapter 25: Object-Database Systems Chapter 26: Spatial Data Management Chapter 27: Deductive Databases Chapter 28: Additional Topics 1

2 관계 질의어 질의어: DB내의 데이타를 조작 및 검색 관계 모델은 단순하면서도 막강한 질의어들을 제공:
논리학에 기반한 강력한 정형화 다양한 최적화 가능 질의어 != 프로그래밍 언어 질의어는 “튜어링식 완전성”을 고려하지 않음. 질의어는 복잡한 계산용이 아님. 질의어는 대규모 데이타 집단에 대한 쉽고 효율적인 접근 제공. 2

3 정형 관계 질의어 “실제의” 언어(SQL등)와, 구현 방법의 기반이 되는 수학적인 질의어 형태 2가지:
관계 대수(Relational Algebra): 더 절차적. 수행 계획 표현에 적절. 관계 해석(Relational Calculus): 원하는 것(what)만 명세하고, 그 방법(how)은 생략. 비절차적, 명세형. 대수와 해석의 이해가 곧 SQL과 질의 수행법 이해의 관건!

4 시작하기 전에 질의는 하나 이상의 릴레이션 인스턴스에 적용되어, 하나의 릴레이션 인스턴스를 낸다. 위치나 이름으로 표기:
입력 릴레이션의 스키마는 고정(인스턴스는 임의). 결과 릴레이션의 스키마도 고정! 질의상의 정의에 따라 결정됨. 위치나 이름으로 표기: 위치 표기법은 정형화가 쉽고, 이름 표기법은 이해하기 쉽다. SQL은 두 방식 모두 사용. 4

5 예제 인스턴스 R1 앞으로 사용할 “뱃사람”과 “에약”의 인스턴스. S1
위치 표기법과 이름 표기법을 병용할 것이며, 질의 결과의 필드명은 입력 테이블을 본딴다고 가정. S1 S2 5

6 관계 대수 기본 연산자: 기타 연산자: 연산의 결과가 다시 릴레이션이므로, 연산의 조합이 가능! (대수의 “닫힌” 성질)
셀렉션(Selection) ( ) 릴레이션에서 투플들을 선별. 프로젝션(Projection) ( ) 필요없는 필드들을 제거. 카티션 프로덕트(Cartesian Product) ( ) 두 릴레이션을 조합. 차집합(Set-difference) ( ) 릴1에는 있고 릴2에는 없는 투플. 합집합(Union) ( ) 릴1과 릴2에 있는 투플들을 모두 모음. 기타 연산자: 교집합(intersection), 죠인(join), 디비전(division), 개명(renaming): 필수는 아니지만 유용함. 연산의 결과가 다시 릴레이션이므로, 연산의 조합이 가능! (대수의 “닫힌” 성질) 6

7 프로젝션 p p ) 2 ( , S ) 2 ( S 프로젝션 리스트에 없는 필드들을 삭제.
결과 테이블의 스키마는 프로젝션 리스트의 필드들로만 구성되며, 그 이름은 입력 테이블로부터 따온다. 프로젝션 연산자는 중복 투플을 없애야 한다!(왜??) Note: 실제 시스템들은, 사용자가 명시하지 않는 한, 중복을 제거하지 않음(왜?) ) 2 ( , S 등급 뱃사람이름 p ) 2 ( S 나이 p 7

8 셀렉션 s s p ) 2 ( 8 S > )) 2 ( S 8 , > 셀렉션 조건에 부합되는 투플들만 선별.
결과에는 중복이 없다!(왜?) 결과의 스키마는 입력 테이블과 동일함. 결과 릴레이션도 다른 관계 대수 연산자의입력 이 될 수 있다!(연산자 조합) ) 2 ( 8 S 등급 > s )) 2 ( S 8 , 등급 뱃사람이름 > s p 8

9 합집합, 교집합, 차집합 모두 입력 테이블은 2개이며, 합병가능(union-compatible) 이어야함. 필드의 수가 같고,
대응 필드의 타입이 같다. 결과의 스키마는? 9

10 카티션 프로덕트 : S1  R1    1 ), 2 5 , ( R S C r )
뱃사람번호 C r 개명 연산자: ) 10

11 죠인 1 R S R c S =  s ( ) < . 조건 죠인: 결과 스키마 는 카티션 프로덕트와 동일.
카티션 프로덕트보다 결과의 양이 적으므로, 더 효율적인 계산이 가능. 세타죠인(theta-join) 이라고도 함. R c S   =  s ( ) 1 . R S 뱃사람번호 <   11

12 죠인(계속) 1 R S 1 동등죠인(Equi-Join): 조건 죠인 중에서 조건이 ‘=’인 경우.
결과 스키마는 카티션 프로덕트와 비슷하지만, 비교 필드는 한번씩만 나온다. 자연 죠인(Natural Join): 모든 공통 필드에 대한 동등 죠인. 1 R S 뱃사람번호   1 12

13 디비젼 기본 연산자는 아니지만, 다음과 같은 경우에 효율적: 모든 배를 예약한 뱃사람들을 구하라.
기본 연산자는 아니지만, 다음과 같은 경우에 효율적: 모든 배를 예약한 뱃사람들을 구하라. A는 x와 y, B는 y로 구성된다면: A/B = 즉, A/B는 B의 모든 y 투플(배)에 대하여, xy 투플이 A내에 존재하는, 그러한 x투플(뱃사람)들의 모임. 또는: A에서 한 x값(뱃사람)에 대응하고 있는 y값(배)집합이 B의 모든 y값으로 구성되면, 그 x는 A/B에 포함. 여기에서 x와 y는 어떤 필드(집합)이 되어도 무관함. y는 B의 필드집합이며, xy 는 A의 필드집합이다. 13

14 디비젼 A/B의 예 B1 B2 B3 A/B1 A/B2 A/B3 A 14

15 A/B를 기본 연산자들로 분해하면 디비전은 필수 연산자가 아님. 표기에 편리할 뿐.
(죠인도 마찬가지이지만, 대부분 별도로 구현하고 있음.) 착상: 먼저, B의 y중에 부합되지 않는 것이 나타나는 x값들을 구한다. B의 y들과 조합한 xy중에 A에 나타나지 않는 쌍이 발견되면, 그 x는 ‘부합되지 않는’ 것이다. 부합되지 않는 x : A/B: 부합되지 않는 투플 15

16 배번호 103을 예약한 뱃사람의 이름을 구하라 ) ( s p ) , 1 ( Temp s r ) 1 , 2 ( Temp r )
뱃사람이름   = s p 방법 1: ) , 1 ( 103 예약 배번호 Temp = s r 방법 2 : ) 1 , 2 ( 뱃사람 Temp   r ) 2 ( Temp 뱃사람이름 p )) ( 103 뱃사람 예약 배번호 뱃사람이름   = s p 방법 3 : 16

17 적색 배를 예약한 뱃사람의 이름을 구하라. ) (( ‘red’ = s p
배의 색상정보는 배 테이블에 있으므로, 죠인이 추가적으로 필요함: ) (( 뱃사람 예약 배 ‘red’ 색상 뱃사람이름   = s p 더 효율적인 방법: ) (( ( 뱃사람 예약 배 ‘red’ 색상 배번호 뱃사람번호 뱃사람이름   = s p 윗 형태가 입력되면 최적화기가 두번째 형태를 구할 수 있다! 17

18 적색 또는 녹색 배를 예약한 뱃사람의 이름을 구하라.
적색 배나 녹색 배를 모두 구한 후, 이중에 한 척을 예약한 사람들을 구한다. )) ( , 배 ‘green’ 색상 ‘red’ Tempboats = s r  ) ( 뱃사람 예약 Tempboats 뱃사람이름   p 합집합 연산으로 Tempboats를 구할 수도있다!(어떻게?) 를 로 바꾸면? 18

19 적색 배와 녹색 배를 예약한 뱃사람들을 구하라. )) ) ( , ‘red’ Temped = s p r )) ) ( ,
앞의 방식으로는 안됨! 적색 배를 예약한 뱃사람들을 구하고, 녹색 배를 예약한 뱃사람들을 구한 후, 교집합한다. (뱃사람의 키는 뱃사람번호임을 이용): )) ) ( , 예약 배 ‘red’ 색상 뱃사람번호 Temped   = s p r )) ) ( , 예약 배 ‘green’ 색상 뱃사람번호 Tempgreen   = s p r ) (( 뱃사람 Tempgreen Tempred 뱃사람이름    p 19

20 모든 배를 예약한 뱃사람의 이름을 구하라. )) ( / ) , Tempsids p r ) ( Tempsids p ) ( /
디비전을 이용한다. 그러러면 입력 릴레이션의 스키마를 잘 만들어야 한다. )) ( / ) , 배 배번호 예약 뱃사람번호 Tempsids p r ) ( 뱃사람 Tempsids 뱃사람이름   p ‘Interlake’라는 배를 모두 예약한 사람을 구하려면? ) ( / 배 Interlake 배이름 배번호 = s p ..... 20

21 요약 관계 모델에서는 질의어가 단순하면서도 막강함, 그 정의는 엄밀하다.
관계 대수는 더 절차적이며, 질의 수행 전략 표현에 적절 같은 질의를 여러가지로 표현 가능. 그 중에서 가장 효율적인 형태를 최적화기가 찾는다.