[Back]

S. Arming, R. Pichler, E. Sallinger:
"Complexity of Repair Checking and Consistent Query Answering";
Talk: International Conference on Database Theory - ICDT 2016, Bordeaux; 2016-03-15 - 2016-03-18; in: "19th International Conference on Database Theory, ICDT 2016, Bordeaux, France, March 15-18, 2016", W. Martens, T. Zeume (ed.); Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, LIPIcs 48 (2016), Paper ID 21, 18 pages.

Inconsistent databases (i.e., databases violating some given set of integrity constraints) may arise in many applications such as, for instance, data integration. Hence, the handling of inconsistent data has evolved as an active field of research. In this paper, we consider two fundamental problems in this context: Repair Checking (RC) and Consistent Query Answering (CQA). So far, these problems have been mainly studied from the point of view of data complexity (where all parts of the input except for the database are considered as fixed). While for some kinds of integrity constraints, also combined complexity (where all parts of the input are allowed to vary) has been considered, for several other kinds of integrity constraints, combined complexity has been left unexplored. Moreover, a more detailed analysis (keeping other parts of the input fixed - e.g., the constraints only) is completely missing. The goal of our work is a thorough analysis of the complexity of the RC and CQA problems. Our contribution is a complete picture of the complexity of these problems for a wide range of integrity constraints. Our analysis thus allows us to get a better understanding of the true sources of complexity.

inconsistency, consistent query answering, complexity

http://dx.doi.org/10.4230/LIPIcs.ICDT.2016.21

http://dx.doi.org/10.4230/LIPIcs.ICDT.2016.21

Project Head Reinhard Pichler:
Heterogene Information Integration

Project Head Reinhard Pichler:
SEE: SPARQL Evaluation and Extensions