License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICDT.2015.363
URN: urn:nbn:de:0030-drops-49958
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/4995/
Go to the corresponding LIPIcs Volume Portal

Lutz, Carsten ; Wolter, Frank

On the Relationship between Consistent Query Answering and Constraint Satisfaction Problems

pdf-format:
22.pdf (0.6 MB)

Abstract

Recently, Fontaine has pointed out a connection between consistent query answering (CQA) and constraint satisfaction problems (CSP) [Fontaine, LICS 2013]. We investigate this connection more closely, identifying classes of CQA problems based on denial constraints and GAV constraints that correspond exactly to CSPs in the sense that a complexity classification of the CQA problems in each class is equivalent (up to FO-reductions) to classifying the complexity of all CSPs. We obtain these classes by admitting only monadic relations and only a single variable in denial constraints/GAVs and restricting queries to hypertree UCQs. We also observe that dropping the requirement of UCQs to be hypertrees corresponds to transitioning from CSP to its logical generalization MMSNP and identify a further relaxation that corresponds to transitioning from MMSNP to GMSNP (also know as MMSNP_2). Moreover, we use the CSP connection to carry over decidability of FO-rewritability and Datalog-rewritability to some of the identified classes of CQA problems.

BibTeX - Entry

@InProceedings{lutz_et_al:LIPIcs:2015:4995,
  author =	{Carsten Lutz and Frank Wolter},
  title =	{{On the Relationship between Consistent Query Answering and Constraint Satisfaction Problems}},
  booktitle =	{18th International Conference on Database Theory (ICDT 2015)},
  pages =	{363--379},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-79-8},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{31},
  editor =	{Marcelo Arenas and Mart{\'i}n Ugarte},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/4995},
  URN =		{urn:nbn:de:0030-drops-49958},
  doi =		{10.4230/LIPIcs.ICDT.2015.363},
  annote =	{Keywords: Consistent Query Answering, Constraint Satisfaction, Data Complexity, Dichotomies, Rewritability}
}

Keywords: Consistent Query Answering, Constraint Satisfaction, Data Complexity, Dichotomies, Rewritability
Collection: 18th International Conference on Database Theory (ICDT 2015)
Issue Date: 2015
Date of publication: 19.03.2015

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI