Axiomatizing approximate inclusion
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916759413456896 |
|---|---|
| author | Häggblom, Matilda |
| author_facet | Häggblom, Matilda |
| contents | We introduce two approximate variants of inclusion dependencies and examine the axiomatization and computational complexity of their implication problems. The approximate variants allow for some imperfection in the database and differ in how this degree is measured. One considers the error relative to the database size, while the other applies a fixed threshold independent of size. We obtain complete axiomatizations for both under some arity restrictions. In particular, restricted to unary inclusion dependencies, the implication problem for each approximate variant is decidable in PTIME. We formalise the results using team semantics, where a team corresponds to a uni-relational database. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_19834 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Axiomatizing approximate inclusion Häggblom, Matilda Logic in Computer Science Logic 03B60, 03B70 F.4.1; H.2.4 We introduce two approximate variants of inclusion dependencies and examine the axiomatization and computational complexity of their implication problems. The approximate variants allow for some imperfection in the database and differ in how this degree is measured. One considers the error relative to the database size, while the other applies a fixed threshold independent of size. We obtain complete axiomatizations for both under some arity restrictions. In particular, restricted to unary inclusion dependencies, the implication problem for each approximate variant is decidable in PTIME. We formalise the results using team semantics, where a team corresponds to a uni-relational database. |
| title | Axiomatizing approximate inclusion |
| topic | Logic in Computer Science Logic 03B60, 03B70 F.4.1; H.2.4 |
| url | https://arxiv.org/abs/2505.19834 |