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:20181028T030000
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
TZNAME:CET
END:STANDARD
BEGIN:DAYLIGHT
DTSTART:20180325T020000
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
RDATE:20190331T020000
TZNAME:CEST
END:DAYLIGHT
END:VTIMEZONE
BEGIN:VEVENT
UID:calendar.13534.field_data.0@glad.uniroma1.it
DTSTAMP:20260405T091431Z
CREATED:20181009T133737Z
DESCRIPTION:The talk will start with a brief overview of querying incomplet
 e information in databases and its main computational challenges. I will p
 resent a summary of the work that came out of the Edinburgh group in the p
 ast several years\, before concentrating on the core of the talk\, reflect
 ed in the title. Querying incomplete data invariably relies on the very co
 arse classification of query answers into those that are certain and those
  that are not. Such a classification is often very costly\, and we refine 
 it by measuring how close an answer is to certainty.This measure is define
 d as the probability that the query is true under a random interpretation 
 of missing information in a database. Since there are infinitely many such
  interpretations\, to pick one at random we adopt the approach used in the
  study of asymptotic properties and 0-1 laws for logical sentences and def
 ine the measure as the limit of a sequence. We show that in the standard m
 odel of missing data\, the 0-1 law is observed: this limit always exists a
 nd can be only 0 or 1 for a very large class of queries. Thus\, query answ
 ers are either almost certainly true\, or almost certainly false\, and thi
 s classification behaves very well computationally. When databases satisfy
  constraints\, the measure is defined as the conditional probability of th
 e query being true if the constraints are true. This can now be an arbitra
 ry rational number\, which is always computable. Another refinement of the
  notion of certainty views answers with a larger set of interpretations th
 at make them true as better ones. We pinpoint the exact complexity of find
 ing best answers for first-order queries. 
DTSTART;TZID=Europe/Paris:20181016T150000
DTEND;TZID=Europe/Paris:20181016T150000
LAST-MODIFIED:20240620T113644Z
LOCATION:Aula Magna
SUMMARY:Certain Answers Meet Zero-One Laws - Leonid Libkin\, University of 
 Edinburgh
URL;TYPE=URI:http://glad.uniroma1.it/node/13534
END:VEVENT
END:VCALENDAR