Join Processing in Non-Conventional Databases

The Hong Kong University of Science and Technology
Department of Computer Science and Engineering


PhD Thesis Defence


Title: "Join Processing in Non-Conventional Databases"

By

Mr. Yin Yang


Abstract

The join operator combines information from multiple data sources. 
Efficient processing of join queries is a pivotal issue in most database 
systems. My PhD research focuses on join processing in two categories of 
novel applications. The first is continuous joins in data streams. 
Specifically, I exploit two key properties of the streaming join. First, 
the initial plan of a long query may gradually become inefficient due to 
changes in data characteristics. This necessitates dynamic plan migration, 
an online transition from the old plan to a more efficient one generated 
based on current statistics. The only known solutions MS and PT have some 
serious shortcomings. Hence, I propose HybMig, which combines their 
merits, and outperforms them on every aspect.

The second important property is that an output tuple from an upstream 
join (called the producer) may never generate any result in downstream 
operators (the consumers) during its entire lifespan. Motivated by this, I 
propose just-in-time (JIT) processing, a novel methodology that enables a 
producer to selectively generate outputs based on feedback returned from 
consumers that express their current demand. Extensive experiments show 
that JIT achieves significant savings in terms of both CPU time and memory 
consumption.

The second class of joins in this thesis are authenticated ones in 
outsourced databases. In particular, database outsourcing requires that 
the query server constructs a proof of result correctness, which can be 
verified by the client using the data owner’s signature. Addressing such 
queries, I propose a comprehensive set of new solutions that cover the 
entire spectrum of index availability. Furthermore, I extend them to 
authenticate complex queries, involving multi-way joins and other 
relational operators. Our experiments demonstrate that, the proposed 
methods outperform two existing benchmark solutions, often by orders of 
magnitude.


Date:			Tuesday, 23 June 2009

Time:			2:00pm-4:00pm

Venue:			Room 3501
 			Lifts 25-26

Chairman:		Prof. Lilong Cai (MECH)

Committee Members:	Prof. Dimitris Papadias (Supervisor)
 			Prof. Wilfred Ng
 			Prof. Ke Yi
 			Prof. Ajay Joneja (IELM)
 			Prof. Jeffrey Yu (Sys. Engg. & Engg. Mgmt., CUHK)


**** ALL are Welcome ****