Axiomatization of approximate exclusion
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913344859930624 |
|---|---|
| author | Häggblom, Matilda |
| author_facet | Häggblom, Matilda |
| contents | We define and axiomatize approximate exclusion atoms in the team semantic setting. A team is a set of assignments, which can be seen as a mathematical model of a uni-relational database, and we say that an approximate exclusion atom is satisfied in a team if the corresponding usual exclusion atom is satisfied in a large enough subteam. We consider the implication problem for approximate exclusion atoms and show that it is axiomatizable for consequences with a degree of approximation that is not too large. We prove the completeness theorem for usual exclusion atoms, which is currently missing from the literature, and generalize it to approximate exclusion atoms. We also provide a polynomial time algorithm for the implication problems. The results also apply to exclusion dependencies in database theory. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_04998 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Axiomatization of approximate exclusion Häggblom, Matilda Logic in Computer Science Logic 03B60, 03B70 F.4.1; H.2.4 We define and axiomatize approximate exclusion atoms in the team semantic setting. A team is a set of assignments, which can be seen as a mathematical model of a uni-relational database, and we say that an approximate exclusion atom is satisfied in a team if the corresponding usual exclusion atom is satisfied in a large enough subteam. We consider the implication problem for approximate exclusion atoms and show that it is axiomatizable for consequences with a degree of approximation that is not too large. We prove the completeness theorem for usual exclusion atoms, which is currently missing from the literature, and generalize it to approximate exclusion atoms. We also provide a polynomial time algorithm for the implication problems. The results also apply to exclusion dependencies in database theory. |
| title | Axiomatization of approximate exclusion |
| topic | Logic in Computer Science Logic 03B60, 03B70 F.4.1; H.2.4 |
| url | https://arxiv.org/abs/2405.04998 |