PhD Thesis Proposal Defence


"Structural Join: Processing Algorithms and Size Estimation"

By

Mr. Wei Wang


Abstract

Recent years have witnessed an increasing interest in researches
in XML, partly due to the fact that XML has now become the
de facto standard for data interchange over the internet.
Efficient query processing methods are in great need due to the
intrinsic complexity of XML data as well as the queries.
Structural join has been identified as an important component of a
XML query processing engine.

In this proposal, we investigate two important issues related to
structural join. The first issues is the efficient evaluation of
structural join operations. We propose a novel PBiTree encoding
scheme and show that the best performance under all possible
dataset configurations can be achieved in a uniform structural
join processing framework based on PBiTree coding. The other is
result size estimation problem for structural join, which is no
doubt essential to generating efficient query processing plans. We
propose two models for XML data and develop histogram based and
sampling based estimation algorithms accordingly. Finally, we
point out some outstanding issues that worth further
investigation, including maintenance of XML coding schemes,
alternative methods for structure join size estimation as well as
evaluation of structural joins for graph structured data.


Date:				Friday, 16 May 2003

Time:				3:30p.m.-5:30p.m.

Venue:				Room 2304
				Lifts 17-18

Committee Members:		Prof. Hongjun Lu (Supervisor)
				Prof. Frederick Lochovsky (Chairman)
				Dr. Qiong Luo
				Dr. Dimitris Papadias


**** ALL are Welcome ****