- 본 논문에서는 211개 대신 일부의 변경 큐보이드만을사용하면서도 변경 반영 단계의 비용을 증가시키지 않고 전체 큐브 뷰를 갱신하는 방법을 제안한다.

[2]는 cubetree라 불리는, 큐브 뷰를 효율적으로 관리할 수 있도록 해주는 큐브의 저장 구조를 제안하였다. ⑶은 큐브 뷰의 정의에 포함된 차원 애 트리 뷰트가 변경된 경우에 대한 점진적 관리 기법을 제안하였다. [4]는 IBM DB2 UDB에서 집단화 뷰의 점진적 관리를 위해 실제로 구현된 관리 방법을 설명하였다.

본 장에서는 제안하는 방법과 2“개의 변경큐보이드를 모두 다 사용하여 큐브를 갱신하는 기존의 방법을 비교한다. 각 방법의 성능은 해당 방법을 사용하여 큐브 뷰를 갱신하는데 걸리는 시간으로 측정하였다. 실험 환경으로는 750MHz UltraSPARC III CPU와 512MB의 메모리가 장착된 Sun Blade 1000 워크스테이션에 설치된 Oracle9i이 사용되었다.

더욱이, 주어진 변경 큐브에 대해 가능한 갱신 파티션의 개수는 변경 큐보이드의 수에 대해 지수적으로 증가한다. 따라서 본 논문에서는 OCMP에 대한 최적 해를 찾는 알고리즘 대신 휴리스틱 알고리즘을 제안한다.

그림 1(b)는본 논문에서 제안하는 방법을 나타낸다, 본 논문에서 제안하는 방법은 하나의 변경 큐보이드로 여러 개의 큐보이드를 갱신한다. 본 논문에서 제안하는 방법은 계산해야 하는 변경 큐보이드의 수를 줄임으로써 변경 계산단계의 비용을 줄인다. 그러면서도 각 큐보이드를 갱신하는 변경 반영 단계의 비용은 증가시키지 않는다, 본 논문의 공헌은 다음과 같다.

본 논문에서는 2“개의 변경 큐보이드를 모두 사용하지 않고 일부의 변경 큐보이드만을 사용하여 전체 큐브 뷰를 갱신하는 방법을 제안한다. 그림 1(b)는본 논문에서 제안하는 방법을 나타낸다, 본 논문에서 제안하는 방법은 하나의 변경 큐보이드로 여러 개의 큐보이드를 갱신한다. 본 논문에서 제안하는 방법은 계산해야 하는 변경 큐보이드의 수를 줄임으로써 변경 계산단계의 비용을 줄인다.

따라서 변경 큐보이드 계산 계획의 비용을 줄이기 위해서는 갱신 체인의 수를 최소화하는 것이 바람직하다. 본 논문에서 제안하는 휴리스틱은 최소한의 갱신 체인만을 포함하는 갱신파티션을 찾는다.

또한, 제안하는 휴리스틱은 2"개의 변경 큐보이드를 사용하는 기존 방법보다 항상 적은 비용을 가지고 있음을 보장한다. 본 논문에서는 제안하는 방법을 구현하고, 실험을 통해 기존 방법과 성능을 비교하였다. 실험 결과를 통해 제안하는 방법은 기존의 방법보다 좋은 성능을 보이고 있음을 알 수 있었다.

본 실험에서는 TPC H 스키마의 lineitem 테이블에 대해 큐브 뷰를 정의하였다. lineitem 테이블은 TPC-H 스키마에서 사실 테이블(fact table)의 역할을 하는 테이블이다.

보인다. 본 장에서는 제안하는 방법과 2“개의 변경큐보이드를 모두 다 사용하여 큐브를 갱신하는 기존의 방법을 비교한다. 각 방법의 성능은 해당 방법을 사용하여 큐브 뷰를 갱신하는데 걸리는 시간으로 측정하였다.

실험에서는 lineitem 테이블에 대한 변경의 크기를 원 테이블의 크기에 대해 2%에서 20%까지 변화시키면서 각 방법의 성능을 측정하였다. lineitem 테이블에 대한 변경은 lineitem 테이블에 새로운 튜플들을 삽입함으로써 이루어졌다.

변경 격자 그래프에서 차원 애트리뷰트의 수가 i개인 변경 큐보이드들의집합을 Leve丄 (i) 로 표시하자. 제안하는 방법은 Leve丄 (0)부터 시작하여 Level (n - 丄)으로 진행하면서 丁의 단말 노드들을 단계적으로 제거해 나간다. 각 Leve丄 (i) 에 대해, 제안하는 방법은 L으vdL(i) 에 포함된 丁의 단말 노드와 Level (i + 1)의 변경 큐보이드들간의 최대 비용 이분할 부합 (maximum weight bipartite matching)2)[21]을 찾는다.

