5

何兆ものセットがどこかに保存されていると仮定します。これらの各セットのドメインは同じです。また、有限で離散的です。したがって、各セットは、比較的短い長さ (例: 1024) のビット フィールド (例: 0000100111...) として格納できます。つまり、ビットフィールドのビット X は、アイテム X (1024 個の可能なアイテムのうち) が特定のセットに含まれているかどうかを示します。

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

これを解決する最も簡単な方法は、セット Y のビットフィールドと、データストア内のすべてのセットのビットフィールドを 1 つずつ AND し、AND の結果が Y のビットフィールドと一致するものを選択することです。

どうすればこれをスピードアップできますか? 格納されているすべてのセットのビットフィールドを AND 処理することなく、このクエリを実行できるツリー構造 (インデックス) またはスマート アルゴリズムはありますか?

セットの大規模なコレクションに対するそのような操作を既にサポートしているデータベースはありますか?

4

6 に答える 6

4

セットを前処理できる場合、サブセット関係は DAG として表現できます (ポーズセットを記述しているため)。推移的な削減が計算されている場合、最大のセットから開始して Y が現在アクセスされているセットのサブセットではなくなったときに停止する DFS を実行するだけで、すべてのセットのテストを回避できると思います。

于 2010-12-28T06:29:09.173 に答える
1

すべてのセットが抽出されるセットのカーディナリティに応じて、要素からそれらを含むセットへの逆インデックス マッピングを構築することが 1 つのオプションになる場合があります。セット Y が与えられた場合、各要素を個別に含むすべてのセットを見つけてそれらの交点を計算することにより、サブセットとして Y を持つすべてのセットを見つけることができます。リストを並べ替えた順序で保存する場合 (たとえば、データベース内のすべてのセットに値 0、1 などの番号を付けることによって)、要素が 1 つも含まれていないと仮定すると、この交差をかなり効率的に計算できるはずです。多くのセット。

于 2010-12-28T16:39:29.157 に答える
0

RDBMS が唯一の選択肢である場合は、SQL での DAG のモデリングに関する次の興味深い記事を参照することをお勧めします。

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

Oracle や MSSQL を購入する余裕がない場合は、再帰クエリをサポートする PostgresQL 9 を検討してください。また、かなり長い間クロス結合もサポートされています。

于 2011-02-09T21:40:47.370 に答える
0

ビットフィールドのカーディナリティが非常に低いため、答えはノーだと言う傾向があります。

于 2010-12-28T00:57:51.920 に答える
0

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

于 2010-12-28T01:03:43.527 に答える
0

一目見ただけで、BDD を思い浮かべます。これは、DAG ソリューションの考え方にある程度沿っています。またはZDD。

于 2010-12-28T16:43:27.927 に答える