「違い」操作は、すでに「結合」を含むクエリ言語に表現力を追加しますか？

Question

セット差分演算子（例： EXCEPT 一部のSQLバリアントでは）は、リレーショナル代数の多くの基本的な演算子の1つです。ただし、Set Differenceオペレーターを直接サポートしないデータベースがいくつかありますが、どのサポート LEFT JOIN （一種の外側の結合）、そして実際には、同じ効果を達成するために設定された違い操作の代わりに使用できます。

これは、クエリ言語の表現力が、設定された違い演算子がなくても同じであることを意味しますか？ LEFT JOIN オペレーターは維持されていますか？この事実をどのように証明するでしょうか？

Answer 1

リレーショナル代数では、最初に左（外側）結合の非公式の定義を提供し、それが違いを構築するために違い、選択、および組合を使用できるだけでなく、それが違いを構築できることを証明します。左（外側）結合。実際、逆にそれを行うことになります。違いを使用して左結合を構築する方法を示し、左結合を使用して違いを構築する方法を示します。

$ r $ and $ s $には、それぞれスキーマ$（r '、t）$と$（t、s'）$を持っています。ここで、$ r '$と$ s' $は1つのスキーマの属性のセットですがもう1つ、$ t $は共通属性のセットです。

$ w =（ epsilon、 epsilon、...、 epsilon）$ $ $ schema $ s '$のnull tupleとします。つまり、それは$ s '$の各属性のすべてのnull値で構成されるタプルです。次に、次のように左外結合を定義します。 R LEFT JOIN S すべてのタプル$（r、t、s）$のセットは、schema $（r '、t、s'）$に属する$ where ...

1. $（r、t）$は$ r $のタプルです。
2. （a）$（t、s）$は$ s $または（b）$ s = w $のタプルです。
3. $（r、t、s）$が$ s neq w $のセットにある場合、$（r、t、w）$はセットにありません。

例：$ r $のスキーマは$（a_ {1}、a_ {2}、a_ {3}）$、$ s $ 's s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s schema is a_ {4 {4 }）$、そして$ r = {（1、2、3）、（4、5、6）} $および$ s = {（2、3、4）、（2、3、 6）} $。 （1）および（2）により、中間結果$ {（1、2、3、4）、（1、2、3、6）、（1、2、3、 epsilon）、（4、 5、6、 epsilon）} $。 （3）by（たとえば）$（1、2、3、4）$および$ s = 4 neq epsilon = w $があるため、$（1、2、3、 epsilon）$を削除する必要があります。 。したがって、$ {（1、2、3、4）、（1、2、3、6）、（4、5、6、 epsilon）} $が残されています。

定理： R LEFT JOIN S に相当します (R EQUIJOIN S) UNION ((((PROJECT_T R) DIFFERENCE (PROJECT_T S)) EQUIJOIN R) JOIN w).

証拠： (R EQUIJOIN S) （1）および（2a）で必要なすべてを提供します。私たちはそれを主張します ((((PROJECT_T R) DIFFERENCE (PROJECT_T S)) EQUIJOIN R) JOIN w) フォームのすべてを提供します (r, t, w) （2b）および（3）で要求されます。

これを見るために、最初にそれを通知します (((PROJECT_T R) DIFFERENCE (PROJECT_T S)) EQUIJOIN R) $ r $のすべてのタプルのセットであり、$ s $に対応するタプルがありません。それを見るために、$ r $と$ s $（属性セット$ t $）から共通属性を投影し、違いを取ることで、すべてのタプルのみが残されていることに注意するだけで十分です（スキーマ$ tを使用して$）は$ r $で表されますが、$ s $ではありません。によって EQUIJOIN $ r $を使用すると、$ r $で存在するが$ s $ではない$ t $の属性を持つ$ r $のすべてのタプルのみを回収します。つまり、これまでに主張していたタプルのセットです。

次に、のスキーマに注意してください (((PROJECT_T R) DIFFERENCE (PROJECT_T S)) $ r $（すなわち、$（r '、t）$）のそれと同じですが、$ w $のスキーマは$ s' $です。 JOIN したがって、操作はデカルト製品です。フォーム$（r、t、w）$のすべてのタプルを取得します。 r $。

これがまさに私たちが追加する必要があるタプルのセットであることを確認するために R EQUIJOIN S 構築するために R LEFT JOIN S, 、以下を考慮してください：建設により、（3）は満足しています。 R EQUIJOIN S $（r、t、s）$を含めることはできませんif ((((PROJECT_T R) DIFFERENCE (PROJECT_T S)) EQUIJOIN R) JOIN w) $（r、t、w）$が含まれます（もしそうなら、2番目の部分は$（r、t、w）$を含む矛盾です）。別の$（r、t、w）$を追加する場合 ((((PROJECT_T R) DIFFERENCE (PROJECT_T S)) EQUIJOIN R) JOIN w), 、次に、$（r、t）$ in $ r $に対応する$ s $ in $（t、s）$があり、の定義により EQUIJOIN, 、$（r、t、s）$も R LEFT JOIN S, 、（3）の矛盾。これにより、証明が完了します。

ここで、左結合を使用して違いを構築できることを示します。

定理： R DIFFERENCE S に相当します PROJECT_T(SELECT_{t'=w}(R LEFT JOIN (SELECT_{s=s'}(((S JOIN RENAME_{T->T'}(S)))))))

証明：ここでは、すべての属性が共有されているため、$ r '$と$ s' $が空であることに注意してください DIFFERENCE 理にかなっている。まず、$ s $（処理された属性セットを複製することにより、$ s $から新しい関係を作成します RENAME と JOIN）属性$（t、t '）$ on属性セット$（t、t'）$ where $ t = t '$（handed byによって処理されます。 SELECT）。左の結合は、フォーム$（t、t '）$のタプルを残します。ここで、$ t = t' $または$ t '= w $です。これで、$ s $にも表示されるエントリを取り除くには、最も外側のものによって処理されるフォーム$（t、w）$のタプルのみを保持する必要があります。 SELECT. 。最後 PROJECT 一時的な属性セット$ t '$を取り除き、元のスキーマの観点から違いを残します。

例：$ r = {（1、2）、（3、4）、（5、6）} $および$ s = {（3、4）、（5、6）、（7、8 ）} $。最初に$ s $を取得します RENAMEd属性セット$ t '$：$ {（3、4）、（5、6）、（7、8）} $。 JOIN 操作により、9つの可能なペアリングがすべて揃ったデカルト製品が提供されます。このセットは、フォーマットの理由でここには書かれていません。 SELECT 次に、これを$ {（3、4、3、4）、（5、6、5、6）、（7、8、7、8）} $に下げます。 LEFT JOIN $ r $で$ {（1、2、 epsilon、 epsilon）、（3、4、3、4）、（5、6、5、6）} $を与えます。 SELECT $ {（1、2、 epsilon、 epsilon）} $を与えます。 PROJECT $ {（1、2）} $を与えます。

Answer 2

SQLが実装した左結合は、結果として関係を生成しません（結果の一部の属性には値がないため）。

SQLが実装した左結合であるErgoは、リレーショナル代数演算子の直接的な対応物ではありません。

エルゴ、 関連した 差分演算子は、左結合の観点から表現することはできません（左結合がリレーショナル代数の一部ではない可能性があるためです。これは、左結合が関係ではないものを生成し、代数の閉鎖に違反するためです）。

の原始演算子のセット 関連した 代数 それは閉鎖を満たします 私が知っていることは、常にリレーショナルの違いまたはリレーショナルセミディファレンスのいずれかを含みます。