Locally Consistent K-relations: Entailment and Axioms of Functional Dependence
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866908847933751296 |
|---|---|
| author | Barlag, Timon Hannula, Miika Kontinen, Juha Pardal, Nina Virtema, Jonni |
| author_facet | Barlag, Timon Hannula, Miika Kontinen, Juha Pardal, Nina Virtema, Jonni |
| contents | Local consistency arises in diverse areas, including Bayesian statistics, relational databases, and quantum foundations, and so does the notion of functional dependence. We adopt a general approach to study logical inference in a setting that enables both global inconsistency and local consistency. Our approach builds upon pairwise consistent families of K-relations, i.e, relations with tuples annotated with elements of some positive commutative monoid. The framework covers, e.g., families of probability distributions arising from quantum experiments and their possibilistic counterparts. As a first step, we investigate the entailment problem for functional dependencies (FDs) in this setting. Notably, the transitivity rule for FDs is no longer sound, but can be replaced by two novel axiom schemas. We provide a complete axiomatisation for, and establish NL-completeness of, the entailment problem of unary FDs, and demonstrate that even this restricted case exhibits context-dependent subtleties. In addition, we explore when contextual families over the Booleans have realisations as contextual families over various monoids. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_11057 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Locally Consistent K-relations: Entailment and Axioms of Functional Dependence Barlag, Timon Hannula, Miika Kontinen, Juha Pardal, Nina Virtema, Jonni Quantum Physics Databases 68P15, 81P13 Local consistency arises in diverse areas, including Bayesian statistics, relational databases, and quantum foundations, and so does the notion of functional dependence. We adopt a general approach to study logical inference in a setting that enables both global inconsistency and local consistency. Our approach builds upon pairwise consistent families of K-relations, i.e, relations with tuples annotated with elements of some positive commutative monoid. The framework covers, e.g., families of probability distributions arising from quantum experiments and their possibilistic counterparts. As a first step, we investigate the entailment problem for functional dependencies (FDs) in this setting. Notably, the transitivity rule for FDs is no longer sound, but can be replaced by two novel axiom schemas. We provide a complete axiomatisation for, and establish NL-completeness of, the entailment problem of unary FDs, and demonstrate that even this restricted case exhibits context-dependent subtleties. In addition, we explore when contextual families over the Booleans have realisations as contextual families over various monoids. |
| title | Locally Consistent K-relations: Entailment and Axioms of Functional Dependence |
| topic | Quantum Physics Databases 68P15, 81P13 |
| url | https://arxiv.org/abs/2505.11057 |