Details
| Original language | English |
|---|---|
| Title of host publication | Foundations of Information and Knowledge Systems |
| Subtitle of host publication | 13th International Symposium, FoIKS 2024 |
| Editors | Arne Meier, Magdalena Ortiz |
| Publisher | Springer Science and Business Media Deutschland GmbH |
| Pages | 23-42 |
| Number of pages | 20 |
| ISBN (electronic) | 978-3-031-56940-1 |
| ISBN (print) | 9783031569395 |
| Publication status | Published - 29 Mar 2024 |
| Event | 13th International Symposium on Foundations of Information and Knowledge Systems, FoIKS 2024 - Sheffield, United Kingdom (UK) Duration: 8 Apr 2024 → 11 Apr 2024 |
Publication series
| Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
|---|---|
| Volume | 14589 LNCS |
| ISSN (Print) | 0302-9743 |
| ISSN (electronic) | 1611-3349 |
Abstract
We discover a connection between finding subset-maximal repairs for sets of functional and inclusion dependencies, and computing extensions within argumentation frameworks (AFs). We study the complexity of existence of a repair, and deciding whether a given tuple belongs to some (or every) repair, by simulating the instances of these problems via AFs. We prove that subset-maximal repairs under functional dependencies correspond to the naive extensions, which also coincide with the preferred and stable extensions in the resulting AFs. For inclusion dependencies one needs a pre-processing step on the resulting AFs in order for the extensions to coincide. Allowing both types of dependencies breaks this relationship between extensions and only preferred semantics captures the repairs. Finally, we establish that the complexities of the above decision problems are -complete and -complete, when both functional and inclusion dependencies are allowed.
Keywords
- abstract argumentation, complexity theory, database repairs, integrity constraints
ASJC Scopus subject areas
- Mathematics(all)
- Theoretical Computer Science
- Computer Science(all)
Cite this
- Standard
- Harvard
- Apa
- Vancouver
- BibTeX
- RIS
Foundations of Information and Knowledge Systems : 13th International Symposium, FoIKS 2024. ed. / Arne Meier; Magdalena Ortiz. Springer Science and Business Media Deutschland GmbH, 2024. p. 23-42 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 14589 LNCS).
Research output: Chapter in book/report/conference proceeding › Conference contribution › Research › peer review
}
TY - GEN
T1 - Computing Repairs Under Functional and Inclusion Dependencies via Argumentation
AU - Mahmood, Yasir
AU - Virtema, Jonni
AU - Barlag, Timon
AU - Ngomo, Axel Cyrille Ngonga
N1 - Funding Information: The work has received funding from the European Union\u2019s Horizon Europe research and innovation programme within project ENEXA (101070305) and the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation): TRR 318/1 2021-438445824 and VI 1045-1/1-432788559. The first author expresses gratitude to Arne Meier (Leibniz University Hannover) for the invitation to discuss the topic in Hannover, as well as for motivating and guiding the discussion on this subject.
PY - 2024/3/29
Y1 - 2024/3/29
N2 - We discover a connection between finding subset-maximal repairs for sets of functional and inclusion dependencies, and computing extensions within argumentation frameworks (AFs). We study the complexity of existence of a repair, and deciding whether a given tuple belongs to some (or every) repair, by simulating the instances of these problems via AFs. We prove that subset-maximal repairs under functional dependencies correspond to the naive extensions, which also coincide with the preferred and stable extensions in the resulting AFs. For inclusion dependencies one needs a pre-processing step on the resulting AFs in order for the extensions to coincide. Allowing both types of dependencies breaks this relationship between extensions and only preferred semantics captures the repairs. Finally, we establish that the complexities of the above decision problems are -complete and -complete, when both functional and inclusion dependencies are allowed.
AB - We discover a connection between finding subset-maximal repairs for sets of functional and inclusion dependencies, and computing extensions within argumentation frameworks (AFs). We study the complexity of existence of a repair, and deciding whether a given tuple belongs to some (or every) repair, by simulating the instances of these problems via AFs. We prove that subset-maximal repairs under functional dependencies correspond to the naive extensions, which also coincide with the preferred and stable extensions in the resulting AFs. For inclusion dependencies one needs a pre-processing step on the resulting AFs in order for the extensions to coincide. Allowing both types of dependencies breaks this relationship between extensions and only preferred semantics captures the repairs. Finally, we establish that the complexities of the above decision problems are -complete and -complete, when both functional and inclusion dependencies are allowed.
KW - abstract argumentation
KW - complexity theory
KW - database repairs
KW - integrity constraints
UR - http://www.scopus.com/inward/record.url?scp=85190660050&partnerID=8YFLogxK
U2 - 10.48550/arXiv.2312.01973
DO - 10.48550/arXiv.2312.01973
M3 - Conference contribution
AN - SCOPUS:85190660050
SN - 9783031569395
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 23
EP - 42
BT - Foundations of Information and Knowledge Systems
A2 - Meier, Arne
A2 - Ortiz, Magdalena
PB - Springer Science and Business Media Deutschland GmbH
T2 - 13th International Symposium on Foundations of Information and Knowledge Systems, FoIKS 2024
Y2 - 8 April 2024 through 11 April 2024
ER -