[8-14]RELATIVE INFORMATION COMPLETENESS

Date:2009-08-11

Title:　RELATIVE INFORMATION COMPLETENESS
Speaker:　WENFEI FAN,  Univ. of Edinburgh & Bell Labs
Date: 3pm, Firday Aug. 14
Venue: Lecture room, Level 3, Building #5, State Key Lab of Computer Science

ABSTRACT:

Real life data is often incomplete, with missing values and missing tuples.  Incomplete information routinely leads to misleading analytical results and biased decisions, and often has disastrous consequences.  In the past 30+ years missing values were typically handled under the Closed World Assumption, and missing tuples under the Open World Assumption.  In emerging applications, however, neither assumption is quite appropriate.  This is evident in, e.g., Master Data Management, one of the fastest growing software markets, which leads to databases that are only partially closed.

This talk presents a model for relative information completeness, and looks into two central problems: to decide whether a partially closed database has complete information to answer a query, and to determine whether there exists a partially closed database at all that is complete for a query.  We establish matching lower and upper bounds on these problems for various query languages.  When the problems are decidable, we provide characterizations for a database to be relatively complete, and for a query to allow a relatively complete database.