PreprintCC BY-NC-SA 4.0arXiv
Non-redundant Independence Atoms
Abstract
Independence atom is a key concept in relational database theory. In the present paper, we prove that the maximum possible size of a non-redundant set of independence atoms on n attributes is asymptotically (1+o(1))binomnfloorn/2. It turns out that this problem is closely related to two extremal set theory problems, the Katona-Tarján question on ``V''-free families of subsets of [n] for the lower bound, and Kleitman's bound on union-free families for the upper bound.
Related
- Solvable groups defined by redundant cyclic presentations
- Simultaneous Recovery of Wave Speeds and Initial Sources on Graphs via Redundant Frontier Propagation
- Redundant generation in PSL2(ℚp)
- Systematic Codes Correcting Two Deletions with Three Redundant Symbols over Large Alphabets
- Differential Realizability of Static Control Allocation in Multirotors: An Impossibility under Nonredundant Full Actuation and a Pseudoinverse Obstruction under Redundant Actuation
BibTeX
@misc{sali2026nonredundant,
title = {{Non-redundant Independence Atoms}},
author = {Attila Sali and Jun Yan},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.05568},
eprint = {2611.05568},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.05568},
note = {CC BY-NC-SA 4.0},
}
RIS
TY - UNPB
TI - Non-redundant Independence Atoms
AU - Attila Sali
AU - Jun Yan
PY - 2026
DA - 2026/11/03
PB - arXiv
DO - 10.48550/arxiv.2611.05568
UR - https://arxiv.org/abs/2611.05568
AB - Independence atom is a key concept in relational database theory. In the present paper, we prove that the maximum possible size of a non-redundant set of independence atoms on n attributes is asymptotically (1+o(1))binomnfloorn/2. It turns out that this problem is closely related to two extremal set theory problems, the Katona-Tarján question on ``V''-free families of subsets of [n] for the lower bound, and Kleitman's bound on union-free families for the upper bound.
ER -