As XML becomes the standard for data representation and exchange on the Internet, querying XML data has become an important issue. Research work in this area can be classified into two categories: the structured query approach and the keyword query approach. The structured query approach specifies the precise structure of the desired results using a structured query language such as XPath and XQuery; the keyword query approach specifies only keywords rather than specific structure information. Both approaches have their own values, trade-offs, and applications.
To support efficient evaluation of XML queries, structural summaries of XML data have been proposed. A structural summary is a data structure that preserves all structural features of XML data in a compact form and can be used as the schema of XML data. In this dissertation, we propose new methods for processing of XML keyword queries and structured queries using a structural summary.
In the first part of this dissertation, we focus on XML keyword query processing (simply, $\sl{XML} \it{keyword search}$) using a structural summary. In XML keyword search, to achieve high precision without sacrificing recall, it is important to remove $\it{spurious}$ results not intended by the user. Efforts to eliminate spurious results have enjoyed some success by using the concepts of LCA or its variants, SLCA and MLCA. However, existing methods still could find many spurious results. The fundamental cause for the occurrence of spurious results is that the existing methods try to eliminate spurious results locally without global examination of all the query results and, accordingly, some spurious results are not consistently eliminated. In this dissertation, we propose a novel keyword search method that removes spurious results consistently by exploiting the new concept of structural consistency. We define $\it{structural consistency}$ as a property that is preserved if there is no query result having an ancestor-descendant relationship $\it{at the schema level}$ with any other query results. Here, we use a structural summary as the schema of XML data. A naive solution to obtain structural consistency would be to compute all the LCAs (or variants) and then to remove spurious results according to structural consistency. Obviously, this approach would always be slower than existing LCA-based ones. To speed up structural consistency checking, we must be able to examine the query results at the schema level without generating all the LCAs. However, this is a challenging problem since the schema-level query results do not homomorphically map to the instance-level query results, causing serious false dismissal. We present a comprehensive and practical solution to this problem and formally prove that this solution preserves structural consistency at the schema level without incurring false dismissal. This solution has been prototyped in Odysseus---a full-fledged object-relational DBMS. Experimental results using real and synthetic data sets show that, compared with the state-of-the-art methods, our solution significantly 1) improves precision without sacrificing recall and 2) enhances the query performance by removing spurious results early.
In the second part of this dissertation, we focus on structured query (specifically, XPath query) processing using a structural summary. Due to wide use of XPath, the problem of efficiently processing XPath queries has recently received a lot of attention. In particular, a considerable effort has been devoted to minimizing XPath queries since the efficiency of query processing greatly depends on the size of the query. Research work in this area can be classified into two categories: constraint-independent minimization and constraint-dependent minimization. The former minimizes queries in the absence of integrity constraints while the latter in the presence of integrity constraints. For a $\it{linear path query}$, which is an XPath query without branching predicates, existing constraint-independent minimization methods are generally known to be unable to minimize the query without processing the query itself. Most recently, however, by using the $\it{DataGuide}$, a representative structural summary of XML data, a constraint-independent method that minimizes linear path queries in a top-down fashion has been proposed. Nevertheless, this method can fail to find a minimal query since it minimizes a query by merely erasing labels from the original query whereas a minimal query could include labels that are not present in the original query. In this dissertation, we propose a new bottom-up approach called $\sl{X} \it{Min}$ that $\it{guarantees}$ finding a minimal query for a given linear path query by using the DataGuide without processing the query itself. We first show that the sequence of labels occurring in the minimal query is a $\it{subsequence}$ of every $\it{schema label sequence}$ that matches the original query. Here, the schema label sequence for a node is the sequence of labels from the root of XML data to the node. We then propose $\it{iterative}$ subsequence generation that iteratively generates subsequences from the shortest schema label sequence matching the original query in a bottom-up fashion and tests query equivalence. Using iterative subsequence generation, we can always find a minimal query and we formally $\it{prove this guarantee}$. This method has been prototyped in Odysseus---a full-fledged object-relational DBMS. The experimental results using real and synthetic data sets show the practicality of our method.
We summarize the contributions of this dissertation as follows. First, we proposed a new concept of structural consistency. Then, based on this concept, we have proposed a novel keyword search method that eliminates spurious results consistently. Second, we have proposed a novel and efficient method for linear path query minimization that guarantees the minimality of the query. Finally, through extensive experiments, we have shown the effectiveness of the proposed methods.
XML이 인터넷 상에서의 데이터 표현과 교환의 표준으로 자리잡음에 따라, XML 데이터에 대한 질의가 중요한 문제로 부각되고 있다. 이 분야의 연구는 구조적 질의(structured query) 방식과 키워드 질의(keyword query) 방식으로 분류할 수 있다. 구조적 질의 방식은 XPath나 XQuery와 같은 구조적 질의 언어를 사용하여 원하는 결과의 정확한 구조를 기술하는 방식이다. 그리고 키워드 질의 방식은 명확한 구조 정보 대신 키워드만을 기술하는 방식이다. 두 방식 모두 각자의 가치, 장단점, 그리고 응용을 가지고 있다.
XML 질의의 효율적인 처리를 지원하기 위해 XML 데이터의 구조적 요약(structural summary)이 제안되었다. 구조적 요약은 XML 데이터의 모든 구조적 특징을 간결한 형태로 가지고 있는 자료 구조로서 XML 데이터의 스키마(schema)로 사용될 수 있다. 본 학위논문에서는 구조적 요약을 이용하여 XML 키워드 질의와 구조적 질의를 처리하는 새로운 방법들을 제안한다.
본 학위논문의 첫 번째 파트에서는 구조적 요약을 이용한 XML 키워드 질의 처리(간단히 XML 키워드 검색)에 초점을 둔다. XML 키워드 검색에서 재현율의 저하없이 정확도를 향상시키기 위해서는 사용자가 의도하지 않은 가짜 결과(spurious result)들을 제거하는 것이 중요하다. 기존 방법들은 LCA나 그것의 변형인 SLCA 또는 MLCA를 이용하여 가짜 결과들을 제거하였다. 그러나 기존 방법들은 여전히 많은 수의 가짜 결과들을 찾는 문제가 있다. 기존 방법들에서 가짜 결과가 발생하는 근본적인 원인은 질의 결과의 전체적인 검사없이 국지적으로 가짜 결과를 제거하기 때문이다. 그리고 그로 인해 가짜 결과가 일관성없이 제거된다. 본 학위논문에서는 구조적 일관성(structural consistency)이라는 새로운 개념을 이용하여 가짜 결과들을 일관적으로 제거하는 키워드 검색 방법을 제안한다. 구조적 일관성은 스키마 수준에서 조상-후손 관계를 가지는 질의 결과가 없을 때 지켜지는 특성이다. 이때, 구조적 요약이 XML 문서의 스키마로 사용된다. 구조적 일관성을 얻기 위한 단순한 방법은 모든 LCA(또는 그 변형)을 구한 다음 구조적 일관성에 따라 가짜 결과들을 제거하는 것이다. 명백히 이 방법은 기존의 LCA 기반 방법보다 항상 느릴 수 밖에 없다. 구조적 일관성 검사의 성능을 향상시키기 위해서는 모든 LCA를 생성하지 않고 스키마 수준에서 질의 결과들을 검사할 수 있어야 한다. 하지만 이는 어려운 문제이다. 왜냐하면 스키마 수준의 질의 결과들이 인스턴스(instance) 수준의 결과들에 준동형적(homomorphically)으로 매핑되지 않아 심각한 착오 기각(false dismissal)을 야기할 수 있기 때문이다. 본 학위논문에서는 이 문제에 대한 포괄적이고 실용적인 해법을 제시하고, 제시한 방법이 착오 기각없이 스키마 수준에서 구조적 일관성을 지킴을 정형적으로 증명한다. 이 방법은 오디세우스 객체관계형 DBMS에 구현되었으며, 실제 데이터와 합성 데이터를 사용한 실험을 통해 제안한 방법이 최근 방법들에 비해 1) 재현율의 저하없이 정확도를 크게 향상시키고, 2) 가짜 결과들을 조기에 제거함으로써 질의 처리 성능을 크게 향상시킴을 보였다.
본 학위논문의 두 번째 파트에서는 구조적 요약을 이용한 구조적 질의(구체적으로는 XPath 질의) 처리에 초점을 둔다. 최근 XPath가 널리 사용됨에 따라 XPath 질의의 효율적인 처리가 중요해지고 있다. 특히, 질의의 크기가 질의 처리 성능에 큰 영향을 미치므로 XPath 질의 최소화에 많은 연구가 이루어져 왔다. 이 분야의 연구는 제약조건 독립적 최소화(constraint-independent minimization)와 제약조건 의존적 최소화(constraint-dependent minimization)로 분류할 수 있다. 전자는 무결성 제약조건(integrity constraint)이 없을 때 질의를 최소화하는 연구이고, 후자는 무결성 제약조건이 있을 때 질의를 최소화하는 연구이다. 분기 조건(branching predicate)이 없는 XPath 질의인 선형 경로 질의(linear path query)에 대해 기존의 제약조건 독립적 최소화 방법들은 일반적으로 질의를 직접 처리하지 않고서는 질의 최소화가 불가능한 것으로 알려져 있다. 그러나 최근에 XML 데이터의 구조적 요약 중에서 대표적인 $\it{DataGuide}$ 를 이용하여 선형 경로 질의를 하향식(top-down)으로 최소화하는 제약조건 독립적 방법이 제안되었다. 하지만 이 방법은 최소 질의(minimal query)를 찾지 못할 수도 있다. 왜냐하면 원본 질의(original query)에 없는 레이블(label)이 최소 질의에 포함될 수 있는데 이 방법은 원본 질의에서 레이블을 삭제하는 방식으로만 질의를 최소화하기 때문이다. 본 학위논문에서는 DataGuide를 이용하여 질의를 직접 처리하지 않고서도 주어진 선형 경로 질의에 대해 최소 질의 획득을 보장하는 새로운 상향식(bottom-up) 방법인 XMin을 제안한다. 이를 위해 먼저 최소 질의에 나타나는 레이블들의 시퀀스(sequence)는 원본 질의에 매치(match)하는 모든 스키마 레이블 시퀀스의 부분시퀀스(subsequence)임을 보인다. 이때, 어떤 노드의 스키마 레이블 시퀀스는 XML 데이터의 루트로부터 그 노드까지의 경로에 나타난 레이블들의 시퀀스이다. 다음으로 원본 질의에 매치하는 최단 스키마 레이블 시퀀스로부터 상향식으로 부분시퀀스를 생성하고 질의 동등성을 검사하는 반복적 부분시퀀스 생성($\it{iterative subsequence generation}$)을 제안한다. 반복적 부분시퀀스 생성을 이용하여 항상 최소 질의를 찾을 수 있으며 정형적으로 이를 증명한다. 이 방법은 오디세우스 객체관계형 DBMS에 구현되었으며, 실제 데이터와 합성 데이터를 사용한 실험을 통하여 제안한 방법의 실용성(practicality)을 보였다.
본 학위논문의 공헌을 요약하면 다음과 같다. 첫째, 구조적 일관성의 개념을 제안하고 이를 이용하여 가짜 결과들을 일관성있게 제거하는 키워드 검색 방법을 제안하였다. 둘째, 최소 질의를 찾는 것을 보장하는 효율적인 선형 경로 질의 최소화 방법을 제안하였다. 마지막으로, 다양한 실험을 통하여 제안한 방법들의 유효성을 입증하였다.
