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

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.