> Detailanzeige

Carmeli, Nofar [VerfasserIn]; Grohe, Martin [VerfasserIn]; Kimelfeld, Benny [VerfasserIn]; Livshits, Ester [VerfasserIn]; Tibi, Muhammad [VerfasserIn] ; Nofar Carmeli and Martin Grohe and Benny Kimelfeld and Ester Livshits and Muhammad Tibi [MitwirkendeR]

Database Repairing with Soft Functional Dependencies

Literatur-
verwaltung

Zur
Merkliste

Lösche von
Merkliste

Per Whatsapp teilen

Schließen

Merkliste



Sie können Bookmarks mittels Listen verwalten, loggen Sie sich dafür bitte in Ihr SLUB Benutzerkonto ein.
  • Medientyp: Elektronischer Konferenzbericht; Sonstige Veröffentlichung; E-Artikel
  • Titel: Database Repairing with Soft Functional Dependencies
  • Beteiligte: Carmeli, Nofar [VerfasserIn]; Grohe, Martin [VerfasserIn]; Kimelfeld, Benny [VerfasserIn]; Livshits, Ester [VerfasserIn]; Tibi, Muhammad [VerfasserIn]
  • Erschienen: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021
  • Sprache: Englisch
  • DOI: https://doi.org/10.4230/LIPIcs.ICDT.2021.16
  • Schlagwörter: soft constraints ; database repairs ; functional dependencies ; Database inconsistency ; integrity constraints
  • Entstehung:
  • Anmerkungen: Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
  • Beschreibung: A common interpretation of soft constraints penalizes the database for every violation of every constraint, where the penalty is the cost (weight) of the constraint. A computational challenge is that of finding an optimal subset: a collection of database tuples that minimizes the total penalty when each tuple has a cost of being excluded. When the constraints are strict (i.e., have an infinite cost), this subset is a "cardinality repair" of an inconsistent database; in soft interpretations, this subset corresponds to a "most probable world" of a probabilistic database, a "most likely intention" of a probabilistic unclean database, and so on. Within the class of functional dependencies, the complexity of finding a cardinality repair is thoroughly understood. Yet, very little is known about the complexity of finding an optimal subset for the more general soft semantics. This paper makes a significant progress in this direction. In addition to general insights about the hardness and approximability of the problem, we present algorithms for two special cases: a single functional dependency, and a bipartite matching. The latter is the problem of finding an optimal "almost matching" of a bipartite graph where a penalty is paid for every lost edge and every violation of monogamy.
  • Zugangsstatus: Freier Zugang