Computing Repairs Under Functional and Inclusion Dependencies via Argumentation

Research output: Chapter in book/report/conference proceedingConference contributionResearchpeer review

Authors

  • Yasir Mahmood
  • Jonni Virtema
  • Timon Barlag
  • Axel Cyrille Ngonga Ngomo

External Research Organisations

  • Paderborn University
  • The University of Sheffield
View graph of relations

Details

Original languageEnglish
Title of host publicationFoundations of Information and Knowledge Systems
Subtitle of host publication13th International Symposium, FoIKS 2024
EditorsArne Meier, Magdalena Ortiz
PublisherSpringer Science and Business Media Deutschland GmbH
Pages23-42
Number of pages20
ISBN (electronic)978-3-031-56940-1
ISBN (print)9783031569395
Publication statusPublished - 29 Mar 2024
Event13th International Symposium on Foundations of Information and Knowledge Systems, FoIKS 2024 - Sheffield, United Kingdom (UK)
Duration: 8 Apr 202411 Apr 2024

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume14589 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

Cite this

Computing Repairs Under Functional and Inclusion Dependencies via Argumentation. / Mahmood, Yasir; Virtema, Jonni; Barlag, Timon et al.
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 proceedingConference contributionResearchpeer review

Mahmood, Y, Virtema, J, Barlag, T & Ngomo, ACN 2024, Computing Repairs Under Functional and Inclusion Dependencies via Argumentation. in A Meier & M Ortiz (eds), Foundations of Information and Knowledge Systems : 13th International Symposium, FoIKS 2024. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 14589 LNCS, Springer Science and Business Media Deutschland GmbH, pp. 23-42, 13th International Symposium on Foundations of Information and Knowledge Systems, FoIKS 2024, Sheffield, United Kingdom (UK), 8 Apr 2024. https://doi.org/10.48550/arXiv.2312.01973, https://doi.org/10.1007/978-3-031-56940-1_2
Mahmood, Y., Virtema, J., Barlag, T., & Ngomo, A. C. N. (2024). Computing Repairs Under Functional and Inclusion Dependencies via Argumentation. In A. Meier, & M. Ortiz (Eds.), Foundations of Information and Knowledge Systems : 13th International Symposium, FoIKS 2024 (pp. 23-42). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 14589 LNCS). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.48550/arXiv.2312.01973, https://doi.org/10.1007/978-3-031-56940-1_2
Mahmood Y, Virtema J, Barlag T, Ngomo ACN. Computing Repairs Under Functional and Inclusion Dependencies via Argumentation. In Meier A, Ortiz M, editors, Foundations of Information and Knowledge Systems : 13th International Symposium, FoIKS 2024. 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)). doi: 10.48550/arXiv.2312.01973, 10.1007/978-3-031-56940-1_2
Mahmood, Yasir ; Virtema, Jonni ; Barlag, Timon et al. / Computing Repairs Under Functional and Inclusion Dependencies via Argumentation. Foundations of Information and Knowledge Systems : 13th International Symposium, FoIKS 2024. editor / Arne Meier ; Magdalena Ortiz. Springer Science and Business Media Deutschland GmbH, 2024. pp. 23-42 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
Download
@inproceedings{cdd13f2d689f40cd94905029082ffade,
title = "Computing Repairs Under Functional and Inclusion Dependencies via Argumentation",
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",
author = "Yasir Mahmood and Jonni Virtema and Timon Barlag and Ngomo, {Axel Cyrille Ngonga}",
note = "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.; 13th International Symposium on Foundations of Information and Knowledge Systems, FoIKS 2024 ; Conference date: 08-04-2024 Through 11-04-2024",
year = "2024",
month = mar,
day = "29",
doi = "10.48550/arXiv.2312.01973",
language = "English",
isbn = "9783031569395",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Science and Business Media Deutschland GmbH",
pages = "23--42",
editor = "Arne Meier and Magdalena Ortiz",
booktitle = "Foundations of Information and Knowledge Systems",
address = "Germany",

}

Download

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 -

By the same author(s)