[Date Prev][Date Next][Date Index]

Reminder: Talk announcement - TODAY, 16:15 - 18:15, Andrea Cali and Andreas Pieris, Seminarraum Goedel



Dear all,

the talk by Andreas Pieris will start at 16:15. After a short break, Andrea Cali will give his talk.

%%%%%%%%%%%%%

Here are the details of the talk by Andrea Cali:

TITLE: Querying Web Data: A Computational Perspective

ABSTRACT:
The Deep Web is constituted by data that are stored in databases and that can be accessed only dynamically, by requesting them e.g. through an HTML form. The problem of querying such Web data in relational form has been studied in the literature since the 1990s and several theoretical results have been since then established. In this talk we present a formalisation of the query answering problem as well as some results on the query answering and query containment problem. We then argue that in order to properly characterise the complexity of query answering a specific computational formalism is necessary; we present our formalism, illustrate its generality, and we present some results on the computational complexity of the basic problems under the aforementioned formalism.

%%%%%%%%%%%%%

Here are the details of the talk by Andreas Pieris, which is an extended version of the talk he gave last week at PODS 2019 in Amsterdam:

TITLE: Counting Database Repairs under Primary Keys Revisited

ABSTRACT:
Consistent query answering aims to deliver meaningful answers when queries are evaluated over inconsistent databases. Such answers must be certainly true in all repairs, which are consistent databases whose difference from the inconsistent one is somehow minimal. An interesting task in this context is to count the number of repairs that entail the query. This problem has been already studied for conjunctive queries and primary keys; we know that it is #P-complete in data complexity under polynomial-time Turing reductions (a.k.a. Cook reductions). However, it is well-known that Cook reductions blur structural differences between counting problems and complexity classes since #P is not closed under Cook reductions (under reasonable assumptions). The goal of this talk is to perform a refined complexity analysis for the problem of counting the number of repairs under primary keys that entail the query through the lens of standard many-one logspace reductions.

This is joint work with Marco Calautti and Marco Console.

%%%%%%%%%%%%%

For details on the speakers, please visit their web pages:
http://homepages.inf.ed.ac.uk/apieris/
http://www.dcs.bbk.ac.uk/~andrea/

kind regards
Reinhard Pichler