설렉션 연산(Selection Operation)
설렉션 연산 기호는 σ p(r)
여기서 p는 명제 그리고 r은 당연히 릴레이션이다
ex) σ branch name = 'Perryridge'(account)
정의하자면 p는 명제계산식의 조건이고 ^(and) v(or) ㄱ(not) 로 연결된다
ex) <attribute> op [<attribute> or <constant>]
설렉션 연산의 실행(Evaluation of Selection Operation)
- File scan:
하나의 검색 알고리즘으로 설렉션을 이행하기 위해서 파일을 스캔하고 검색하기 위해 사용된다
-Index scan :
역시 하나의 알고리즘으로 인덱스를 사용해서 검색한다
설렉션 연산을 위한 알고리즘(File scan : linear search)
설렉션 상태(selection condition)를 만족했더라도 모든 파일 블록을 스캔하고 모든 레코드를 테스트한다
여기서 br은 릴레이션 r로 부터 레코드를 담고 있는 블록의 갯수다
Cost estimate = br block transfers + 1 seek
설렉션이 키속성인 경우는 기록 찾는 것을 멈출 수 있다
Cost estimate = (br/2) block transfers + 1 seek
리니어 스캔은 항상 다음과 같은 환경에 영향을 받는다
- 설렉션 컨디션(Selection condition)
- 파일안에 레코드의 순서
- 인덱스의 가용도(Availability)
설렉션 연산을 위한 알고리즘(File scan : binary search)
선택된 파일이 정렬된 속성에 대해서 동일 비교인 경우에만 해당된다
Cost estimate : 블록에 대해서 이진검색을 통해 첫번째 튜플을 찾는 비용
만약 만족하는 레코드 값이 여러개 일때
해당 설렉션 상황을 만족하는 레코드 안에 포함된 블록을 갯수의 전송 비용만큼 추가한다
인덱스를 사용한 설렉션(Primary index on candidate key, equality)
해당 동일 조건을 만족하는 단일 레코드 검색 비용
Cost = (hi +1)*(tT +tS)
hi 는 인덱스의 높이
B+트리인덱스의 높이는
여기서 n은 노드당 포인터의 갯수고, K는 서치키(Search key)의 개수이다
만약 1,000,000개의 서치키와 100개의 인덱스 엔트리가 노드마다 있다면 포인터는 101개이고,
n은 51이 되고, K는 1,000,000이된다. 그래서 결론적으로 hi는 4가 된다
인덱스를 사용한 설렉션(Primary index on nonkey, equality)
여러 레코드를 검색할때,
레코드는 연속적 블록일 것이다
Let b = 일치하는 레코드에 포함하는 블록의 수
Cost = hi * (tT + tS) + tS + tT * b
인덱스를 사용한 설렉션(Equality on key and non-key of secondary index)
서치키가 후보키일때, 단일레코드 검색 :
- Cost = (hi + 1) * (tT + tS)
서치키가 후보키가 아니고, 여러 레코드를 검색 :
- Cost = (hi + n) * (tT + tS)
(n개의 매칭되는 각각의 레코드는 다른 블록에 있을 수 있다)
Comparative Selections(σ A<=V(r) or σ A>= V(r))
위와 같이 리니어 파일 스캔 혹은 바이너리 서치를 사용한다
Using primary index,
σ A>= V(r)에 대해서, 인덱스를 사용해 v보다 크거나 같은 첫번째 튜플을 찾고 거기서부터 순차적으로 릴레이션을 스캔한다
σ A<=V(r) 에 대해서, 첫번째 튜플이 v보다 클때 까지 릴레이션을 순차적으로 스캔해서 한다
Using secondary index,
σ A>= V(r)에 대해서, 인덱스를 사용해 v보다 크거나 같은 첫번째 인덱스 엔트리을 찾고 거기서부터 순차적으로 릴레이션을 스캔한다
σ A<=V(r) 에 대해서, 첫 번째 항목 > v까지 레코드에 대한 포인터를 찾기 위해 인덱스의 리프 페이지를 스캔합니다