同じドメインを持つ大きな集合の集合に対して部分集合のテスト操作を行う最速の方法

Question

何組ものセットがあると仮定します。これらのセットのそれぞれのドメインは同じです。それは有限で離散的でもあります。したがって、各セットは、比較的短い長さ（例えば：1024）のビットフィールド（例えば：0000100111 ...）として記憶されてもよい。すなわち、ビットフィールドのビットXは、（1024個の可能なアイテムのうちの）アイテムXが所定のセットに含まれるか否かを示す。

ここで、データストア内のどのセットがYをサブセットとして設定しているかというクエリに効率的に応答するストレージ構造とアルゴリズムを考案したいと考えています。セットY自体はデータストアに存在せず、実行時に指定されます。

これを解決する最も簡単な方法は、YのビットフィールドにAND結果が一致するものを1つずつ取り出して、セットYのビットフィールドとビットセットを1つずつANDでANDすることです。

これをスピードアップするにはどうすればよいですか？ツリー構造（インデックス）やスマートなアルゴリズムがあります。これは、すべてのストアドセットのビットフィールドとANDを取らずにこのクエリを実行できるようにするものですか？

このような操作をすでにサポートしているデータベースは、大量の集合でですか？

Answer 1

私は、ビットフィールドが非常に低い基数のため、答えはいいえと言いがちです。

Answer 2

これは、グラフストレージモデルに基づいてNeo4jを見たことがありますあなたのボリュームに基づいて、従来のRDBMSのストレッチですか？

Answer 3

セットを前処理することができれば、サブセットリレーションはDAGとして表現できます（posetを記述しているため）。推移の減少が計算されたら、Yが現在の訪問セットのサブセットではなくなるたびにDFSを実行し、最大のセットから開始するだけですべてのセットをテストすることを避けることができると思います。

Answer 4

すべてのセットが描画されるセットのカーディナリティに応じて、1つのオプションは、要素からそれらを含むセットへの逆インデックスマッピングを構築することです。集合Yが与えられると、各要素を個別に含むすべての集合を見つけてそれらの交わりを計算することによって、Yを部分集合として持つすべての集合を見つけることができます。ソートされた順序でリストを格納する場合（データベース内のすべての集合に値0、1などの番号を付けるなど）、この交点をかなり効率的に計算できるはずです。多くのセット。

Answer 5

DDDソリューションのアイデアに沿った、BDDについて考えてみましょう。あるいは、ZDD。

Answer 6

RDBMSはあなたの唯一の選択肢だった場合、私はSQLでDAGをモデリングする上で、この興味深い記事を見てお勧めします：

http://www.codeproject.com/KB/database/Modeling_DAGs_on_SQL_DBs.aspx?msg=3051183

OracleまたはMSSQLを買う余裕ができない場合は、を見て再帰クエリをサポートするPostgresQL 9また、かなりの時間、クロスジョインもサポートされています。