Name
Abstract | ||
|---|---|---|
Computing an optimal subset repair of an inconsistent database is becoming a standalone research problem and has a wide range of applications. However, it has not been well-studied yet. A tight inapproximability bound of the problem computing optimal subset repairs is still unknown, and there is still no existing algorithm with a constant approximation factor better than two. In this paper, we prove a new tighter inapproximability bound of the problem computing optimal subset repairs. We show that it is usually NP-hard to approximate it within a factor better than 17/16. An algorithm with an approximation ratio (2 - 1/2(sigma-1)) is developed, where sigma is the number of functional dependencies. It is the current best algorithm in terms of approximation ratio. The ratio can be further improved if there are a large amount of quasi -Turan clusters in the input database. Plenty of experiments are conducted on real data to examine the performance and the e.ectiveness of the proposed approximation algorithms in real-world applications. |
Year | DOI | Venue |
|---|---|---|
2020 | 10.14778/3407790.3407809 | PROCEEDINGS OF THE VLDB ENDOWMENT |
DocType | Volume | Issue |
Journal | 13 | 11 |
ISSN | Citations | PageRank |
2150-8097 | 1 | 0.35 |
References | Authors | |
0 | 5 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Dongjing Miao | 1 | 18 | 9.91 |
| Zhipeng Cai | 2 | 1928 | 132.81 |
| Jianzhong Li | 3 | 63 | 24.23 |
| Xiangyu Gao | 4 | 1 | 1.03 |
| Xianmin Liu | 5 | 12 | 5.00 |