HKUST Library Institutional Repository Banner

HKUST Institutional Repository >
Computer Science and Engineering >
CSE Doctoral Theses >

Please use this identifier to cite or link to this item:
Title: Data dependencies in the presence of difference
Authors: Song, Shaoxu
Issue Date: 2010
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, 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.
Description: Thesis (Ph.D.)--Hong Kong University of Science and Technology, 2010
xii, 128 p. : ill. ; 30 cm
HKUST Call Number: Thesis CSED 2010 SongS
Appears in Collections:CSE Doctoral Theses

Files in This Item:

File Description SizeFormat

All items in this Repository are protected by copyright, with all rights reserved.