Maximum size of non-redundant independence sets found for databases
Non-redundant Independence Atoms
Databases
Summary
In databases, independence atoms describe when some data attributes don't affect others. The authors show the largest possible set of these independent rules that don’t overlap too much grows like a special large combination number. They connect this problem to known questions in math about certain groups of sets without specific patterns. Their work gives a clearer sense of how complex these independence conditions can get as the number of attributes grows.
What this means in practice
- •For database system designers: Design constraints for optimization algorithms that handle sets of independence rules by knowing their maximal non-overlapping size.
- •For combinatorial algorithm developers: Use bounds on special set families to improve or verify algorithms analyzing independence properties in large attribute sets.
A theory result. No direct application yet.
Authors
Attila Sali, Jun Yan
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))\binom{n}{\floor{n/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.