2

関係代数と、シータ結合、等結合、および自然結合を相互にどのように分類できるかについて質問があります。

stackoverflow.comのコメントで、sqlvogelはデータベース管理のリレーショナルモデルを発明したコンピューター科学者のEFCoddを引用しています。「[the]Natural [-join]は、Theta[-のサブセットであるEqui[-join]のサブセットです。加入]。" (stackoverflow.comは2月12日の午後9時1分に取得されました)。*

等結合がシータ結合のサブセットとしてどのように見えるかを理解しています。これらは両方とも結合し、両方とも固定数の属性を使用しますが、等結合は等式演算子(=)の使用に制限されています。一方、自然結合は、2つの関係を結合する際のタプル(属性の固定数ではない)のすべての組み合わせのセットであり、等式演算子(=)の使用に制限されます。等結合とシータ結合は、使用できる演算子が異なりますが、定義に属性を必要としないため、自然結合は次元が異なると思います。

誰かがこの問題に光を当てることができますか?

*この見積もりの​​元のソースが見つかりません。

4

2 に答える 2

3

概要:技術的な詳細を無視し、結合の意図に焦点を当てると、自然結合は等結合のサブセットになります。これらの技術的な詳細を含めると、事態はさらに複雑になります。次に、使用される定義に応じて、自然結合を等結合のサブセットにすることができます。


私の意見では、それはサブセットが取られるものに関して本当に依存します。

編集:この段落は、以下のWikipedia関係代数のセクションで大幅に拡張されていますが、元の回答のコンテキストを保持するためにここに残されています。

オペレーションが技術的に何をするかについて話している場合、equi-joinは明らかにtheta-joinのサブセットです。これは、平等でのみ結合できるのに対し、thetaは比較よりも大きい、比較よりも小さいなどで結合できるためです。 、equi-joinとtheta-joinはどちらも任意の属性で動作します。ただし、自然結合は、この点で他の2つの結合とは異なります。厳密に言えば、equi-joinとtheta-joinは、共通の属性名を共有しないリレーションに対してのみ機能します。自然結合は、共通の属性名が等しい場合に2つの関係を結合し、重複する属性を「削除」します。これは、自然結合が異なると言うときにあなたが行っている定義であると私は信じています。その場合、あなたは正しいです。

操作が意味的に(または実際に)何をするかについて話している場合、それらはお互いのサブセットであると私が言うよりも。シータ結合は、任意の属性間のさまざまなブール条件に基づいて結合します。等結合は、等式比較のみに制限されます。自然結合は、属性が任意ではなく、名前を共有する必要があるという点でさらに制限されています。


編集:より技術的な答え:

免責事項:私は集合論の1年目のレベルの知識を前提としています。

定義

技術的な答えについては、技術的な定義が必要です。では、どのような技術的定義を順守しますか?関係代数をグーグルで検索すると、最初のページに、ウィキペディアのリンク、Youtubeビデオ、さまざまな大学のデータベースコースからの講義ノートが表示されます(特に、Coddの論文へのリンクはありません)。それらはすべて、選択、投影、結合などの「基本」に同意します。ただし、次のような詳細のいくつかについては異なります。

  • 属性名を共有する2つのリレーション間でシータ結合が発生することを許可しますか?その場合、どのように処理しますか?
  • 選択とシータ結合では、どのような述語と命題が許可されますか?
  • 名前を共有する属性がない場合(この場合、デカルト積に縮退します)、自然結合を実行できますか?

関係代数の2つの定義、ウィキペディアとコッドを見ていきます

ウィキペディアの関係代数

ウィキペディアの関係代数の記事から始めます。これは、大学がデータベースの入門コースで最近教えている傾向に非常に近いためです。ただし、この記事では、特に技術的な部分で、その出典を効果的に引用することはできません。また、かなり数学的なものです。そのため、関係代数を初めて見る人には、この記事はお勧めしません。

ナチュラルジョイン

ウィキペディアでは、自然結合を次のように定義しています。

[...]共通の属性名が等しいRSのタプルのすべての組み合わせのセット。

また、

通常、RSには少なくとも1つの共通属性が必要ですが、この制約を省略し、RSに共通属性がない場合、自然結合は正確にデカルト積になります。

