[논문]데이타 웨어하우스에서 데이타 큐브를 위한 효율적인 점진적 관리 기법

이기용; 박창섭; 김명호

문제 정의

따라서, n이 커질수록 변경 큐보이드들을 계산하는 비용이 매우 커지게 된다. 본 논문에서는 2“개의 변경 큐보이드를 모두 사용하지 않고 일부의 변경 큐보이드만을 사용하여 전체 큐브 뷰를 갱신하는 방법을 제안한다. 그림 1(b)는본 논문에서 제안하는 방법을 나타낸다, 본 논문에서 제안하는 방법은 하나의 변경 큐보이드로 여러 개의 큐보이드를 갱신한다.
본 논문에서는 큐브 뷰의 효율적인 점진적 관리 기법을 제안하였다. 차원 애트리뷰트의 수가 n인, 211개의 큐보이드로 이루어진 큐브 뷰를 갱신하기 위해 기존의 방법은 /개의 변경 큐보이드를 사용한다.
변경 반영 단계의 비용을 증가시키지 않고 전체 큐브 뷰를 갱신할 수 있도록 하는 변경 큐보이드의 집합은 여러 가지가 있을 수 있다. 본 논문은 이러한 집합 들 중 변경 계산 단계의 비용을 최소화하는 변경 큐보이드의 집합을 찾는 문제를 정의하고, 해당 문제에 대한해결책을 제안한다.
본 절에서는 여러 개의 큐보이드를 포함하는 큐브 뷰에 대한 점진적 관리 방법을 알아본다. 1장에서 언급한
이제 전체 큐브 뷰의 갱신 방법을 알아보자. 1장에서의 큐브 C는 abc, ab, ac, be, a, b, c, none의 8개의큐보이드를 가진다.

가설 설정

Ci =)Cj인 변경 큐보이드 와 에 대해 Cost(Aci, Acj) 는 2X6로부터 를 구하는 비용을 나타낸다. 본 논문에서는 Cost(ACi, 는 주어져 있다고 가정한다. Cost(Aci, 八勺)를 구하는 방법은 [10, 18]을 참조하라.
본 논문에서는 모든 group-by 연산자는 정렬 알고리즘으로 계산되며, 변경 큐보이드의 결과는 별도의 추가적인 비용 없이 차원 애트리뷰트의 값에 따라 정렬시킬 수 있다고 가정한다 또한, 이 때 order-by 연산자둥을 사용하여 차원 애트리뷰트의 정렬 순서를 자유롭게 지정할 수 있다고 가정한다. 예를 들어, 膈庭를 계산할 때는 그의 결과를 abc로 정렬할지, cba로 정렬할지를 자유롭게 선택할 수 있으며, 두 경우 모두 膈比를계산하는 비용 외에는 추가적인 비용이 들지 않는다.
삭제 또는 갱신에 대한 자세한 내용은 [1]을 참조하라. 본 논문에서는 설명의 편의를 위해 F에 튜플이 추가되는 경우만을 가정한다. 그러나 본 논문에서 제안하는 방법은 F의 튜플이 삭제 또는 갱신되는 경우로도 쉽게 확장이 가능하다.
본 논문에서는 설명의 편의를 위해 집단화 함수로 SUM() 만을 가정 한다. 그러나 본 논문에서 제 안하는 방법은 일반적인 분배적 함수로 쉽게 확장이 가능하다.

제안 방법

- 본 논문에서는 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] 개의 변경 큐보이드만을 계산하면 된다는 것을 보장한다. 이에 따라 제안하는 방법은 변경 큐보이드를 계산하는 데 드는 비용을 크게 줄일 수 있다.
실험 결과를 통해 제안하는 방법은 기존의 방법보다 좋은 성능을 보이고 있음을 알 수 있었다. 특히 큐브 뷰의 차원 애트리뷰트의 수가 증가할수록 성능 상의 이득이 커짐을 기대할 수 있었다.

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증

데이타 웨어하우스에서 데이타 큐브를 위한 효율적인 점진적 관리 기법
An Efficient Incremental Maintenance Method for Data Cubes in Data Warehouses 원문보기

초록
AI-Helper

Abstract ▼ AI-Helper

주제어

AI 본문요약
AI-Helper

문제 정의

가설 설정

제안 방법

대상 데이터

이론/모형

성능/효과

참고문헌 (21)

이 논문을 인용한 문헌

저자의 다른 논문 :

관련 콘텐츠

원문 보기

원문 URL 링크

연관된 기능

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

연합인증

데이타 웨어하우스에서 데이타 큐브를 위한 효율적인 점진적 관리 기법 An Efficient Incremental Maintenance Method for Data Cubes in Data Warehouses 원문보기

초록 용어보기논문에서 용어와 풀이말을 자동 추출한 결과로, 시범 서비스 중입니다. AI-Helper

Abstract ▼ AI-Helper

주제어

AI 본문요약 엑셀 다운로드 AI-Helper

문제 정의

가설 설정

제안 방법

대상 데이터

이론/모형

성능/효과

참고문헌 (21)

이 논문을 인용한 문헌

저자의 다른 논문 :

김명호 (71)

관련 콘텐츠

원문 보기

원문 URL 링크

연관된 기능

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

데이타 웨어하우스에서 데이타 큐브를 위한 효율적인 점진적 관리 기법
An Efficient Incremental Maintenance Method for Data Cubes in Data Warehouses 원문보기

초록
AI-Helper

AI 본문요약
AI-Helper