관계 대수 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
관계 질의어 질의어: DB내의 데이타를 조작 및 검색 관계 모델은 단순하면서도 막강한 질의어들을 제공: 논리학에 기반한 강력한 정형화 다양한 최적화 가능 질의어 != 프로그래밍 언어 질의어는 “튜어링식 완전성”을 고려하지 않음. 질의어는 복잡한 계산용이 아님. 질의어는 대규모 데이타 집단에 대한 쉽고 효율적인 접근 제공. 2
정형 관계 질의어 “실제의” 언어(SQL등)와, 구현 방법의 기반이 되는 수학적인 질의어 형태 2가지: 관계 대수(Relational Algebra): 더 절차적. 수행 계획 표현에 적절. 관계 해석(Relational Calculus): 원하는 것(what)만 명세하고, 그 방법(how)은 생략. 비절차적, 명세형. 대수와 해석의 이해가 곧 SQL과 질의 수행법 이해의 관건!
시작하기 전에 질의는 하나 이상의 릴레이션 인스턴스에 적용되어, 하나의 릴레이션 인스턴스를 낸다. 위치나 이름으로 표기: 입력 릴레이션의 스키마는 고정(인스턴스는 임의). 결과 릴레이션의 스키마도 고정! 질의상의 정의에 따라 결정됨. 위치나 이름으로 표기: 위치 표기법은 정형화가 쉽고, 이름 표기법은 이해하기 쉽다. SQL은 두 방식 모두 사용. 4
예제 인스턴스 R1 앞으로 사용할 “뱃사람”과 “에약”의 인스턴스. S1 위치 표기법과 이름 표기법을 병용할 것이며, 질의 결과의 필드명은 입력 테이블을 본딴다고 가정. S1 S2 5
관계 대수 기본 연산자: 기타 연산자: 연산의 결과가 다시 릴레이션이므로, 연산의 조합이 가능! (대수의 “닫힌” 성질) 셀렉션(Selection) ( ) 릴레이션에서 투플들을 선별. 프로젝션(Projection) ( ) 필요없는 필드들을 제거. 카티션 프로덕트(Cartesian Product) ( ) 두 릴레이션을 조합. 차집합(Set-difference) ( ) 릴1에는 있고 릴2에는 없는 투플. 합집합(Union) ( ) 릴1과 릴2에 있는 투플들을 모두 모음. 기타 연산자: 교집합(intersection), 죠인(join), 디비전(division), 개명(renaming): 필수는 아니지만 유용함. 연산의 결과가 다시 릴레이션이므로, 연산의 조합이 가능! (대수의 “닫힌” 성질) 6
프로젝션 p p ) 2 ( , S ) 2 ( S 프로젝션 리스트에 없는 필드들을 삭제. 결과 테이블의 스키마는 프로젝션 리스트의 필드들로만 구성되며, 그 이름은 입력 테이블로부터 따온다. 프로젝션 연산자는 중복 투플을 없애야 한다!(왜??) Note: 실제 시스템들은, 사용자가 명시하지 않는 한, 중복을 제거하지 않음(왜?) ) 2 ( , S 등급 뱃사람이름 p ) 2 ( S 나이 p 7
셀렉션 s s p ) 2 ( 8 S > )) 2 ( S 8 , > 셀렉션 조건에 부합되는 투플들만 선별. 결과에는 중복이 없다!(왜?) 결과의 스키마는 입력 테이블과 동일함. 결과 릴레이션도 다른 관계 대수 연산자의입력 이 될 수 있다!(연산자 조합) ) 2 ( 8 S 등급 > s )) 2 ( S 8 , 등급 뱃사람이름 > s p 8
합집합, 교집합, 차집합 모두 입력 테이블은 2개이며, 합병가능(union-compatible) 이어야함. 필드의 수가 같고, 대응 필드의 타입이 같다. 결과의 스키마는? 9
카티션 프로덕트 : S1 R1 1 ), 2 5 , ( R S C r ) 뱃사람번호 C r 개명 연산자: ) 10
죠인 1 R S R c S = s ( ) < . 조건 죠인: 결과 스키마 는 카티션 프로덕트와 동일. 카티션 프로덕트보다 결과의 양이 적으므로, 더 효율적인 계산이 가능. 세타죠인(theta-join) 이라고도 함. R c S = s ( ) 1 . R S 뱃사람번호 < 11
죠인(계속) 1 R S 1 동등죠인(Equi-Join): 조건 죠인 중에서 조건이 ‘=’인 경우. 결과 스키마는 카티션 프로덕트와 비슷하지만, 비교 필드는 한번씩만 나온다. 자연 죠인(Natural Join): 모든 공통 필드에 대한 동등 죠인. 1 R S 뱃사람번호 1 12
디비젼 기본 연산자는 아니지만, 다음과 같은 경우에 효율적: 모든 배를 예약한 뱃사람들을 구하라. 기본 연산자는 아니지만, 다음과 같은 경우에 효율적: 모든 배를 예약한 뱃사람들을 구하라. 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의 필드집합이며, xy 는 A의 필드집합이다. 13
디비젼 A/B의 예 B1 B2 B3 A/B1 A/B2 A/B3 A 14
A/B를 기본 연산자들로 분해하면 디비전은 필수 연산자가 아님. 표기에 편리할 뿐. (죠인도 마찬가지이지만, 대부분 별도로 구현하고 있음.) 착상: 먼저, B의 y중에 부합되지 않는 것이 나타나는 x값들을 구한다. B의 y들과 조합한 xy중에 A에 나타나지 않는 쌍이 발견되면, 그 x는 ‘부합되지 않는’ 것이다. 부합되지 않는 x : A/B: 부합되지 않는 투플 15
배번호 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
적색 배를 예약한 뱃사람의 이름을 구하라. ) (( ‘red’ = s p 배의 색상정보는 배 테이블에 있으므로, 죠인이 추가적으로 필요함: ) (( 뱃사람 예약 배 ‘red’ 색상 뱃사람이름 = s p 더 효율적인 방법: ) (( ( 뱃사람 예약 배 ‘red’ 색상 배번호 뱃사람번호 뱃사람이름 = s p 윗 형태가 입력되면 최적화기가 두번째 형태를 구할 수 있다! 17
적색 또는 녹색 배를 예약한 뱃사람의 이름을 구하라. 적색 배나 녹색 배를 모두 구한 후, 이중에 한 척을 예약한 사람들을 구한다. )) ( , 배 ‘green’ 색상 ‘red’ Tempboats = s r ) ( 뱃사람 예약 Tempboats 뱃사람이름 p 합집합 연산으로 Tempboats를 구할 수도있다!(어떻게?) 를 로 바꾸면? 18
적색 배와 녹색 배를 예약한 뱃사람들을 구하라. )) ) ( , ‘red’ Temped = s p r )) ) ( , 앞의 방식으로는 안됨! 적색 배를 예약한 뱃사람들을 구하고, 녹색 배를 예약한 뱃사람들을 구한 후, 교집합한다. (뱃사람의 키는 뱃사람번호임을 이용): )) ) ( , 예약 배 ‘red’ 색상 뱃사람번호 Temped = s p r )) ) ( , 예약 배 ‘green’ 색상 뱃사람번호 Tempgreen = s p r ) (( 뱃사람 Tempgreen Tempred 뱃사람이름 p 19
모든 배를 예약한 뱃사람의 이름을 구하라. )) ( / ) , Tempsids p r ) ( Tempsids p ) ( / 디비전을 이용한다. 그러러면 입력 릴레이션의 스키마를 잘 만들어야 한다. )) ( / ) , 배 배번호 예약 뱃사람번호 Tempsids p r ) ( 뱃사람 Tempsids 뱃사람이름 p ‘Interlake’라는 배를 모두 예약한 사람을 구하려면? ) ( / 배 Interlake 배이름 배번호 = s p ..... 20
요약 관계 모델에서는 질의어가 단순하면서도 막강함, 그 정의는 엄밀하다. 관계 대수는 더 절차적이며, 질의 수행 전략 표현에 적절 같은 질의를 여러가지로 표현 가능. 그 중에서 가장 효율적인 형태를 최적화기가 찾는다.