Document Open Access Logo

Consistent Query Answering for Primary Keys and Conjunctive Queries with Counting

Authors Aziz Amezian El Khalfioui, Jef Wijsen

PDF
Thumbnail PDF

File

LIPIcs.ICDT.2023.23.pdf
  • Filesize: 0.83 MB
  • 19 pages

Document Identifiers

Author Details

Aziz Amezian El Khalfioui
  • Research fellow FNRS
  • University of Mons, Mons, Belgium
Jef Wijsen
  • University of Mons, Mons, Belgium

Cite As Get BibTex

Aziz Amezian El Khalfioui and Jef Wijsen. Consistent Query Answering for Primary Keys and Conjunctive Queries with Counting. In 26th International Conference on Database Theory (ICDT 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 255, pp. 23:1-23:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.ICDT.2023.23

Abstract

The problem of consistent query answering for primary keys and self-join-free conjunctive queries has been intensively studied in recent years and is by now well understood. In this paper, we study an extension of this problem with counting. The queries we consider count how many times each value occurs in a designated (possibly composite) column of an answer to a full conjunctive query. In a setting of database repairs, we adopt the semantics of [Arenas et al., ICDT 2001] which computes tight lower and upper bounds on these counts, where the bounds are taken over all repairs. Ariel Fuxman defined in his PhD thesis a syntactic class of queries, called Cforest, for which this computation can be done by executing two first-order queries (one for lower bounds, and one for upper bounds) followed by simple counting steps. We use the term "parsimonious counting" for this computation. A natural question is whether Cforest contains all self-join-free conjunctive queries that admit parsimonious counting. We answer this question negatively. We define a new syntactic class of queries, called Cparsimony, and prove that it contains all (and only) self-join-free conjunctive queries that admit parsimonious counting.

Subject Classification

ACM Subject Classification
  • Information systems → Relational database query languages
  • Theory of computation → Incomplete, inconsistent, and uncertain databases
  • Theory of computation → Logic and databases
Keywords
  • Consistent query answering
  • primary key
  • conjunctive query
  • aggregation
  • counting

Metrics

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

Related Versions

References

  1. Marcelo Arenas, Leopoldo E. Bertossi, and Jan Chomicki. Consistent query answers in inconsistent databases. In PODS, pages 68-79. ACM Press, 1999. Google Scholar
  2. Marcelo Arenas, Leopoldo E. Bertossi, and Jan Chomicki. Scalar aggregation in FD-inconsistent databases. In ICDT, volume 1973 of Lecture Notes in Computer Science, pages 39-53. Springer, 2001. Google Scholar
  3. Marcelo Arenas, Leopoldo E. Bertossi, Jan Chomicki, Xin He, Vijay Raghavan, and Jeremy P. Spinrad. Scalar aggregation in inconsistent databases. Theor. Comput. Sci., 296(3):405-434, 2003. Google Scholar
  4. Leopoldo E. Bertossi. Database Repairing and Consistent Query Answering. Synthesis Lectures on Data Management. Morgan & Claypool Publishers, 2011. Google Scholar
  5. Leopoldo E. Bertossi. Database repairs and consistent query answering: Origins and further developments. In PODS, pages 48-58. ACM, 2019. Google Scholar
  6. 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
  7. Andrei A. Bulatov. Complexity of conservative constraint satisfaction problems. ACM Trans. Comput. Log., 12(4):24:1-24:66, 2011. Google Scholar
  8. Marco Calautti, Marco Console, and Andreas Pieris. Counting database repairs under primary keys revisited. In PODS, pages 104-118. ACM, 2019. Google Scholar
  9. Marco Calautti, Marco Console, and Andreas Pieris. Benchmarking approximate consistent query answering. In PODS, pages 233-246. ACM, 2021. Google Scholar
  10. Marco Calautti, Leonid Libkin, and Andreas Pieris. An operational approach to consistent query answering. In PODS, pages 239-251. ACM, 2018. Google Scholar
  11. Marco Calautti, Ester Livshits, Andreas Pieris, and Markus Schneider. Counting database repairs entailing a query: The case of functional dependencies. In PODS, pages 403-412. ACM, 2022. Google Scholar
  12. Marco Calautti, Ester Livshits, Andreas Pieris, and Markus Schneider. Uniform operational consistent query answering. In PODS, pages 393-402. ACM, 2022. Google Scholar
  13. Ashok K. Chandra, Larry J. Stockmeyer, and Uzi Vishkin. Constant depth reducibility. SIAM J. Comput., 13(2):423-439, 1984. Google Scholar
  14. Akhil A. Dixit and Phokion G. Kolaitis. A SAT-based system for consistent query answering. In SAT, volume 11628 of Lecture Notes in Computer Science, pages 117-135. Springer, 2019. Google Scholar
  15. Akhil A. Dixit and Phokion G. Kolaitis. Consistent answers of aggregation queries via SAT. In ICDE, pages 924-937. IEEE, 2022. Google Scholar
  16. Zhiwei Fan, Paraschos Koutris, Xiating Ouyang, and Jef Wijsen. LinCQA: Faster consistent query answering with linear time guarantees. CoRR, abs/2208.12339, 2022. URL: http://arxiv.org/abs/2208.12339.
  17. Gaëlle Fontaine. Why is it hard to obtain a dichotomy for consistent query answering? ACM Trans. Comput. Log., 16(1):7:1-7:24, 2015. Google Scholar
  18. Ariel Fuxman. Efficient query processing over inconsistent databases. PhD thesis, University of Toronto, 2007. Google Scholar
  19. Ariel Fuxman, Elham Fazli, and Renée J. Miller. ConQuer: Efficient management of inconsistent databases. In SIGMOD Conference, pages 155-166. ACM, 2005. Google Scholar
  20. Ariel Fuxman, Diego Fuxman, and Renée J. Miller. ConQuer: A system for efficient querying over inconsistent databases. In VLDB, pages 1354-1357. ACM, 2005. Google Scholar
  21. Ariel Fuxman and Renée J. Miller. First-order query rewriting for inconsistent databases. In ICDT, volume 3363 of Lecture Notes in Computer Science, pages 337-351. Springer, 2005. Google Scholar
  22. M. R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979. Google Scholar
  23. Miika Hannula and Jef Wijsen. A dichotomy in consistent query answering for primary keys and unary foreign keys. In PODS, pages 437-449. ACM, 2022. Google Scholar
  24. Aziz Amezian El Khalfioui, Jonathan Joertz, Dorian Labeeuw, Gaëtan Staquet, and Jef Wijsen. Optimization of answer set programs for consistent query answering by means of first-order rewriting. In CIKM, pages 25-34. ACM, 2020. Google Scholar
  25. Aziz Amezian El Khalfioui and Jef Wijsen. Consistent query answering for primary keys and conjunctive queries with counting. CoRR, abs/2211.04134, 2022. URL: http://arxiv.org/abs/2211.04134.
  26. Benny Kimelfeld, Ester Livshits, and Liat Peterfreund. Counting and enumerating preferred database repairs. Theor. Comput. Sci., 837:115-157, 2020. Google Scholar
  27. Phokion G. Kolaitis, Enela Pema, and Wang-Chiew Tan. Efficient querying of inconsistent databases with binary integer programming. Proc. VLDB Endow., 6(6):397-408, 2013. Google Scholar
  28. Paraschos Koutris, Xiating Ouyang, and Jef Wijsen. Consistent query answering for primary keys on path queries. In PODS, pages 215-232. ACM, 2021. Google Scholar
  29. 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. Google Scholar
  30. Paraschos Koutris and Jef Wijsen. Consistent query answering for primary keys and conjunctive queries with negated atoms. In PODS, pages 209-224. ACM, 2018. Google Scholar
  31. Paraschos Koutris and Jef Wijsen. First-order rewritability in consistent query answering with respect to multiple keys. In PODS, pages 113-129. ACM, 2020. Google Scholar
  32. Paraschos Koutris and Jef Wijsen. Consistent query answering for primary keys in datalog. Theory Comput. Syst., 65(1):122-178, 2021. Google Scholar
  33. Dany Maslowski and Jef Wijsen. A dichotomy in the complexity of counting database repairs. J. Comput. Syst. Sci., 79(6):958-983, 2013. Google Scholar
  34. Dany Maslowski and Jef Wijsen. Counting database repairs that satisfy conjunctive queries with self-joins. In ICDT, pages 155-164. OpenProceedings.org, 2014. Google Scholar
  35. Slawek Staworko, Jan Chomicki, and Jerzy Marcinkowski. Prioritized repairing and consistent query answering in relational databases. Ann. Math. Artif. Intell., 64(2-3):209-246, 2012. Google Scholar
  36. Jef Wijsen. On the first-order expressibility of computing certain answers to conjunctive queries over uncertain databases. In PODS, pages 179-190. ACM, 2010. Google Scholar
  37. Jef Wijsen. Foundations of query answering on inconsistent databases. SIGMOD Rec., 48(3):6-16, 2019. 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 About DROPS Imprint Privacy Contact