The series will showcase different perspectives on handling imperfect data and feature distinguished researchers issuing from AI, databases, and related areas.
The timeslot is Tuesday 15-16, with talks roughly every 1-2 months. Until we can meet safely in person, we will hold the seminar online.
To receive announcements for upcoming talks, join our mailing list.
Speaker: Sudeepa Roy, Duke University, USA
Abstract: I will discuss various computational challenges on database constraints that we have been exploring over the past years, focusing on quantitative aspects and functional dependencies. Among these are repair counting and repair minimization, which we view as different instances of inconsistency measures for databases. The need for inconsistency measurement can arise in various scenarios, including reliability estimation for datasets, progress indication in data cleaning, and the attribution of responsibility to individual tuples for the overall inconsistency. As in many fields, a conventional responsibility-sharing mechanism is the Shapley value from cooperative game theory; I will describe a systematic investigation of the complexity of this quantity under basic inconsistency measures. Finally, I will present a recent work on the problem of database repairing with soft constraints under the common interpretation that penalizes the database for every violation of every constraint, where the penalty is the cost (weight) of the constraint. A special instance of this problem is that of finding an optimal “almost matching” of a bipartite graph where a penalty is paid for every lost edge and every violation of monogamy.