Name
Abstract | ||
|---|---|---|
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 this problem in 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. |
Year | DOI | Venue |
|---|---|---|
2021 | 10.4230/LIPIcs.ICDT.2021.16 | ICDT |
DocType | Citations | PageRank |
Conference | 0 | 0.34 |
References | Authors | |
0 | 5 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Nofar Carmeli | 1 | 6 | 4.84 |
| Martin Grohe | 2 | 2280 | 127.40 |
| Benny Kimelfeld | 3 | 1034 | 71.63 |
| Ester Livshits | 4 | 5 | 4.47 |
| Muhammad Tibi | 5 | 0 | 0.68 |