XML 반복부 데이터의 변경 협상 방법

서지정보

· 발행기관 : 한국정보처리학회
· 수록지 정보 : 정보처리학회논문지. 컴퓨터 및 통신시스템 / 11권 / 6호 / 459 ~ 468페이지
· 저자명 : 이은정

초록

모바일 환경에서 여러 사용자가 XML 트리를 공유하는 응용이 점차 많아지고 있다. XML 트리를 낙관적인 중복 방식으로 모바일 환경에서 공유하려면 동시에 수정된 데이터를 협상하여 하나의 버전을 만들 수 있어야 한다. 특히 XML 트리의 부분 트리를 삽입/삭제한 구조 변경 행위들을 협상하기 위해서는 트리의 노드 매핑과 비교 과정이 필요한데, 이것은의 복잡도를 가지는 문제로 알려져 있다. 또한 응용에 따라 달라지는 의미 기반의 충돌 해결 방식이 도입되어야 할 필요성이 제기되고 있다. 본 연구에서는 모바일 환경에서 XML 트리의 편집 기록(edit script)을 협상하기 위한 효율적인 협상 방법을 제시하였다. 본 논문에서는 이러한 요구를 만족시킬 수 있는 XML 데이터 공유 모델로서 문서 타입에서 반복부에 해당하는 부분만 삽입과 삭제를 허용하고 반복부의 부분 트리들이 형제들과 구분되는 키 값을 가지는 리스트 공유 모델을 이용한다. 이러한 리스트 공유 모델은 구조 변경 행위가 항상 문서의 유효성을 보장할 수 있다는 장점을 가지며, 키 기반의 리스트 협상을 하게 되므로 효율적인 협상 알고리즘을 얻는 것이 가능하다. 본 논문에서는 리스트 공유 모델에서 서로 키의 충돌이 없는 편집 기록에 대해 편집 기록의 길이를이라 할 때복잡도를 가지는 협상 알고리즘을 제안하였다. 기존 트리 협상 방법이 키의 충돌이 없는 경우 트리 크기에 선형 비례하는 시간 복잡도를 가지므로 제안된 방법은 모바일 환경에서 효과적인 협상 방법으로 사용될 수 있을 것이다.

참고자료

· 없음