Document Open Access Logo

On the Relationship between Consistent Query Answering and Constraint Satisfaction Problems

Authors Carsten Lutz, Frank Wolter

PDF
Thumbnail PDF

File

LIPIcs.ICDT.2015.363.pdf
  • Filesize: 0.6 MB
  • 17 pages

Document Identifiers

Author Details

Carsten Lutz
Frank Wolter

Cite AsGet BibTex

Carsten Lutz and Frank Wolter. On the Relationship between Consistent Query Answering and Constraint Satisfaction Problems. In 18th International Conference on Database Theory (ICDT 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 31, pp. 363-379, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
https://doi.org/10.4230/LIPIcs.ICDT.2015.363

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.
Keywords
  • Consistent Query Answering
  • Constraint Satisfaction
  • Data Complexity
  • Dichotomies
  • Rewritability

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Foto N. Afrati and Phokion G. Kolaitis. Repair checking in inconsistent databases: algorithms and complexity. In Proc. of ICDT, volume 361 of ACM International Conference Proceeding Series, pages 31-41. ACM, 2009. Google Scholar
  2. Marcelo Arenas and Leopoldo E. Bertossi. On the decidability of consistent query answering. In Proc. of AMW, volume 619 of CEUR Workshop Proceedings. CEUR-WS.org, 2010. Google Scholar
  3. Marcelo Arenas, Leopoldo E. Bertossi, and Jan Chomicki. Consistent query answers in inconsistent databases. In Proc. of PODS, pages 68-79. ACM Press, 1999. Google Scholar
  4. Albert Atserias. On digraph coloring problems and treewidth duality. In Proc. of LICS, pages 106-115, 2005. Google Scholar
  5. Libor Barto and Marcin Kozik. Constraint satisfaction problems of bounded width. In Proc. of FOCS, pages 595-603, 2009. Google Scholar
  6. Catriel Beeri, Ronald Fagin, David Maier, and Mihalis Yannakakis. On the desirability of acyclic database schemes. J. ACM, 30(3):479-513, 1983. Google Scholar
  7. Leopoldo E. Bertossi. Consistent query answering in databases. SIGMOD Record, 35(2):68-76, 2006. Google Scholar
  8. Leopoldo E. Bertossi, Loreto Bravo, Enrico Franconi, and Andrei Lopatenko. The complexity and approximation of fixing numerical attributes in databases under integrity constraints. Inf. Syst., 33(4-5):407-434, 2008. Google Scholar
  9. Meghyn Bienvenu, Carsten Lutz, and Frank Wolter. First-order rewritability of atomic queries in Horn description logics. In Proc. of IJCAI. IJCAI/AAAI, 2013. Google Scholar
  10. Meghyn Bienvenu, Balder ten Cate, Carsten Lutz, and Frank Wolter. Ontology-based data access: a study through disjunctive datalog, CSP, and MMSNP. In Proc. of PODS, pages 213-224. ACM, 2013. Google Scholar
  11. Manuel Bodirsky, Hubie Chen, and Tomás Feder. On the complexity of MMSNP. SIAM J. Discrete Math., 26(1):404-414, 2012. Google Scholar
  12. Manuel Bodirsky and Florent Madeleine. Feder and Vardi’s logic revisited. In preparation. Google Scholar
  13. Andrei A. Bulatov. A dichotomy theorem for constraint satisfaction problems on a 3-element set. J. ACM, 53(1):66-120, 2006. Google Scholar
  14. Andrea Calì, Domenico Lembo, and Riccardo Rosati. On the decidability and complexity of query answering over inconsistent and incomplete databases. In Proc. of PODS, pages 260-271. ACM, 2003. Google Scholar
  15. Jan Chomicki. Consistent query answering: Five easy pieces. In Proc. of ICDT, volume 4353 of LNCS, pages 1-17. Springer, 2007. Google Scholar
  16. Jan Chomicki and Jerzy Marcinkowski. Minimal-change integrity maintenance using tuple deletions. Inf. Comput., 197(1-2):90-121, 2005. Google Scholar
  17. Jan Chomicki, Jerzy Marcinkowski, and Slawomir Staworko. Computing consistent query answers using conflict hypergraphs. In Proc. of CIKM, pages 417-426. ACM, 2004. Google Scholar
  18. David Cohen and Peter Jeavons. The complexity of constraint languages, chapter 8. Elsevier, 2006. Google Scholar
  19. Stavros S. Cosmadakis, Haim Gaifman, Paris C. Kanellakis, and Moshe Y. Vardi. Decidable optimization problems for database logic programs (preliminary report). In Proc. of STOC, pages 477-490. ACM, 1988. Google Scholar
  20. Tomás Feder and Moshe Y. Vardi. The computational structure of monotone monadic SNP and constraint satisfaction: A study through datalog and group theory. SIAM J. Comput., 28(1):57-104, 1998. Google Scholar
  21. Tomás Feder and Moshe Y. Vardi. Homomorphism closed vs. existential positive. In 18th IEEE Symposium on Logic in Computer Science (LICS 2003), 22-25 June 2003, Ottawa, Canada, Proceedings, pages 311-320, 2003. Google Scholar
  22. Gaëlle Fontaine. Why is it hard to obtain a dichotomy for consistent query answering? In Proc. of LICS, pages 550-559. IEEE Computer Society, 2013. Google Scholar
  23. Ralph Freese, Marcin Kozik, Andrei Krokhin, Miklós Maróti, Ralph KcKenzie, and Ross Willard. On Maltsev conditions associated with omitting certain types of local structures. In preparation. Manuscript available from URL: http://www.math.hawaii.edu/~ralph/Classes/619/OmittingTypesMaltsev.pdf.
  24. Ariel Fuxman and Renée J. Miller. First-order query rewriting for inconsistent databases. In Proc. of ICDT, volume 3363 of LNCS, pages 337-351. Springer, 2005. Google Scholar
  25. Georg Gottlob, Nicola Leone, and Francesco Scarcello. Hypertree decompositions and tractable queries. J. Comput. Syst. Sci., 64(3):579-627, 2002. Google Scholar
  26. Neil Immerman. Descriptive complexity. Springer, 1999. Google Scholar
  27. Phokion G. Kolaitis and Enela Pema. A dichotomy in the complexity of consistent query answering for queries with two atoms. Inf. Process. Lett., 112(3):77-85, 2012. Google Scholar
  28. Paraschos Koutris and Dan Suciu. A dichotomy on the complexity of consistent query answering for atoms with simple keys. In Proc. of ICDT, pages 165-176. OpenProceedings.org, 2014. Google Scholar
  29. Gábor Kun. Constraints, MMSNP and expander relational structures. Combinatorica, 33(3):335-347, 2013. Google Scholar
  30. Benoit Larose, Cynthia Loten, and Claude Tardif. A characterisation of first-order constraint satisfaction problems. Logical Methods in Computer Science, 3(4), 2007. Google Scholar
  31. Benoit Larose and Pascal Tesson. Universal algebra and hardness results for constraint satisfaction problems. Theor. Comput. Sci., 410(18):1629-1647, 2009. Google Scholar
  32. Florent R. Madelaine. Universal structures and the logic of forbidden patterns. Logical Methods in Computer Science, 5(2), 2009. Google Scholar
  33. Florent R. Madelaine and Iain A. Stewart. Constraint satisfaction, logic and forbidden patterns. SIAM J. Comput., 37(1):132-163, 2007. Google Scholar
  34. Jaroslav Nesetril. Many facets of dualities. In Bonn Workshop of Combinatorial Optimization, pages 285-302, 2008. Google Scholar
  35. Benjamin Rossman. Homomorphism preservation theorems. J. ACM, 55(3), 2008. Google Scholar
  36. Thomas J. Schaefer. The complexity of satisfiability problems. In Proc. of STOC, pages 216-226. ACM, 1978. Google Scholar
  37. Slawomir Staworko and Jan Chomicki. Consistent query answers in the presence of universal constraints. Inf. Syst., 35(1):1-22, 2010. Google Scholar
  38. Balder ten Cate, Gaëlle Fontaine, and Phokion G. Kolaitis. On the data complexity of consistent query answering. In Proc. if ICDT, pages 22-33. ACM, 2012. Google Scholar
  39. Jef Wijsen. On the first-order expressibility of computing certain answers to conjunctive queries over uncertain databases. In Proc. of PODS, pages 179-190. ACM, 2010. Google Scholar
  40. Jef Wijsen. Charting the tractability frontier of certain conjunctive query answering. In Proc. of PODS, pages 189-200. ACM, 2013. Google Scholar
  41. Jef Wijsen. A survey of the data complexity of consistent query answering under key constraints. In Proc. of FoIKS, volume 8367 of LNCS, pages 62-78. Springer, 2014. Google Scholar
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