Data Dependencies in the Presence of Difference

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


PhD Thesis Defence


Title: "Data Dependencies in the Presence of Difference"

By

Mr. Shaoxu Song


Abstract

The importance of difference semantics (e.g., "similar" or "dissimilar") 
is recently recognized for declaring dependencies among various types of 
data, such as numerical values or text values. We propose a novel form of 
differential dependencies (dds), which specifies constraints on 
difference, instead of equality function in traditional dependency 
notations like functional dependencies. Informally, a differential 
dependency states that if two tuples have distances on attributes X 
agreeing with a certain differential function, then their distances on 
attributes Y should also agree with the corresponding differential 
function on Y. For example, [date(<=7)]->[price(<100)] states that the 
flight price difference of any two days in a week length should be no 
greater than 100$. Such differential dependencies are useful in various 
applications, e.g., violation detection, data partition, query 
optimization, and record linkage, etc.

In this thesis, we first report our preliminary work on several 
theoretical issues of differential dependencies, including formal 
definitions of dds and differential keys, subsumption order relation of 
differential functions, implication of dds, closure of a differential 
function, a sound and complete inference system, and minimal cover for 
dds. Then, we investigate a practical problem, i.e., how to discover dds 
and differential keys from a given sample data. Due to the intrinsic 
hardness, we develop several pruning methods to improve the discovery 
efficiency in practice. Moreover, we address differential dependencies 
that "almost" hold in a given data instance, namely approximate 
differential dependencies. Several approaches are studied to evaluate how 
a dd approximately holds in a data instance. Through the extensive 
experimental evaluation on real data sets, we demonstrate the performance 
of discovery algorithms, and the effectiveness of dds in several real 
applications.


Date:			Friday, 20 August 2010

Time:			10:00am – 12:00noon

Venue:			Room 3501
 			Lifts 25/26

Chairman:		Prof. Xijun Hu (CBME)

Committee Members:	Prof. Lei Chen (Supervisor)
 			Prof. Frederick Lochovsky
 			Prof. Wilfred Ng
                         Prof. Ling Shi (ECE)
                         Prof. Jianliang Xu (Comp. Sci., Baptist U.)


**** ALL are Welcome ****