Dependence, independence, logic 
(Seminars)
22 August 2012
12noon
Venue: Room 303S.561, City Campus
Department of Computer Science seminar by Associate Professor Sebastian Link.
Data dependencies enforce meaningful properties of a given application domain within a database system. Dependencies are essential for the design of databases, and facilitate many data processing tasks. Conditional independencies capture structural aspects of probability distributions, deal with knowledge in Artificial Intelligence, and help with learning and reasoning in intelligent systems. Application areas include natural language processing, speech processing, computer vision, robotics, computational biology, and error-control coding. Automated reasoning about data dependencies, or about conditional independencies is infeasible in general. However, expressive yet efficient subclasses have
been identified in both cases, for examples, multivalued dependencies and saturated conditional independencies. These findings are based on the classic assumption that the underlying data are complete. In practice, data are missing or unknown, and structural or sampling zeros occur. The talk introduces expressive and efficient notions of multivalued dependencies and saturated conditional independencies in the presence of incomplete data. It is demonstrated that reasoning about multivalued dependencies is the same as reasoning about saturated conditional independencies. A fragment of propositional logic shows that reasoning in the presence of incomplete data soundly approximates classic reasoning; and that reasoning can be done in almost linear time in the input.
Sebastian Link is Associate Professor in the Department of Computer Science. He has been Associate Professor with the Victoria University of Wellington, and received his PhD from Massey University. Sebastian's main research interest concerns semantics in data. This area applies methods from algebra, combinatorics, logic and statistics to database theory.
