Добавляет ли операция «разница» выразительность к языку запросов, который уже включает в себя «присоединение»?

Question

Оператор сет -разницы (например, EXCEPT В некоторых вариантах SQL) является одним из многих фундаментальных операторов реляционной алгебры. Тем не менее, есть некоторые базы данных, которые не поддерживают оператор SET WITLES напрямую, но которые поддерживают LEFT JOIN (своего рода внешнее соединение), и на практике это можно использовать вместо установленной разницы для достижения того же эффекта.

Означает ли это, что выразительная сила языка запросов одинакова даже без установленного оператора разницы, до тех пор, пока LEFT JOIN Оператор поддерживается? Как можно доказать этот факт?

Answer 1

В реляционной алгебре мы сначала предоставим неформальное определение соединения левого (внешнего) и продолжим доказать, что оно, переименование, отбор, соединение и проекция, могут построить разницу, а также эта разница, выбор и объединение могут использоваться для построения слева (внешнее) присоединение. На самом деле, мы в конечном итоге сделаем это в обратном порядке: мы покажем, как построить левые соединения, используя различия, а затем покажем, как создавать различия, используя левые соединения.

Пусть $ r $ и $ s $ имеют схемы $ (r ', t) $ и $ (t, s') $, соответственно, где $ r '$ и $ s' $ являются наборами атрибутов в одной схеме, но не Другой, и $ t $ - набор общих атрибутов.

Пусть $ w = ( epsilon, epsilon, ..., epsilon) $ будет нулевым кортежом для схемы $ s '$. То есть это кортеж, состоящий из всех нулевых значений для каждого атрибута $ s '$. Затем мы определяем левое внешнее соединение следующим образом: R LEFT JOIN S это набор всех кортежей $ (r, t, s) $, принадлежащий схеме $ (r ', t, s') $, где ...

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 $ схема $ (a_ {2}, a_ {3}, a_ {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) мы должны удалить $ (1, 2, 3, epsilon) $, поскольку мы имеем (например) $ (1, 2, 3, 4) $ и $ s = 4 neq epsilon = w $ Анкет Таким образом, у нас есть $ {(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) и (2а). Мы утверждаем это ((((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 $, которые имеют ценности для атрибутов в $ t $, которые присутствуют в $ r $, но не в $ s $; а именно, именно набор кортежей, которые мы до сих пор утверждали.

Затем обратите внимание, что схема (((PROJECT_T R) DIFFERENCE (PROJECT_T S)) это то же самое, что и $ r $ (а именно, $ (r ', t) $), в то время как схема $ w $ - это $ s' $. А JOIN Следовательно, операция является декартовым продуктом, мы получаем все корте R $.

Чтобы увидеть, что это именно набор кортежей, которые нам нужно было добавить к R EQUIJOIN S Чтобы построить R LEFT JOIN S, рассмотрим следующее: по строительству, (3) удовлетворяется, поскольку R EQUIJOIN S не может содержать $ (r, t, s) $, если ((((PROJECT_T R) DIFFERENCE (PROJECT_T S)) EQUIJOIN R) JOIN w) Содержит $ (r, t, w) $ (если это так, то вторая часть, содержащая $ (r, t, w) $, будет противоречием); Если бы мы добавили еще $ (r, t, w) $ не в ((((PROJECT_T R) DIFFERENCE (PROJECT_T S)) EQUIJOIN R) JOIN w), тогда будет $ (t, s) $ в $ s, соответствующий $ (r, t) $ in $ r $, и по определению 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 ') $ ontruity set $ (t, t') $, где $ t = t '$ (обрабатывается 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 Атрибут SET $ T '$: $ {(3, 4), (5, 6), (7, 8) } $. А JOIN Операция дает нам картезианский продукт со всеми девятью возможными парами; Этот набор не написан здесь по причинам форматирования. А 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

Left Join, реализованное SQL, не дает отношений в качестве результата (потому что некоторые атрибуты результата не будут иметь значения).

Ergo, оставленное соединением в соответствии с реализацией SQL, не является прямым аналогом какого -либо оператора реляционной алгебры.

Ergo, реляционный Разница в разнице не может быть выражен в терминах левого соединения (поскольку левое соединение не может быть частью реляционной алгебры, это потому, что левое соединение дает что -то, что не является отношением, что нарушает закрытие алгебры).

Любой набор примитивных операторов реляционный алгебра это удовлетворяет закрытию Что я знаю, всегда включает в себя либо реляционную разницу, либо реляционную полудиффиальность.