Semantic query optimization is an approach to optimizing a query with respect to some semantic information such as structural information and integrity constraints. This thesis presents new schema-based semantic query optimization techniques, which rely on available structural information, for XML queries. The techniques described in the thesis resolve several open problems in the field of schema-based query optimization for XML queries.
First, we present a new technique called the two-phase query pruning that consists of the preprocessing phase and the pruning phase. Our two-phase query pruning is effective in optimizing multiple regular path expressions, and is more scalable and efficient than the combination of the previous query pruning and post-processing in that it never deals with exponentially many combinations of sub-results produced from all the regular path expressions. Several experiments we conducted show that the two-phase query pruning outperforms the previous approach.
Second, another new technique called structural function inlining is presented. Based on the technique, we develop a new approach to optimizing and typing structurally recursive queries. The approach produces an optimal algebraic expression for a query with regard to available type information. Furthermore, it yields a precise result type for the query. Our experiments show that the number of node lookups by our approach is on the average 3.7 times and up to 279.8 times smaller than that by the current approach in evaluating structurally recursive queries.
의미적 질의 최적화는 구조 정보와 무결성 제약조건과 같은 의미 정보에 따라 질의를 최적화하는 기법을 말한다. 본 논문은 XML 질의를 위한 스키마 기반 의미적 질의 최적화에 관한 중요한 연구결과들을 제시한다. 이러한 연구 결과들은 현존하는 기술들로 해결할 수 없었던 미해결 문제들을 해결한다.
첫째 결과는 상호 관련있는 다중 정규 경로 표현들을 위한 효과적이면서 확장성이 있는 질의전지 기법이다. 상호 관련있는 정규 경로 표현들은 예를 들어 분기 경로 표현이나 경로 상에 조건 부여가 필요한 간단하지 않은 질의를 작성하는데 필수적이다. 우리의 두 단계 질의전지는 모든 재귀 탐색에 적용가능하고 시간 복잡도를 악화시키지 않으면서도 스키마 차원의 과잉 경로들을 제거한다. 전처리 단계는 이전 질의전지의 문제를 해결하기 위한 새로운 개념에 근거하여 정규 경로 표현의 수에 대해서 PTIME에 입력 질의로부터 모든 최소 최대화 조건 집합을 구한다. 이전 질의전지의 확장된 버전으로 생각할 수 있는 전지 단계는 준구조적 스키마의 노드 수와 정규 경로 표현의 수에 대하여 PTIME에 완전히 최적화된 경로 표현들을 구한다. 우리는 이러한 전처리 단계가 정확하고 완전하다는 성질과 두 단계 질의전지가 정확하고 효과적이란 성질을 증명하였다. 그리고 여러 실험을 통해서 우리의 두 단계 질의전지가 이전의 기법과는 달리 효과적이며 확장성이 있음을 보였다.
둘째 결과는 구조적 함수 인라이닝이라는 새로운 기술과 구조적 재귀 질의를 최적화하고 타이핑하는 문제에 대한 새로운 접근 방법이다. 우리는 그 기술이 어떻게 동작하는지, 무한 인라이닝과 같은 기술적 장애물들을 어떻게 해결하는지, 그리고 구조적 재귀 질의에 그 기술을 어떻게 적용하는지를 제시하였다. 우리의 접근 방법은 구조적 재귀 질의를 타입 도출이 용이한 최적 표현으로 바꾼다. 이러한 사항을 여러 예제를 통해 설명하였고, 실험을 통해 구조적 재귀 질의의 실행에 있어서 우리의 접근 방법에 의한 노드 접근 횟수가 XQuery의 현 접근 방법에 의한 경우보다 평균 3.7배, 최대 279.8배 적다는 것을 보였다. 그리고 구조적 함수 인라이닝에 의한 결과 표현이 가용 구조 정보에 대해서 최적임을 보였다.
