BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Date iCal//NONSGML kigkonsult.se iCalcreator 2.20.2//
METHOD:PUBLISH
X-WR-CALNAME;VALUE=TEXT:Eventi DIAG
BEGIN:VTIMEZONE
TZID:Europe/Paris
BEGIN:STANDARD
DTSTART:20131027T030000
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
TZNAME:CET
END:STANDARD
BEGIN:DAYLIGHT
DTSTART:20130331T020000
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
TZNAME:CEST
END:DAYLIGHT
END:VTIMEZONE
BEGIN:VEVENT
UID:calendar.6709.field_data.0@www.open.diag.uniroma1.it
DTSTAMP:20260407T230945Z
CREATED:20130709T132329Z
DESCRIPTION:Incomplete information is ubiquitous in database applications\,
  and yet our understanding of it is still rather basic. The key goal of th
 is work is to see when query answering over databases with incomplete info
 rmation can be solved by standard query evaluation techniques - this is us
 ually referred to as naive evaluation.Since an incomplete database can rep
 resent multiple databases\, query answering over them boils down to solvin
 g the validity problem\, while database systems are good at performing mod
 el-checking algorithms on first-order structures. Thus\, we need to unders
 tand when validity can be reduced to model-checking. We first show that th
 is happens for queries which are monotone with respect to semantic orderin
 gs which specify the degree of incompleteness of a database. Then we show 
 that for most commonly used semantics of incompleteness\, such monotonicit
 y can be described via homomorphism preservation\, for different notions o
 f homomorphisms. Combining the latter with preservation theorems from logi
 c (existing as well as new)\, we obtain classes of queries for which stand
 ard database systems can correctly compute answers over incomplete databas
 es\, or\, logically speaking\, for which validity can be solved by simple 
 model-checking. 
DTSTART;TZID=Europe/Paris:20130710T150000
DTEND;TZID=Europe/Paris:20130710T150000
LAST-MODIFIED:20240620T113644Z
LOCATION:Rome\, DIAG\, Aula Magna
SUMMARY:Incomplete Information\, Naive Evaluation\, and Homomorphism Preser
 vation - Leonid Libkin
URL;TYPE=URI:http://www.open.diag.uniroma1.it/node/6709
END:VEVENT
END:VCALENDAR