XML 데이터가 동적으로 업데이트되는 환경에 적합한 원 개념을 사용한 레이블링 방법
A Labeling Scheme using Circle Concepts for Dynamically Updating XML Data
- 주제(키워드) XML , Circle Labeling Scheme , Labeling Scheme , Re-labeling , Dynamic XML Environment , 레이블링 방법 , 원형 레이블링 방법 , 레이블 재작성
- 발행기관 서강대학교 일반대학원
- 지도교수 박석
- 발행년도 2009
- 학위수여년월 2009. 2
- 학위명 석사
- 실제URI http://www.dcollection.net/handler/sogang/000000044955
- 본문언어 한국어
초록/요약
XML은 인터넷과 유비쿼터스 환경의 데이터에 대한 저장과 교환, 출판의 목적으로 광범위하게 표준으로 사용되고 있다. XML 데이터 모델의 광범위한 사용으로 데이터의 효율적인 저장과 활용을 위한 레이블링 방법과 안전한 접근제어 방법에 대한 연구가 이슈화되고 있다. XML 문서에 대한 레이블링 방법은 데이터를 효율적으로 저장하고 활용하기 위한 목적으로 연구되고 있다. 초기 질의처리 시스템은 문서 전체를 탐색하는 문제점을 갖는다. 레이블링 방법은 구조적 조인을 빠르게 수행할 수 있게 함으로써 이러한 문제점을 해결했다. 초기 레이블링 방법은 레이블 크기가 작아 레이블 저장을 위해 적은 저장공간을 사용한다. 그러나 XML 데이터의 업데이트가 발생하면 기존 레이블들을 재작성해야 하는 문제점이 있다. 이러한 문제점 해결을 위해 최근 XML 데이터의 업데이트가 빈번한 환경에 적합한 동적 레이블링 방법들이 제시되고 있다. 그러나 1) 큰 레이블 크기, 2) 길어지는 레이블 길이, 3) 기존 레이블 재작성 필요 등의 문제점을 갖는다. 본 논문에서는 기존 동적 레이블링 방법의 문제점들을 해결하기 위해 개선된 레이블링 방법인 원형 레이블링 방법을 제시한다. 원형 레이블링 방법은 XML 문서를 원으로 이해하는 새로운 시도를 하였고 반지름과 회전수, 부모원/자식원 개념을 사용한다. 반지름 개념을 사용함으로써 새로운 데이터가 삽입될 경우 기존 데이터들의 레이블 재작성이 불필요하고 레이블 길이의 증가가 제한된다. 또한 레이블 구조에 반지름이라는 추가적인 정보가 필요하기 때문에 레이블의 크기를 줄이기 위한 방법으로 회전수 개념과 부모원/자식원 개념을 사용한다. 원형 레이블링 방법은 반지름, 회전수, 부모원/자식원 개념을 사용함으로써 XML 문서의 업데이트가 빈번한 환경에 효율적이며 레이블 저장공간에 효율적이다. XML 데이터 모델에 대한 접근제어 방법의 기존 연구들은 단순히 접근제어의 효율성을 증가시키는데 중점을 두었다. 이러한 연구들의 성능은 접근제어 후 질의처리기의 성능에 종속된다. 이러한 문제점에 대한 해결책으로 접근제어와 질의처리를 병행 처리하는 메커니즘이 제시됐다. 그러나 기존 병행 수행 메커니즘은 사용자가 XML 문서를 읽는 행위에 대해서만 고려하고 있고 ‘범위 기반 레이블링 방법’을 사용하기 때문에 실제 XML 문서의 업데이트가 빈번한 환경에 적합하지 않다. 원형 레이블링 방법의 활용 방안으로 XML 문서의 업데이트까지 고려하는 질의처리와 접근제어를 병행 수행하는 개선된 메커니즘을 제시한다. 원형 레이블링 방법을 사용하여 XML 문서를 레이블링 하여 XML 문서가 업데이트 되는 환경을 지원하기 때문에 업데이트를 위한 사용자들의 접근제어가 가능하다. 본 논문에서는 XML 문서의 업데이트가 빈번한 환경에 효율적이며 레이블 저장공간 효율적인‘원형 레이블링 방법’을 제시한다. 그리고 원형 레이블링 방법의 활용 방안으로 기존의 질의처리와 접근제어를 병행 수행하는 메커니즘에 원형 레이블링 방법을 적용하여 XML 문서의 업데이트가 요구되는 환경에 사용할 수 있는 개선된 메커니즘을 제시한다.
more초록/요약
XML has become the new standard for storing and exchanging data in the Internet and the Ubiquitous environment. As demand for efficiency in handling XML document grows, labeling scheme has become an important topic in data storage and the need to provide controlled access to such information is issued. Labeling schemes can be classified into Static Labeling Schemes and Dynamic Labeling Schemes. Static Labeling Schemes provide compact storage size but are not efficient for frequent update. Dynamic Labeling Schemes have nice update performance in Dynamic XML environment. However these schemes have several problems such as large storage space due to increase of length of labels, and re-labeling existing nodes. In this thesis, we propose a new labeling scheme called the Circle Labeling Scheme (CLS) which solves the problems of the previous Dynamic Labeling Schemes. In the CLS, XML document is represented in a circular form and the concepts of Radius, Rotation Number and Parent Circle/Child Circle are introduced. The notion of Radius is applied to support inclusion of new nodes at arbitrary positions in the XML tree. This eliminates the need for re-labeling existing nodes and prevents the label length from growing. Furthermore, the efficient storage of labels is supported by the use of concepts Rotation Number and Parent Circle/Child Circle. Hence the CLS is the efficient labeling scheme for memory space and dynamic XML environment. Previous research on access control mechanisms for XML data considered the efficiency of control the access only. Therefore, the performance of these access control mechanisms is depend on the performance of query processing systems. To solve these problems, the mechanism for integrating access control and query processing is proposed. Since this mechanism only considers read action for each user in authorization and is based on the Range-based Labeling Scheme, the mechanism is not inefficient for dynamic XML environment. In this thesis, we show practical use of the CLS. The proposed application is derived from the previous mechanism for integrating access control and query processing. To engance the adoptability for dynamic XML environment, we apply the CLS to the previous integrating mechanism and propose new action types in authorization. In this thesis, we propose the new labeling scheme called the Circle Labeling Scheme, which is efficient for dynamic environment and storage space. Moreover the application based on CLS is introduced. This application is an advanced mechanism for integrating access control and query processing, which is suitable for dynamic XML environment.
more목차
I. 서론 = 1
1.1 연구배경 및 동기 = 1
1.1.1 레이블링 방법 = 1
1.1.2 원형 레이블링 방법의 활용 방안 = 4
1.2 논문의 구성 = 6
II. 관련 연구 = 7
2.1 XML 데이터 모델 = 7
2.2 XPath = 9
2.3 XML 레이블링 방법에 대한 기존 연구 = 9
2.3.1 정적 레이블링 방법 (Static Labeling Scheme) = 9
2.3.1.1 전위-후위 레이블링 방법 (Pre-Post Labeling Scheme) = 9
2.3.1.2 범위 기반 레이블링 방법 (Range-based Labeling Scheme) = 10
2.3.2 동적 레이블링 방법 (Dynamic Labeling Scheme) = 11
2.3.2.1 소수 기반 레이블링 방법 (Prime Number based Labeling Scheme) = 11
2.3.2.2 접두사 기반 레이블링 방법 (Prefix based Labeling Scheme) = 13
2.3.2.3 섹터 기반 레이블링 방법 (Sector based Labeling Scheme) = 14
2.3.3 기존 레이블링 방법 분석 = 15
2.4 XML 접근제어 수행 메커니즘에 대한 기존 연구 = 18
2.4.1 관계형 데이터베이스 기반의 접근제어 메커니즘 = 18
2.4.2 뷰 기반의 접근제어 메커니즘 = 20
2.4.3 뷰 독립적인 접근제어 메커니즘 = 22
2.4.3.1 오토마타 기반 접근제어 메커니즘 = 22
2.4.3.2 질의처리와 접근제어 병행 수행 메커니즘 = 23
III. 동적 XML 환경에 적합한 원형 레이블링 방법 = 26
3.1 범위 기반 레이블링 방법 = 26
3.2 문제 정의 = 28
3.3 XML 문서의 원형 표현 = 31
3.4 동적 XML 환경에서의 원형 레이블링 방법 = 34
3.4.1 반지름 개념 = 34
3.4.2 삽입연산 발생 시 레이블 재작성이 필요한 노드들의 수 = 39
3.4.3 증가하지 않는 레이블 길이 = 40
3.5 회전수, 부모원/자식원 개념 = 41
3.5.1 회전수 개념 = 42
3.5.2 부모원/자식원 개념 = 46
IV. 성능 평가 = 52
4.1 실험 환경 설정 = 52
4.2 전체 레이블 저장공간 = 53
4.3 레이블 생성 시간 = 54
4.4 동적 XML 환경에서의 실험 = 54
4.4.1 동적 XML 환경에서의 실험 = 55
4.4.2 삽입 연산 수행 시 걸린 시간 = 57
V. 원형 레이블링 방법의 활용 방안 = 58
5.1 기본개념 = 59
5.1.1 접근권한 정보 = 59
5.1.2 보안정책 = 61
5.2 갱신 연산자의 종류와 액션타입 확장 = 62
5.3 질의처리와 접근제어 병행 수행 메커니즘의 개선된 방법 = 63
VI. 결론 및 추후 연구 = 69
참고문헌 = 73
그림 및 표차례
[그림 1] HTML 문서와 XML 문서의 예 = 8
[그림 2] XML 문서의 종류 = 8
[그림 3] 정적 레이블링 방법의 예 = 10
[그림 4] 소수 기반 레이블링 방법의 예 = 12
[그림 5] LSDX의 예 = 13
[그림 6] 섹터 기반 레이블링 방법의 예 = 14
[그림 7] 접근제어 메커니즘 연구의 흐름 = 18
[그림 8] XENA의 구조 = 19
[그림 9] 뷰 기반 XML 접근제어 수행 과정 = 20
[그림 10] 정적 분석을 통한 XML 접근제어 수행 메커니즘의 구조 = 23
[그림 11] DP를 사용했을 때 성능 향상을 가져 음을 나타내는 예 = 24
[그림 12] DP를 사용하는 예 = 24
[그림 13] XML 문서(hospital.xml)와 (start, end)를 사용한 레이블링의 예 = 27
[그림 14] (start, end)로 레이블링 된 XML 문서와 부여된 접근권한의 예 = 29
[그림 15] XML 문서(hospital.xml)을 트리, 수평선, 원으로 표현한 예 = 32
[그림 16] 반지름 개념을 적용한 원형 레이블링 방법의 예 = 37
[그림 17] 참조 XML 트리 = 37
[그림 18] 각 방법 별 레이블 재작성이 필요한 노드들의 범위 = 40
[그림 19] XML 문서 크기 증가에 따른 변수 크기 변경과 변수의 내부 단편화 문제 = 43
[그림 20] 큰 XML 문서에 대한 레이블링 시 레이블 값 누적과 해결 방법의 예 = 47
[그림 21] 원형 레이블링 방법에 부모원/자식원 개념을 적용한 예 = 51
[그림 22] 다양한 크기의 문서, 레이블링 방법 별 전체 레이블 저장공간 = 53
[그림 23] 다양한 크기의 문서, 레이블링 방법 별 레이블링 시간 = 54
[그림 24] 1,000개의 노드를 삽입했을 경우 레이블 재작성이 필요한 시간 = 56
[그림 25] XML 문서(hospital.xml)와 접근권한의 예 = 61
[그림 26] XML 문서에 Radius.(start_angle, end_angle) 을 사용해 레이블링한 예 = 64
[그림 27] [표 7]의 접근권한을 [그림 26]의 XML 트리에 나타낸 예 = 65
[그림 28] user_(A)의 접근권한 인덱스 = 66
[그림 29] [표 8]의 Q2, Q3을 통해 업데이트된 XML 트리 = 68
[표 1] XML 레이블링 방법에 대한 기존 연구 비교 = 16
[표 2] 범위 기반 레이블링 방법과 동적 레이블링 방법 비교 = 29
[표 3] 동적 레이블링 방법 간 비교 = 30
[표 4] 부모원 / 자식원 관계 테이블의 예 = 49
[표 5] XML 문서 크기 별 노드 수와 XMark의 Scaling Factor = 52
[표 6] 1,000개의 노드를 삽입했을 경우 레이블 재작성이 필요한 노드 수 = 56
[표 7] user_(A)의 접근권한의 예 = 65
[표 8] user_(A)가 입력한 질의의 예 = 66
[함수 3.1] (start_angle, end_angle)을 사용한 레이블링 함수 = 33
[함수 3.2] (start_RN.start_angleRN, end_RN.end_angleRN)를 사용한 레이블링 함수 = 45
[알고리즘 3.1] 새로운 데이터가 기준 노드의 왼쪽에 삽입될 때의 레이블링 알고리즘 = 36
[알고리즘 3.2] 새로운 데이터가 기준 노드의 오른쪽에 삽입될 때의 레이블링 알고리즘 = 36
