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

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

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

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

Пусть и S имеют схемы ( R ′ , T ) и ( T , S ′ ) соответственно, где R ′ и S ′ являются наборами атрибутов в одной схеме, но не другой, а T является набором общих атрибутов.$R$$S$$(R', T)$$(T, S')$$R'$$S'$$T$

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

1. кортеж в R ;$(r, t)$$R$
2. (а) - кортеж из S или (b) s = w ;$(t, s)$$S$$s = w$
3. Если в наборе для s ≠ w , то ( r , t , w ) не в наборе.$(r, t, s)$$s \neq w$$(r, t, w)$

Пример: схема - ( A 1 , A 2 , A 3 ) , схема S - ( A 2 , A 3 , A 4 ) , и мы имеем R = { ( 1 , 2 , 3 ) , ( 4 , 5 , 6 ) } и S = { ( 2 , 3 , 4 $R$$(A_{1}, A_{2}, A_{3})$$S$$(A_{2}, A_{3}, A_{4})$$R = \{(1, 2, 3), (4, 5, 6)\}$ . По (1) и (2) получаем промежуточный результат { ( 1 , 2 , 3 , 4 ) , ( 1 , 2 , 3 , 6 ) , ( 1 , 2 , 3 , ϵ ) , ( 4 , 5 , 6 , ϵ ) } . По (3) мы должны удалить ( 1 , $S = \{(2, 3, 4), (2, 3, 6)\}$$\{(1, 2, 3, 4),(1, 2, 3, 6), (1, 2, 3, \epsilon),(4, 5, 6, \epsilon)\}$ , так как мы имеем (например) ( 1 , 2 , 3 , 4 ) и s = 4 ≠ ϵ = w . Таким образом, у нас остаются { ( 1 , 2 , 3 , 4 ) , ( 1 , 2 , 3 , 6 ) , ( 4 , 5 , 6 , ϵ ) $(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) и (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)есть множество всех кортежей в , для которых нет соответствующего кортежа в S . Чтобы увидеть это, достаточно заметить, что, проецируя общие атрибуты из R и S (набор атрибутов T ) и принимая разницу, остается один со всеми и только теми кортежами (со схемой T ), которые представлены в R, но не S . С помощью R мы восстанавливаем все и только те кортежи в R, которые имеют значения для атрибутов в T, которые присутствуют в R, но отсутствуют в $R$$S$$R$$S$$T$$T$$R$$S$EQUIJOIN$R$$R$$T$$R$$S$ а именно, набор кортежей, о котором мы до сих пор заявляли.

Далее, обратите внимание, что схема для R(((PROJECT_T R) DIFFERENCE (PROJECT_T S)) такая же, как и для (а именно ( R ' , T ) ), в то время как схема для W является S ' . Операция , следовательно, декартово произведение, мы получаем все кортежи вида ( г , т , ш ) , где нет ( т , ев ) в S , соответствующая ( г , т ) в R .$R$$(R', T)$$w$$S'$JOIN$(r, t, w)$$(t, s)$$S$$(r, t)$$R$

Чтобы увидеть, что это именно тот набор кортежей, который нам нужно добавить для R EQUIJOIN Sпостроения R LEFT JOIN S, рассмотрим следующее: по построению выполняется (3), так как R EQUIJOIN Sне может содержать если содержит ( r , t , w ) (если это так, то вторая часть, содержащая ( r , t , w ), будет противоречием); если бы мы добавили еще один ( r , t , w ) не в , то было бы $(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) в S , соответствующая ( г , т ) в R , и по определению, ( г , т , ев ) также были бы впротиворечие (3). Это завершает доказательство.$(t, s)$$S$$(r, t)$$R$EQUIJOIN$(r, t, s)$R LEFT JOIN S

Теперь мы показываем, что левое соединение может использоваться для построения различий:

Теорема: R DIFFERENCE SэквивалентноPROJECT_T(SELECT_{t'=w}(R LEFT JOIN (SELECT_{s=s'}(((S JOIN RENAME_{T->T'}(S)))))))

Доказательство: обратите внимание, что здесь и S ′ пусты, поскольку все атрибуты являются общими для того, чтобы иметь смысл. Во-первых, мы создаем новое отношение из S , дублируя набор атрибутов в S (обработанный и ) так, чтобы он состоял из кортежей ( t , t ′ ) в наборе атрибутов ( T , T ′ ), где t = t ′ (обрабатывается ). Левое соединение оставляет нас с кортежами вида ( t , t ′$R'$$S'$DIFFERENCE$S$$S$RENAMEJOIN$(t, t')$$(T, T')$$t = t'$SELECT$(t, t')$где или т ' = ш . Теперь, чтобы избавиться от записей, которые также появляются в S , мы должны сохранить только кортежи формы ( t , w ) , которые обрабатываются самым внешним . Последний избавляется от временного набора атрибутов T ′ и оставляет нам разницу с точки зрения исходной схемы.$t=t'$$t'=w$$S$$(t, w)$SELECTPROJECT$T'$

Пример: Пусть и S = { ( 3 , 4 ) , ( 5 , 6 ) , ( 7 , 8 ) } . Сначала мы получаем S с набором атрибутов d T ′ : { ( 3 , 4 $R = \{(1, 2), (3, 4), (5, 6)\}$$S = \{(3, 4), (5, 6), (7, 8)\}$$S$RENAME$T'$ . Операция дает нам декартово произведение со всеми девяти возможных спариваний; этот набор не написан здесь по причинам форматирования. Затем рагез это вниз к { ( 3 , 4 , 3 , 4 ) , ( 5 , 6 , 5 , 6 ) , ( 7 , 8 , 7 , 8 ) } . с$\{(3, 4), (5, 6), (7, 8)\}$JOINSELECT$\{(3, 4, 3, 4), (5, 6, 5, 6), (7, 8, 7, 8)\}$LEFT JOIN дает { ( 1 , 2 , ϵ , ϵ ) , ( 3 , 4 , 3 , 4 ) , ( 5 , 6 , 5 , 6 ) } . Дает { ( 1 , 2 , ε , ε ) } . Дает { ( 1 , 2 ) } , желаемый ответ.$R$$\{(1, 2, \epsilon, \epsilon), (3, 4, 3, 4), (5, 6, 5, 6)\}$SELECT$\{(1, 2, \epsilon, \epsilon)\}$PROJECT$\{(1, 2)\}$

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

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

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

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