Polynomial-time algorithm for consistent query answering
Organisatsiooni nimi
Chair of Data Science
Kokkuvõte
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.
Lõputöö kaitsmise aasta
2024-2025
Juhendaja
Miika Hannula
Suhtlemiskeel(ed)
inglise keel
Nõuded kandideerijale
Tase
Bakalaureus, Magister
Märksõnad
Kandideerimise kontakt
Nimi
Miika Hannula
Tel
E-mail