Polynomial-time algorithm for consistent query answering
Organization
Chair of Data Science
Abstract
A database is called inconsistent if it does not satisfy all of its integrity constraints, and otherwise consistent. Such inconsistencies can emerge in a number of ways, and while they can be resolved by deleting data, this may lead to a loss of valuable information. The paradigm of consistent query answering (CQA) addresses the challenge of handling inconsistencies without discarding any data [1,2]. A query answer is called certain if it is returned no matter how inconsistencies are repaired. Computing certain query answers is in general computationally intractable, but in many cases it can be done in polynomial time. The objective in this thesis is to present the basic theory of CQA, and implement a recent simple polynomial-time algorithm for CQA under primary-key constraints [3]. Depending on the scope of the thesis (BSc or MSc), the project can include comparisons with other methods, such as SQL rewritings and/or SAT solvers [4]. A theory-oriented alternative is to prove soundness and completeness of the algorithm (challenging).
[1] Marcelo Arenas, Leopoldo E. Bertossi, and Jan Chomicki. Consistent query answers in inconsistent databases. In PODS, pages 68–79. ACM Press, 1999.
[2] Leopoldo E. Bertossi. Database Repairing and Consistent Query Answering. Synthesis Lectures on Data Management. Morgan & Claypool Publishers, 2011
[3] Diego Figueira, Anantha Padmanabha, Luc Segoufin, and Cristina Sirangelo. A simple algorithm for consistent query answering under primary keys. In ICDT, volume 255 of LIPIcs, pages 24:1–24:18. Schloss Dagstuhl - Leibniz- Zentrum für Informatik, 2023.
[4] 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.
[1] Marcelo Arenas, Leopoldo E. Bertossi, and Jan Chomicki. Consistent query answers in inconsistent databases. In PODS, pages 68–79. ACM Press, 1999.
[2] Leopoldo E. Bertossi. Database Repairing and Consistent Query Answering. Synthesis Lectures on Data Management. Morgan & Claypool Publishers, 2011
[3] Diego Figueira, Anantha Padmanabha, Luc Segoufin, and Cristina Sirangelo. A simple algorithm for consistent query answering under primary keys. In ICDT, volume 255 of LIPIcs, pages 24:1–24:18. Schloss Dagstuhl - Leibniz- Zentrum für Informatik, 2023.
[4] 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.
Graduation Theses defence year
2024-2025
Supervisor
Miika Hannula
Spoken language (s)
English
Requirements for candidates
Level
Bachelor, Masters
Keywords
Application of contact
Name
Miika Hannula
Phone
E-mail