database-design - アルゴリズム/データベースサイズスケーリング分析

Question

データモデルのサイズ要件を説明する式を見つけるのに問題があります。

タグのリストを用意します。この例では、タグは単なる数字です。
タグは常にソートされており、重複は存在しません。

3つの数字のすべての可能なタグの組み合わせ：

1:2:3
1:2
1:3
2:3
1
2
3

4つの数字：

1:2:3:4
1:2:3
1:2:4
1:3:4
2:3:4
1:2
1:3
1:4
2:3
2:4
3:4
1
2
3
4

私が計算したいくつかの値：

1=>1
2=>3
3=>7
4=>15
5=>29
6=>70

n個のタグに対して（上記のように）最大でいくつの行がありますか？

Answer 1

これは組み合わせ論の問題です。「Nから1アイテム」+「Nから2アイテム」+「Nから3アイテム」+...最大「NからNアイテム」を選択する方法の数の合計が必要です。

NからNの可能な組み合わせの合計は2^Nであるため、データベースの行は2 ^ N-1になります（空の組み合わせは有効な行ではないため）。

組み合わせの合計の詳細については、この投稿を参照してください。

これはセットの観点から考えることもできます。N個のアイテムのセット（空のセットを除く）のサブセットの数が必要です。