1 Search Results for "Arming, Sebastian"

Document
DOI: 10.4230/LIPIcs.ICDT.2016.21
Complexity of Repair Checking and Consistent Query Answering

Authors: Sebastian Arming, Reinhard Pichler, and Emanuel Sallinger

Published in: LIPIcs, Volume 48, 19th International Conference on Database Theory (ICDT 2016)

Abstract
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.
Cite as

Sebastian Arming, Reinhard Pichler, and Emanuel Sallinger. Complexity of Repair Checking and Consistent Query Answering. In 19th International Conference on Database Theory (ICDT 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 48, pp. 21:1-21:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{arming_et_al:LIPIcs.ICDT.2016.21,
  author =	{Arming, Sebastian and Pichler, Reinhard and Sallinger, Emanuel},
  title =	{{Complexity of Repair Checking and Consistent Query Answering}},
  booktitle =	{19th International Conference on Database Theory (ICDT 2016)},
  pages =	{21:1--21:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-002-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{48},
  editor =	{Martens, Wim and Zeume, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2016.21},
  URN =		{urn:nbn:de:0030-drops-57900},
  doi =		{10.4230/LIPIcs.ICDT.2016.21},
  annote =	{Keywords: inconsistency, consistent query answering, complexity}
}
  • Refine by Author
  • 1 Arming, Sebastian
  • 1 Pichler, Reinhard
  • 1 Sallinger, Emanuel

  • Refine by Classification

  • Refine by Keyword
  • 1 complexity
  • 1 consistent query answering
  • 1 inconsistency

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2016

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact