Bruno Marnette visiting Webdam
Bruno Marnette is visiting Webdam Thursday 16 April 2009. He is a phD student at the computing laboratory of the Oxford University.
He will present his work on schema mappings Thursday at 10:30am at ENS Cachan in LSV-library.
Title : Schema-Mappings: From Termination To Tractability
Summary : Data-Exchange is the problem of creating automatically a new database while integrating the information encoded in (1) a given source database and (2) a high-level specification called schema-mapping. After investing the general properties of (generalised) schema-mappings and their semantics, I will introduce in this talk a new sufficient condition TOC for polynomial data-complexity. This criteria TOC generalizes strictly and substantially the best previously-known criteria called Weak-Acyclicity and relies on the termination of (a refinement of) a known procedure called Oblivious Chase. While TOC is RE-complete, I will finally present a more restrictive criteria SwA (for Super-weak Acylicity) that can be decided in polynomial time while generalizing already substantially the notion of Weak Acyclicity.