Due to its flexibility, XML is becoming the de facto standard for exchanging and querying documents over the Web. The key distinction between data in XML and data in traditional models is that XML is not rigidly structured. Because of the self-describing feature of XML data, XML can naturally model irregularities that cannot be modeled by relational or object-oriented data. Thus, new structures such as path indexes that improve the XML query performance are needed. Also, to describe the XML data structure, some languages are proposed.
Many XML query languages such as XQuery and XPath use label paths to traverse the irregularly structured XML data. Without a structural summary and efficient indexes, query processing can be quite inefficient due to an exhaustive traversal on XML data. To overcome the inefficiency, several path indexes have been proposed in the research community. Traditional indexes generally record all label paths from the root element in XML data and are constructed with the use of data only. Such path indexes may result in performance degradation due to large sizes and exhaustive navigations for partial matching path queries which start with the self-or-descendent axis("//"). To improve the query performance, we propose an adaptive path index for XML data (termed APEX). APEX does not keep all paths starting from the root and utilizes frequently used paths on query workloads. APEX also has a nice property that it can be updated incrementally according to the changes of query workloads. Experimental results with synthetic and real-life data sets clearly confirm that APEX improves the query processing cost typically 2 to 69 times compared with the traditional indexes, with the performance gap increasing with the irregularity of XML data.
To specify the constraint on the XML data structure, many languages such as Document Type Definition (DTD), Document Content Description (DCD), and XML Schema have been proposed. The schema described by these structure specifying languages for XML data serves several important purposes. Thus, we present a technique for efficient extraction of concise and accurate schemas for XML documents which were created without schemas. By restricting the schema form and applying some heuristic rules, we achieve the efficiency and conciseness. The result of an experiment shows that our approach attains high accuracy and is 20 to 200 times faster than existing approaches.
XML은 그 유연성 때문에 웹상에서의 문서 교환 및 질의의 표준으로 간주되고 있다. XML 데이타와 전통적인 데이타의 주요 차이점은 XML이 정형화된 구조가 아니라는 것이다. XML의 자기 표현 특성은 관계형 데이타나 객체 지향 데이타에 의하여 표현되지 못하는 비정규적인 데이타를 자연스럽게 모델링 할수 있도록 한다. 따라서, XML 질의 성능을 향상할 수 있는 경로 인덱스와 같은 새로운 구조가 필요하게 되었다. 또한 XML 데이타의 구조를 기술하기 위하여 몇가지 언어들이 제안되었다.
XQuery와 XPath 같은 많은 XML 질의언어들은 비정규적 구조의 XML 데이타를 탐색하기 위하여 레이블 경로를 이용한다. 구조적 요약 정보나 효율적인 인덱스가 없으면 XML 데이타를 소모적으로 탐색해야하므로 질의 처리가 매우 비효율적이다. 이러한 비효율성을 극복하고자,연구 분야에서 몇 가지의 경로 인덱스가 제안되었다. 전통적인 경로 인덱스는 일반적으로 XML 데이타의 루트 엘리먼트로부터 시작되는 모든 레이블 경로를 기록하고 XML 데이타만을 이용하여 생성된다. 이러한 경로 인덱스들은 거대한 크기와 자신-또는-자손 축(//)으로 시작되는 부분 매칭 경로 질의에 대한 소모적인 탐사때문에 성능이 저하되게 된다. 질의 처리 성능을 향상시키고자, 우리는 XML데이타를 위한 적응형 경로 인덱스 (APEX) 를 제안한다. APEX는 루트로부터 시작되는 모든 경로를 유지하지 않으며 질의 부하 로부터 자주 쓰이는 경로들을 활용한다. APEX는 또한 질의 부하의 변경데 따라서 증가적으로 갱신되는 좋은 특성을 지니고 았다. 합성 데이타와 실제 데이타를 이용한 실험 결과는 APEX가 질의 처리 비용을 전통적인 인덱스들에 비하여 2배에서 69배나 향상시켰음을 보여 준다. 이러한 성능의 차는 XML 데이타의 비정규성이 커질수록 증가된다.
XML 데이타 구조의 제약사항을 명시하기 위하여 Document Type Definition (DTD), Document Content Description (DCD), 그리고 XML Schema와 같은 많은 언어들이 제안되었다. 이러한 구조 명시 언어들로 표현되어진 스키마는 다양하고 중요한 목적으로 사용되어진다. 따라서, 우리는 XML 데이타의 간결하고 정확한 스키마의 효율적인 추출 기법을 제안한다. 스키마 구조의 제한과 경험적 규칙들을 적용하여 우리는 효율성과 간결성을 이룩할 수 있었다. 실제 DTD를 이용한 실험에서 제안된 기법의 높은 정확성과 기존의 기법들보다 20에서 200배의 빠른 성능을 보였다.
