관계 연산 알고리즘 및 비용

마지막 -> htps : // m / s0t00524 / ms / a 4f57f7568f2784464 a0
이 기사는 대학의 기말 시험 공부를 위해 작성한 것입니다. 실수 등은 나쁘지 않습니다.

관계 데이터베이스 연산 유형

입력 연산

선택(Selection)

투영 ([Delta] Projection)

집계(Aggregation)

정렬(Order-By)

중복 제거(Duplication Elimination)

그룹화(Group-By)

조인

준결합(Semi-Join)

집합적(Intersection)

집합 차이(Difference)

집합합(Union)

직적(Cartesian Product)

상(Division)

계산 비용 견적

비교 횟수(CPU 비용)와 디스크 I/O에 의해 추정한다. 또한, 이하의 논의에서는 관계 대수 R의 사이즈를 이하에서 정의한다.

R 튜플 수: $\{R\}$

R 디스크 페이지 수: $|R|$

각 선택 연산과 비용 견적

GRACE 해시 조인 및 그 비용

분산 및 결합 단계의 각 단계에서 독립적인 해시 함수를 사용합니다. 합계로 2개 사용한다.

해시 적용 횟수: $2(\{R\} +\{S\})$

각 단계에서 $\{R\} +\{S\}$

비교 횟수: $\sum\{S_i\} = (\{S\}/n)\times n =\{S\}$

디스크 I/O 횟수: $3(|R|+|S|)$

하이브리드 해시 조인

비교 횟수와 해시 적용 횟수: GRACE와 동일

디스크 I/O 횟수:$3(|R|+|S|) - 2(|R|+|S|)/L = (3 - 2|M|/|R|)\times (|R |+|S|)$

메모리 부족의 경우의 3종류의 해시 결합의 비용을 이하에 정리한다.



<참고>
h tp // w w. 오 cw. 치테 ch. 아 c. jp / 그럼 x. php? 모즈이 = 게네라 l & 아 치온 = T0300 & 가부 CD = 4 & 가카 CD = 342300 & 케이 CD = & 코기 CD = 201902434 & 넨도 = 2019 & ぁg = 그럼 & ぃ d = 05

나누기

나눗셈($R_a[X]\div R_b[Y]$)에 대한 알고리즘을 생각한다.

직접법

정렬을 이용하는 경우

$R_a$의 $X$를 마이너, $X_c$를 메이저로 소트하고, $R_b$도 $X$로 소트한다. 이때 $X_c$가 바뀔 때마다 $X$를 붙여 끝까지 일치하면 몫에 추가.



해시를 이용한 경우

$R_b$에 대응한 해시 테이블 $H_1$과 상 후보의 해시 테이블 $H_2$에 $R_b$에 대응한 비트를 준비한다. 즉, $R_a$를 해시하고 $H_1$의 엔트리를 조사해, $H_2$의 bit를 세운다.

간접법

집계 연산을 사용한다. 즉, $R_a$를 Group-By하고 $R_b$와 같은 Count인지 조사한다. 미리 R_a를 R_b로 Semi-Join 해 두는 것이 필요.

준결합(Semi-Join)

준 결합은 관계 R과 S의 자연 결합 결과로부터 S에만 존재하는 속성을 투영 연산으로 제거하는 연산이다.

<참고>
htps //w w. s에서 멋지다. 네 t/쇼헤이요코야마아 c/04-27443570

등결합의 결과는 한 관계 만. 이 때 기본 비용은 등 결합과 동일하며, 집합 연산이나 분산 데이터베이스 등으로 전송 데이터를 좁힐 때 사용된다.

집합적

모든 속성에 대한 등결합 또는 준결합

집합합

두 관계의 결합 후 중복 제거. 또는 한 관계와 집합 차이의 결합으로 표시됩니다.

집합 차이

모든 속성에 대해 준결합 결과의 보집합 튜플을 선택한다(Anti-Semi-Join). 비용은 등 결합과 동일합니다.