| Abstract: |
| In this talk, two critical problems, data quality evaluation and data repairing, will be investigated. First, a graph class called conflict graph will be introduced, which is a union of a finite number of given forests of complete multipartite graphs. It is demonstrated that vertex cover in conflict graphs can be utilized to evaluate data quality in database. It is interesting that conflict graphs can model many natural problems, such as in database applications. It is shown that this property is non-trivial if the number of forests of complete multipartite graphs is limited. Then the problem of vertex cover in conflict graphs will be introduced. For data repairing, view propagation in database will be introduced. It is shown that a repair of an inconsistent database is a maximal consistent subset. A comprehensive view of the computational complexity of conjunctive queries will be presented. |
|