CS&E Seminar Mon. 24 Jan. 2011, 12.00 Leonid Libkin -- @ Aula Magna
SPEAKER: Leonid Libkin, School of Informatics, University of Edinburgh, UK
TIME AND LOCATION: 24 January 2011, 12.00 -- Aula Magna
TITLE: Incomplete Information and Certain Answers in General Data Models
ABSTRACT: While incomplete information is ubiquitous in all data models - especially in applications involving data translation or integration - our understanding of it is still not completely satisfactory. For example, even such a basic notion as certain answers for XML queries was only introduced recently, and in a way seemingly rather different from relational certain answers.
The goal of this talk is to introduce a general approach to handling incompleteness, and to test its applicability in known data models such as relations and documents. The approach is based on representing degrees of incompleteness via semantics-based orderings on database objects. We use it to both obtain new results on incompleteness and to explain some previously observed phenomena. Specifically we show that certain answers for relational and XML queries are two instances of the same general concept; we describe structural properties behind the naive evaluation of queries; answer open questions on the
existence of certain answers in the XML setting; and show that previously studied ordering-based approaches were only adequate for SQL's primitive view of nulls. We define a general setting that subsumes relations and documents to help us explain in a uniform way how to compute certain answers, and when good solutions can be found in data exchange. We also look at the complexity of common problems related to incompleteness, and generalize several results from relational and XML contexts.
CONTACTS:
Domenico Lembo (lembo@dis.uniroma1.it), Massimo Mecella(mecella@dis.uniroma1.it)
home page of the Seminars in Computer Science and Engineering Series