Document Open Access Logo

A Simple Algorithm for Consistent Query Answering Under Primary Keys

Authors Diego Figueira, Anantha Padmanabha, Luc Segoufin, Cristina Sirangelo



PDF
Thumbnail PDF

File

LIPIcs.ICDT.2023.24.pdf
  • Filesize: 2.31 MB
  • 18 pages

Document Identifiers

Author Details

Diego Figueira
  • Univ. Bordeaux, CNRS, Bordeaux INP, LaBRI, UMR 5800, Talence, France
Anantha Padmanabha
  • DI ENS, ENS, CNRS, PSL University, Paris, France
  • Inria, Paris, France
Luc Segoufin
  • INRIA, ENS-Paris, PSL University, France
Cristina Sirangelo
  • Université Paris Cité, CNRS, Inria, IRIF, F-75013, Paris, France

Cite AsGet BibTex

Diego Figueira, Anantha Padmanabha, Luc Segoufin, and Cristina Sirangelo. A Simple Algorithm for Consistent Query Answering Under Primary Keys. In 26th International Conference on Database Theory (ICDT 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 255, pp. 24:1-24:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.ICDT.2023.24

Abstract

We consider the dichotomy conjecture for consistent query answering under primary key constraints. It states that, for every fixed Boolean conjunctive query q, testing whether q is certain (i.e. whether it evaluates to true over all repairs of a given inconsistent database) is either polynomial time or coNP-complete. This conjecture has been verified for self-join-free and path queries. We propose a simple inflationary fixpoint algorithm for consistent query answering which, for a given database, naively computes a set Δ of subsets of database repairs with at most k facts, where k is the size of the query q. The algorithm runs in polynomial time and can be formally defined as: 1) Initialize Δ with all sets S of at most k facts such that S⊧ q. 2) Add any set S of at most k facts to Δ if there exists a block B (i.e., a maximal set of facts sharing the same key) such that for every fact a ∈ B there is a set S' ∈ Δ contained in S ∪ {a}. The algorithm answers "q is certain" iff Δ eventually contains the empty set. The algorithm correctly computes certainty when the query q falls in the polynomial time cases of the known dichotomies for self-join-free queries and path queries. For arbitrary Boolean conjunctive queries, the algorithm is an under-approximation: the query is guaranteed to be certain if the algorithm claims so. However, there are polynomial time certain queries (with self-joins) which are not identified as such by the algorithm.

Subject Classification

ACM Subject Classification
  • Theory of computation → Database query languages (principles)
Keywords
  • consistent query answering
  • primary keys
  • conjunctive queries

Metrics

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

References

  1. Foto N. Afrati and Phokion G. Kolaitis. Repair checking in inconsistent databases: algorithms and complexity. In Ronald Fagin, editor, Database Theory - ICDT 2009, 12th International Conference, St. Petersburg, Russia, March 23-25, 2009, Proceedings, volume 361 of ACM International Conference Proceeding Series, pages 31-41. ACM, 2009. URL: https://doi.org/10.1145/1514894.1514899.
  2. Marcelo Arenas, Leopoldo E. Bertossi, and Jan Chomicki. Consistent query answers in inconsistent databases. In Victor Vianu and Christos H. Papadimitriou, editors, Proceedings of the Eighteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, May 31 - June 2, 1999, Philadelphia, Pennsylvania, USA, pages 68-79. ACM Press, 1999. URL: https://doi.org/10.1145/303976.303983.
  3. Diego Figueira, Anantha Padmanabha, Luc Segoufin, and Cristina Sirangelo. A simple algorithm for consistent query answering under primary keys. arXiv, 2023. URL: http://arxiv.org/abs/2301.08482.
  4. Ariel Fuxman and Renée J. Miller. First-order query rewriting for inconsistent databases. J. Comput. Syst. Sci., 73(4):610-635, 2007. URL: https://doi.org/10.1016/j.jcss.2006.10.013.
  5. John E. Hopcroft and Richard M. Karp. An n^5/2 algorithm for maximum matchings in bipartite graphs. SIAM J. Comput., 2(4):225-231, 1973. URL: https://doi.org/10.1137/0202019.
  6. 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. URL: https://doi.org/10.1016/j.ipl.2011.10.018.
  7. Paraschos Koutris, Xiating Ouyang, and Jef Wijsen. Consistent query answering for primary keys on path queries. In Leonid Libkin, Reinhard Pichler, and Paolo Guagliardo, editors, PODS'21: Proceedings of the 40th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, Virtual Event, China, June 20-25, 2021, pages 215-232. ACM, 2021. URL: https://doi.org/10.1145/3452021.3458334.
  8. Paraschos Koutris and Jef Wijsen. Consistent query answering for self-join-free conjunctive queries under primary key constraints. ACM Trans. Database Syst., 42(2):9:1-9:45, 2017. URL: https://doi.org/10.1145/3068334.
  9. Paraschos Koutris and Jef Wijsen. Consistent query answering for primary keys in datalog. Theory Comput. Syst., 65(1):122-178, 2021. URL: https://doi.org/10.1007/s00224-020-09985-6.
  10. Jef Wijsen. A remark on the complexity of consistent conjunctive query answering under primary key violations. Inf. Process. Lett., 110(21):950-955, 2010. URL: https://doi.org/10.1016/j.ipl.2010.07.021.
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