있다. 제안하는 방법은 Mbc의 매 튜플마다 ab 에 접근하는 대신, 의 현재 튜플이 속한 그룹이 바뀌는 경우에만 ab에 접근한다. 예를 들어, 그림 5에서는 △abc의 튜플 (1, 1, 1, 3)에 대해서는 ab의 튜플 (1, 1, 9)를 갱신하지 않는다.

변경 격자 그래프 G가 주어졌다고 하자. 제안하는 방법은 먼저 G의 MST 丁를 구한다. 변경 격자 그래프에서 차원 애트리뷰트의 수가 i개인 변경 큐보이드들의집합을 Leve丄 (i) 로 표시하자.

이에 따라 제안하는 방법은 2"개의 변경 큐보이드 대신 nC「n/2] 개의 변경 큐보이드만 계산하면 된다는 것을 보장한다. 제안하는 방법은 변경 큐브의 각 변경 큐보이드들이각각 하나의 갱신 체인을 형성하는, 尸개의 갱신 체인으로 이루어진 갱신 파티션으로부터 출발한다. 이 갱신 파티션은 211개의 변경 큐보이드를 모두 사용하는 기존의 방법을 나타냄을 상기하라.

이 갱신 파티션에 대한 최소비용의 변경 큐보이드 계산 계획은 변경 격자 그래프 전체에 대한 최소 비용 신장 트리 (minimum spanning tree, MST)가 된다. 제안하는 방법은 이 MST가 나타내는 변경 큐보이드 계산 계획으로부터 시작하여 변경큐보이드 계산 계획의 단말 노드들을 단계적으로 제거해 나간다. 단말 노드가 제거되었다는 것은 단말 노드가 포함된 갱신 체인이 다른 갱신 체인과 합병되었다는 것을 의미한다.

증명. 본 증명에서는 HeuristicCubeMaintenancePlan 으로 찾아진 갱신 파티션에서 임의의 변경 큐보이드 는 반드시 어떤 변경 큐보이드 e Level ( fn/2 ] ) 와 같은 갱신 체인에 포함됨을 보인다 Level ( [n/2 [ ) 에 포함되어 있는 변경 큐보이드의 개수는 nC[n/2] 개이고 이들은 같은 갱신 체인에 포함될 수 없으므로, 이들을 포함하고 있는 갱신 체인의 개수는 정확히 nCfn/2] 개이다. 따라서 위 가설이 증명되면 이것은 Heuristic- CubeMaintenancePlan-^S.

각 방법의 성능은 해당 방법을 사용하여 큐브 뷰를 갱신하는데 걸리는 시간으로 측정하였다. 실험 환경으로는 750MHz UltraSPARC III CPU와 512MB의 메모리가 장착된 Sun Blade 1000 워크스테이션에 설치된 Oracle9i이 사용되었다. 실험에 사용된 테이블들의 스키마와 데이타는 TPC-H 벤치마크의 스키마와 데이타[22]를 사용하였으며, 큐브의 점진적 관리 방법들은 Ora이e9i의 PL/SQL을 기반으로 구현되었다.

실험 환경으로는 750MHz UltraSPARC III CPU와 512MB의 메모리가 장착된 Sun Blade 1000 워크스테이션에 설치된 Oracle9i이 사용되었다. 실험에 사용된 테이블들의 스키마와 데이타는 TPC-H 벤치마크의 스키마와 데이타[22]를 사용하였으며, 큐브의 점진적 관리 방법들은 Ora이e9i의 PL/SQL을 기반으로 구현되었다.

예제 1은 갱신 체인이 3개와 4개인 갱신 파티션의예를 보여준다. 갱신 체인의 수는 계산해야 하는 커버변경 큐보이드의 수를 의미한다.

lineitem 테이블은 TPC-H 스키마에서 사실 테이블(fact table)의 역할을 하는 테이블이다. 큐브 뷰의 차원 애트리뷰트들로는 lineitem 테이블의 l_orderkey, l_partkey, l_suppkey, l_shipdate, l_receiptdate 애 트리 뷰트들이 사용되었으며, 측정 애트리뷰트로는 l_quan- tity 애트리뷰트가 사용되었다. 실험에서는 표 1과 같은 큐브 뷰 Cl, C₂, C₃를 정의하였다.

제안하는 방법은 Leve丄 (0)부터 시작하여 Level (n - 丄)으로 진행하면서 丁의 단말 노드들을 단계적으로 제거해 나간다. 각 Leve丄 (i) 에 대해, 제안하는 방법은 L으vdL(i) 에 포함된 丁의 단말 노드와 Level (i + 1)의 변경 큐보이드들간의 최대 비용 이분할 부합 (maximum weight bipartite matching)2)[21]을 찾는다. 찾아진 이분할 부

