2

少し数学を理解できたらすみません：

X と Y の2 つのセットと、多対多の関係ℜ ⊆ X✗Y があります。

  • すべての x ∈ X に対して、xℜ = { y | (x,y) ∈ ℜ } ⊆ Y、ℜ によって x に関連付けられた Y のサブセット。
  • すべての y ∈ Y について、ℜy = { x | (x,y) ∈ ℜ } ⊆ X、ℜ によって y に関連付けられた X のサブセット。

クエリを Y, Q ⊆ ℘(Y) のサブセットのセットとして定義します。

クエリのイメージを Q のサブセットの結合とします。

image(Q) = U q∈Q q

すべての q ∈ Q について q ∩ xℜ ≠ ∅ である場合、つまり、Q のすべてのサブセットが x に関連付けられた Y のサブセットと重複する場合、X x の要素がクエリ Q を満たすとします。

次のようなクエリ Q の要素 x の満足の証拠を定義します。

証拠(x,Q) = xℜ ∩ 画像(Q)
つまり、x に関連付けられ、Q の一部と一致するために使用された Y の部分です。これは、x が Q を満たすかどうかを検証するために使用できます。

私の質問は、クエリを満たす x∈X を効率的に報告し、できれば満足の証拠を報告できるように、関係 ℜ をどのように保存すればよいかということです。

csvは約6GBしかないので、関係はそれほど大きくありません。いくつかのアイデアがありますが、どちらも特に満足していません。

  1. { (x, xℜ) | ∀ x∈X } をフラット ファイルで実行すると、O(|X||Q||Y|) が各 x をチェックして、クエリを満たすかどうかを確認します。これは並列化できますが、間違っているように感じます。
  2. Y でインデックス付けされた DB テーブルに ℜ を格納し、{ (y, ℜy) | を取得できます。∀ y∈image(Q) }、次にそれを反転して { (x, 証拠(x,Q)) | を取得します。∀ x stevidence(x,Q) ≠ ∅ } ならば、それをチェックして、Q と証拠を満たす x を見つけます。これは少し良いように思えますが、自分で逆にすることで、RDBMS に依頼できることを行うことができるように感じます。

どうすればこれをより良く行うことができますか?

4

1 に答える 1

1

2番がいいと思います。また、Q を CNF で表すことができる場合は、いくつかのクエリと INTERSECT を使用して、RDBMS に重い作業の一部を実行させることができます。(DNF と UNION も同様です。)

これは、一部の RDBMS がサポートしている「逆インデックス」が必要なようにも見えます。X = ドキュメントのセット、Y = 単語のセット、q = グロブ「a*c」に一致する単語のセット。

HTH

于 2013-04-24T04:01:19.137 に答える