これから説明するように、Coddには共通の属性名が必要なので、縮退した自然結合を許可する定義を使用します。共通の属性は、結果のリレーションに1回だけ表示されることに注意してください。したがって、リレーションRm個の属性があり、リレーションSn個の属性があり、それらに共通のx個の属性がある場合( x≥0、x≤m 、x≤n 、結果のリレーションR NATURALJOINSにはm +n-x属性あります。 。

シータ結合と等結合

ウィキペディアでは、関係RSの間θ結合をθ関係aθbまたはθvを満たす結合として定義しています。ここで、abは属性名、 vは定数値、θは{<、、=、≥、>}。

また、

この操作の結果は、関係θを満たすRSのタプルのすべての組み合わせで構成されます。θ結合の結果は、 SRのヘッダーが互いに素である場合、つまり共通の属性が含まれていない場合にのみ定義されます。

等結合は、操作が「=」である単純なθ結合です。

結合間の関係

簡単に言うと、equi-joinはtheta-joinのサブセットです。

RSに共通の属性がある場合、シータ結合はリレーションを直接操作できません。したがって、自然結合は、シータ結合では不可能な関係を生み出すことができます。それらに共通の属性がない場合、自然結合はデカルト積に縮退します。シータ結合は現在合法です。結合することはできますが、使用する特定のθ関係に応じて異なる結果を生成する可能性があります。一般的な場合、シータ結合は、自然結合では不可能な関係を生成できます。

したがって、結論として、等結合はシータ結合のサブセットであり、自然結合はシータ結合のサブセットではなく、シータ結合も自然結合のサブセットではありません(これは私が最初に言ったときに意味したことです異なっていた)。したがって、自然結合は等結合のサブセットではありません

コッドの元の関係代数1

それでは、ソースに移動して、 Coddによる初期の論文を見てみましょう。確かに、これは私がそれを読んだのは初めてですので、私が犯したかもしれない間違いを指摘してください。しかし、私の意見では、関係代数についての前提を捨てれば、この論文はウィキペディアの記事よりもはるかに読みやすくなります。

いくつかの注意:

  • この論文では、コッドは実際に彼の操作を「代数」と呼ぶことはありません。
  • Coddは二項関係(つまり、2つの属性のみを持つ関係)に焦点を当てていますが、セクション2.1.3の終わりに、より高度な関係が二項関係に簡単に還元できることを示しています。
  • 実際、ウィキペディアの定義と同じ操作は投影だけです。

ドメインと役割

セクション1.3では、関係は有限量の集合のデカルト積のサブセットとして定義されています。これらの各セットはドメインと呼ばれ、ドメイン名は2です。リレーションには、同じドメイン名の列を含めることができます(つまり、2つの列が同じセットからのものです)。この場合、同一のドメイン名を持つ列は、一意のロール名で区別できます。したがって、ウィキペディアの属性名はCoddのdomain_name.role_name3に似ています

参加する

セクション2.1.3で、Coddは、2つの関係がドメインを共有する場合にのみ、可能な限り結合を定義します。さらに彼は次のように述べています。

二項関係Rは、 π12U)= Rおよびπ23 U = Sとなるような三項関係Uが存在する場合、二項関係Sと結合可能です。このような三項関係は、RとSの結合と呼ばれます。RSがπ2(R)=π1(S)のような二項関係ある場合RS結合可能です。

これは非常に理論的ですが、本質的には、RとSの関係が結合された関係から完全に回復できる場合にのみ、RとSの間で結合が発生する可能性あることを意味ますこれは、結合される列の値のセットがRSで同じでなければならないことを意味します。

これは、SQLの結合やウィキペディアの記事で定義されている結合(自然結合を含む)よりも制限が厳しくなります。

ナチュラルジョイン

上記のことを考えると、NaturalJoinの定義は簡単に外れます。

R x S = {(abc):Rab)⋀S (bc }

制限

結合から少し迂回して、制限について説明しているセクション2.1.5を見ていきます。これは、 (ウィキペディアで定義されている)選択と同様の操作です。関係Rは、次の方法で関係Sによって制限できます。新しい関係R'は、Rのタプルで構成され、その列の値のサブセットはSの列のサブセットの要素です。私はそれをうまく説明したかどうかわからないので、ここにいくつかの同等のSQLがあります:

SELECT * FROM R 
WHERE some_attributes IN (
    SELECT some_comparable_attributes FROM S)

シータ結合と等結合

このペーパーでは、シータと等結合の明確な定義は提供されていません。また、単にシータ結合を定義することは不可能のようです(ただし、間違っている場合は修正してください)。ただし、リレーションRSに対する一連の操作を定義することはできます。これにより、ウィキペディアの記事で定義されている等結合とほぼ同じ4の結果が得られます。

二項関係を考慮するだけでよいという事実を利用します。したがって、Rに列(ab)があり、Sに列(bc)があるとします。πb (R )は必ずしもπbS に等しいとは限らないため、これらは必ずしも結合可能ではありません。次に、属性bに関してRをSで制限することによって関係R'を形成し、属性bに関してSRによって再び制限することによってS 'を形成します。。ここで、πb R ')=πb S ' )なので、 R'S'の自然結合を取ることができます。

結合間の関係

与えられた等結合の定義から外れますが、πb (R)=πb S の場合、等結合は自然結合と同等です。したがって、自然結合は等結合のサブセットです


さらに読む:この回答は、シータ結合と関係代数に関するより役立つ情報を提供することがわかりました。


脚注

  1. CS.SEの回答でわかったように、このコッドのの関係代数を2年後、ウィキペディアのものと非常によく似た関係代数と定義することがどれほど公平かはわかりません(ただし、θで≠を許可しています) -参加)。それにもかかわらず、この答えの大きなポイントは、関係代数の定義が異なることを強調することであり、何らかの形の証明を行う前に定義を確立する必要があります。

  2. ドメインの位置を最初に定義するステップと、関係と関係の違いについて詳しく説明します。

  3. Coddは、追加の世代識別子を定義します。これについても詳しく説明します。

  4. コッドの理論では、結合される列は同じドメインを持っている必要があります。ウィキペディアに示されている理論によれば、これは要件ではありませんが、実際には、とにかくそのような種類の結合を行うべきではありません。

于 2013-02-22T04:41:12.057 に答える
1

彼はおそらく次のことを言及しました:

自然結合は、同じ名前の属性に等式比較が適用される等結合です。

TABLE_A JOIN TABLE_B ON TABLE_A.X = TABLE_B.Yは等結合ですが、自然結合ではありません。

したがって、すべての自然結合は実際には等結合ですが、すべての等結合が自然結合であるとは限りません。

したがって、テーブル間のすべての可能な自然結合のセットは、それらの同じテーブル間のすべての可能な等結合のセットのサブセット(多くの場合適切)です。

于 2013-02-22T23:51:38.240 に答える