제안하는 휴리스틱은 2"개의 변경 큐보이드 대신 ncrn/21 개의 변경 큐보이드만을 사용하여 큐브 뷰를 갱신할 수 있음을 보장한다. 또한, 제안하는 휴리스틱은 2"개의 변경 큐보이드를 사용하는 기존 방법보다 항상 적은 비용을 가지고 있음을 보장한다. 본 논문에서는 제안하는 방법을 구현하고, 실험을 통해 기존 방법과 성능을 비교하였다.

□ 본 논문에서 제안하는 휴리스틱은 정확히 nC「n/키 개의 갱신 체인을 가지는 갱신 파티션을 찾는다. 이에 따라 제안하는 방법은 2"개의 변경 큐보이드 대신 nC「n/2] 개의 변경 큐보이드만 계산하면 된다는 것을 보장한다. 제안하는 방법은 변경 큐브의 각 변경 큐보이드들이각각 하나의 갱신 체인을 형성하는, 尸개의 갱신 체인으로 이루어진 갱신 파티션으로부터 출발한다.

그러나 이러한 추가 비용은 전체적인 성능에 큰 영향을 미치지 않는다. 특히, 제안하는 방법은 큐브 뷰의 차원 애트리뷰트가 증가함에 따라 2"개의 변경 큐보이드를 모두 계산해야 하는 기존의 방법보다 더 좋은 성능을 보이고 있음을 알 수 있다.

갱산 파티션 {Si, S2, …, Sk} 에 따라 큐브 뷰를 갱신하기 위해서는 갱신 파티션에 포함된 각 갱신 체인의 커버 변경 큐보이드들, 즉, h(Si), h(s2), …, h(Sk) 를 계산해야 한다. 3.2절에서 설명한 바와 같이, 어떤 커버 변경 큐보이드들을 사용하든지 각 큐보이드들에 대한 변경 반영 비용은 일정하게 유지된다. 따라서 갱신 파티션의 비용은 h (si), h (s2), ■ h(sQ 를 계산하는 비용으로 나타낼 수 있다.

따라서 丁는 Level (0), Level (1), …, Level (『n/2] )의 변경 큐보이드들을 포함하지 않는 Tg의 부그래프이므로 Tg/2 二>T임이 성립된다. 口 보조 정리 4는 제안하는 방법이 211개의 모든 변경 큐보이드들을 계산하는 기존의 방법보다 적은 비용을 보장한다는 것을 의미한다. 또한 보조 정리 4에 따라 제안하는 방법은 전체의 절반 이하의 변경 큐보이드들, 즉, Level ( \ n/2 ] ), Level ( \ n/2 ] +1), Level (n) 에 속하는 변경 큐보이드들만을 계산하는 비용보다도더 적은 비용을 보장한다.

본 논문에서는 설명의 편의를 위해 집단화 함수로 SUM() 만을 가정 한다. 그러나 본 논문에서 제 안하는 방법은 일반적인 분배적 함수로 쉽게 확장이 가능하다. 『에서 튜플이 삭제되는 경우도 그림 2와 비슷한 방법으로 처리될 수 있다.

본 논문에서는 설명의 편의를 위해 F에 튜플이 추가되는 경우만을 가정한다. 그러나 본 논문에서 제안하는 방법은 F의 튜플이 삭제 또는 갱신되는 경우로도 쉽게 확장이 가능하다.

이와 같이, 주어진 큐브 뷰에 대한 갱신 방법에는 여러 개가 있을 수 있다. 그러나 제안하는 방법에서는 어떠한 변경 큐보이드들이 사용되든지 간에 각 큐보이드들에 대한 변경반영 비용은 일정하게 유지된다. 따라서, 큐보이드의 갱신에 사용되는 변경 큐보이드들을 계산하는 비용을 최소화하는 것이 중요하다.

본 논문에서는 제안하는 방법을 구현하고, 실험을 통해 기존 방법과 성능을 비교하였다. 실험 결과를 통해 제안하는 방법은 기존의 방법보다 좋은 성능을 보이고 있음을 알 수 있었다. 특히 큐브 뷰의 차원 애트리뷰트의 수가 증가할수록 성능 상의 이득이 커짐을 기대할 수 있었다.

□ 보조 정리 3에 따라, 제안하는 방법은 큐브 뷰를 갱신하는데 2"개의 변경 큐보이드대신 nC「n/2] 개의 변경 큐보이드만을 계산하면 된다는 것을 보장한다. 이에 따라 제안하는 방법은 변경 큐보이드를 계산하는 데 드는 비용을 크게 줄일 수 있다.

실험 결과를 통해 제안하는 방법은 기존의 방법보다 좋은 성능을 보이고 있음을 알 수 있었다. 특히 큐브 뷰의 차원 애트리뷰트의 수가 증가할수록 성능 상의 이득이 커짐을 기대할 수 있었다.